Lobsters - 03 Oct 2026
Page 2 of 2
On the other hand, some data types can be represented using 30 bits or less and are stored as value types. The great thing about value types is they do not have to be garbage collected because no extra data is allocated for them. This makes them super efficient for commonly-used data types.
Value types are stored using a common technique that is described in Lisp in Small Pieces (among other places). On many machines addresses are multiples of four, leaving the two least significant bits free. A brief explanation:
The reason why most pointers are aligned to at least 4 bytes is that most pointers are pointers to objects or basic types that themselves are aligned to at least 4 bytes. Things that have 4 byte alignment include (for most systems): int, float, bool (yes, really), any pointer type, and any basic type their size or larger.
In Cyclone the two least significant bits are used to indicate the following data types:
| Binary Bit Pattern | Data Type |
|---|---|
| 00 | Pointer (an object type) |
| 01 | Integer |
| 10 | Character |
Booleans are potentially another good candidate for value types. But for the time being they are represented in the runtime using pointers to the constants boolean_t and boolean_f.
Thread Data Parameter
At runtime Cyclone passes the current continuation, number of arguments, and a thread data parameter to each compiled C function. The continuation and arguments are used by the application code to call into its next function with a result. Thread data is a structure that contains all of the necessary information to perform collections, including:
- Thread state
- Stack boundaries
- Cheney on the MTA jump buffer
- List of mutated objects detected by the minor GC write barrier
- Parameters for major GC
- Call history buffer
- Exception handler stack
Each thread has its own instance of the thread data structure and its own stack (assigned by the C runtime/compiler).
Call History
Each thread maintains a circular buffer of call history that is used to provide debug information in the event of an error. The buffer itself consists of an array of pointers-to-strings. The compiler emits calls to runtime function Cyc_st_add that will populate the buffer when the program is running. Cyc_st_add must be fast as it is called all the time! So it does the bare minimum - update the pointer at the current buffer index and increment the index.
Exception Handling
A family of Cyc_rt_raise functions is provided to allow an exception to be raised for the current thread. These functions gather the required arguments and use apply to call the thread's current exception handler. The handler is part of the thread data parameter, so any functions that raise an exception must receive that parameter.
A Scheme API for exception handling is provided as part of R7RS.
Scheme Libraries
This section describes a few notable parts of Cyclone's Scheme API.
Native Thread Support
A multithreading API is provided based on SRFI 18. Most of the work to support multithreading is accomplished by the runtime and garbage collector.
Cyclone attempts to support multithreading in an efficient way that minimizes the amount of synchronization among threads. But objects are still copied during minor GC. In order for an object to be shared among threads the application must guarantee the object is no longer on the stack. One solution is for application code to initiate a minor GC before an object is shared with other threads, to guarantee the object will henceforth not be relocated.
Reader
Cyclone uses a combined lexer / parser to read S-expressions. Input is processed one character at a time and either added to the current token or discarded if it is whitespace, part of a comment, etc. Once a terminating character is read the token is inspected and converted to an appropriate Scheme object. For example, a series of numbers may be converted into an integer.
The full implementation is written in Scheme and located in the (scheme read) library.
Interpreter
The eval function is written in Scheme, using code from the Metacircular Evaluator from SICP as a starting point.
The interpreter itself is straightforward but there is nice speed up to be had by separating syntactic analysis from execution. It would be interesting see what kind of performance improvements could be obtained by compiling to VM bytecodes or even using a JIT compiler.
The interpreter's full implementation is available in the (scheme eval) library, and the icyc executable is provided for convenient access to a REPL.
Compiler Internals
Most of the Cyclone compiler is implemented in Scheme as a series of libraries.
Scheme Standards
Cyclone targets the R7RS-small specification. This spec is relatively new and provides incremental improvements from the popular R5RS spec. Library support is the most important new feature but there are also exceptions, system interfaces, and a more consistent API.
Benchmarks
ecraven has put together an excellent set of Scheme benchmarks based on a R7RS suite from the Larceny project. These are the typical benchmarks that many implementations have used over the years, but the remarkable thing here is all of the major implementations are supported, allowing a rare apples-to-apples comparison among all the widely-used Schemes.
Over the past year Cyclone has matured to the point where almost all of the 56 benchmarks will run:
The remaining ones are:
- mbrotZ fails because Cyclone does not support complex numbers yet.
- pi does not work because Cyclone does not support bignums yet.
- compiler passes but returns the wrong result. This will be fun to track down since the program is huge and takes a long time to compile...
Regarding performance, from Feeley's presentation [10]:
Performance is not so bad with NO optimizations (about 6 times slower than Gambit-C with full optimization)
But Cyclone has some optimizations now, doesn't it? The following is a chart of total runtime in minutes for the benchmarks that each Scheme passes successfully. This metric is problematic because not all of the Schemes can run all of the benchmarks but it gives a general idea of how well they compare to each other. Cyclone performs well against all of the interpreters but still has a long ways to go to match top-tier compilers. Then again, most of these compilers have been around for a decade or longer:
Future
Some goals for the future are:
- Implement more of R7RS-large; work has already started on the data structures side.
- Implement more libraries (for example, by porting some of industria to r7rs).
- Improve the garbage collector. Possibly by allowing more than one collector thread (Per gambit's parallel GC).
- Perform additional optimizations, EG: Andrew Appel used a similar runtime for Standard ML of New Jersey which is referenced by Baker's paper. Appel's book Compiling with Continuations includes a section on how to implement compiler optimizations - many of which could still be applied to Cyclone.
In addition, developing Husk Scheme helped me gather much of the knowledge that would later be used to create Cyclone. In fact the primary motivation in building Cyclone was to go a step further and understand how to build a full, free-standing Scheme system. At this point Cyclone has eclipsed the speed and functionality of Husk and it is not clear if Husk will receive much more than bug fixes going forward. Perhaps if there is interest from the community some of this work can be ported back to that project.
Conclusion
Thanks for reading!
Want to give Cyclone a try? Install a copy using cyclone-bootstrap.
Terms
- Abstract Syntax Tree (AST) - A tree representation of the syntactic structor of source code written in a programming language. Sometimes S-expressions can be used as an AST and sometimes a representation that retains more information is required.
- Free Variables - Variables that are referenced within the body of a function but that are not bound within the function.
- Garbage Collector (GC) - A form of automatic memory management that frees memory allocated by objects that are no longer used by the program.
- REPL - Read Eval Print Loop; basically a command prompt for interactively evaluating code.
References
- CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A., by Henry Baker
- CHICKEN Scheme
- CHICKEN Scheme - Internals
- Chibi Scheme
- Compiling Scheme to C with closure conversion, by Matt Might
- Lisp in Small Pieces, by Christian Queinnec
- R5RS Scheme Specification
- R7RS Scheme Specification
- Structure and Interpretation of Computer Programs, by Harold Abelson and Gerald Jay Sussman
- The 90 minute Scheme to C compiler, by Marc Feeley
- The Development of Chez Scheme, by R. Kent Dybvig
Previous page | More Lobsters | Headlines
Original: https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017