Chicken (Scheme implementation)

From Wikipedia, the free encyclopedia

Chicken Scheme
Developer: Felix Winkelmann
Latest release: 2.5 / Oct 21, 2006
OS: Cross-platform
Use: Programming language
License: BSD License
Website: callcc.org

Chicken is a compiler and interpreter for the Scheme programming language that compiles Scheme code to standard C. It is mostly R5RS compliant and offers many extensions to the standard. Chicken is free software available under the BSD license.

Contents

[edit] Design

Like many Scheme compilers, Chicken uses standard C as an intermediate language. A Scheme program is translated into C by the Chicken compiler, and then a C compiler translates the C program into machine code for the target architecture, producing an executable program. The universal availability of C makes it ideal for this purpose.

Chicken's design was inspired by a 1994 paper by Henry Baker that outlined an innovative strategy for Scheme compilation into C. A scheme program is compiled into C functions. These C functions never reach the return statement; instead, they call a new continuation when complete. These continuations are C functions themselves and are passed on as extra arguments to other C functions. They are calculated by the compiler.

So far, this is the essence of continuation-passing style. Baker's novel idea is to use the C stack for the Scheme heap. Hence, normal C stack operations such as automatic variable creation, variable-sized array allocation, and so on can be used to automatically populate the heap. When the heap fills up (that is, the stack pointer reaches the top of the heap), a garbage collection can be initiated. The design used is a copying garbage collector originally designed by C.J. Cheney, which copies all live continuations and other live objects to the heap. Despite this, the C code does not copy C stack frames, only Scheme objects, so it does not require knowledge of the C implementation.

In full, the Scheme heap is made up of the C stack as the nursery of the generational garbage collector and the two heaps required by that kind of collector. This approach gives the speed of the C stack for many operations, and it allows the use of continuations as simple calls to C functions. Further, Baker's solution guarantees asymptotic tail recursive behavior, as required by the Scheme language standard. The implementation in the Chicken scheme compiler is even asymptotically safe for space.

[edit] Limitations and deviations from the standard

Chicken Scheme is mostly R5RS-compliant. The majority of the current deviations will be covered by the forthcoming standard, R6RS.

The basic distribution lacks arbitrary-precision arithmetic (bignums). However, these can be installed as an extension (see below). There is currently a maximum of 126 arguments to a procedure. This is a comparatively serious limitation for a Scheme compiler, which may expect to have quite long lists passed as arguments using the apply primitive. There is a workaround for some architectures that extends the maximum number of arguments per procedure to 1000.

[edit] Add-on software

Chicken has a large repository of additional libraries and programs called "eggs". This eggs system is quite similar to RubyGems. It too does not integrate with the packaging system of the user's operating system. SWIG also supports Chicken.

[edit] See also

[edit] References

[edit] External links