Wednesday, October 17, 2007

Two optimizations, only one safe

PLT Scheme's module system suggests some simple compiler optimizations. For one, identifiers bound in a module cannot be mutated from outside the module. This makes it very easy to determine whether the binding is immutable: just scan the source for instances of set!. If there aren't any, you can rely on the binding's immutability for optimizations like constant propagation.

Here's another tempting one: if a module imports a library but doesn't use some of the library's exported bindings, it seems like it should be safe not to load those bindings, right? Nope! Because the macro system has complete access to the syntactic environment, a macro exported by the module might actually compute a reference to the binding:
(define-syntax (foo stx)
(syntax-case stx
... (datum->syntax-object
(string->symbol "mumbly-foo")) ...
The syntax object #'here encapsulates the entire syntactic environment, and if the imported library exports mumbly-foo, looking up 'mumbly-foo in the syntactic environment will find it. Similarly, run-time code in the module might perform
(eval (datum->syntax-object #'here 'mumbly-foo))
and it would again find the binding. So it's not generally possible to prune any library imports, as long as macros and eval have complete access to the syntactic environment through syntax objects.

Well, eval is scary... does this mean the first optimization is unsafe, say, if eval tries to mutate it? I don't think so. Module bindings are stored in the lexical (i.e., local) environment, which I believe is not available to eval. The bindings available to eval are the ones that come from PLT Scheme's "namespace" objects. As I understand it, these namespaces do not contain mappings for local variables, only for globals and module imports.


Ryan Culpepper said...

It is possible to get a namespace corresponding to the bindings visible within a module (using 'module->namespace'). That's how DrScheme's "(module ...)" language works. By default, though, the compiler does not allow mutation of variables through that namespace (but that's customizable via the 'compile-enforce-module-constants' parameter).

So yes, the first optimization is safe.

Anonymous said...


Quick question that has nothing to do with this blog: The logo of the word "timshel" on your that how it is written in Hebrew? I'm having a hard time finding anywhere it is written in Hebrew (including a bunch of online dictionaries). The story of timshel is by far my favorite part of East of Eden.

Can you please let me know the answer by emailing me? It'd be much appreciated. (