no continuations

[oleg at pobox.com]

Ashley Yakeley wrote:

> > Similarly, R5RS obligates any Scheme implementation to resort to
> > assignments when processing a letrec form.

> Not mine! I do use a polyvariadic fixed-point function.

I'm sorry but you don't have the choice in the matter -- if you wish
to call your implementation R5RS-compliant. R5RS _requires_ letrec to
use assignments. The latter issue has been extensively discussed, on
comp.lang.scheme, in Amr Sabry's Technical report "Recursion as a
computational effect" and in many other places.

Here's the exact quote from R5RS, Section 4.2.2

"Semantics [of letrec]: The variables are bound to fresh locations
holding undefined values, the inits are evaluated in the resulting
environment (in some unspecified order), each variable is assigned
[sic!] 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."

>   (define circular (letrec ((c (cons 'x c))) c))

I'm afraid that is not a R5RS compliant code.

R5RS states (in the same Section 4.2.2)

"One restriction on letrec is very important: it must be possible to
evaluate each init without assigning or referring to the value of any
variable . If this restriction is violated, then it is an error."

In the quoted code, the <init> is (cons 'x c), and it is impossible to
evaluate that expression according to the semantics of Scheme without
referring to the value of variable c.

If it were
	(define circular (letrec ((c (cons 'x (delay c)))) c))
then there is no contradiction with R5RS.

> Do you have an example of use of Y for letrec where a program would 
> violate R5RS?

http://google.com/groups?selm=7eb8ac3e.0304131423.4f103d4f%40posting.google.com

The difference between the Y and set! approaches to letrec *is*
observable. I must state that the exact conformance to the R5RS
semantics of letrec is important -- for example, for the code that
uses the non-deterministic choice operator 'amb' or for the code that
uses shift/reset. Otherwise, bizarre behavior can occur -- and has
occurred. I can send you an example privately.