From posting-system@google.com Sun Dec 16 16:14:09 2001
Date: Sun, 16 Dec 2001 13:14:02 -0800
From: oleg@pobox.com (oleg@pobox.com)
Newsgroups: comp.lang.functional,comp.lang.scheme
Subject: Re-writing abstractions, or Lambda: the ultimate pattern macro
Message-ID: <7eb8ac3e.0112161314.5b86b826@posting.google.com>
Status: OR

A practical topic of this message is making programming of
pattern-based rewriting systems more intuitive. It is far from trivial
to build complex re-writing rules from simpler ones, in head-first
pattern-based rewriting systems. The familiar idioms of a 'function
call' and a functional composition -- let alone higher-level
combinators such as fold -- do not easily apply.

This article proposes a solution: continuation-passing-style (CPS)
coupled with a macro-lambda. The solution makes it trivial to compose
re-writing rules and to use higher-order rule combinators. We can code
re-writing rules using traditional, well-understood applicative
programming idioms. The solution relies on a first-class denotation
for a future re-writing.

The article will illustrate the proposed technique on several examples
-- from practical to bizarre. The most complex example is a
normal-order evaluator for untyped lambda-calculus, implemented as a
R5RS macro. More practical illustrations are discussed in an earlier
article [1], which aimed to make programming of re-writing systems
(R5RS macros) more like a craft than a witchcraft.

Throughout this message you will see several kinds of lambdas -- a
lambda of lambda calculus, a rewriting-rule lambda, and a lambda of
Scheme. Each is handled by its own evaluator, yet they look
similar. In fact, the former and the latter lambda forms are
identical. In all the cases, the lambda forms play the same role: a
_denotation_ for a parameterized future evaluation. The evaluation
occurs in different ways, yet the idea of delaying an action and
passing its promise as a first-class object is universal.

	* R5RS macros -- head-first pattern-based re-writing system
	* Why coding of head-first pattern-based re-writing systems is
	  so difficult
	* Macro-CPS programming
	* Lambda-calculator as an R5RS macro
	* Related work
	* References


* R5RS macros -- head-first pattern-based re-writing system

We will use R5RS macros as a representative head-first pattern-based
re-writing system. R5RS macros are the "blessed" macro facility of
Scheme, defined in the Revised5 Report on Scheme (R5RS) [2]. They are
also called hi-level, define-syntax or hygienic macros, to distinguish
them from a defmacro facility. The latter system is inherited from
Lisp. A defmacro expander is the Scheme evaluator itself, hence
defmacro is essentially a Scheme code that runs at compile time.

The R5RS macro system is a completely different language. It is a
re-writing system based on pattern-matching. Unlike the Scheme
evaluator, which is call-by-value, a R5RS macro-expander applies
reductions in the normal order, that is, leftmost first. A reduction
step is matching against a set of patterns and replacement of the
matched expression by a template. There is no guarantee that a given
expression has a normal form, nor there is a guarantee that the
macro-expander always finds the normal form when there is one.

One can say that perhaps the R5RS macro system is closer to a Haskell
(typechecker) than to Scheme. Patterns are linear and matching is
based on (deep) equality.  Unfortunately, R5RS patterns cannot have
guards or other constraints. OTH, R5RS patterns have a special '...'
pattern. Furthermore, R5RS macros are hygienic:

"Identifiers that appear in the template but are not pattern variables
or the identifier ... are inserted into the output as literal
identifiers. If a literal identifier is inserted as a free identifier
then it refers to the binding of that identifier within whose scope
the instance of syntax-rules appears. If a literal identifier is
inserted as a bound identifier then it is in effect renamed to prevent
inadvertent captures of free identifiers." [4]. 

In this article, we will call such renaming 'coloring' of an
identifier [3]. R5RS macro system is defined in [4].


* Why coding of head-first pattern-based re-writing systems is so
difficult

Such a fundamental idiom as a 'function call' does not immediately
apply to our re-writing system. Ditto for higher-order combinators
such as fold.

For example, let's consider a function 
    app_rev:: ([a] -> b, [a]) -> b

that takes two arguments and applies the first argument to the reverse
of the list given as the second argument.  In most programming
languages, this function is trivial:

    app_rev (f,lst) = f (reverse lst)

