Scheme - Correct implementation of letrec* ?

Author

Correct implementation of letrec* ?

Andrew Wilcox

2004-12-07, 4:04 pm

Anyone like to venture an opinion as to whether this is a 100% correct
implementation of letrec* ?

(define-syntax letrec*
(syntax-rules ()
((letrec* ((variable expression) ...) body ...)
(let ((variable (void)) ...)
(set! variable expression) ...
body ...))))

Where (void) returns an undefined value, such as (if #f 0).

Thank you,

Andrew Wilcox
email: scheme[at]andrewwilcox.name

Marcin 'Qrczak' Kowalczyk

2004-12-07, 8:57 pm

Andrew Wilcox <scheme@andrewwilcox.name> writes:

> Anyone like to venture an opinion as to whether this is a 100% correct
> implementation of letrec* ?
>
> (define-syntax letrec*
> (syntax-rules ()
> ((letrec* ((variable expression) ...) body ...)
> (let ((variable (void)) ...)
> (set! variable expression) ...
> body ...))))
>
> Where (void) returns an undefined value, such as (if #f 0).

letrec* should allow internal definitions, while the translation
doesn't. It can be fixed by replacing body ... with (let () body ...).

Not incorrect but does not detect some errors: it is an error to
evaluate a variable before it has been bound, while the translation
guarantees that the error will not be detected, even if the
implementation otherwise detects similar errors.

--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

Lauri Alanko

2004-12-07, 8:57 pm

In article <7_KdnXB4at2edijcRVn-sg@gwi.net>,
Andrew Wilcox <scheme@andrewwilcox.name> wrote:
> Anyone like to venture an opinion as to whether this is a 100% correct
> implementation of letrec* ?

Yes, except if you want to signal an error if an uninitialized
variable is used.

If you are interested in the specification and implementation of
letrec and letrec*, you may want to read Waddell, Sarkar and Dybvig's
"Fixing Letrec": http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Lauri Alanko
la@iki.fi

Sponsored Links