order of evaluation

order of evaluation

[Andy Wingo]

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/

Re: order of evaluation

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 2621 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 3452 bytes --]

Re: order of evaluation

[Andy Wingo]

Hi :)

On Mon 17 Jun 2013 15:49, Noah Lavine <noah.b.lavine@gmail.com> writes:

> Unspecified-order looks exactly like `let', except that it can evaluate
> its clauses in any order before evaluating its body.

So it's exactly like `let', then? ;)

> I think we could make CSE work with this, don't you think?

Oh sure.  It works with let already.  It's just not as effective.

> 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?

It's tough for me to read this example.  Does it have some strange
formatting?

If I understand correctly, I think this is going in the wrong
abstractive direction -- CPS is nice because it's a limpid medium for
program transformations that also corresponds neatly to runtime.  With
this sort of thing we'd be moving farther away from the kind of code we
want to emit.  Dunno.

Andy
-- 
http://wingolog.org/

Re: order of evaluation

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1812 bytes --]

Hello,

On Mon, Jun 17, 2013 at 1:14 PM, Andy Wingo <wingo@pobox.com> wrote:
>
> So it's exactly like `let', then? ;)
>

Oh, yes, you're right. :-)


>
> > I think we could make CSE work with this, don't you think?
>
> Oh sure.  It works with let already.  It's just not as effective.


> > 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?
>
> It's tough for me to read this example.  Does it have some strange
> formatting?
>

Yes, I'm using a webmail client. The formatting probably got messed up
there.

In retrospect, that's too complicated anyway. I think we can make something
very much like a `let' work in CPS, but I realize that's not ideal.


> If I understand correctly, I think this is going in the wrong
> abstractive direction -- CPS is nice because it's a limpid medium for
> program transformations that also corresponds neatly to runtime.  With
> this sort of thing we'd be moving farther away from the kind of code we
> want to emit.  Dunno.
>

I think there's sort of a fundamental problem here - the point of leaving
the order undefined is that we don't know what code we want to emit yet, so
we might have to move further away from emitted code. But I also don't
think that's a bad thing as long as it's for something that's really
useful, like reordering function arguments.

What do you think?

Noah

[-- Attachment #2: Type: text/html, Size: 3142 bytes --]

Re: order of evaluation

[William ML Leslie]

On 18 June 2013 06:14, Andy Wingo <wingo@pobox.com> wrote:
> If I understand correctly, I think this is going in the wrong
> abstractive direction -- CPS is nice because it's a limpid medium for
> program transformations that also corresponds neatly to runtime.  With
> this sort of thing we'd be moving farther away from the kind of code we
> want to emit.  Dunno.

Emit where?

Noah's example of building a continuation graph represents the
unspecified order of argument evaluation, but why stop there?  For the
most flexibility during optimising, a program may as well be
represented as a directed graph, with several classes of edge labels,
allowing you to express commutativity more cleanly.  For example,
stores can be re-ordered if one sets a car and the other a cdr, and
stores into freshly-allocated pairs with those into pairs that come
from the environment.  The 'Context' in [0] (Effect, Test, Value, App,
and probably Identity in a language with mutabality) is then just a
lattice which describes how to remove redundant edges and nodes from
that graph.

Since you're implementing an AOT compiler for a safe language, such a
mechanism may actually be useful.  I don't think it has been when I've
played with it before, partially because making the most of the graph
means using information taken from other functions, which introduces
compile-dependencies that need to be invalidatable at runtime (in the
languages I've targetted, anyway), and partially because I've always
tried to enlarge the set of edge labels with region variables, which
can be non-trivial, especially in a dynamic language.

But if taking advantage of the unspecified argument order is the sort
of thing you want to do, instruction graphs are possible, just a lot
of work.  If you just want to represent the fact that these
expressions are in argument position for input to the interpreter
(which may do something fancy with those later) then a (regular,
unordered) let is simpler.

[0] Oscar Waddell and R. Kent Dybvig, Fast and Effective Procedure Inlining

--
William Leslie

Notice:
Likely much of this email is, by the nature of copyright, covered
under copyright law.  You absolutely may reproduce any part of it in
accordance with the copyright law of the nation you are reading this
in.  Any attempt to deny you those rights would be illegal without
prior contractual agreement.

Re: order of evaluation

[Ludovic Courtès]

Andy Wingo <wingo@pobox.com> skribis:

> 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!

I don’t know either ;-), but I think the guideline should be to give as
much freedom as possible to the compiler.

Leaving the evaluation order unspecified is one way to do it; fixing it
internally it not contradictory with that, as long as it remains
Officially Unspecified.

My €2e-3.

Ludo’.

Re: order of evaluation, letrec-values, and define-values.

[Mark H Weaver]

Hi Andy,

Andy Wingo <wingo@pobox.com> writes:
> 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!

I think the proper solution is to fix order of evaluation somewhere in
the _middle_ of compilation, so that compiler passes can be placed
either before or after the order is fixed.  Then we can have the best of
both worlds.

Some passes, such as fixing-letrec, can benefit greatly from UNspecified
order of evaluation, whereas other passes such as CSE can benefit from a
fixed order of evaluation and CPS form.

Speaking of the fixing-letrec pass, I have a chunk of free time over the
next week during which I intend to dust off my fixing-letrec-reloaded
implementation, and to start generalizing that algorithm to support
'letrec-values', 'letrec*-values', and 'define-values'.

Andy: the reason I bring this up is that it will require the 'letrec'
and 'letrec*' node types to be changed to 'letrec-values' and
'letrec*-values'.  I know you're working on that area of the code now,
so consider this a heads-up.

I suspect that fixing-letrec should be done fairly early in compilation.
This has several advantages, most notably that later passes needn't
understand 'letrec' or 'letrec*' nodes at all.

What do you think?

      Mark