Cyclone

Cheney on the M.T.A. with native threads.

User Manual

Introduction

Cyclone is an experimental Scheme-to-C compiler that uses a variant of the Cheney on the MTA technique to implement full tail recursion, continuations, generational garbage collection, and native threads.

Cyclone works by converting a Scheme program to continuation passing style and compiling each continuation to a C function. At runtime these functions never return and are allowed to fill up the stack until they trigger a minor garbage collection. Live stack objects are then copied to the heap and longjmp is used to return to the beginning of the stack. This is the same technique proposed by Henry Baker (Cheney on the MTA) and implemented first by CHICKEN Scheme. The difference is that our compiler allows multiple native threads, each with their own stack. A tracing garbage collector is used to manage the second-generation heap and perform major collections without “stopping the world”.

Cyclone is developed by Justin Ethier.

Bug reports and patches are welcome! Please report any issues using the Issues Page.

Requirements

Cyclone has been tested under Linux on the x86, x86-64, and ARM platforms.

The following packages are required:

On a Debian variant such as Ubuntu the necessary packages may be installed via the command:

sudo apt-get install libtommath-dev libck-dev make gcc

The following command can be used to install dependencies on Fedora, though libck will also need to be built from source:

sudo yum install libtommath-devel gcc make

Installation

Cyclone cannot be built directly on a system that does not have Cyclone binaries installed because the compiler is self-hosting. The easiest way to install Cyclone binaries is to build from source using cyclone-bootstrap:

$ git clone git@github.com:justinethier/cyclone-bootstrap.git
$ cd cyclone-bootstrap
$ ./install.sh

Once Cyclone is installed, it can be rebuilt directly from the cyclone repository:

$ make
$ make test
$ sudo make install

Usage

Compiling Scheme Programs

A Scheme program may be compiled using the cyclone command:

$ cyclone  examples/fac.scm
$ examples/fac
3628800

Compiling Scheme Libraries

Scheme code can be organized into libraries that are compiled separately from programs. Cyclone intends a library to represent a single C module (or file) when compiled.

Each library must be placed into a .sld file that corresponds to the library name. For example, the library

(scheme cyclone util) 

would be defined in its .sld file as:

(define-library (scheme cyclone util)
  ... )

and should be located in the file

scheme/cyclone/util.sld

Cyclone will not automatically generate libraries when compiling a program. Each library will need to be built separately prior to building the program.

Command Line Options

cyclone has the following command line options:

Option Notes
-A directory Append directory to the list of directories that are searched in order to locate imported libraries.
-I directory Prepend directory to the list of directories that are searched in order to locate imported libraries.
-CP cc-commands Specify a custom command line for the C compiler to compile a program module. See Makefile.config for an example of how to construct such a command line.
-CE cc-commands Specify a custom command line for the C compiler to compile an executable.
-CL cc-commands Specify a custom command line for the C compiler to compile a library module.
-Ox Optimization level, higher means more optimizations will be used. Set to 0 to disable optimizations.
-d Only generate intermediate C files, do not compile them. This option will also show the C compiler commands that would have been used to compile the C file.
-t Show intermediate trace output in generated C files
-h, --help Display usage information
-v Display version information

Generated Files

The following files are generated during the Cyclone compilation process:

File Extension Notes
.meta These text files contain the expanded version of any macros exported by a Scheme library, and allow other modules to easily use those macros during compilation. This file is not generated when compiling a program.
.c C code file generated by Cyclone.
.o Object file generated by the C compiler from the corresponding .c file.
(None) Final executable file generated by the C compiler when compiling a program.

Interpreter

Scheme code can be evaluated interactively using the icyc command:

    $ icyc
    cyclone> (write 'hello-world)
    hello-world

Language Details

Cyclone implements the Scheme language as documented by the R7RS Scheme Specification.

A R7RS Compliance Chart lists differences between the specification and Cyclone’s implementation.

API Documentation is available for the libraries provided by Cyclone.

Multithreaded Programming

The srfi 18 library may be imported to provide support for multithreaded programs. See the SRFI 18 specification for more background information.

Due to how Cyclone’s garbage collector is implemented, objects are relocated in memory when they are moved from the first generation (on the stack) to the second generation (on the heap). This causes problems when an object is used by multiple threads, as the address another thread expects to find an object at may suddenly change. To prevent race conditions an object must be guaranteed to be on the heap prior to being used by another thread. There are two ways to meet this guarantee:

Finally, note there are some objects that are not relocated so the above does not apply:

Foreign Function Interface

Writing a Scheme Function in C

The define-c special form can be used to define a function containing user-defined C code. This code will be carried through from the Scheme file all the way to the compiled C file. For example:

 (define-c Cyc-add-exception-handler
   "(void *data, int argc, closure _, object k, object h)"
   " gc_thread_data *thd = (gc_thread_data *)data;
     make_pair(c, h, thd->exception_handler_stack);
     thd->exception_handler_stack = &c;
     return_closcall1(data, k, &c); ")

The arguments to define-c are:

Functions that may block must call the set_thread_blocked macro to let the system know the thread may block. After the blocking section is finished, the return_thread_runnable macro must be called to recover from the blocking operation and call into the current continuation. For example:

object Cyc_mutex_lock(void *data, object cont, object obj) {
  mutex m = (mutex) obj;
  Cyc_check_mutex(data, obj);
  set_thread_blocked(data, cont);
  if (pthread_mutex_lock(&(m->lock)) != 0) {
    fprintf(stderr, "Error locking mutex\n");
    exit(1);
  }
  return_thread_runnable(data, boolean_t);
}

The Cyclone runtime can be used as a reference for how to write your own C functions. A good starting point would be runtime.c and types.h.

Including a C Header File

A C header may be included using the include-c-header special form. This special form may be used either as part of a library definition:

(define-library (example life)
  (include-c-header "../write-png.h")
  (export life)
  ... )

Or as part of a program (add any includes immediately after the import expression, if one is present):

(import (scheme base)
        (example life)
        (example grid))
(include-c-header "stdlib.h")
(include-c-header "<stdio.h>")

By default this will generate an #include preprocessor directive with the name of the header file in double quotes. However, if include-c-header is passed a text string with angle brackets (EG: "<stdio.h>"), the generated C code will use angle brackets instead.

Licensing

Cyclone is available under the MIT license.

References and Further Reading