CPSCM: interfacing Javascript and Scheme

Calling Javascript from Scheme just got easier in CPSCM:

(define v 10)
(define (f x) (+ x v))
(%cpscm:native "alert (" v ")")
;; Can pass Scheme variables and computations
(%cpscm:native "alert (" (f 5) ")")

All string arguments to %cpscm:native are copied verbatim to the output. Inner computations are still compiled as any normal Scheme code, and their results are passed to the native call via temporary variables. Each native call must correspond to a single JS statement.

The old method was to provide a CPS wrapper with the correct mangled name, e.g. to create a function callable as (fun 1 2) from Scheme:

var cpscmjsfun = cpscm__cpswrap (
  function fun (x, y) { return x + y; }

This still works, of course (as demonstrated in the DHTML bubble-sort example), but the new method adds convenience.

The main reason for native is the anticipated Emacs Lisp backend: users will surely want to call a myriad of elisp functions from Scheme, and writing a CPS stub for each of them would be impractical.

Note: the new code is in SVN, but the I haven't updated the online compiler demo webapp yet.

Emacs Lisp vs. Scheme: scoping and globals

I've been considering an elisp back-end for CPSCM (so that we can program Emacs in R5RS Scheme). I thought the lack of lexical scoping would prove a major stumbling block, but in the end it turns out that Elisp will be somewhat easier to support than Common Lisp. Here are the twists and turns (to evaluate Elisp code, go to the *scratch* buffer, paste the code and type C-x C-e):

  • Elisp has dynamic scope by default:
    (defun f () y)
    (let ((y 10)) (f))  ;; 10
    ;; lambda arguments are also dynamic
    (funcall (lambda (y) (f)) 11)  ;; 11
  • However, with (require 'cl) you get access to the (lexical-let ...) macro, which does exactly what the name says (there is also a lexical-let*)
  • Using lexical-let, one can easily define lexical-lambda — here's a simple version (optimized for minimal line lengths, not Lisp-ness)
    (defmacro lexical-lambda (args &rest body)
      (lexical-let* ((r '&rest) (g (lambda (x) (if (eq x r) x (gensym))))
                     (gvars (mapcar g args))
                     (bnd (mapcar* #'list args gvars)))
        `(lambda ,gvars
           (lexical-let ,(delete-if (lambda (b) (eq (car b) r)) bnd)

OK, so we've played catch up with Common Lisp and managed to work around dynamic scoping; here's the beautiful part:

  • Elisp has sane(r) globals (from a Schemer's POV, at least)

To those who haven't bashed their heads against this problem, Common Lisp's "normal" way of declaring globals (defvar / defparameter) makes variables "pervasively special" (i.e. dynamic) — meaning that

(defvar myvar 10)
(defun (f) myvar)
(defun g () (let ((myvar 1)) (f)))
(g)  ;; => 1, not 10

This is not such a problem for Lisp, but what with Scheme being a Lisp-1, translation of global functions is problematic:

(define (f x) x)  ;; Scheme
;; Lisp translation -- broken
(defvar f (lambda (x) x))

There's another standard-compliant way to simulate globals in Lisp (using symbol macros — search comp.lang.lisp for deflex); however this method requires you to define each global before referencing it, which would preclude mutually-recursive global functions:

(deflex f (lambda (x) (funcall g (- x 1))))  ;; broken: g undefined
(deflex g (lambda (x) (if (> x 0) (funcall f x) 0)))

There are other, more convoluted ways to implement "non-special" globals that have elicited endless (and inconclusive, as far as I could tell) threads on comp.lang.lisp, e.g. using (locally (declare (special myvar))). Finally, in many Lisp's one can simply use (setq myvar ...) and at most get a warning, but this is not standards-compliant.

As luck would have it, setq globals work in Elisp too, and the manual seems to indicate that this is intended semantics, not accident. So this will save me the pain of working around Common Lisp's "special" variable rules (I've never found a satisfactory solution), which is why I'm happy about Elisp.

Of course there are areas that need work, e.g. an easier "FFI" to access Elisp functions from Scheme (currently, one has to define a CPS-style wrapper in the back-end with the proper mangled name to make a function callable from CPSCM). But I find the prospect of programming Emacs in Scheme a pretty good motivation...

CPSCM passes R5RS pitfalls

After several fixes and tweaks, the CPSCM Javascript backend passes the R5RS Pitfalls test with a full score. The Lisp backend almost does, but since I decided to stick with Lisp's convention of representing both false booleans and empty lists with NIL, it fails cases 5.1 - 5.3.

Additionally, I have tested the bubble sort example and the JS backend in general under IE 6, Firefox and Opera (the browsers I can access easily). I haven't encountered any issues. If you are using IE 7 or Safari and run into problems, please report. The online compiler now lets you execute compiled code directly in your browser, so it's much easier to test than before.

On the negative side, some of you have noticed that the CPS code is more bloated than before. This is because I had to back out η-reduction for some cases, in the interest of correctness: (lambda (x) (f x)) does not reduce to f automaticaly if f is mutable (and, of course, Scheme is not Erlang). The analysis module will catch up eventually...

CPSCM translates Scheme to Javascript

I have added a Javascript backend for CPSCM. The compiled code runs either inside a browser or in Rhino. The Bubble sort example demonstrates compiled Scheme code running "in a web page" and interfacing with native Javascript code (the latter provides DHTML functionality). You can call Scheme functions from Javascript and Javascript functions from Scheme with no restrictions (even continuations will work correctly). The explanations on the bubblesort page should get you started, in case you want to roll your own Scheme programs.

I have made updates and fixes to all backends. There are still missing pieces, but at least now they are summarized on the conformance page, so you know what to expect. Among the improvements, there is an error function which interacts correctly with dynamic-wind. I have borrowed the concept of failure continuations from SISC; you can access them via with-failure-continuation.

Finally, since Javascript console I/O is not standardized, I have implemented SRFI-6 output strings. By default, (display) and its family assume you are using Rhino and try to print to standard output. You can switch to a string using (current-output-port (open-output-string)), and at any point retrieve the accumulated output using (get-output-string (current-output-port)).

CPSCM improvements

Alessandro Colomba (of SISCweb fame) played with CPSCM and noted that he had trouble compiling the SRFI-1 reference implementation (you need a self-contained SRFI-1 to check). After investigating the problem, I found out that the culprit was the η-reduction code in simplify-sexp, which wasn't designed carefully and exhibited exponential behavior on certain inputs (in practice, I've only seen that happen on CPS-ed code). After refactoring simplify-sexp, SRFI-1 compiles in just a few seconds.

The fixes are up in SVN (I've tagged the current version as rel-0.9.2). Other improvements:

  • Most of the code can be compiled under Chicken, with remarkable speed gains. Just type make in the scm directory. csi (which is still needed for the REPL) uses the compiled libraries automatically.
  • By popular demand I have added a file->lisp procedure for compiling a Scheme source file.
  • Programs are no longer wrapped in a giant letrec, but generate a sequence of top-level definitions and evaluation calls. This means you can compile libraries (such as SRFI-1 above) to separate files, and then load those compiled files independently in the back-end.

Announcing CPSCM, a new Scheme

I am releasing CPSCM, a new Scheme compiler based on classic CPS conversion and trampolines. It will eventually support multiple backends (Javascript and Java are in the works), but currently it supports Scheme to Common Lisp translation. You can see it work right from your browser on the online demo page (no large jobs, please), or you can download and run it by following the instructions on the CPSCM homepage.

Macro-expansion is delegated to Al Petrofsky's alexpander, which means that CPSCM has full syntax-rules support from the start. I'll probably add define-macro support at some point. I don't feel up to integrating syntax-case, but if anyone wants to contribute, it would be greatly appreciated.

Other than this, CPSCM supports full continuations, including correct call/cc + dynamic-wind interaction, and SRFI-0. It still lacks eval, error protection in dynamic-wind, streams, load, and multiple-file source facilities. An interesting point is that as soon as CPSCM is able to compile itself, eval can be added in (though the environment functions other than interaction-environment will be problematic.)

As with scsh-regexp, I will use Google Code Project Hosting. Some people have questioned this choice (and Google Code has earned mixed reviews); compared to Sourceforge, Google Code has a big advantage: they don't make you fill out multi-page forms (and wait for approval!) for the "privillege" of uploading an open-source project.