Chicken (Scheme)
Chicken ist ein Compiler und Interpreter für die Programmiersprache Scheme, der den Scheme-Quelltext nach C übersetzt. Chicken ist weitestgehend R5RS konform und bietet viele Erweiterungen zu diesem Standard. Es handelt sich um freie Software, die unter einer BSD-Lizenz vertrieben wird. Der Autor ist Felix Winkelmann.
| Chicken | |
|---|---|
 | |
| Basisdaten | |
| Erscheinungsjahr | 20. Juli 2000 |
| Aktuelle Version | 5.1.0 (18. Juni 2019) |
| Betriebssystem | Plattformunabhängig |
| Programmiersprache | Scheme |
| Kategorie | Programmiersprache |
| Lizenz | BSD |
| call-cc.org | |
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 der ein innovativer Weg zur Übersetzung von Scheme nach C beschrieben wurde.[1] Hierbei wird ein Scheme-Programm in C-Funktionen übersetzt, die jedoch nicht zum Aufrufer zurückkehren, sondern stattdessen nach Beendigung eine sogenannte Continuation aufrufen. Diese Continuations sind 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 erstmals 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 übermäßig steigt.
Beschränkungen und Abweichungen vom Standard
Chicken Scheme ist weitestgehend R5RS-konform. Es werden andere Makros (explicit renaming) anstelle der Makros des Sprachstandards verwendet.
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.
Einzelnachweise
- 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
- C. J. Cheney: A Nonrecursive List Compacting Algorithm. In: CACM. Band 13, Nr. 11, 1970, S. 677–678, doi:10.1145/362790.362798.