Chicken (Scheme)

Chicken
Aktuelle Version	4.7.0 (25. Mai 2011)
Betriebssystem	Plattformunabhängig
Kategorie	Programmiersprache
Lizenz	BSD
call-with-current-continuation.org

Chicken ist ein Compiler und ein Interpreter für die Programmiersprache Scheme, welcher den Scheme Quelltext nach C übersetzt. Chicken ist weitestgehend R⁵RS konform und bietet viele Erweiterungen zu diesem Standards. Es handelt sich um freie Software, die unter einer BSD-Lizenz vertrieben wird.

Design

Wie viele Scheme-Compiler verwendet auch Chicken die Programmiersprache C als Zwischencode. Scheme Programme werden vom Chicken-Compiler nach C übersetzt und anschließend von einem Standard C-Compiler in die Maschinensprache des Zielsystems übersetzt, die dann ausgeführt werden kann. Die weite Verbreitung von C-Compilern erlaubt eine weitgehende Plattformunabhängigkeit

Das Design von Chicken wurde inspiriert von einer Veröffentlichung von Henry G. Baker aus dem Jahre 1994, in welcher ein innovativer Weg zur Übersetzung von Scheme nach C beschrieben wurde.^[1] Hierbei wird ein Scheme Programm in C-Funktionen übersetzt, welche jedoch nicht zum Aufrufer zurückkehren, sondern stattdessen nach Beendigung eine sogenannte Continuation aufrufen. Diese Continuations sind nichts anderes als weitere C-Funktionen, die vom Chicken Compiler erzeugt werden und als Parameter an andere C-Funktionen übergeben werden.

Dies ist nichts anderes als der Continuation-passing style formuliert in C. Bakers neuartige Idee ist es den C-Stack als Scheme-Heap zu verwenden. Daher können normale Stack-Operation wie automatische Variablenerzeugung, alloca-Aufrufe zur Erzeugung von Arrays variabler Größe und ähnliches verwendet werden. Sobald der Stack voll ist, wird eine Garbage Collection gestartet um den Stack wieder zu leeren. Im Chicken Design wird ein Copying Garbage Collector verwendet, der erstmalig 1970 von C. J. Cheney beschrieben wurde.^[2] Hierbei werden alle noch verwendeten Scheme-Objekte und Continuations auf den Heap verschoben, es werden jedoch keine C-Stack-Frames verschoben, wodurch Chicken ohne Kenntnis der zugrundeliegenden C-Implementierung auskommt.

Dieser Ansatz gibt vielen Operationen die Geschwindigkeit von normalen Stack-Operationen, insbesondere das Aufrufen der Continuations ist ein einfacher Funktionsaufruf. Weiterhin kann hierbei das von Scheme geforderte endrekursive Verhalten erreicht werden, ohne dass der Speicherbedarf asymptotisch ansteigt.

Beschränkungen und Abweichungen vom Standard

Chicken Scheme ist weitestgehend R⁵RS-konform. In der Grundversion sind jedoch nicht alle vom Standard geforderten numerischen Datentypen (numerical tower) implementiert und es werden Lisp-Macros anstelle von hygienischen Macros verwendet. Diese fehlenden Elemente können aber durch Erweiterungsmodule hinzugefügt werden.

Die Anzahl der Parameter einer Prozedur ist in der aktuellen Version auf 126 beschränkt, auf einigen verbreiteten Plattformen werden bis zu 1000 Parameter unterstützt.

Add-on-Software

Eine große Anzahl zusätzlicher Libraries und Programme, die sogenannten Eggs, sind für Chicken verfügbar. Diese Eggs sind vergleichbar mit den Ruby Gems der Programmiersprache Ruby.

Chicken wird vom Wrappergenerator SWIG unterstützt.

Einzelnachweise

1. ↑ Henry Baker: CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A., ACM SIGPLAN Notices 30, (1995), 17-20, doi:10.1145/214448.214454
2. ↑ C. J. Cheney: A Nonrecursive List Compacting Algorithm. In: CACM. 13, Nr. 11, 1970, S. 677-678, doi:10.1145/362790.362798.

Weblinks

• Chicken Scheme website
• The Chicken Wiki