Chicken (Scheme implementation)

Last updated
Chicken Scheme
Chicken Scheme logo and wordmark.svg
Logo for Chicken Scheme
Chicken 5.0.0.png
Chicken 5.0.0 interpreter running on macOS
Paradigms Multi-paradigm: functional, imperative, meta
Family Lisp
Designed by Felix Winkelmann
Developer The Chicken Team
First appeared20 July 2000;22 years ago (2000-07-20) [1]
Stable release
5.3.0 / 18 November 2021;14 months ago (2021-11-18)
Typing discipline Dynamic, latent, strong
Scope Lexical
Implementation language Scheme, C
Platform IA-32, x86-64, ARM, MIPS, SPARC64, PowerPC
OS Cross-platform: Windows, Linux, macOS, FreeBSD, NetBSD, OpenBSD, Solaris, AIX, Haiku, Android, iOS
License BSD
Filename extensions .scm
Website www.call-cc.org OOjs UI icon edit-ltr-progressive.svg
Influenced by
Lisp, Scheme

Chicken (stylized as CHICKEN) is a programming language, specifically a compiler and interpreter which implement a dialect of the programming language Scheme, and which compiles Scheme source code to standard C. It is mostly R5RS compliant and offers many extensions to the standard. The newer R7RS standard is supported through an extension library. [2] Chicken is free and open-source software available under a BSD license. It is implemented mostly in Scheme, with some parts in C for performance or to make embedding into C programs easier.

Contents

Focus

Chicken's focus is quickly clear from its slogan: "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 has seen little use in business and industry. [3] Chicken's community has produced a large set of libraries to perform a variety of tasks. The Chicken wiki (the software running it is also a Chicken program) also contains a list of software that has been written in Chicken. [4]

Chicken's other goal is to be portable. By compiling to an intermediate representation, in this case portable C (as do Gambit and Bigloo), programs written in Chicken can be compiled for common popular operating systems such as Linux, macOS, other Unix-like systems, Windows, Haiku, and mobile platforms iOS and Android. [5] It also has built-in support for cross-compiling programs and extensions, [6] which allows it to be used on various embedded system platforms.

Design

Like many Scheme compilers, Chicken uses standard C as an intermediate representation. 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 computer architecture, producing an executable program. The universal availability of C makes it useful for this purpose.

Chicken's design was inspired by a 1994 paper [7] by Henry Baker that outlined an innovative strategy to compile Scheme 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 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 call 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. [8] 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. [9] R7RS compatibility is supplied as an extension library. [2]

The core system has basic support for UTF-8 characters, however the string indexing and manipulation procedures are not UTF-8 aware. An extension library exists which adds support for full UTF-8 awareness. [10]

Add-on software

Chicken has a large software repository of added libraries and programs, termed eggs. [11] This system is very similar to RubyGems. [12]

Initially, these eggs were developed in one central svn repository, [13] 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. [14] 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 they choose, and can even choose to avoid public version control and distribute only plain tarballs.

For all released eggs, the latest version is tested automatically as part of a continuous integration process. A canonical test server exists, [15] where the core system and all eggs are tested daily against the most recent development version (to catch regressive bugs), and the most recent stable version (to ensure that everything works for users of the stable system). Also, anyone can volunteer to supply further testing capacity, on different: hardware, operating systems, or core releases.

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

Chicken compiling to C makes it possible to inject custom C code into the compiled result, which eases integrating with C libraries. Its foreign function interface supports converting back and forth between most built-in C types and corresponding Scheme objects.

Also, extension libraries exist for interfacing to Python, [16] Lua, [17] and Java, via Java Native Interface (JNI) [18] or a bridge. [19]

Cross-compiling

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

To make cross-compiling possible for Scheme code, Chicken imposes a model of separate compiling: 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 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 macros [20] (before version 4, this was available through an add-on library). Standard syntax-rules macros are also supported, and implicit renaming macros, [21] which is basically a reversed version of explicit renaming.

This mechanism trades performance for convenience. Each identifier not explicitly injected as unhygienic will be automatically renamed to avoid name capture. The performance cost occurs because implicit renaming requires the macro-expander to retraverse the expressions two more times. This cost is paid at expansion time, so a macro author must consider if longer compiling times are acceptable.

Remote debugger

Since version 4.11, Chicken comes shipped with a debugger named Feathers. [22] When Scheme code is compiled with the needed debugging option, debugging events are injected at specific points in the code. These are implemented as calls to a C function, which is relatively low-overhead when not actually debugging the code. When debugging, it will try to make a TCP connection to a Feathers server process, possibly on a different machine. The process is halted, the user may set breakpoints and start the program. Then, when the breakpoint is hit, the client (process being debugged) enters a command loop, which allows interrogation of the client, to read out variables, or mutate them.

Limited static type analysis

Chicken supports 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 compiling unit (or module).

History