We are confident that by the time f needs the value of its argument,
the reverse of lst will be computed. This computation may be carried
out a bit earlier than that, depending on the evaluator.

Things are not that simple for R5RS macros. The macro that reverses a
list is easy to define:

(define-syntax m-reverse
  (syntax-rules ()
    ((m-reverse lst)		; pattern
     (letrec-syntax
	 ((loop
	   (syntax-rules ()
	     ((loop () accum)		  ; pattern
              accum)			  ;    re-writes into this
	     ((loop (x . rest) accum)	  ; another pattern
	      (loop rest (x . accum)))))) ; template 
       (loop lst ())))))

We rely on an ancillary tail-recursive re-writing rule 'loop' that
moves elements from its first argument to the second, the
accumulator. Pattern (x . tail) in Scheme is identical to (x:tail) in
Haskell.


(m-reverse (1 2 3 4 5)) ; ==expands-to==> (5 4 3 2 1)

We are then tempted to define app_rev as

(define-syntax app_rev
  (syntax-rules ()
    ((app_rev f lst)		; pattern
     (f (m-reverse lst))	; template of the re-written expression
   )))

If we try to expand (app_rev quote (1 2 3 4 5)), we might expect to
see '(5 4 3 2 1). In reality, we get '(m-reverse (1 2 3 4 5)). We
may hope that
    (app_rev m-reverse (1 2 3 4 5))
expands to the original list, (1 2 3 4 5). In reality,
    (app_rev m-reverse (1 2 3 4 5))
is re-written to
    (m-reverse (m-reverse (1 2 3 4 5)))
then to
    ((1 2 3 4 5) m-reverse)
and the latter raises an error because the syntax m-reverse is being
used inappropriately.

We can see the problem: in many programming languages, a function can
force evaluation of an argument expression just by using its value. In
strict languages, argument expressions are always evaluated, at the
time of the call. In a head-first re-writing system, a rule can force
expansion of a subrule only by placing the subrule in the head
position of the re-written expression. In that case however, the outer
rule can't get hold of the subrule's result. A re-writing rule
_cannot_ "invoke" the other rule and have the control return back with
the result.

Head-fist re-writing systems are anti-functional
(anti-applicative). We cannot easily compose more complex rules from
simpler ones. We lose the all-important modularity principle. That's
why writing R5RS macros are so complex. That's why we have to resort
to contortions and hacks even in simple cases (R5RS, Section 7.3).

Enter Ultimate Lambda. It makes R5RS macros functional, it restores
the modularity principle, it makes possible even higher-order
combinators.


* Macro-CPS programming

The magic bullet is a form that denotes a parameterized future
re-writing action:

	      (??!lambda (bound-var) body)
Here 'body' is an expression, bound-var is a variable, and ??!lambda
is just a symbol. Not a macro, not a special syntax -- just a
symbol. The 'body' may contain a form (??! bound-var). The ??!lambda-form
is just a form.  It is interpreted by a re-writing rule ??!apply. To
be more precise,
     (??!apply (??!lambda (bound-var) body) arg)
expands to 'body', with all non-shadowed instances of (??!  bound-var)
replaced by 'arg'.

In Scheme, question and exclamation marks are considered ordinary
characters. Hence ??!lambda, ??!apply and ??! are ordinary symbols --
albeit weirdly looking, on purpose.

The definition of ??!apply is given in [1]. Again, ??!lambda is not a
macro, is not a special syntax -- it is just a regular, unbound
symbol.

The second ingredient to our solution is a continuation-passing style
(CPS). We will require re-writing rules to receive an extra argument,
a continuation. When a rule has computed its expansion, it should
??!apply the received continuation to the result. This convention
confers functional composition and functional invocation. If rule foo
wants to 'invoke' rule bar, it should expand to (bar args
continuation) and encode in the 'continuation' argument whatever
processing needs to be done with the bar's result. The ??!lambda form
makes encoding of such future parameterized processing trivial.

Let us re-write the previous example using the macro-lambda:

(define-syntax ?reverse ; reverse in CPS
  (syntax-rules ()
    ((_ _lst _k)
     (letrec-syntax
	 ((loop
	   (syntax-rules ()
	     ((loop () accum k)		; pattern
	      (??!apply k accum))	; its expansion
	     ((loop (x . rest) accum k) ; the second pattern
	      (loop rest (x . accum) k))))) ; its expansion
       (loop _lst () _k)))))

