Chicken Scheme compiler
Encyclopedia
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.
Much like Gauche, 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. 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 and Haiku
. It also has built-in support for cross-compilation of programs and extensions, which allows it to be used on various embedded platforms.
. 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. 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. 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.
There is currently a guaranteed maximum of 120 arguments to a procedure. On common platforms, up to 2048 arguments are supported.
. It too does not integrate with the packaging system of the user's operating system. SWIG
also supports Chicken.
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
and interpreter
Interpreter (computing)
In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language...
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
Free software
Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
available under the BSD license.
Focus
Chicken's focus is immediately clear from its tagline: "A practical and portable Scheme system".Much like Gauche, 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. 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
Gambit (Scheme implementation)
Gambit, also called Gambit-C, is a free software Scheme implementation, consisting of a Scheme interpreter, and a compiler which compiles Scheme to C. Its documentation claims conformance to the R4RS, R5RS, and IEEE standards, as well as several SRFIs...
and Bigloo
Bigloo
Bigloo is an implementation of the Scheme programming language developed at the French IT research institute INRIA. Its orientation is towards providing tools for effective and diverse code generation that can match the performance of hand-written C or C++. The Bigloo system contains a Scheme...
), programs written in Chicken can be compiled for common popular platforms like Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
, Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
and other Unix-like
Unix-like
A Unix-like operating system is one that behaves in a manner similar to a Unix system, while not necessarily conforming to or being certified to any version of the Single UNIX Specification....
systems as well as Windows and Haiku
Haiku (operating system)
Haiku is a free and open source operating system compatible with BeOS. Its development began in 2001, and the operating system became self-hosting in 2008, with the first alpha release in September 2009, the second in May 2010 and the third in June 2011....
. It also has built-in support for cross-compilation of programs and extensions, which allows it to be used on various embedded platforms.
Design
Like many Scheme compilers, Chicken uses standard C as an intermediate languageIntermediate language
In computer science, an intermediate language is the language of an abstract machine designed to aid in the analysis of computer programs. The term comes from their use in compilers, where a compiler first translates the source code of a program into a form more suitable for code-improving...
. 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
Henry Baker (computer scientist)
Henry Givens Baker Jr. is a computer scientist who has made contributions in garbage collection, functional programming languages, and linear logic. He was also one of the founders of Symbolics...
that outlined an innovative strategy for Scheme compilation into C. A scheme program is compiled into C functions
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
. These C functions never reach the return statement
Statement (programming)
In computer programming a statement can be thought of as the smallest standalone element of an imperative programming language. A program written in such a language is formed by a sequence of one or more statements. A statement will have internal components .Many languages In computer programming...
; instead, they call a new continuation
Continuation
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
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
Continuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
. Baker's novel idea is to use the C stack
Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the 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
Garbage collection (computer science)
In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...
can be initiated. The design used is a copying garbage collector
Cheney's algorithm
Cheney's algorithm, first described in a 1970 ACM paper by C.J. Cheney, is a method of garbage collection in computer software systems. In this scheme, the heap is divided into two equal halves, only one of which is in use at any one time...
originally devised 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 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.There is currently a guaranteed maximum of 120 arguments to a procedure. On common platforms, up to 2048 arguments are supported.
Add-on software
Chicken has a large repository of additional libraries and programs called "eggs". This eggs system is quite similar to RubyGemsRubyGems
RubyGems is a package manager for the Ruby programming language that provides a standard format for distributing Ruby programs and libraries , a tool designed to easily manage the installation of gems, and a server for distributing them. It is analogous to EasyInstall for the Python programming...
. It too does not integrate with the packaging system of the user's operating system. SWIG
SWIG
SWIG is an open source software tool used to connect computer programs or libraries written in C or C++ with scripting languages such as Lua, Perl, PHP, Python, R, Ruby, Tcl, and other languages like C#, Java, Modula-3, Objective Caml, Octave, and Scheme...
also supports Chicken.
See also
- Tail recursion
- Cheney's algorithmCheney's algorithmCheney's algorithm, first described in a 1970 ACM paper by C.J. Cheney, is a method of garbage collection in computer software systems. In this scheme, the heap is divided into two equal halves, only one of which is in use at any one time...
- M.T.A.
- GambitGambit (Scheme implementation)Gambit, also called Gambit-C, is a free software Scheme implementation, consisting of a Scheme interpreter, and a compiler which compiles Scheme to C. Its documentation claims conformance to the R4RS, R5RS, and IEEE standards, as well as several SRFIs...
- Stalin