Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!rice!news
From: matthias@leto.rice.edu (Matthias Felleisen)
Newsgroups: comp.lang.scheme
Subject: Re: macros, understanding of macros
Summary: macros "are as hard as" procedures
Keywords: macros, elimination of macros
Message-ID: <1991Mar9.202550.10979@rice.edu>
Date: 9 Mar 91 20:25:50 GMT
References: <jte12i8to@snitor.uucp>
Sender: Matthias Felleisen
Organization: Rice University, Houston
Lines: 101

CLAIM: Disciplined uses of macros can be reduced to the uses of
procedures. They are therefore as understandable (or even more so) as
uses of procedures as far as their semantics is concerned.

  [** Distilled by many hours of discussions with Bruce Duba, Dan 
  Friedman, Tim Griffin, Todd Jonkers, and Eugene Kohlbecker, and
  by even more hours of teaching the use of macros at Indiana and 
  Rice **]

DEFINITION: Disciplined macros. 
  (1) A disciplined macro is equivalent to a new syntactic 
      (special) form, i.e., its definition changes the syntax of 
      the language. It exists before the beginning of time of 
      all code. It translates syntax into syntax of the base 
      language (the one we thought was unextended). 
  (2) A disciplined macro is used in the following circumstances: 
      * introducing a new binding structure,
	e.g., let, letrec, coroutine when expanded into lambdas; 
      * imposing an evaluation order on expressions that 
	is not guaranteed by  procedure application,
	e.g., cond, case, record-case when expanded into if;
      * implicit quoting by transforming a syntactic token that is 
	apparently used as an identifier into a symbol, 
	e.g., case tag lists when expanded into quote lists. 
      * cosmectis for procedure application or one of the above 
	three cases: add embellishing keywords,
	e.g., like THEN and ELSE to if. 

JUSTIFICATION OF CLAIM: It is easy to show that each use of a macro
can be translated into the use of a procedure, with appropriate
changes to instances of macros. 

   1. Consider the first use: the introduction of new bindings. Replace
   by using lambda explicitly in the macro instance and applying the
   resulting arguments appropriately. 
     Example: (mymacro1 x ex y ey e) 
       is supposed to bind x in ey, y in ex, and x and y in e. 
       Translate it to 
	     (myproc1 (\y.ex) (\x.ey) (\xy.e)). 
       The procedure body depends on the transliteration of mymacro1. 
       If the above instance were to be expanded to
	     (let ((x \y.ex) (y \x.ey)) e)
       then myproc1 would be the function 
	     \px,py,pe. (pe px py).

   2. Consider the second use: the choice of a non-applicative order of
   evaluation of sub-expressions in a macro instance. Replace by using
   thunks for the sub-expressions, and apply when needed. 
     Example: (mymacro2 e1 e2 e3),
       when expanded, evaluates e2, if the result is 0, e1, 
       and otherwise e3. Translate this use to: 
	      (myproc2  \().e1 \().e2 \().e3)
       where myproc2 = \p1,p2,p3.if (zero? (p2)) (p1) (p2). 

   3. Consider the third use: implicit tagging. Tag explictly. I would
   almost claim that this use of macros is superfluous. We shouldn't think 
   of tags at all when we program: it's a confusion of identifiers and 
   symbols, which just happen to be in 1-1 correspondence. 

   4. Cosmetics: skip it. 				QEJ

QUESTION: Why do we use disciplined macros then, if (in Scheme) their
use can be reduced to the use of procedures? 

ANSWER: For syntactic reasons: disciplined macros abstract syntactic
patterns just like procedures abstract action patterns. 

WHY DO WE WANT TO HIDE PATTERNS: basically for psychological reasons,
but they are difficult to formalize. For example, 
	(let (x 1) fifty-lines-of-code)
is just much easier to comprehend than 
	((lambda (x) fifty-lines-of-code) 1).

>> Are there macro systems that let us only write good macros? No. 
A lot more research is needed. 

>> Are there procedural (sub)languages that let us only write good 
procedures? No. Ditto. 

For all the people interested in (disciplined) macros, I recommend the
following two dissertations:

[1] {Kohlbecker, E}.  {\it Syntactic Extensions in the Programming
    Language Lisp}.  Ph.D. dissertation, Indiana University, 1986.

[2] {Griffin, T.G}.  {\it Notational Definition and Top-Down
    Refinement for Interactive Proof Development Systems.} Ph.D.
    dissertation, Cornell University, 1988.

They are not text books on macros, but the former comes pretty close
(even if we know a little bit more now than extend-syntax and
hygiene).

-- Matthias Felleisen

P.S. When I coined the phrase "hygienic macros" in 86, I borrowed the
term from a paper by Barendregt on the lambda calculus who assumed
that readers can "hygienically" rename bound variables when neceesary.
The term specifically refers to the AUTOMATIC ENFORCEMENT OF LEXICAL
SCOPE FOR MACROS, and is inappropriate for characterising other
improvements of macro systems.