CHICKEN Scheme was originally developed by Felix Winkelmann on Cygwin/gcc and later Visual C++ 5.0 on Windows 98. [1] He came up with the name "CHICKEN" arbitrarily as the "first thing that came to my mind that day" thinking of a plastic toy of Feathers McGraw on his desk. As the project matured, he decided not to change the name out of superstition. [23]

See also

Related Research Articles

<span class="mw-page-title-main">Common Lisp</span> ANSI-standardized dialect of Lisp

Common Lisp (CL) is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 (S20018). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived from the ANSI Common Lisp standard.

<span class="mw-page-title-main">Lisp (programming language)</span> Programming language family

Lisp is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in 1960, Lisp is the second-oldest high-level programming language still in common use, after Fortran. Lisp has changed since its early days, and many dialects have existed over its history. Today, the best-known general-purpose Lisp dialects are Common Lisp, Scheme, Racket and Clojure.

<span class="mw-page-title-main">Macro (computer science)</span> Rule for substituting a set input with a set output

In computer programming, a macro is a rule or pattern that specifies how a certain input should be mapped to a replacement output. Applying a macro to an input is known as macro expansion. The input and output may be a sequence of lexical tokens or characters, or a syntax tree. Character macros are supported in software applications to make it easy to invoke common command sequences. Token and tree macros are supported in some programming languages to enable code reuse or to extend the language, sometimes for domain-specific languages.

<span class="mw-page-title-main">PHP</span> Scripting language created in 1994

PHP is a general-purpose scripting language geared toward web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by The PHP Group. PHP was originally an abbreviation of Personal Home Page, but it now stands for the recursive initialism PHP: Hypertext Preprocessor.

<span class="mw-page-title-main">Scheme (programming language)</span> Dialect of Lisp

Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT AI Lab and released by its developers, Guy L. Steele and Gerald Jay Sussman, via a series of memos now known as the Lambda Papers. It was the first dialect of Lisp to choose lexical scope and the first to require implementations to perform tail-call optimization, giving stronger support for functional programming and associated techniques such as recursive algorithms. It was also one of the first programming languages to support first-class continuations. It had a significant influence on the effort that led to the development of Common Lisp.

<span class="mw-page-title-main">Microsoft Visual C++</span> Integrated development environment product by Microsoft

Microsoft Visual C++ (MSVC) is a compiler for the C, C++ and C++/CX programming languages by Microsoft. MSVC is proprietary software; it was originally a standalone product but later became a part of Visual Studio and made available in both trialware and freeware forms. It features tools for developing and debugging C++ code, especially code written for the Windows API, DirectX and .NET.

<span class="mw-page-title-main">PIC microcontrollers</span> Programmable single-chip 16-bit microprocessor for computer

PIC is a family of microcontrollers made by Microchip Technology, derived from the PIC1650 originally developed by General Instrument's Microelectronics Division. The name PIC initially referred to Peripheral Interface Controller, and is currently expanded as Programmable Intelligent Computer. The first parts of the family were available in 1976; by 2013 the company had shipped more than twelve billion individual parts, used in a wide variety of embedded systems.

Programming languages can be grouped by the number and types of paradigms supported.

The C preprocessor is the macro preprocessor for the C, Objective-C and C++ computer programming languages. The preprocessor provides the ability for the inclusion of header files, macro expansions, conditional compilation, and line control.

<span class="mw-page-title-main">D (programming language)</span> Multi-paradigm system programming language

D, also known as dlang, is a multi-paradigm system programming language created by Walter Bright at Digital Mars and released in 2001. Andrei Alexandrescu joined the design and development effort in 2007. Though it originated as a re-engineering of C++, D is a profoundly different language —features of D can be considered streamlined and expanded-upon ideas from C++, however D also draws inspiration from other high-level programming languages, notably Java, Python, Ruby, C#, and Eiffel.

An object file is a computer file containing object code, that is, machine code output of an assembler or compiler. The object code is usually relocatable, and not usually directly executable. There are various formats for object files, and the same machine code can be packaged in different object file formats. An object file may also work like a shared library.

<span class="mw-page-title-main">Factor (programming language)</span> Stack-oriented programming language

Factor is a stack-oriented programming language created by Slava Pestov. Factor is dynamically typed and has automatic memory management, as well as powerful metaprogramming features. The language has a single implementation featuring a self-hosted optimizing compiler and an interactive development environment. The Factor distribution includes a large standard library.

In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion is particularly useful, and is often easy to optimize in implementations.

<span class="mw-page-title-main">GNU Guile</span> Extension Language

GNU Ubiquitous Intelligent Language for Extensions is the preferred extension language system for the GNU Project and features an implementation of the programming language Scheme. Its first version was released in 1993. In addition to large parts of Scheme standards, Guile Scheme includes modularized extensions for many different programming tasks.

In computing, Stalin is a programming language, an aggressive optimizing batch whole-program Scheme compiler written by Jeffrey Mark Siskind. It uses advanced data flow analysis and type inference and a variety of other optimization methods to produce code. Stalin is intended for production use in generating an optimized executable.

