Macro Expansion: HoPL 2/25/2004

Presented by Ryan Culpepper
Transcribed by Felix Klock

Macros: what are they? Why expand them?

Suppose we're defining a language with the following core evaluation rules:

Now, if we wanted to add a rule for a let form, we could write out a new evaluation rule, with yet another meta-linguistic expression on the right hand side.

Or we could write the following concise rule:

Likewise, we could write or like so

In a sense, we're getting "New syntax for free"

Q ( from Audience ): Why macro-expand ahead of time?
A: Its hard to get it right if you interleave computations and expansions. Also, there are forms that you want to statically check for syntactic correctness ahead of time.

Lisp Macros (pre '86)
      
(define-macro (or e1 e2)
  `(let ((v ,e1))
     (if v v ,e2)))

    

So...

      
(or #f 3)
==>
(let ((v #f)) (if v v 3))

    

Looks good. But ...

      
(let ((v 3)) (or #f v))
==>
(let ((v 3))
  (let ((v #f)) (if v v v)))

    

Scribe's Note:
As Ryan pointed out later, this rewrite is not quite right; you would actually see the rewrite for let into λ first, and then the rewrite for or on that. But the bug would still occur in that elaborated pair of rewrites.

Above we see that an expression that we would expect to return 3 is rewritten into an expression that returns #f. This is bad.

The problem was well known folklore; people generally used (gensym) to fix the macro by hand when they encountered such problems (That, or just choose a more obscure name for the introduced variable).

Q ( from Audience ): When did define-macro first appear
A: Matthias says: as far back as '65 or '66

Q ( from Matthias ): Why shouldn't this happen?
A: We should have transparent expression activity, without having to know what variable names macros like or play with.

Note that as far as our denotational semantics is concerned, the above macro is correct. What we really wanted to say was

Scribe's Note: There was some disagreement between Ryan and Matthias on this point, where Ryan thought that Barendregt implicitly introduced fresh variables as necessary, and Matthias insisted that Barendregt's convention does not apply to Denotational Semantics

Program Macro M
           
           
   
M
         
 
E
     
         
     
           
           
           
M
                 
                 
                 
     
E
         
                 
                 
                 

Above is a rough picture of how one could visualize the behavior we want from a macro expander; it should expand from its use on the left into its definition on the right, but the inner expression E that has been passed to the macro should get its variable bindings only from areas that are painted gray.

In other words, we want naiive substitution.

Scribe's Note: At this point, Matthias said that this is "filling in context holes". But emphasized that it is not evaluation context holes. What kind of holes should we call them? Textual context holes? Syntactic context holes?

Q ( from Ryan ): Why can't we automatically perform alpha-renaming
A: Because in general you can't tell which variable instances are binding instances; in the or definition, if you don't know that let is a binding special form, you can't tell whether to create a fresh name for the occurances of v

Q ( from Audience ): Why not just provide a seperate explicit list of variables to inform the macro expander
A: Ryan said that will come later. The scribe isn't actually sure that it did.

Hygenienic Macro Expansion (KFFD '86)

Our goal: Hygeniene.

Indentifiers introduced by macro expansion (the red area of M's right hand box above) which become binding instances should only bind identifiers introduced in the same expansion step

      
(let ((v 3)) (or #f v))

    

Stamp the Identifiers, but not the macro names

      
(let ((v.0 3)) (or #f v.0))

    

Q ( from Audience ): Why are we expanding let now, when we didn't before
A: We should have expanded the lets before the or before. (See scribe's note)

      
((lambda (v.0) (or #f v.0)) 3)

    

We're done expanding the outer context; now expand the macros inside the lambda bodies.

      
(or #f v.0)

    
      
(let ((v.2 #f))
  (if v.2 v.2 v.0))

    
      
((lambda (v.2)
   (if v.2 v.2 v.0))
 #f)

    

Now put the expanded expression back into the proper syntactic context.

      
((lambda (v.0)
   ((lambda (v.2)
      (if v.2 v.2 v.0))
    #f))
 3)

    

Finally, unmangle names AFTER alpha-renaming terms bound by lambda expressions.

      
((lambda (a)
   ((lambda (b) (if b b a))
    #f))
 3)

    

We need to do the unmangling to retrieve proper references to global identifiers.

Scribe's Note: This led to a discussion about introducing capturing identifiers. Matthias provided the example of a for loop macro that introduced identifiers continue and break and the class attempted to determine whether it would be feasible to handle such a macro automatically. Matthias kept referencing something he called the "Channel Problem," which presumably refers to the difficulty in determining whether the identifiers introduced by one macro are meant to refer to the capturing performed by another macro (for example, if someone wrote a macro that expanded into uses of continue or break However, I imagine that if we group macros that are meant to work together into a hierarchy of modules, such problems could be statically resolved in a sensible manner.

Local Macros
      
(let ((cons ~~~))
  (let-syntax ((m ==> cons))
    (let ((cons ***)) (m))))

    

Historically, the macro m ends up being bound to the code marked *** when we really would want it to be bound to ~~~

Q ( from Matthias ): Why is Lexical Scope better than Dynamic Scope here?
A: There was much discussion here, with many people (the scribe included) confused and frightened by the fact that Matthias could ask such a question. After rejection of terms like Referential Transparency, and some discussion of how Lexical Scope is inherently less confusing than Dynamic (though I will admit here that once you're dealing with macros, this argument doesn't hold as much water), finally someone (Richard? Peter?) hit the jackpot: you can acheive the Dynamic Scoping behavior on top of the Lexical Scoping behavior by making cons a parameter to the macro. There is no clear way to go in the other direction. So when in doubt, you're almost certainly better off going with the option that maximizes flexibility


Syntactic Closures (Bawden Rees '88)

A Syntactic Closure is a triple holding an S-Exp, a Syntactic Environment, and a Set of names. The macro itself determines what is closed in the environment, and what is open.

This system was abandoned, however, because it could not compile syntax-rules macros into syntactic closures


Macros that Work
Code Environment (pee, rho, whatever)
            
(or #f x)

          
p0 = { or -> <~~, p0>, let -> <**, p0> }
            
(let.1
 ((v.1 #f))
 (if.1 v.1 v.1 x))

          
p1 = { let.1 -> <**,p0>, if.1 -> if, v.1 -> v } ++ p0
            
((lambda.2
   (v.1)
   (if.1 v.1 v.1 x))
 #f)

          
p2 = { lambda.2 -> lambda } ++ p1
            
((lambda (g3)
   (if.1 v.1 v.1 x))
 #f)

          
p3 = { v.1 -> g3 } ++ p2
            
((lambda (g3) (if g3 g3 x))
 #f)

          
DONE

Restricted attention to hygenic pattern-based macros.

Removed the O(n^2) complexity that plagued the original KFFD algorithm

Q ( from Audience/Matthias ): What the hell does O(n^2) mean in this context? Its easy to make the algorithm diverge; how can you measure the complexity of an infinite loop?
A: The answer is that we're measuring complexity in terms of the output size. So, if the algorithm completes, it will take O(n^2) time, where n is the number of tokens in the output s-exp

Scribe's Note: Do output s-exp's tend to be asympotically larger than input ones? Or do parameters tend to be used in a somewhat linear fashion in macros? I know I've used parameters non-linearly in various debugging/trace macros, but otherwise...


Syntactic Abstraction in Scheme (Dybig, and ?)

Note that mark_m is idempotent with respect to m (neighboring occurences are smushed)

Key difference from KFFD: propogation of marsk is done lazily

provides a forging function to introduce capturing identifiers (it passes set of marks from a source identifier to the new one)