Een efficiente compilatie van de R (S, Splus) taal vertaald naar CommonLisp

Naar de engelse versie »

Wat is het

R2cl is een minimalistische, proof of concept vertaler van de R of S taal naar Common Lisp. Een versnelling van ruim 1000x kan dan worden behaald met behulp van de gratis CMU Common Lisp native code compiler op de resterende code. Dit maakt het equivalent aan FORTRAN, Ada of C. Het enige doel van de huidige versie (0.1) is om automatische vertalingen en compilaties van een simpele benchmark uit te voeren. We hebben geen features geïmplementeerd die hier niet voor nodig waren.

Download

R2cl-0.1.tgz uitgebracht op 7 januari 2006.

Installatie en gebruik.

Om te installeren dien je eerst cmucl (de CMU Common Lisp) en R te installeren. Beide komen standaard met de meeste linux distributies, maar dienen wel geselecteerd te worden voor installaties. Ik denk dat de meest recente (na 2000) versies zullen werken. Ik heb R 1.5.1 en cmucl x86-linux 3.0.8 18c+ draaiende op Debian 3.0 (woody). Je moet gebruik maken van de bash shell (dit is standaard) en gnu make op je systeem (dit zul je normaliter hebben).

Vervolgens kun je het volgende untar commando gebruiken:
tar xvzf R2cl-0.1.tgz

Het zal een directory genaamd R2cl aanmaken. Typ vervolgens:
cd R2cl make

en bekijk de vertaling, compilatie en runtime van de benchmarks. Dat is alles, behalve als je wil kijken naar de code.

Rationeel

R is een vernieuwde implementatie van de S-taal voor het statisch verwerken. Het is een gratis project, dat je kunt bekijken op r-project.org. R is een zeer expressieve 'matrix' taal (het maakt uitgebreid gebruik van matrix- en vectoroperatoren) met een grote bibliotheek van statische functies. Echter, expressiviteit vereist een dynamische uitvoer, gebaseerd op een 'onbeperkt geheugen' model dat traag is. Daarnaast is het een vereiste dat expressies en functies kunnen worden geconstrueerd via het programma of door een operator tijdens runtime, wat zorgt voor een herhalende aanpak. Dit maakt een rechttoe rechtaan implementatie traag. Voor programma's die tevens gemaakt zijn in FORTRAIN, zou FORTRAIN 1000x sneller zijn.

Lisp is een taal met eenzelfde uitvoer model. Het verschil is dat het nog generieker is en een uitvoerige macro en object oriented mogelijkheid bevat. Er zijn veel verschillende smaken, maar de boventoon voeren Scheme (wat reductionistisch is, eenvoud bevorderend) en Common Lisp (de ISO standaard welke zeer uitgebreid is en zorgvuldig compileert).

Geen van deze talen zouden eenvoudig te vertalen zijn in, zeg, C. Om de volledige taal te hebben dien je, tenminste gedeeltelijk, de interpreterende engine en de 'oneindige geheugen'-machine verfijnd te laten combineren met de gegenereerde code.

Er is echter geen reden om stukjes code die geen gebruik maken van de algemeenheid (zoals het genereren van broncodes en uitvoering tijdens runtime) niet te compileren om zo snel te coderen als FORTRAN. In de praktijk is dit een enorme taak. Desalniettemin werd het bereikt met een gratis implementatie, bijvoorbeeld in CMU CommonLisp, omdat ik heel blij was om te leren tijdens het proberen van deze benchmarks.

De semantiek van R is een subset van de semantiek van Schema. Het bevat natuurlijk ook een schat aan gegevenstypen die geschikt zijn voor statistieken. De semantiek (expressieve mechanismen) van CommonLisp zijn waarschijnlijk een superset van Scheme. Dit betekent dat R gemakkelijk kan worden uitgedrukt in Schema (feitelijk is de engine van de gratis implementatie een Scheme-engine) en misschien gemakkelijk te vertalen in CommonLisp. Dit is later interessant vanwege de beschikbaarheid van de efficiënte compiler.

Ik ben dus bij dit speelgoedproject aangekomen om te kijken of een dergelijke route voor een efficiënte compilatie van R mogelijk is.

Veel R-toepassingen hebben geen snelheid nodig. Je kunt de taak die je nodig hebt zo snel beschrijven dat je het zelden erg vindt om een paar seconden te wachten voordat het systeem het doet. Er zijn echter ook hele klassen van toepassingen waarbij snelheid nodig is en als een volledige portering van R op CommonLisp (echt groot project) zou worden gedaan, zouden ze allemaal haalbaar worden voor R-gebruikers zoals ikzelf.