eighty-twenty

I've just finished taking scheme-pg version 0.4.0, which is intended for MzScheme version 299.30, and updating it (1) so that it builds on MacOS X, thanks to Geoffrey Knauth's patches (slightly edited to undo some kind of whitespace mangling probably introduced by the HTML mailing-list archiver); and (2) so that it builds with MzScheme v299.400. The only change to the Scheme code is in sql.ss — MzScheme v299.400 seems to have sprouted versions of string-upcase, string-titlecase, and string-downcase that conflict with SRFI-13's versions of the same procedures.

My revised scheme-pg package is available at http://www.eighty-twenty.org/~tonyg/Darcs/scheme-pg/. That's both a browseable snapshot, and a darcs repository that you can retrieve with

darcs get http://www.eighty-twenty.org/~tonyg/Darcs/scheme-pg/

This afternoon I implemented a simple partial evaluator for a Scheme-like language, based on the paper "Partial Evaluator as a Compiler for Reflective Languages" (Asai, Masuhara, Matsuoka and Yonezawa, 1995). So far I've restricted myself to an IO-free, side-effect free language, but by using the notion of preactions I ought to easily be able to add support for IO. I'd like to explore extending the simple system I have now to cope with the Composable Memory Transactions of Harris et al instead of supporting Scheme's destructive updates.

The addition of pattern-matching data-destructuring will help the partial evaluator out, too, in the same way it makes dealing with primitive data easier for the Spineless Tagless G-Machine (see section 4.7). For example, using the partial evaluator to specialize the expression

(fold + 0 a)

I currently get

(letrec ((g17 (lambda (x acc)
                (if (null? x)
                  acc
                  (GOTO g17
                        (if (pair? x)
                          (PRIMcdr x)
                          (error '"Not a pair in cdr" x))
                        (+ (if (pair? x)
                             (PRIMcar x)
                             (error '"Not a pair in car" x))
                           acc))))))
  (g17 a '0))

(Ignore the strange GOTO syntax — I'm also experimenting with identifying the places I can transform recursive procedures into iterative loops.) Note that the type test (pair? x) is repeated twice. If some kind of match clause were used instead, we would see the test lifted to wrap the (GOTO g17 ...) expression, leaving us with something more like

(letrec ((g17 (lambda (x acc)
                (if (null? x)
                  acc
		  (if (pair? x)
		      (GOTO g17 (PRIMcdr x) (+ (PRIMcar x) acc))
		      (error '"Not a pair in match" x))))))
  (g17 a '0))

which, when compiled, is about as efficient as you will get with a statically compiled Scheme. Lots of the optimizations developed in the Self system apply to dynamically compiled variants, of course, potentially leading to further efficiencies.

On this page about syntactic closures, we see the definition of an anaphoric-if macro that doesn't transmit the "it" binding to the alternative clause — just to the consequent. This is pretty sophisticated. I immediately began to think about how you could do the same with syntax-case (as clearly others had before me) and it turns out to actually be easier. The only real downside is the introduction of another binding — but of course the mythical Sufficiently Smart Compiler will optimise that away immediately anyway.