CHICKEN (Scheme implementation)

CHICKEN Scheme
Logo for CHICKEN Scheme
Original author(s) Felix Winkelmann
Developer(s) The CHICKEN Team
Initial release July 20, 2000 (2000-07-20)[1]
Stable release 4.10.0 / August 4, 2015 (2015-08-04)
Development status Active
Written in Scheme and C
Operating system Cross-platform
Type Programming language
License BSD License
Website call-cc.org
Standard(s) R5RS (mostly)

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. It is implemented mostly in Scheme, with some parts in C for performance or to make embedding into C programs easier.

Focus

CHICKEN's focus is immediately clear from its tagline: "A practical and portable Scheme system".

CHICKEN's main focus is the practical application of Scheme for writing "real-world" software. Scheme is well known for its use in computer science curricula and programming language experimentation, but it hasn't seen much use in business and industry.[2] CHICKEN's community has produced a large set of libraries for performing a variety of tasks. The CHICKEN wiki (the software running it is also a CHICKEN program) also contains a list of software that people have written in CHICKEN.

CHICKEN's other goal is to be portable. By compiling to portable C (like Gambit and Bigloo), programs written in CHICKEN can be compiled for common popular platforms like Linux, Mac OS X and other Unix-like systems as well as Windows, Haiku and the mobile platforms iOS and Android.[3] It also has built-in support for cross-compilation of programs and extensions,[4] which allows it to be used on various embedded platforms.

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[5] 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. When the stack fills up (that is, the stack pointer reaches the top of the stack), a garbage collection can be initiated. The design used is a copying garbage collector originally devised by C.J. Cheney, which copies all live continuations and other live objects to the heap.[6] 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 consists of the C stack as the nursery together with the two heaps required by the generational garbage 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.

Limitations and deviations from the standard

CHICKEN Scheme is mostly R5RS-compliant, with a few notable limitations and deviations.[7]

There is currently a guaranteed maximum of 120 arguments to a procedure. On common platforms, up to 2048 arguments are supported.

There is no support for the full numeric tower in the core system. However, an extension library exists which adds support for the full numeric tower. The next major version will remove this limitation.[8]

The core system has basic support for UTF-8 characters, however the string indexing and manipulation procedures are not UTF-8 aware. Here again there is an extension library which adds support for full UTF-8 awareness.

Add-on software

CHICKEN has a large repository of additional libraries and programs called "eggs". This eggs system is quite similar to RubyGems.

Initially, these eggs were developed in one central svn repository,[9] in which creating a tag would automatically cause a new version of the extension to become available for download. Currently, eggs can be developed anywhere and under any version control system, while still maintaining "semi-automatic" release management when using most of the popular code hosting sites.[10] This release method is VCS-agnostic in the sense that the user does not need to have these VCSes installed. The developer is free to host anywhere he or she likes, and could even choose to avoid public version control altogether and distribute only plain tarballs.

For all released eggs, the latest version is tested automatically as part of a continuous integration process. Anyone can volunteer to supply additional testing capacity (on different hardware, or different operating systems or on different core releases), but there's also a canonical test server where the core system and all eggs will be tested daily against the most recent development version (to catch regressive bugs) as well as the most recent stable version (to ensure that everything works for users of the stable system).

Features

CHICKEN supports most of R5RS standard Scheme, but it also adds a few nonstandard features which are not available in all Scheme implementations.

Foreign function interface

As mentioned above, CHICKEN compiles to C, which makes it possible to "inject" custom C code into the compiled result, which eases integration with C libraries. Its Foreign function interface supports converting back and forth between most built-in C types and corresponding Scheme objects.

There are also extension libraries for interfacing to Python, Lua, and Java via JNI or through a bridge.

Cross-compilation

It is relatively easy to cross-compile Scheme code to another platform (for example for embedded use on a device).

In order to make cross-compilation possible for Scheme code, CHICKEN imposes a model of separate compilation: A compiled module consists of two shared libraries. One library contains the actual code which will be used at runtime (compiled for the target platform), and the other is an "import module", which will be used to load the code which runs at compile-time (on the host platform), such as procedural macro code.

The CHICKEN compiler itself can also be easily cross-compiled; after translation to C has been achieved, one can simply use a C compiler which is set up to build for another platform.

Modules and macros

Since version 4, CHICKEN has a built-in module system and support for low-level hygienic macros through explicit renaming (prior to CHICKEN 4 this was available through an add-on library). Standard syntax-rules macros are also supported, as well as implicit renaming macros, which is basically a "reversed" version of explicit renaming.

This mechanism trades in performance for convenience. Each identifier not explicitly "injected" as unhygienic will be automatically renamed to avoid name capture. The performance cost lies in the fact that this "implicit" renaming requires the macro-expander to traverse the expressions an additional two times. This cost is paid at expansion time, so a macro author must consider whether longer compilation times are acceptable.

Limited static type analysis

More recently, support was added for local flow analysis. This allows the compiler to catch variable type errors at compile-time, and perform type specialisation. This specialisation makes it possible to remove several safety checks for type detection at runtime when the type can be deduced at compile-time. This results in improved run-time performance.

This "scrutinizer" does not allow cross-module flow analysis, so it can only be used to optimize code that's part of one compilation unit (or module).

See also

References

  1. ↑ Winkelmann, Felix "Announcing the CHICKEN Scheme-to-C compiler"., comp.lang.scheme
  2. ↑ "Scheme FAQ"., section "what is Scheme used for?"
  3. ↑ "Portability". page on the CHICKEN wiki
  4. ↑ "Cross development". - a section from the CHICKEN manual
  5. ↑ Baker, Henry "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A.".
  6. ↑ Cheney, C.J. "A Nonrecursive List Compacting Algorithm". CACM 13,11 (Nov. 1970), 677-678.
  7. ↑ The CHICKEN Team, "Deviations from the standard"., the CHICKEN manual
  8. ↑ The CHICKEN Team, "CHICKEN 5 roadmap".
  9. ↑ Bex, Peter "VCS-independent distribution of language extensions"., blogpost on More magic
  10. ↑ The CHICKEN wiki, "Instructions for popular code hosting methods and VCSes".

External links

This article is issued from Wikipedia - version of the Tuesday, March 29, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.