[r6rs-discuss] [Formal] preposterous mustard

From: Felix Klock <pfr6rs>
Date: Mon Feb 5 12:31:32 2007

On Feb 5, 2007, at 7:18 AM, Michael Sperber wrote:

>
> William D Clinger <will_at_ccs.neu.edu> writes:
>
>> Page 35, specification of letrec*:
>>
>> One restriction on letrec* is very important: it must be possible
>> to evaluate each init without assigning or referring to the value
>> the corresponding variable or the variable of any of the bindings
>> that follow it in bindings.
>>
>> It is undecidable whether there exists an order of evaluation
>> for the right hand sides of the bindings that can avoid such
>> assignments or references. The R6RS should permit implementations
>> to evaluate expressions in some particular order, without
>> requiring implementations to perform an exhaustive search of
>> the order-of-evaluation space at run time, complete with the
>> overhead necessary to undo any side effects that are performed
>> by evaluations that run afoul of the restriction.
>
> I see your point for `letrec', which you describe separately.
> However, for `letrec*' order of evaluation is specified. So the
> comment about "exhaustive search of the order-of-evaluation space"
> doesn't seem to apply. Am I missing something?

The order of evaluation of the bindings themselves is specified by
letrec*.

But the order of evaluation of the argument expressions in an
invocation subexpression on the right-hand-side of a particular
binding is not specified.

For example, an implementation that uniformly evaluates invocation
arguments in left-to-right order might end up having no assignment or
reference to successor variables of the letrec* expression, but
another implementation that uniformly evaluates invocation arguments
in right-to-left order might have an assignment or reference to
successor variables of the letrec* expression.

The following expression might serve as an illustration of the
problem: (letrec* ((x 3) (y (foocall (begin (set! x 4) 5) (if (= x 4)
6 z))) (z 7)) y)

-Felix
Received on Mon Feb 05 2007 - 12:31:24 UTC