Hello,
I always thought that at some point we'd want a form that explicitly didn't
fix the order of evaluation. Maybe the for it is now. I imagine something
like this:
(foo (a (b)) (c (d))) =>
(unspecified-order ((A (let ((B (b))) (a B))
(C (let ((D (d))) (c D))))
(foo A C))
Unspecified-order looks exactly like `let', except that it can evaluate its
clauses in any order before evaluating its body. I think we could make CSE
work with this, don't you think?
To translate this into CPS, I think you need a form that introduces a
continuation for every unspecified-order clause and then merges them, like
this:
(let ((foo-cont (lambda (A C) (foo A C))))
(let-merge-points ((A A-cont) (C C-cont))
(let ((make-A ((lambda () (a (b))))) ;; not CPS-translating this
(make-C ((lambda () (c (d))))))
(any-order (make-A A-cont) (make-C C-cont)))))
Here let-merge-points introduces several continuations, and any-order calls
them in any order. What do you think?
Noah
On Mon, Jun 17, 2013 at 6:10 AM, Andy Wingo <wi...@pobox.com> wrote:
> I really enjoy the unspecified order of evaluation that Scheme has, but
> perhaps that's an implementor's perspective. So I thought that when we
> went to convert to an intermediate form that names all intermediary
> values like ANF or CPS, that we'd be able to preserve this; but it turns
> out that it's not possible with ANF:
>
> This transformation for example is incorrect:
>
> (foo (a (b)) (c (d)))
>
> => (let ((B (b)) (D (d)))
> (let ((A (a B)) (C (c D)))
> (foo A C)))
>
> This is incorrect because it interleaves evaluation of the first and
> second argument, which is not permitted by Scheme, and is silly anyway:
> it introduces order-of-evaluation restrictions: evaluation of (d) and (a
> B) is not specified in the original form, but is in this second form.
>
> The normal way to do ANF is to choose an evaluation order:
>
> (let* ((B (b))
> (A (a B))
> (D (d))
> (C (c D)))
> (foo A C))
>
> This is better from a CSE perspective, but it does fix order of
> evaluation.
>
> Preserving order of evaluation agnosticism would be possible in a more
> direct-style IL:
>
> (let ((A (let ((B (b))) (a B)))
> (C (let ((D (d))) (c D))))
> (foo A C))
>
> Not sure what to do. The part of me that wants to do aggressive CSE
> wants to transform to a form that fixes order of evaluation, but the
> part of me that wants to be able to shuffle values using the Dybvig
> algorithm wants to do the direct form. Dunno!
>
> Andy
> --
> http://wingolog.org/
>
>
