15 August 2007

One More Reason to Love Module Systems and Hygiene

I just released an Automatic Differentiation PlaneT Package, and am now converting my numerical relativity code to use it. The package exports procedures like +, -, =, etc, which are modified from the standard ones so it can compute derivatives of numerical procedures which use them. Of course, these modified procedures are slower than their standard cousins.

My numerical relativity code uses all sorts of looping constructs from the excellent SRFI-42. These loops iterate over vectors, over ranges of numbers, lists, matrices, .... The iteration macros expand to code like (this is just an illustration---the real code is more complicated than this)

(let loop ((vector-index 0))
  (if (>= vector-index (vector-length vector))
      'done
      (let ((vector-elt (vector-ref vector vector-index)))
        <body>
        (loop (+ vector-index 1)))))
You'll note that this code uses +, >=, etc. It is acceptable for these functions to be the addition and comparison from my PlaneT package, since that package preserves the meaning of the numerical functions operating on pure numbers. But, it would be nicer if the + and >= came from the mzscheme language module. In this case, the compiler could inline the addition and comparison, and even if it didn't there wouldn't be the differentiation overhead.

No problem! PLT Scheme's module system takes care of this automatically: SRFI-42 is defined in the mzscheme language, so all references to + and >= in its macros refer to those bindings from mzscheme. So, even if the module using the SRFI-42 macros is written in a different language (like "deriv-lang.ss"), the expansion of these macros uses the correct procedures.

This is a combined effect of of hygiene and the PLT module system. Neither alone would reproduce the correct behavior. For example, in schemes without a module system which handles macros properly, it would be necessary to re-define + and >= at the top level in the deriv.plt package. Then, the hygiene of the macro expander would ensure that the + and >= in the macro expansion of SRFI-42 iterators referred to the top-level bindings (even if there were local bindings for these symbols at the macro use-site), but these would be the deriv-enabled + and >=, not the usual, optimizable mzscheme ones.

In short: I know of no other module system that would handle this so elegantly (in a current scheme system, anyway---the proposed R6RS module system would do just as well for this). (In fact, I think only the module system of Chez scheme, immortalized in the portable syntax-case expander by Dybvig and Waddell handles this at all. Unfortunately, it requires you to list the local variables which a macro can expand into manually along with the usual exports of the module, which is not nearly as convenient.) Hooray for PLT!

1 comment:

Barak said...

Technically speaking, this module implements only "Forward AD" or to be less cryptic, "Automatic Differentiation with Forward-Mode Accumulation". Reverse mode is much trickier to implement correctly, but can compute gradients efficiently.