On Clojure

May 6, 2009

Simulating dynamic scoping

Filed under: Uncategorized — khinsen @ 4:36 pm

In the early days of Lisp, and programming languages in general, scoping was a hot issue of debate. What is better, lexical scoping or dynamic scoping?

Scoping refers to where a function looks for the definitions of symbols that it doesn’t have locally. Given (fn [x] (+ b x)), where does b come from? With lexical scoping, b is taken from the lexical environment, i.e. the forms surrounding the function definition, or from the global namespace if the lexical environment doesn't have a b. The lookup typically happens when the function is compiled. With dynamic scoping, the lookup happens at runtime and by following the call stack: first the calling function is checked for a definition of b, then the calle's caller, etc.

By now the issue has been settled: lexical scoping is the default in all modern programming languages, including all modern Lisp dialects. And that includes Clojure, of course. Lexical scoping is more predictable and permits compile-time analysis of which value a symbol refers to. It also permits closures, which have become a popular technique in functional programming.

However, dynamic scoping is of use in some occasions and it can in fact be simulated in Clojure. In this post I will show how and what to watch out for.

First of all, why would one want dynamic scoping? Here is one example. Recently I wrote an implementation of macrolet and symbol-macrolet for Clojure. These are both macros that modify the macro expansion procedure by adding local macro definitions. This means that a stack of macro definitions must be maintained: each macrolet adds definitions to the stack, and at the end of the macrolet form the new definitions are popped off again.

One usual way to handle this would be to pass the stack around among the functions that do the macro expansion, which could modify it as needed. Another approach would be hiding this passed-around state using the state monad (see part 3 of my monad tutorial). But in the specific situation of macro expansion, Clojure's macroexpand-1 enters into the call chain. I couldn't modify this function to pass on the macro definition stack, so I had to work around it in some way. I could have avoided using macroexpand-1, for example. But I chose to try simulating dynamic scoping at this occasion.

With dynamic scoping, a function that wants to modify the stack just redefines the variable containing it, calls the expansion recursively, and sets the stack back to its old value. A function accessing the stack just uses the current value of the variable, which is looked up in the call chain.

How can this be simulated in Clojure? The obvious candidate is binding. The binding form redefines a var in a namespace for the duration of the execution of its body. The redefinition is valid only inside the thread that is being executed, so other threads are not affected. In my macro expansion code, one of the stack vars is defined by

(defvar- macro-fns {})

and modified in each call to macrolet:

(defmacro macrolet
  [fn-bindings & exprs]
  (let [names      (map first fn-bindings)
	name-map   (into {} (map (fn [n] [(list 'quote n) n]) names))
	macro-map  (eval `(letfn ~fn-bindings ~name-map))]
    (binding [macro-fns     (merge macro-fns macro-map)
	      macro-symbols (apply dissoc macro-symbols names)]
      `(do ~@(map expand-all exprs)))))

Well, that's almost all there is to say about it. Except that the definition of macrolet given above does not work.

The problem is laziness. The binding form changes the definition of macro-fns only for the duration of the execution of its body and then resets it to its previous value. But the execution of the body is just a call to map. This doesn't actually do anything, it merely returns a package that calls expand-all as soon as the first element of the sequence is requested. And that happens only after the binding form has been left.

Once the problem is identified, the solution is simple: add a doall around the map:

(defmacro macrolet
  [fn-bindings & exprs]
  (let [names      (map first fn-bindings)
	name-map   (into {} (map (fn [n] [(list 'quote n) n]) names))
	macro-map  (eval `(letfn ~fn-bindings ~name-map))]
    (binding [macro-fns     (merge macro-fns macro-map)
	      macro-symbols (apply dissoc macro-symbols names)]
      `(do ~@(doall (map expand-all exprs))))))

However, adding all then necessary doalls requires careful attention. Forgetting does cause errors, but not necessarily immediately. For this reason, simulating dynamic scoping should be avoided except when there is a good reason. In retrospect, I am not even sure if my reason was good enough, and perhaps one day I will rewrite the code in a different way.

About these ads

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: