From posting-system@google.com Fri Nov 30 20:24:25 2001 Date: Fri, 30 Nov 2001 17:24:21 -0800 Reply-To: oleg@pobox.com From: oleg@pobox.com (oleg@pobox.com) Newsgroups: comp.lang.scheme X-comment: beautified ??!apply, Dec 13, 2001 The implementation of ??!apply is separated out into macro-lambda.scm. Apr 7, 2002. Mention the complete source code syntax-rule-CPS-lambda.scm Mar 30, 2003. Subject: Transparent macro-CPS programming Message-ID: <7eb8ac3e.0111301724.2dbb156@posting.google.com> Status: OR R5RS macro programming is an art. Can we make it more like a craft? Can we just take a regular Scheme code written for an appropriate domain, and (preferably mechanically) transform it into a R5RS macro? That was the goal of an article 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 As the presenter (Erik Hilsdale) concluded, the goal is still elusive. Transforming a CPS code into an R5RS macro is complicated and obscure, because the most obvious transformation does not work:
The natural way to transform these procedures into macros is to assume the existence of two macros that behave like lambda and apply. This syntactic lambda, or (since it is only used to create continuations) syn-cont, might take a formal argument and an expression body, and freeze expansion of the body until the syn-cont is applied, with apply-syn-cont, to an expression. ... Unfortunately, it doesn't work because of hygiene. Consider the macro defined with let-syntax: (syntax-rules () ((f Formal ...) Body)) The R5RS macro system guarantees that the introduced Formal identifiers will not be captured by Body, dashing our hopes for a general syn-cont macro. Even if it had worked, though, the substitution of the argument would naively use the standard macro-template substitution mechanism of the R5RS macro system. This mechanism is unaware of our intended scopes; it substitutes the values for all occurrences of the formals in the body, even if such an occurrence should be shadowed by another syn-cont. Unfortunately, it's worse than that: It would actually substitute a value in place of the formal parameter of a contained syn-cont, if allowed: (apply-syn-cont (syn-cont (X) (context (syn-cont (X) (context X)))) (V W)) would expand into (context (syn-cont ((V W)) (context (V W)))) So it seems we cannot write a macro to express these syntactic continuations.
In this article, we shall show that syntactic 'lambda' and 'apply' are nevertheless possible. With their help, we can almost mechanically transform regular Scheme code into a R5RS macro. We give several examples, one of them from the above paper. The code->macro transformation can only apply to the Scheme code that manipulates lists or vectors (because this is the proper domain of R5RS macros). Some numerical code can be handled as well, but it is too ugly and won't be considered here. The first stage of the transformation is CPS, which is a well-understood and mechanical transformation. The second stage requires, essentially, a way to express and apply syntactic lambda terms. The global-sub macro introduced recently on a related thread turns out of great help. First, we define a representation for a lambda-form. We chose the most obvious one (??!lambda (bound-var) (body 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 (distinguished) symbol, not bound to anything. The 'body' may contain a form (??! bound-var). The lambda-form is just a form. It is interpreted by a syntax ??!apply. To be more precise, (??!apply (??!lambda (bound-var) body) arg) expands to 'body', with all non-shadowed (free) instances of (??! bound-var) replaced by 'arg'. The reason we distinguish free occurrences is that the body of a ??!lambda-expression may in turn contain (??!lambda (var) (body body ...)) forms that bind the same var. [include href="macro-lambda.scm" for the implementation of ??!apply] The following example illustrates nested applications of several nested lambda forms. (??!apply (??!lambda (x) (list (??!apply (??!lambda (x) (list '(??! x) 5 '(??! x))) (1 2)) '(??! x))) (3 4)) ===expands-to===> (list (list '(1 2) 5 '(1 2)) '(3 4)) Because all the occurrences of variables to be substituted must be specially marked, the danger mentioned in the Erik Hilsdale's paper quoted above does not apply in our case. The first example to illustrate our code->macro transformation is taken from Erik Hilsdale's paper. The task is to write a macro that deeply reverses a list. An argument list can have arbitrarily nested sublists, all of them are reversed as well. The paper gives the the corresponding Scheme code, already in the CPS form: (define (reverse*-cps x k) (cond ((not (pair? x)) (k x)) ((pair? (car x)) (reverse*-cps (cdr x) (lambda (new-tail) (reverse*-cps (car x) (lambda (new-head) (anoc-cps new-tail new-head k)))))) (else (reverse*-cps (cdr x) (lambda (new-tail) (anoc-cps new-tail (car x) k)))))) (define (anoc-cps la x k) (k (append la (list x)))) Let us apply our method and convert the code to a macro: (define-syntax sreverse* (syntax-rules () ((_ () k) (??!apply k ())) ((_ ((hdhd . hdtl) . tail) k) (sreverse* tail (??!lambda (new-tail) (sreverse* (hdhd . hdtl) (??!lambda (new-head) (sanon (??! new-tail) (??! new-head) k)))))) ((_ (head . tail) k) (sreverse* tail (??!lambda (new-tail) (sanon (??! new-tail) head k)))))) (define-syntax sanon (syntax-rules () ((_ (l ...) x k) (??!apply k (l ... x))) ((_ () x k) (??!apply k (x))) )) As you see, it's straightforward. (sreverse* (1 (2 3) (4 (5)) 6 7) (??!lambda (x) (begin (display '(??! x)) (newline)))) ===prints===> (7 6 ((5) 4) (3 2) 1) The printing happens at run-time, but the deep reversion is done at macro-expand time. You can ask Bigloo to stop after the macro-expand phase. The output code clearly shows the reversed list, which the display procedure prints. The second example is computing a factorial. Nobody can avoid the factorial. We'll compute factorials with Peano-Church numerals. That is, the empty list, (), will represent numeral 0. A list that contains an empty list will represent numeral 1, etc. For instance, a list ((( () ))) stands for number 3. This representation is reminiscent of Peano integers. From a different point a view, a form ((( ... () ...))) is a repeated application of function 'list' to the empty list. We begin by implementing arithmetic operations for Peano-Church numerals. We will write these procedures in CPS directly. Alternatively, we could've written a 'direct' Scheme code and do the CPS transformation afterwards. (define (plc-zero k) (k '())) (define (plc-succ c k) (k (list c))) (define (plc-pred c k) (k (car c))) (define (plc-zero? c k-on-zero k-on-pos) (cond ((null? c) (k-on-zero c)) (else (k-on-pos c)))) (define (plc-add c1 c2 k) (plc-zero? c1 (lambda (c1) (k c2)) ; if c1 is zero (lambda (c1) (plc-succ c2 (lambda (c2+1) (plc-pred c1 (lambda (c1-1) (plc-add c1-1 c2+1 k)))))))) (define (plc-mul c1 c2 k) (letrec ((loop (lambda (c1 accum k) (plc-zero? c1 (lambda (c1) (k accum)) (lambda (c1) (plc-pred c1 (lambda (c1-1) (plc-add c2 accum (lambda (new-accum) (loop c1-1 new-accum k)))))))))) (plc-zero (lambda (accum) (loop c1 accum k))))) (define (plc-display c) (display "The result is: ") (display c) (newline) (display "In other words: ") (let loop ((c c) (n 0)) (if (null? c) (display n) (loop (car c) (+ 1 n)))) (newline)) (define (plc-fact c k) (plc-zero? c (lambda (c) (plc-succ c k)) (lambda (c) (plc-pred c (lambda (c-1) (plc-fact c-1 (lambda (c-1-fact) (plc-mul c c-1-fact k)))))))) (plc-fact '((((( () ))))) plc-display) ===prints===> The result is: ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) In other words: 120 Now, we convert the above Scheme code to R5RS macros. (define-syntax ?plc-zero (syntax-rules () ((_ k) (??!apply k ())))) (define-syntax ?plc-succ (syntax-rules () ((_ c k) (??!apply k (c))))) (define-syntax ?plc-pred (syntax-rules () ((_ (c) k) (??!apply k c)))) (define-syntax ?plc-zero? (syntax-rules () ((_ () k-on-zero k-on-pos) (??!apply k-on-zero ())) ((_ c k-on-zero k-on-pos) (??!apply k-on-pos c)) )) (define-syntax ?plc-add (syntax-rules () ((_ c1 c2 k) (?plc-zero? c1 (??!lambda (vc1) (??!apply k c2)) (??!lambda (vc1) (?plc-succ c2 (??!lambda (c2+1) (?plc-pred (??! vc1) (??!lambda (c1-1) (?plc-add (??! c1-1) (??! c2+1) k)))))))))) ; Test case (?plc-add (( () )) ((( () ))) (??!lambda (c) (plc-display '(??! c)))) ===prints===> The result is: (((((()))))) In other words: 5 (define-syntax ?plc-mul (syntax-rules () ((_ c1 c2 _k) (letrec-syntax ((?loop (syntax-rules () ((_ c accum k) (?plc-zero? c (??!lambda (vc1) (??!apply k accum)) (??!lambda (vc1) (?plc-pred (??! vc1) (??!lambda (c1-1) (?plc-add c2 accum (??!lambda (new-accum) (?loop (??! c1-1) (??! new-accum) k))))))))))) (?plc-zero (??!lambda (accum) (?loop c1 (??! accum) _k))))))) ; Test case (?plc-mul (( () )) ((( () ))) (??!lambda (c) (plc-display '(??! c)))) ===prints===> The result is: ((((((())))))) In other words: 6 (define-syntax ?plc-fact (syntax-rules () ((_ co k) (?plc-zero? co (??!lambda (c) (?plc-succ (??! c) k)) (??!lambda (c) (?plc-pred (??! c) (??!lambda (c-1) (?plc-fact (??! c-1) (??!lambda (c-1-fact) (?plc-mul (??! c) (??! c-1-fact) k)))))))))) (?plc-fact ((( () ))) (??!lambda (c) (plc-display '(??! c)))) ===prints===> The result is: ((((((())))))) In other words: 6 (?plc-fact (((( () )))) (??!lambda (c) (plc-display '(??! c)))) ===prints, after a notable delay===> The result is: ((((((((((((((((((((((((())))))))))))))))))))))))) In other words: 24 The transformation is remarkably straightforward. The complete source code for this article can be found in the file syntax-rule-CPS-lambda.scm in the current directory.