Local defines and LETREC vs LETREC*

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/

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

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/

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 wrote:

> There is a Petrofsky test that distinguishes letrec from letrec*.

Here is the link:

http://groups.google.com/groups?sel...
=gplain

Aziz,,,

Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> wrote:
> Here is the link:
>
> http://groups.google.com/groups?sel...=gplai
n

Very interesting!

Thanks,

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 <aghuloum@c-s-remove-dashes.indiana.edu> wrote:
> I have 6.9c which is available from http://www.scheme.com/csv6.9c/

I tried 6.9 and it works fine.

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 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,,,

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