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 <wingo@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/
>
>