[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: order of evaluation

From: Noah Lavine
Subject: Re: order of evaluation
Date: Mon, 17 Jun 2013 09:49:14 -0400


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?


On Mon, Jun 17, 2013 at 6:10 AM, Andy Wingo <address@hidden> 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

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!


reply via email to

[Prev in Thread] Current Thread [Next in Thread]