Home > Archive > Scheme > May 2005 > Local defines and LETREC vs LETREC*
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Local defines and LETREC vs LETREC*
|
|
| Nils M Holm 2005-05-05, 8:57 am |
|
R5RS says that local DEFINEs are equivalent to LETREC, ie
(let ()
(define foo ...)
(define bar ...)
x)
is equivalent to
(let ()
(letrec ((foo ...)
bar ...))
x)
R5RS says about LETREC that its initializing expressions are
evaluated in unspecified order. Does this mean that local
DEFINEs are also evaluated in unspecific order?
Is this going to change in R6RS when DEFINE will be defined
in terms of LETREC*?
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Abdulaziz Ghuloum 2005-05-05, 8:57 am |
| Nils M Holm wrote:
> R5RS says about LETREC that its initializing expressions are
> evaluated in unspecified order. Does this mean that local
> DEFINEs are also evaluated in unspecific order?
Yes. Internal defines are the same as letrec in R5RS (as you said).
> Is this going to change in R6RS when DEFINE will be defined
> in terms of LETREC*?
Yes. If that proposal goes through.
A side note: [Petite-]Chez had internal defines evaluate left-to-right
at some point in time (up to 6.0a I believe). The behavior changed
later to be conformant to r5rs. If you use Chez, then you can already
get r6rs internal defines by adding (internal-defines-as-letrec* #t) to
the top of your file.
From the abstract in [1]:
A variant of letrec that enforces left-to-right evaluation
of bindings is also presented and shown to add virtually
no overhead.
Aziz,,,
[1] Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme's
Recursive Binding Construct. Oscar Waddell, Dipanwita Sarkar, and
R. Kent Dybvig. Higher-Order and Symbolic Computation}. (To appear.)
http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf
| |
| Nils M Holm 2005-05-05, 4:00 pm |
| Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> wrote:
> A side note: [Petite-]Chez had internal defines evaluate left-to-right
> at some point in time (up to 6.0a I believe). The behavior changed
> later to be conformant to r5rs. If you use Chez, then you can already
> get r6rs internal defines by adding (internal-defines-as-letrec* #t) to
> the top of your file.
I just downloaded Petite Chez 6.1, but could not find any references
to 'internal-defines-as-letrec*'. Things I tried include grepping the
documentation and running strings(1) on the binary and heap file.
Because an implementation may actually implement LETREC* and call it
LETREC (if order of evaluation is unspecified, it may as well be
left-to-right), it is hard to tell what Petite Chez 6.1 does.
BTW, are there any implementations that make use of the fact the
initializers of LETREC are evaluated in unspecified order? I tried
Scheme48, mzscheme, and Petite Chez, and they all appear to evaluate
LETREC left-to-right.
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Abdulaziz Ghuloum 2005-05-05, 4:00 pm |
| Nils M Holm wrote:
> Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> wrote:
>
>
>
> I just downloaded Petite Chez 6.1, but could not find any references
> to 'internal-defines-as-letrec*'. Things I tried include grepping the
> documentation and running strings(1) on the binary and heap file.
I have 6.9c which is available from http://www.scheme.com/csv6.9c/
I don't know about 6.1.
> Because an implementation may actually implement LETREC* and call it
> LETREC (if order of evaluation is unspecified, it may as well be
> left-to-right), it is hard to tell what Petite Chez 6.1 does.
There is a Petrofsky test that distinguishes letrec from letrec*.
> BTW, are there any implementations that make use of the fact the
> initializers of LETREC are evaluated in unspecified order? I tried
> Scheme48, mzscheme, and Petite Chez, and they all appear to evaluate
> LETREC left-to-right.
Chez does not guarantee ltr evaluation. The evaluation order is chosen
such that the spill costs are minimized[1]. In the following example,
(begin (foo) i) is always evaluated before (begin (set! i 1) 2)
regardless of the order in which they appear in the letrec form.
Petite Chez Scheme Version 6.9c
Copyright (c) 1985-2003 Cadence Research Systems
> (define foo void)
> (let ([i 0])
(letrec ([k (begin (foo) i)]
[j (begin (set! i 1) 2)])
(cons j k)))
(2 . 1)
> (let ([i 0])
(letrec ([j (begin (set! i 1) 2)]
[k (begin (foo) i)])
(cons j k)))
(2 . 1)
>
[1] Register Allocation Using Lazy Saves, Eager Restores, and Greedy
Shuffling. Robert G. Burger, Oscar Waddell, and R. Kent Dybvig. ACM
SIGPLAN 1995 Conference on Programming Language Design and
Implementation, pp. 130-138, June 1995.
http://www.cs.indiana.edu/~dyb/pubs...lloc-PLDI95.pdf
| |
|
|
|
|
|
|
| Abdulaziz Ghuloum 2005-05-05, 4:00 pm |
| Abdulaziz Ghuloum wrote:
> Chez does not guarantee ltr evaluation. The evaluation order is chosen
> such that the spill costs are minimized[1]. In the following example,
> (begin (foo) i) is always evaluated before (begin (set! i 1) 2)
> regardless of the order in which they appear in the letrec form.
I got these backwards. The order in this case in not enforced by the
register allocator but rather (maybe!) by the letrec transformation. In
(let ([i 0])
(letrec ([k (begin (foo) i)]
[j (begin (set! i 1) 2)])
(cons j k)))
- j is unassigned
- j is not referenced/set in any expression on the rhs of the letrec.
- (begin (set! i 1) 2) cannot capture a continuation
Therefore, it can be pulled out of the letrec yielding:
(let ([i 0])
(let ([j (begin (set! i 1) 2)])
(letrec ([k (begin (foo) i)])
(cons j k))))
=>
(let ([i 0])
(let ([j (begin (set! i 1) 2)])
(let ([k (void)])
(let ([t (begin (foo) i)])
(set! k t))
(cons j k))))
Aziz,,,
| |
| Scott G. Miller 2005-05-05, 4:00 pm |
| Nils M Holm wrote:
> Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> wrote:
>
>
>
> BTW, are there any implementations that make use of the fact the
> initializers of LETREC are evaluated in unspecified order? I tried
> Scheme48, mzscheme, and Petite Chez, and they all appear to evaluate
> LETREC left-to-right.
SISC evaluates them right to left.
Scott
|
|
|
|
|