<span class="mw-page-title-main">Racket (programming language)</span> Lisp dialect

Racket is a general-purpose, multi-paradigm programming language and a multi-platform distribution that includes the Racket language, compiler, large standard library, IDE, development tools, and a set of additional languages including Typed Racket, Swindle, FrTime, Lazy Racket, R5RS & R6RS Scheme, Scribble, Datalog, Racklog, Algol 60 and several teaching languages.

Gambit, also called Gambit-C, is a programming language, a variant of the language family Lisp, and its variants named Scheme. The Gambit implementation consists of a Scheme interpreter, and a compiler which compiles Scheme into the language C, which makes it cross-platform software. It conforms to the standards R4RS, R5RS, and Institute of Electrical and Electronics Engineers (IEEE), and to several Scheme Requests for Implementations (SRFIs). Gambit was released first in 1988, and Gambit-C (Gambit with a C backend) was released first in 1994. They are free and open-source software released under a GNU Lesser General Public License (LGPL) 2.1, and Apache License 2.0.

SISC is an R5RS Scheme implementation, which includes a full number tower, hygienic macros, proper tail recursion, and first class continuations. SISC is short for Second Interpreter of Scheme Code, in reference to its predecessor LISC, the Lightweight Interpreter of Scheme Code.

<span class="mw-page-title-main">Rust (programming language)</span> General-purpose programming language

Rust is a multi-paradigm, high-level, general-purpose programming language. Rust emphasizes performance, type safety, and concurrency. Rust enforces memory safety—that is, that all references point to valid memory—without requiring the use of a garbage collector or reference counting present in other memory-safe languages. To simultaneously enforce memory safety and prevent concurrent data races, Rust's "borrow checker" tracks the object lifetime of all references in a program during compilation. Rust is popular for systems programming but also offers high-level features including some functional programming constructs.

In computing, Java bytecode is the bytecode-structured instruction set of the Java virtual machine (JVM), a virtual machine that enables a computer to run programs written in the Java programming language and several other programming languages, see List of JVM languages.

References

  1. 1 2 Winkelmann, Felix. "Announcing the Chicken Scheme-to-C compiler". Google Groups (comp.lang.scheme).
  2. 1 2 evhan (2018-11-09). "r7rs (Chicken manual)". Chicken Scheme. Retrieved 2019-02-28.
  3. "Scheme FAQ"., section "what is Scheme used for?"
  4. Bex, Peter (sjamaan) (2018-08-16). "Software written in Chicken Scheme". Chicken Scheme. Retrieved 2019-02-26.
  5. "Portability". Chicken Scheme Wiki.
  6. Bex, Peter (sjamaan) (2016-05-28). "Cross development". Chicken Scheme (Manual). Retrieved 2019-02-26.
  7. Baker, Henry (1994). "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." Archived from the original on 2006-03-03.
  8. Cheney, C.J. "A Nonrecursive List Compacting Algorithm". CACM 13,11 (Nov. 1970), 677-678.
  9. Bex, Peter (sjamaan); Winkelmann, Felix (2016-05-28). "Confirmed deviations (Chicken manual)". Chicken Scheme. Retrieved 2019-02-28.
  10. Bex, Peter (sjamaan); kooda; mario; svnwiki; wasamasa; kon; mario (2018-08-11). "utf8 (Chicken manual)". Chicken Scheme. Retrieved 2019-02-28.
  11. "Chicken eggs". Chicken Scheme.
  12. "RubyGems". RubyGems.org. Retrieved 2019-02-26.
  13. Bex, Peter (sjamaan). "VCS-independent distribution of language extensions"., blogpost on More magic
  14. "Instructions for popular code hosting methods and VCSes". Chicken wiki.
  15. "Chicken automated tests". Chicken Scheme. Retrieved 2019-02-28.
  16. iraikov (2016-06-11). "pyffi". Chicken Scheme Wiki. Retrieved 2019-03-03.
  17. Bex, Peter (sjamaan); iraikov (2012-03-11). "Lua". Chicken Scheme Wiki. Retrieved 2019-03-03.
  18. mario; svnwiki (2013-06-04). "JNI". Chicken Scheme Wiki. Retrieved 2019-03-03.
  19. Winkelmann, Felix; mario (2013-06-04). "Javahack". Chicken Scheme Wiki. Retrieved 2019-03-03.
  20. Bex, Peter (sjamaan); Winkelmann, Felix; mario (2018-09-23). "Module (Chicken syntax)". Chicken Scheme. Retrieved 2019-02-28.
  21. Bex, Peter (sjamaan); Winkelmann, Felix; mario (2018-09-23). "Module (Chicken syntax)". Chicken Scheme. Retrieved 2019-02-28.
  22. Bex, Peter (sjamaan) (2018-11-25). "Debugging". Chicken Scheme.
  23. Croisant, John (2013-06-19). "Behind the Scenes with CHICKEN Scheme and SPOCK (Part 2)". Atomic Spin. Retrieved 2023-02-17.