I figured it out. I was being very lax in ordering my scopes.
The data structure of traditional lexical environments consists of a table of bindings, and a pointer to the next outer binding:
A -> B -> C -> D
Here A is the innermost scope that gets checked first. The sequence of scopes checked is ABCD.
Wart's new scoping rules are for macros: we provide access to the caller's scope.
A -> B -> C -> D
\
E -> F -> G -> H
Each 'level' of scopes is a traditional lexical environment. Since we want to only use caller scopes for bindings we can't find in the lexical environment, we traverse the lexical environment before 'dropping down a level to the caller's environment. Thus the order of lookups is ABCDEFGH.
This was where things stood until I ran into keep. The problem with keep was that the tree structure was more complex. Consider this slightly more complex scope tree:
A -> B -> C -> D
\ \
E -> F G -> H
It's clear that ABCD comes before EFGH. But what order should the caller scopes be traversed in? It turns out you want to unwind the stack first close to the callee: ABCDEFGH, which corresponds to a breadth-first traversal. However, I had lazily done the simplest possible thing, a depth-first search. ABCDGHEF. Wrong.
---
This took forever to debug because I struggled to find a nice way to visualize scopes. One drawback of everything being an f-expr is that I quickly run into complex trees that are impossible to visualize (http://github.com/akkartik/wart/commit/3932165bbf until http://github.com/akkartik/wart/commit/9ffcdec864). Eventually I came up with the idea of visualizing paths instead (http://github.com/akkartik/wart/commit/b234594cfa). I came up with a helper that takes a sym and enumerates in order all the paths that find bindings to it in the current environment. Once I did that it became easy to see that 10 should come before 0010 (0 is a horizontal edge, 1 is a diagonal edge)
This seems relevant: "With macros, you have hygiene issues because you work with quoted identifiers, that somehow have to refer back to their original bindings. With fexprs, you have the luxury of using live values instead of identifiers referring to values, thereby achieving hygiene simply through good old lexical scope, already built-in to the language anyway."http://lambda-the-ultimate.org/node/4345#comment-66868