The leading question mark or underscores have no syntactic
significance. Question mark is a regular "letter" in Scheme; it may
occur in identifiers at any position.

The app_rev function of the previous section can trivially be defined as

(define-syntax ?app_rev
  (syntax-rules ()
    ((_ f lst k)
     (?reverse lst (??!lambda (reversed) (f (??! reversed) k))))))

A form

(?reverse (1 2 3 4 5)
   (??!lambda (result) (display '(??! result))))
==expands-to==> (display '(5 4 3 2 1))

whereas

(?app_rev ?reverse (1 2 3 4 5)
   (??!lambda (result) (display '(??! result))))
==expands-to==> (display '(1 2 3 4 5))

as expected.

Two more elaborate examples are discussed in [1]. One of them was a
compile-time implementation of a factorial over Peano-Church
numerals. No CS paper is complete without working out the
factorial. Here's the factorial macro itself:

(define-syntax ?plc-fact
  (syntax-rules ()
    ((?plc-fact co k)			     ; pattern
     (?plc-zero? co
       (??!lambda (c) (?plc-succ (??! c) k)) ; k on c being zero
       (??!lambda (c)			     ; k on c being non-zero
	  (?plc-pred (??! c)		     ; the predecessor
	     (??!lambda (c-1)
	       (?plc-fact (??! c-1)
		  (??!lambda (c-1-fact)
		     (?plc-mul (??! c) (??! c-1-fact) k))))))))))

The form
(?plc-fact (((( () ))))
	   (??!lambda (c) (plc-display '(??! c))))

printed, after a slight delay,

The result is: ((((((((((((((((((((((((()))))))))))))))))))))))))
In other words: 24

The delay was entirely due to compilation (macro-expansion). Once
compiled, the code printed the answer instantly.

The complete code for the example is given in [1]. This fragment is
quoted here to illustrate modularity: the factorial "function"
relies on previously defined macros for arithmetics (?plc-pred,
?plc-mul) and comparison. Selection forms (such as ?plc-zero?)  take
several continuation arguments, and apply the result to one of them.


* Lambda-calculator as an R5RS macro

In this message, we discuss a more elaborate example: a normal-order
evaluator for lambda calculus. It is a rather challenging example:
capture-free substitutions and the repeated identification of the
left-most redex to reduce are not too trivial. We use the regular
Scheme notation as the input language for our calculator: in
particular,
	 (lambda (x) expr)
the regular Scheme lambda form, shall represent abstraction in our
calculus. The example shows an interesting interplay of compile-time
and run-time lambdas.

First we introduce a few utility re-writing rules:

; cons in CPS
; ?cons A LST K
; passes (A . LST) to K

(define-syntax ?cons
  (syntax-rules ()
    ((_ x y k)
     (??!apply k (x . y)))))

; append in CPS
; ?append LIST1 LIST2 K
; passes (append LIST1 LIST2) to K

(define-syntax ?append 
  (syntax-rules ()
    ((_ () x k)
     (??!apply k x))
    ((_  x () k)
     (??!apply k x))
    ((_ (x ...) (y ...) k)
     (??!apply k (x ... y ...)))))

; map in CPS
; ?map F (X Y ...) K
; passes ((f X) (f Y) ...) to K
; Here F is a CPS (syntax) function F X KX that passes (f x) to KX

; The algorithm:
; map f () => ()
; map f (x . tail) => (f x . map f tail)

(define-syntax ?map
  (syntax-rules ()
    ((_ f () k)
     (??!apply k ()))
    ((_ f (x . rest) k)
     (f x
      (??!lambda (new-x)
	 (?map f rest
	   (??!lambda (new-rest)
	     (?cons (??! new-x) (??! new-rest) k))))))))

Note that ?map is an example of a higher-order combinator for
re-writing rules.

Now we can implement a hygienic (i.e., avoiding capture of free
variables) substitutor.

; ?lc-beta VAR TERM VALUE K
; passes to K the result of a hygienic substitution of VALUE
; for VAR in TERM
; The algorithm is a basic induction on the shape of the TERM
; We have to be careful only in two cases, where the TERM is
;  (lambda (var) body) -- in this case var is rebound and the result is
;			  the term itself
;  (lambda (var1) body) -- a direct substitution into the body
;      may capture var1 if it appears free in VALUE.
;      Therefore, we must first alpha-convert the TERM to replace var1
;      with a unique variable. To be more precise, we replace var1
;      with a var1 of a different color. See [3] for generating
;      colored ids.
; Note that alpha-conversion of body uses ?lc-beta itself!
; The algorithm terminates since body is smaller than the original lambda-term

(define-syntax ?lc-beta
  (syntax-rules ()
    ((_ var oterm oval ok)
     (letrec-syntax
	 ((subs
	   (syntax-rules (lambda var)
	     ((_ var val k)
	      (??!apply k val))
	     ((_ (lambda (var) body) val k) ; var is shadowed; don't rename
	      (??!apply k (lambda (var) body)))
	     ((_ (lambda (var1) body) val k) ; alpha-convert var1 first
	      (let-syntax		; we use lc-beta itself for alpha-conv
		  ((uv
		    (syntax-rules ()
		      ((_ var1- body- val- k-)
		       (?lc-beta var1- body- var1
			  (??!lambda (alpha-converted-body)
			       (subs (??! alpha-converted-body) val-
				  (??!lambda (new-body)
				     (??!apply k-
					(lambda (var1) (??! new-body))))))))
		      )))
		(uv var1 body val k)))
	     ((_ (x . rest) val k)	; beta-reduce an application
	      (subs x val		; reduce the head
		(??!lambda (new-x)
		  (subs rest val	; then reduce the tail
		    (??!lambda (new-rest)	; and re-combine them
	                 (?cons (??! new-x) (??! new-rest) k))))))
	     ((_ var1 val k)		; var1 is distinct from var
	      (??!apply k var1))
	     )))
       (subs oterm oval ok)))))


We should note the modularity of the macro. Curiously, the
beta-substitutor uses itself to perform an alpha-conversion.


Finally, the following re-writing rule is the normal-order lambda-evaluator.
It tries the leftmost outermost reduction first.
We rely on the left-associativity of applications:
If (a b) is not a redex and a is not a pair, we try reducing b
If (a b) is not a redex and a is a pair (x y), we unfold this
as (x y b) and repeat.

(define-syntax ?lc-calc
  (syntax-rules (lambda)
		; The top-level is a lambda-term: reduce inside
    ((_ (lambda (var) body) k)
     (?lc-calc body (??!lambda (new-body)
		(??!apply k (lambda (var) (??! new-body))))))
		; The top-most leftmost is a redex
		; Reduce it and retry from the top
    ((_ ((lambda (var) body) exp . rest) k)
     (?lc-beta var body exp
	       (??!lambda (result)
			  (?lc-calc ((??! result) . rest) k))))
		; The topmost is a nested application
		; Unfold using the associativity rule
    ((_ ((x) . rest) k) (?lc-calc (x . rest) k))
    ((_ ((x y . in-rest) . rest) k)
     (?append (x y . in-rest) rest 
       (??!lambda (result)
	  (?lc-calc (??! result) k))))
		; In topmost (x y z ...), x is not an appl and not an abst
		; It is equivalent to ((x y) z ...)
		; Try to reduce y, z, etc. separately
    ((_ (x y . rest) k)
     (?map ?lc-calc (y . rest)
	   (??!lambda (new-args) 
			  (?cons x (??! new-args) k))))
		; The topmost is (x) -- remove the extra parens
    ((_ (term) k) (?lc-calc term k))
    ((_ var k) (??!apply k var))
    ))

And this is it.

For example,
(?lc-calc
 ((lambda (x) (x x)) (lambda (y) (y z)))
 (??!lambda (result) (display '(??! result)))
)

==expands-to==>
(display '(z z)) 

As a good test of hygiene, we will try expanding
   (lambda (a) ((lambda (x) (lambda (a) (x a))) a))
The result is
    (lambda
        (a~2397)
        (lambda (a~5~2398) (a~2397 a~5~2398)))

Note that the inner-most application involves differently colored 
(i.e., distinct) identifiers. To be sure of that, we take advantage of
the fact that abstractions in our ?lc-calculus look exactly like
regular Scheme lambda-forms. Therefore, we can use the Scheme evaluator
to "run" them.

(?lc-calc
 (lambda (a) ((lambda (x) (lambda (a) (x a))) a))
 (??!lambda (result) (write (((??! result) list) 1)))
)

==expands-to==>
(write (((lambda
           (a~2397)
           (lambda (a~5~2398) (a~2397 a~5~2398)))
         list)
        1))
which, upon evaluation, prints (1). 


Finally, we try some arithmetics. Let's try to compute a*(a+b) for a=2
and b=1:

(?lc-calc 
 (	; term to expand, an application of...
  (lambda (a) (lambda (b)  ; lambda-term for a*(a+b)
     (lambda (f) (a (lambda (x) ((b f) ((a f) x)))))))

  (lambda (f) (lambda (x) (f (f x))))	; Numeral 2, for a
  (lambda (f) (lambda (x) (f x)))	; Numeral 1, for b
  )
 (??!lambda (result) (display '(??! result)))
)

after some 2 minutes of compilation and 40000+ reduction steps expands into

(display
  '(lambda
     (f~7~7107)
     (lambda
       (x~21865~24432)
       (f~7~7107
         (f~7~7107
           (f~7~7107
             (f~7~7107 (f~7~7107 (f~7~7107 x~21865~24432)))))))))

which is the Church numeral for 6. Perhaps this is one of the most
expensive ways to compute 2*3. I'm constantly working on enhancing
the complexity.


* Related work

Using CPS for writing R5RS macros is not a new idea. In fact, that was
the impetus for an article "Writing macros in continuation-passing
style" by Erik Hilsdale and Daniel P. Friedman [5]. The article has
noted that "The natural way to transform these [CPS] procedures into
macros is to assume the existence of two macros that behave like
lambda and apply. ... Unfortunately, it doesn't work because of
hygiene " and a few other reasons. The article concluded, "So it seems
we cannot write a macro to express these syntactic continuations." The
article chose a different way, which turns normally anonymous
continuation abstractions into regular, named macros. 

We have shown however that anonymous re-writing abstractions are
possible. The key observation is that we do not assume the existence
of a macro that behaves like 'lambda'. In our formulation, re-writing
abstraction is just an expression rather than a macro.

To make comparison of the two approaches clearer, the present and the
previous [1] articles have implemented examples from Erik Hilsdale's
paper. In particular, Erik Hilsdale's paper also discusses a
lambda-evaluator. The code in the paper occupies most of the
two-column page. In contrast, our evaluator is only 60 lines long; it
appears easier to write and to comprehend.

Erik Hilsdale's article admitted that their style is "akin to
programming in an assembly language for macros, where we have given up
not only all but one control structure (pattern selection) but also
lexical closures". In this article, we have regained what have been
lost.


* References

[1] "Transparent macro-CPS programming"
    http://pobox.com/~oleg/ftp/Scheme/syntax-rule-CPS-lambda.txt
The earlier article posted on comp.lang.scheme on Fri, 30 Nov 2001
17:24:21 -0800

[2] R. Kelsey, W. Clinger, J. Rees (eds.), Revised5 Report on
the Algorithmic Language Scheme, J. Higher-Order and
Symbolic Computation, Vol. 11, No. 1, September, 1998
	http://www.schemers.org/Documents/Standards/R5RS/

[3] Coloring of identifiers. It was revealing to meditate on the following:

(define-syntax tid-3
  (syntax-rules ()
    ((_ x)
     (let-syntax
       ((foo
	 (syntax-rules ()
	   ((_ y) (lambda (x) y)))))
       (foo x)))))

(tid-3 a) ; ==expands-to==> (lambda (a~2~3) a)

whereas

(define-syntax tid-31
  (syntax-rules ()
    ((_ x)
     (let-syntax
       ((foo
	 (syntax-rules ()
	   ((_ x y) (lambda (x) y)))))
       (foo x x)))))

(tid-31 a) ; ==expands-to==>  (lambda (a~3) a~3)

Here a~3 and a~2~3 denote identifier 'a' colored in different
hues. Differently-colored symbols are distinct when used as variables
in code.

[4] R5RS, Section 4.3.2  Pattern language 
http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.3

[5] Erik Hilsdale and Daniel P. Friedman. "Writing macros in
continuation-passing style". Scheme and Functional Programming 2000.
September 2000.
	http://www.ccs.neu.edu/home/matthias/Scheme2000/hilsdale.ps


