natethern/cpscm

fork of CPSCM Scheme

CPSCM Scheme

CPSCM is a Scheme compiler based on CPS conversion. It outputs code for two back-ends: Javascript and Common Lisp (as well as a "Simple Scheme" back-end). There is an online CPSCM compiler that lets you play with the compiler right from your browser without downloading anything. Also see the bubble sort example which combines compiled Scheme and DHTML.

Download and run CPSCM

Get the latest source code via SVN from the Google Code CPSCM project page (which is also where you can report bugs):

svn checkout http://cpscm.googlecode.com/svn/trunk/ cpscm

Older releases are in http://cpscm.googlecode.com/svn/tags/.

CPSCM runs under SISC and Chicken. To run:

cd cpscm/scm; ./setup.sh

Follow the instructions printed on the screen. At the Scheme prompt, use (import ) (:compile src dst-file) where is one of scm2js or scm2lisp and src is either a list of s-expressions, or a Scheme source file. The import statement is only required once per session. For example:

(import scm2js)
(scm2js:compile "../static/scheme-examples/fact.txt" "prog.js")

Features

All R5RS standard macros are supported, along with user-defined syntax-rules macros. I'm planning to add define-macro support, since certain things are not expressible (easily) with hygienic macros.

SRFI-0 (cond-expand) is built-in; feature cpscm allows you to include custom code that will be seen only by CPSCM.

Continuations and call/cc are fully supported and interact correctly with dynamic-wind and error. CPSCM borrows from SISC the concept of failure continuations, accessible via with-failure-continuation.

Eval and the related environment functions are not supported yet. Once R5RS support is complete, eval will be added by "compiling the compiler" for each back-end.

The conformance page details which procedures required by the R5RS standard are not yet implemented. Some backends offer extras (such as support for various SRFIs).

Javascript backend

Assuming you saved your compiled program in prog.js, fire up Rhino:

java -jar /path/to/rhino/js.jar

... and type:

js> load ("cpscm-drv.js"); load ("prelude.js"); load ("prog.js")

It's possible to run the Javascript code inside a browser. You will need to upload your Javascript files, plus a skeleton HTML file referencing them inside the section, on a web server. The bubble sort example demonstrates how to call Scheme from Javascript and vice-versa. Here's a simplified summary: in your Scheme program, provide a function called fun. In Javascript, call Scheme as in the following template:

var result = cpscm__drive (cpscm__call_scm (cpscmfun (cpscm__id, arg1, arg2 /* ... */));

Common Lisp back-end

To run a compiled program, bring up a new shell, start Lisp and type

lisp> (mapc #'load '("cpscm-drv.lsp" "prelude.lsp" "prog.lsp"))

Common Lisp is a 2-Lisp, which means that functions exist in a namespace separate from symbols. CPSCM takes the easy way out by

• avoiding (defun) and using defparameter and setq instead (for example, (defparameter inc1 (lambda (x) (+ x 1)))).
• calling all functions via funcall

How it works

CPSCM uses a modified version of the alexpander program to expand R5RS syntax-rules macros. The macroless code is converted to ANF, which in turn is CPS-transformed. The CPS step generates a large number of redexes. Simple β and η reductions cut down on the number of closures (see simplify-sexp in scm/analysis.scm); however, the output can still be difficult to read. The "intermediate Scheme" representation is then fed to one of the back-ends (e.g. Common Lisp). The language-specific translator renames identifiers to prevent conflicts with the host (for example, car becomes cpscmcar in all back-ends). The back-end translators insert trampolines at each step to avoid unbounded stack growth and implement tail-call optimization. All back-ends include a trampoline "driver" loop to run the generated code. Many of the trampoline wrappers are not necessary (and cost time and space); in future versions there will hopefully be an optimizer to deal with them.

Bootstrapping R5RS

Many R5RS procedures are expressible in terms of a core set of primitives. This eases the burden of the implementor (my own definitions are in r5rs-bootstrap.scm). Each backend includes a (create-*-prelude) procedure to compile the non-primitive procedures to a corresponding prelude.* file.

Scheme in Scheme

For debugging and educational purposes, there is a "simple Scheme" back-end. The underlying Scheme need not provide continuations, multiple values or dynamic-wind. The relevant backend is scm/scm2scm.scm, and the "driver" is in static/scheme-backend/cpscm-drv.scm (the latter embeds the "prelude" file which stands separate in the Common Lisp backend).

Dan Muresan