Implementing letrec-syntax using only let-syntax and syntax-rules

212 views
Skip to first unread message

Al Petrofsky

unread,
May 15, 2001, 3:34:15 AM5/15/01
to
In February, there was a discussion of how to implement letrec without
using set!. About the closest you can get is something like this:

(define-syntax letrec
(syntax-rules (lambda)
((letrec ((var init) ...) . body)
(let ((dispatch
(lambda (dispatch which . args)
(let ((var (lambda args (apply dispatch dispatch 'var args)))
...)
(if which
(apply (case which ((var) init) ...) args)
(let () . body))))))
(dispatch dispatch #f)))))

This usually works if all the init expressions are lambdas and there
are no assignments to the variables. It can break if there are
comparisons of the procedure values, e.g.:

(letrec ((foo (lambda (x) (eq? x foo))))
(foo foo))

will evaluate to #f, but it should be #t.


Yesterday I started thinking about implementing letrec-syntax using
only the other required special forms. There is no set!-syntax, but
it seemed we might be able to do better than the set!-less letrec
because (1) all the initializers are guaranteed to be transformers
(the syntactic equivalent of lambda expressions), and (2) we don't
need to worry about there being assignments to the keywords, because
there is no set!-syntax.

Here's what I came up with:

(define-syntax letrec-syntax
(syntax-rules (with-names bind-names)
((_ ((name transformer) ...) . body)
(letrec-syntax with-names (name ...) ((name transformer) ...) . body))
((_ with-names names ((name transformer) ...) . body)
(let-syntax
((select
(syntax-rules names
((_ select name . args)
(letrec-syntax bind-names names select
(let-syntax ((x transformer)) (x . args))))
...)))
(letrec-syntax bind-names names select . body)))
((_ bind-names (name ...) select . body)
(let-syntax
((name (syntax-rules ()
((_ . args) (select select name . args))))
...)
. body))))

This works, so long as the transformers don't use any ellipses. If
your syntax-rules implementation supports the ellipsis quotation
convention, i.e. (... <template>) causes ellipsis to lose its special
meaning within <template>, then change

(let-syntax ((x transformer)) (x . args))

to

(let-syntax ((x ((... ...) transformer))) (x . args))

and the macro will work with any transformers.

The above solution is a bit of a cheat because it contains free
references to itself, making use of the letrec-like nature of
top-level definitions. Here is a self-contained version:

(define-syntax letrec-syntax
(syntax-rules ()
((_ ((name transformer) ...) . the-body)
(let-syntax
((reverse-let*-syntax-rules
(syntax-rules ()
((_ reverse-let*-syntax-rules () . body)
(let-syntax () . body))
((_ reverse-let*-syntax-rules ((keyword . x) . bindings) . body)
(reverse-let*-syntax-rules reverse-let*-syntax-rules bindings
(let-syntax ((keyword (syntax-rules . x))) . body))))))
(reverse-let*-syntax-rules reverse-let*-syntax-rules
((bind-and-select ()
((_ bind-and-select which . args)
(bind-names (name ...) bind-and-select
(select which (transformer ...) . args))))
(bind-names ()
((_ (name ...) bind-and-select . body)
(let-syntax
((name (syntax-rules ()
((_ . args)
(bind-and-select bind-and-select name . args))))
...)
. body)))
(select (name)
((_ name (transformer1 . transformers) . args)
(let-syntax ((x transformer1)) (x . args)))
((_ other (transformer1 . transformers) . args)
(select other transformers . args)))
...)
(bind-names (name ...) bind-and-select . the-body))))))

Again, substitute ((... ...) transformer) for transformer if possible.

Unfortunately, these macros suffer the same equivalence pitfall as the
set!-less letrec macro did, and they will cause the following
expression to evaluate to #f instead of #t:

(letrec-syntax ((foo (syntax-rules (foo) ((_ foo) #t) ((_ x) #f))))
(foo foo))

Rats.

-al


P.S. Has anyone else noticed that there's a bug in the r5rs sample
implementation of letrec? It expands into an error if there are
internal definitions in the body of the letrec.

P.P.S. Here are single-expansion macros for letrec and do:

(define-syntax letrec
(syntax-rules ()
((_ ((var init) ...) . body)
(let ((var 'undefined) ...)
(let ((var (let ((temp init)) (lambda () (set! var temp)))) ...
(bod (lambda () . body)))
(var) ... (bod))))))

(define-syntax do
(syntax-rules ()
((_ ((var init . step) ...) (test expr ...) command ...)
(let loop ((var init) ...)
(cond (test expr ...)
(else command ... (loop (begin var . step) ...)))))))

ol...@pobox.com

unread,
May 18, 2001, 8:38:12 PM5/18/01
to
Al Petrofsky <Alymph...@Petrofsky.Berkeley.CA.US> wrote in message news:<87eltrc...@app.dial.idiom.com>...

> P.S. Has anyone else noticed that there's a bug in the r5rs sample
> implementation of letrec? It expands into an error if there are
> internal definitions in the body of the letrec.
>
> P.P.S. Here are single-expansion macros for letrec and do:
>
> (define-syntax letrec
> (syntax-rules ()
> ((_ ((var init) ...) . body)
> (let ((var 'undefined) ...)
> (let ((var (let ((temp init)) (lambda () (set! var temp)))) ...
> (bod (lambda () . body)))
> (var) ... (bod))))))
>

It appears there may be a simpler way of fixing the problem. I wonder
what is wrong with the following:

(define-syntax letrec^


(syntax-rules ()
((_ ((var init) ...) . body)
(let ((var 'undefined) ...)

(set! var init) ...
(let () . body)))))


Bigloo doesn't seem to have any problem with it. For example, the
following fragment

(display
(letrec^ ((myodd? (lambda (n) (and (not (zero? n)) (myeven? (- n 1)))))
(myeven? (lambda (n) (or (zero? n) (myodd? (- n 1)))))
(n 5))
(list (myodd? n) (myeven? n)))
)

prints the expected answer (#t #f)

Bigloo can be asked to show the expansion of all macros. Here it is:


(display
((lambda (myodd?~3 myeven?~3 n~3)
(begin
(set! myodd?~3
(lambda (n~4)
(if (not (zero? n~4)) (myeven?~3 (- n~4 1)) #f)))
(set! myeven?~3
(lambda (n~7)
((lambda (temp~8~10)
(if temp~8~10 temp~8~10 (myodd?~3 (- n~7 1))))
(zero? n~7))))
(set! n~3 5)
((lambda () (list (myodd?~3 n~3) (myeven?~3 n~3))))))
'undefined
'undefined
'undefined))

Looks rather reasonable.

Let's test defines in the body of letrec. First we check a 'define' in
the body of let:

(display
(let ((n 5))
(define n 7)
n))
==prints==> 7

An internal define in the body of letrec^ works as well:

(display
(letrec^ ((myodd? (lambda (n) (and (not (zero? n)) (myeven? (- n 1)))))
(myeven? (lambda (n) (or (zero? n) (myodd? (- n 1)))))
(n 5))
(define n 120)
(list (myodd? n) (myeven? n)))
)

==prints==> (#f #t)

Erik Hilsdale's test passes as well:

(display
(letrec^
((even? (list (lambda (n) (if (zero? n) #t ((car odd?) (- n 1))))))
(odd? (list (lambda (n) (if (zero? n) #f ((car even?) (- n 1))))))
(num 42))
((car even?) num)))

==prints==> #t
as expected


Finally, the letrec impurity test gives the right answer (letrec is
Scheme is impure as mandated by R5RS)

(display
(letrec^
((fact
(cons #f
(lambda (n)
(set-car! fact #t)
(if (zero? n) 1
(* n ((cdr fact) (- n 1))))))))
(let* ((before (car fact))
(res ((cdr fact) 5)))
(list before res (car fact)))))

==prints==> (#f 120 #t)
as expected.

Alexandretta Petrofsky

unread,
May 19, 2001, 12:56:28 AM5/19/01
to
ol...@pobox.com (ol...@pobox.com) writes:
> Al Petrofsky <Alymph...@Petrofsky.Berkeley.CA.US> wrote in message news:<87eltrc...@app.dial.idiom.com>...
>
> > P.S. Has anyone else noticed that there's a bug in the r5rs sample
> > implementation of letrec? It expands into an error if there are
> > internal definitions in the body of the letrec.
> >
> > P.P.S. Here are single-expansion macros for letrec and do:
> >
> > (define-syntax letrec
> > (syntax-rules ()
> > ((_ ((var init) ...) . body)
> > (let ((var 'undefined) ...)
> > (let ((var (let ((temp init)) (lambda () (set! var temp)))) ...
> > (bod (lambda () . body)))
> > (var) ... (bod))))))
> >
>
> It appears there may be a simpler way of fixing the problem.

The simplest way of fixing the r5rs version is to change body ... to
(let () body ...) in the terminal template. I provided my totally
rewritten version because I thought people might be interested to see
that it could be done in one rule (and, therefore, that laboriously
generating O(n) hygienic identifiers is unnecessary).

> I wonder what is wrong with the following:
>
> (define-syntax letrec^
> (syntax-rules ()
> ((_ ((var init) ...) . body)
> (let ((var 'undefined) ...)
> (set! var init) ...
> (let () . body)))))

I'm so glad you asked! You missed my favorite gotcha in letrec. The
spec says:

The <variable>s are bound to fresh locations holding undefined
values, the <init>s are evaluated in the resulting environment (in
some unspecified order), each <variable> is assigned to the result
of the corresponding <init>, the <body> is evaluated in the
resulting environment, and the value(s) of the last expression in
<body> is(are) returned.

Notice that all the inits should be evaluated before any of the
assignments are performed. This guarantees that:

(let ((cont #f))
(letrec ((x (call-with-current-continuation (lambda (c) (set! cont c) 0)))
(y (call-with-current-continuation (lambda (c) (set! cont c) 0))))
(if cont
(let ((c cont))
(set! cont #f)
(set! x 1)
(set! y 1)
(c 0))
(+ x y))))
=> 0

With your version, it evaluates to 1.

-al


P.S. Here's a much simpler let-values implementation than the one in
SRFI-11:

(define-syntax let-values
(syntax-rules ()
((let-values () . body)
(let () . body))
((let-values ((vars mv) . mvbindings) . body)
((let-values mvbindings
(let ((body-func (lambda vars . body)))
(lambda (thunk)
(call-with-values thunk body-func))))
(lambda () mv)))))

The SRFI-11 version always evaluates the initializer expressions in
order. The version above always evaluates them in reverse order.
Both are compliant with the spec, which allows any order. If you want
the order of evaluation of the initializers to be able to vary
arbitrarily at the whim of the underlying system, then use the
following version (which is probably less efficient):

(define-syntax let-values
(syntax-rules ()
((let-values (((var) mv) ...) . body)
(let ((var mv) ...) . body))
((let-values (((var) mv) mvbinding ...) . body)
(let-values (mvbinding ... ((var) mv)) . body))
((let-values ((vars mv) mvbinding ...) . body)
(let-values
(mvbinding ... ((temp) (call-with-values (lambda () mv) list)))
(apply (lambda vars . body) temp)))))

Alcoa Petrofsky

unread,
May 19, 2001, 2:02:43 AM5/19/01
to

One of my many identical cousins, Alexandretta Petrofsky

<Alexan...@Petrofsky.Berkeley.CA.US> wrote:
>
> P.S. Here's a much simpler let-values implementation than the one in
> SRFI-11:
>
> (define-syntax let-values
> (syntax-rules ()
> ((let-values () . body)
> (let () . body))
> ((let-values ((vars mv) . mvbindings) . body)
> ((let-values mvbindings
> (let ((body-func (lambda vars . body)))
> (lambda (thunk)
> (call-with-values thunk body-func))))
> (lambda () mv)))))

Oops, I accidentally posted the version from that period when I had
given up reliance on hygienic renaming for Lent. That period ensued
shortly after someone (Olin Shivers, maybe? I'm afraid I can't
remember) pointed out that with the appropriate scope choices, renamed
identifiers aren't really needed nearly as often as you might think.
(At least, not for hygiene. Renamings for achieving referential
transparency are another matter.)

Putting such asceticism aside, here's an even simpler version (which
relies on the hygienic renaming of "thunk"):

(define-syntax let-values
(syntax-rules ()
((let-values () . body)
(let () . body))
((let-values ((vars mv) . mvbindings) . body)
((let-values mvbindings

(lambda (thunk)
(call-with-values thunk (lambda vars . body))))
(lambda () mv)))))


Also, I forgot to plug my favorite obscure syntax concept: named
let-values. The following implementation supports named and unnamed
let-values uses:

(define-syntax let-values
(syntax-rules ()
((let-values (mvbinding ...) . body)
(let-values foo (mvbinding ...) . body))
((let-values name () . body)
(let name () . body))
((let-values name ((vars mv) . mvbindings) . body)
((let-values name mvbindings
(lambda (thunk)
(call-with-values thunk
(lambda vars
(let-syntax
((name (syntax-rules ()
((name arg . args)
((name . args) (lambda () arg))))))
. body)))))
(lambda () mv)))))


Here are a couple example uses of named let-values:

(let ((radix 10) (num 123))

(define (divide m n)
;; imagine a bignum division algorithm that generates quotient and
;; remainder simultaneously
(values (quotient m n) (remainder m n)))

;; convert num to list of digits. Note that 0 is handled correctly.
(let-values collect-digits (((digits) '())
((quot rem) (divide num radix)))
(if (zero? quot)
(cons rem digits)
(collect-digits (cons rem digits) (divide quot radix)))))

=> (1 2 3)


(let ((elisp-env '((a . 1) (b . 5) (c . a) (d . 3)))
(var-name 'c))

;; first return val indicates success or failure, second is value found.
(define (lookup key alist)
(cond ((null? alist) (values #f #f))
((eq? key (caar alist)) (values #t (cdar alist)))
(else (lookup key (cdr alist)))))

;; look up var-name in elisp-env, obeying symbol redirections.
(let-values find-it (((found val) (lookup var-name elisp-env)))
(cond ((not found) (error "not in elisp-env"))
((symbol? val) (find-it (lookup val elisp-env)))
(else val))))
=> 1


-al

ol...@pobox.com

unread,
May 20, 2001, 4:18:47 PM5/20/01
to
Alexandretta Petrofsky <Alexan...@Petrofsky.Berkeley.CA.US> wrote in message news:<87bsoq0...@app.dial.idiom.com>...

Hmm, SCM indeed evaluates the above expression to 0. However, Gambit, MIT Scheme
and Bigloo all evaluate it to 1. Furthermore, if I ask Bigloo to print the code
of the above expression after all syntax forms are expanded, I get

((lambda (cont~2)
((lambda (x~5 y~5)
(begin
(set! x~5
(call-with-current-continuation
(lambda (c~6) (begin (set! cont~2 c~6) 0))))
(set! y~5
(call-with-current-continuation
(lambda (c~7) (begin (set! cont~2 c~7) 0))))
(if cont~2
((lambda (c~9)
(begin
(set! cont~2 #f)
(set! x~5 1)
(set! y~5 1)
(c~9 0)))
cont~2)
(+ x~5 y~5))))
'*
'*))
#f)

It appears Bigloo implements exactly the same algorithm as the letrec^ macro
in the original article. The Gambit evaluator (procedure ##cprc-letrec,
line 2073 of gambc30/lib/_eval.scm) does the same thing.

Altazimuth Petrofsky

unread,
May 20, 2001, 7:07:33 PM5/20/01
to
ol...@pobox.com (ol...@pobox.com) writes:
> Alexandretta Petrofsky <Alexan...@Petrofsky.Berkeley.CA.US> wrote in message news:<87bsoq0...@app.dial.idiom.com>...
> > The spec says:
> >
> > The <variable>s are bound to fresh locations holding undefined
> > values, the <init>s are evaluated in the resulting environment (in
> > some unspecified order), each <variable> is assigned to the result
> > of the corresponding <init>, the <body> is evaluated in the
> > resulting environment, and the value(s) of the last expression in
> > <body> is(are) returned.
> >
> > Notice that all the inits should be evaluated before any of the
> > assignments are performed. This guarantees that:
> >
> > (let ((cont #f))
> > (letrec ((x (call-with-current-continuation (lambda (c) (set! cont c) 0)))
> > (y (call-with-current-continuation (lambda (c) (set! cont c) 0))))
> > (if cont
> > (let ((c cont))
> > (set! cont #f)
> > (set! x 1)
> > (set! y 1)
> > (c 0))
> > (+ x y))))
> > => 0

> Hmm, SCM indeed evaluates the above expression to 0. However,


> Gambit, MIT Scheme and Bigloo all evaluate it to 1.

Rscheme also returns 1.

It seems clear to me, to the extent that anything regarding multiply
used continuations can seem clear, that the above expression is legal
in r5rs and that it must return 0.

I think this is a case of implementors missing one of the amazingly
pervasive implications of call/cc.

I think the rnrs authors also may have missed this. Although the
macro given in r5rs 7.3 is correct, it says "a trick is used to
generate the temporary names needed to avoid specifying the order in
which the values are evaluated". That implies that Oleg's simple
definition would be correct. It also misses the fact that you can get
unspecified evaluation order by simply doing:

(define-syntax letrec
(syntax-rules ()
((_ ((var val) ...) . body)
(let ((var 'undefined) ...)
((lambda x 'ignore) (set! var val) ...)
(let () . body)))))

...although that fails the call/cc test. In case you missed it from a
couple posts back, here is how to get correct call/cc interaction, as
well as unspecified evaluation order, without having to generate O(n)
temp names:

(define-syntax letrec


(syntax-rules ()
((_ ((var init) ...) . body)
(let ((var 'undefined) ...)

(let ((var (let ((temp init)) (lambda () (set! var temp))))
...
(bod (lambda () . body)))
(var) ... (bod))))))


Here's a more fun and mysterious test of letrec:

(letrec ((x (call/cc list)) (y (call/cc list)))
(cond ((procedure? x) (x (pair? y)))
((procedure? y) (y (pair? x))))
(let ((x (car x)) (y (car y)))
(and (call/cc x) (call/cc y) (call/cc x))))

This returns #t if letrec does all initializer evaluations before the
assignments, and #f if the evaluations and assignments are
interleaved. I consider this expression to be further evidence
supporting Dan Friedman's argument for including call/cc rather than
let/cc in the standard: it allows for more elegant braintwisters.

-al


P.S. As further evidence of what fools call/cc makes of us all,
consider that in the postscript of the very same article in which I
described this letrec problem, I unknowingly provided a let-values
implementation that suffers from an equivalent bug (I was thinking
only of the macrological connections between the two topics). The
following expression fails to evaluate to #t using the let-values I
posted:

(let ((cont #f))
(let-values (((x) (call/cc (lambda (c) (set! cont c) #t)))
((y) (call/cc (lambda (c) (set! cont c) #t))))
(cond ((procedure? x) (x y))
((procedure? y) (y x))
(else (set! x #f) (set! y #f) (call/cc cont)))))

For a correct, compact definition of let-values, use this:

(define-syntax let-values
(syntax-rules ()
((_ (((var) mv) ...) . body)
(let ((var mv) ...) . body))
((_ (((var) mv) mvbinding ...) . body)


(let-values (mvbinding ... ((var) mv)) . body))

((_ ((vars mv) mvbinding ...) . body)


(let-values
(mvbinding ... ((temp) (call-with-values (lambda () mv) list)))
(apply (lambda vars . body) temp)))))

For a possibly more efficient implementation that avoids creating
lists, use the one in SRFI-11.

ol...@pobox.com

unread,
May 21, 2001, 1:30:33 PM5/21/01
to
Alexandretta Petrofsky <Alexan...@Petrofsky.Berkeley.CA.US> wrote in message news:<87bsoq0...@app.dial.idiom.com>...
> The spec says:
>
> The <variable>s are bound to fresh locations holding undefined
> values, the <init>s are evaluated in the resulting environment (in
> some unspecified order), each <variable> is assigned to the result
> of the corresponding <init>, the <body> is evaluated in the
> resulting environment, and the value(s) of the last expression in
> <body> is(are) returned.
>
> Notice that all the inits should be evaluated before any of the
> assignments are performed. This guarantees that:
>
> (let ((cont #f))
> (letrec ((x (call-with-current-continuation (lambda (c) (set! cont c) 0)))
> (y (call-with-current-continuation (lambda (c) (set! cont c) 0))))
> (if cont
> (let ((c cont))
> (set! cont #f)
> (set! x 1)
> (set! y 1)
> (c 0))
> (+ x y))))
> => 0

Here's the definition of letrec that behaves correctly with respect to the above
test, permits defines in the letrec body, is much simpler than the
R5RS definition, permits an arbitrary order of evaluating the init expressions,
and avoids creation of many closures and O(n) temporary names:

(define-syntax letrec^^


(syntax-rules ()
((_ ((var init) ...) . body)
(let ((var 'undefined) ...)

(let ((temp (list init ...)))
(begin (set! var (car temp)) (set! temp (cdr temp))) ...
(let () . body))))))

Initialization expressions are indeed evaluated before any of the assignments
are performed.
(letrec^^ ((x (call-with-current-continuation (lambda (c) (set! cont c) 0)))


(y (call-with-current-continuation (lambda (c) (set! cont c) 0))))
(if cont
(let ((c cont))
(set! cont #f)
(set! x 1)
(set! y 1)
(c 0))
(+ x y)))

==> 0 as expected.

All other letrec tests (given in the previous messages) pass as well.

An example:

(display
(letrec^ ((myodd? (lambda (n) (and (not (zero? n)) (myeven? (- n 1)))))
(myeven? (lambda (n) (or (zero? n) (myodd? (- n 1)))))
(n 5))
(list (myodd? n) (myeven? n)))
)

expands into

(display
((lambda (myodd?~3 myeven?~3 n~3)

((lambda (temp~1~5)
(begin
(set! myodd?~3 (car temp~1~5))
(set! temp~1~5 (cdr temp~1~5))
(begin
(set! myeven?~3 (car temp~1~5))
(set! temp~1~5 (cdr temp~1~5)))
(begin
(set! n~3 (car temp~1~5))
(set! temp~1~5 (cdr temp~1~5)))


((lambda () (list (myodd?~3 n~3) (myeven?~3 n~3))))))

(list (lambda (n~8)
(if (not (zero? n~8)) (myeven?~3 (- n~8 1)) #f))
(lambda (n~11)
((lambda (temp~12~14)
(if temp~12~14 temp~12~14 (myodd?~3 (- n~11 1))))
(zero? n~11)))
5)))
'undefined
'undefined
'undefined))

Indeed, all initialization is done before the assignments.

Originally I wanted to do

? (define-syntax letrec^^
? (syntax-rules ()
? ((_ ((var init) ...) . body)
? (let ((var 'undefined) ...)
? (let ((temp init) ...)
? (set! var temp) ...
? (let () . body))))))

but that didn't work out. Hygien does not extend that far.

BTW, an example with an initializer returning twice is similar to an
argument expression returning twice.

(let ((cont #f))
(let ((foo (lambda (x y)


(if cont
(let ((c cont))
(set! cont #f)
(set! x 1)
(set! y 1)
(c 0))

(+ x y)))))
(foo (call-with-current-continuation (lambda (c) (set! cont c) 0))
(call-with-current-continuation (lambda (c) (set! cont c) 0)))))

although this piece of code is very similar to the letrec example above,
Gambit, SCM, Bigloo and MIT Scheme all evaluate it to 0, as expected.

Alloweenhay Petrofsky

unread,
May 21, 2001, 5:50:36 PM5/21/01
to
ol...@pobox.com (ol...@pobox.com) writes:

> Here's the definition of letrec that behaves correctly with respect
> to the above test, permits defines in the letrec body, is much
> simpler than the R5RS definition, permits an arbitrary order of
> evaluating the init expressions, and avoids creation of many
> closures and O(n) temporary names:
>
> (define-syntax letrec^^
> (syntax-rules ()
> ((_ ((var init) ...) . body)
> (let ((var 'undefined) ...)
> (let ((temp (list init ...)))
> (begin (set! var (car temp)) (set! temp (cdr temp))) ...
> (let () . body))))))

And here's one that does all that and avoids using twice as many as
necessary of those dreaded set! forms. Now how much would you pay?

(define-syntax letrec


(syntax-rules ()
((_ ((var init) ...) . body)
(let ((var 'undefined) ...)

((lambda inits
(let* ((inits (begin (set! var (car inits)) (cdr inits))) ...)
. body))
init ...)))))

Actually, I lied. This does create O(n) closures, but at least they
are all in the operator position.

Of course, letrec should really be implemented as a primitive so that
it can exploit and/or enforce the prohibition against using the
variables before the body is first entered. More precisely, internal
definitions should be implemented as a primitive (and must be, in
order for macro uses to be able to expand into them), and letrec
should use internal definitions to do all the work:

(define-syntax letrec


(syntax-rules ()
((_ ((var init) ...) . body)

(let ()
(define var init)


...
(let () . body)))))

-al

ol...@pobox.com

unread,
May 21, 2001, 10:26:43 PM5/21/01
to
Alloweenhay Petrofsky <Allow...@Petrofsky.Berkeley.CA.US> wrote in message news:<87ae468...@app.dial.idiom.com>...

> Of course, letrec should really be implemented as a primitive so that
> it can exploit and/or enforce the prohibition against using the
> variables before the body is first entered. More precisely, internal
> definitions should be implemented as a primitive (and must be, in
> order for macro uses to be able to expand into them), and letrec
> should use internal definitions to do all the work:

It may also be useful to introduce a form set-multiple!
(set-multiple! var init) ==the-same-as==> (set! var init)
for backwards compatibility.
(set-multiple! (var) init) see above
Finally
(set-multiple! (var1 var2 ...) init1 init2 ...)
evaluates init1 init2 ... in an unspecified order and assigns the results
to var1 var2...

(set! var init) relates to (let ((var init)) ...) as
(set-multiple! (var1 var2 ...) init1 init2 ...) relates to
(let ((var1 init1) (var2 init2) ...) ...)

set-multiple! can be useful in situations like
(let ((fibn-1 1) (fibn 1))
...
(set-multiple! (fibn-1 fibn) fibn (+ fibn fibn-1)))

(define-syntax set-multiple!
(syntax-rules ()
((_ (var) init)
(set! var init))
((_ var init)
(set! var init))
((_ (var ...) init ...)


((lambda inits
(let* ((inits (begin (set! var (car inits)) (cdr inits))) ...)

(if #f #f)))
init ...))))

The implicit building and deconstruction of an argument list in the
last clause is neat indeed.

(display
(let ((a #f) (b #f))
(set-multiple! a 4)
(set-multiple! (b) 5)
(set-multiple! (a b) (+ a b) (- a b))
(list a b)))
==prints==> (9 -1)


With set-multiple!, implementing letrec is straightforward.

I personally try to avoid mutations. Therefore, I found let-values*
more helpful. let-values* is defined as
(let-values* ((var init)) ...) ==the-same-as==> (let* ((var init)) ...)
(let-values* (((var) init)) ...) see above
Finally
(let-values* (((var1 var2 ...) init)) ...)
expects that init returns as many values as variables in the (var1
var2 ...) list. Intentionally let-values* is backwards compatible
with let*: you can replace all let* with let-values* without affecting
the code, and without incurring a run-time penalty (for the compiled
code).

let-values, named let-values and let-values* deserve the status of
fundamental primitives -- because often they can be implemented more
efficiently. Whereas (call-with-values producer consumer) does not
know how many values the consumer takes, the let-values forms know the
arity of the init expression's continuation at compile-time.

Here's an example of let-values* usage (excerpted from SSAX.scm):

(let-values*
(((elem-gi attributes namespaces expected-content)
(SSAX:complete-start-tag start-tag-head port elems
entities namespaces))
(seed
(my-new-level-seed elem-gi attributes
namespaces expected-content parent-seed)))
(case expected-content
...))

The definition of let-values* is trivial:

(define-macro (let-values* bindings . body)
(if (null? bindings) (cons 'begin body)
(apply (lambda (vars initializer)
(let ((cont ; "continuation" for the expansion
(cons 'let-values*
(cons (cdr bindings) body))))
(cond
((not (pair? vars)) ; regular let case, a single var
`(let ((,vars ,initializer)) ,cont))
((null? (cdr vars)) ; single var, see the prev case
`(let ((,(car vars) ,initializer)) ,cont))
(else ; the most generic case
`(call-with-values (lambda () ,initializer)
(lambda ,vars ,cont))))))
(car bindings))))

I'm afraid I'm biased towards low-level macros. Low- and high-level
macros are incomparable. There are certain things that are possible
only with low-level macros, for example:

; Concise and efficient definition of a function that takes one or two
; optional arguments, e.g.,
;
; (define-opt (foo arg1 arg2 (optional (arg3 init3) (arg4 init4))) body)
;
; define-opt is identical to a regular define, with one exception: the
; last argument may have a form
; (optional (binding init) ... )

(cond-expand
((or bigloo gambit)

; For Gambit and Bigloo, which support DSSSL extended lambdas,
; define-opt like the one in the example above is re-written into
; (define-opt (foo arg1 arg2 #!optional (arg3 init3) (arg4 init4)) body)
(define-macro (define-opt bindings body . body-rest)
(let* ((rev-bindings (reverse bindings))
(opt-bindings
(and (pair? rev-bindings) (pair? (car rev-bindings))
(eq? 'optional (caar rev-bindings))
(cdar rev-bindings))))
(if opt-bindings
`(define ,(append (reverse
(cons (with-input-from-string "#!optional" read)
(cdr rev-bindings)))
opt-bindings)
,body ,@body-rest)
`(define ,bindings ,body ,@body-rest))))
)
(else
; For Scheme systems without DSSSL extensions, we rewrite the definition
; of foo of the example above into the following:
; (define (foo arg1 arg2 . rest)
; (let* ((arg3 (if (null? rest) init3 (car rest)))
; (arg4 (if (or (null? rest) (null? (cdr rest))) init4
; (cadr rest)))
; body))
; We won't handle more than two optional arguments
see http://pobox.com/~oleg/ftp/Scheme/input-parse.scm for implementation
))

Performing with-input-from-string at macro-expand time seems
excessive. However, there is no other way. I cannot introduce
#!optional explicitly. SCM reader will reject such a lexical token at
read-time -- even if the token occurs in a cond-expand branch that
will _not_ be expanded on SCM. High-level macros lack such facilities
for manufacturing tokens and symbols. Otherwise the hygiene is not
enforceable. OTH, high-level macros are not reducible to low-level
macros. As has been discussed in a recent thread, an expansion of a
high-level macro may depend on the fact if a particular variable is
bound in the macro-expansion context. A low-level macro cannot emulate
this feat as R5RS offers no procedures to check if a variable is bound
or free.

Low-level macros expand regardless of their lexical context -- that's
their biggest drawback (e.g, lack of hygiene) as well as the
advantage. High-level macros on the other hand can be
context-sensitive. These macros however can contain definitions and
thus affect the context of their own expansion. The resulting
interactions are hard to analyze.

Reply all
Reply to author
Forward
0 new messages