* order of evaluation @ 2013-06-17 10:10 Andy Wingo 2013-06-17 13:49 ` Noah Lavine ` (2 more replies) 0 siblings, 3 replies; 7+ messages in thread From: Andy Wingo @ 2013-06-17 10:10 UTC (permalink / raw) To: guile-devel 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/ ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: order of evaluation 2013-06-17 10:10 order of evaluation Andy Wingo @ 2013-06-17 13:49 ` Noah Lavine 2013-06-17 20:14 ` Andy Wingo 2013-06-23 13:46 ` Ludovic Courtès 2013-07-03 18:57 ` order of evaluation, letrec-values, and define-values Mark H Weaver 2 siblings, 1 reply; 7+ messages in thread From: Noah Lavine @ 2013-06-17 13:49 UTC (permalink / raw) To: Andy Wingo; +Cc: guile-devel [-- 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 --] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: order of evaluation 2013-06-17 13:49 ` Noah Lavine @ 2013-06-17 20:14 ` Andy Wingo 2013-06-18 0:39 ` Noah Lavine 2013-06-18 1:06 ` William ML Leslie 0 siblings, 2 replies; 7+ messages in thread From: Andy Wingo @ 2013-06-17 20:14 UTC (permalink / raw) To: Noah Lavine; +Cc: guile-devel 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/ ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: order of evaluation 2013-06-17 20:14 ` Andy Wingo @ 2013-06-18 0:39 ` Noah Lavine 2013-06-18 1:06 ` William ML Leslie 1 sibling, 0 replies; 7+ messages in thread From: Noah Lavine @ 2013-06-18 0:39 UTC (permalink / raw) To: Andy Wingo; +Cc: guile-devel [-- 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 --] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: order of evaluation 2013-06-17 20:14 ` Andy Wingo 2013-06-18 0:39 ` Noah Lavine @ 2013-06-18 1:06 ` William ML Leslie 1 sibling, 0 replies; 7+ messages in thread From: William ML Leslie @ 2013-06-18 1:06 UTC (permalink / raw) To: guile-devel 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. ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: order of evaluation 2013-06-17 10:10 order of evaluation Andy Wingo 2013-06-17 13:49 ` Noah Lavine @ 2013-06-23 13:46 ` Ludovic Courtès 2013-07-03 18:57 ` order of evaluation, letrec-values, and define-values Mark H Weaver 2 siblings, 0 replies; 7+ messages in thread From: Ludovic Courtès @ 2013-06-23 13:46 UTC (permalink / raw) To: guile-devel 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’. ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: order of evaluation, letrec-values, and define-values. 2013-06-17 10:10 order of evaluation Andy Wingo 2013-06-17 13:49 ` Noah Lavine 2013-06-23 13:46 ` Ludovic Courtès @ 2013-07-03 18:57 ` Mark H Weaver 2 siblings, 0 replies; 7+ messages in thread From: Mark H Weaver @ 2013-07-03 18:57 UTC (permalink / raw) To: Andy Wingo; +Cc: guile-devel 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2013-07-03 18:57 UTC | newest] Thread overview: 7+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2013-06-17 10:10 order of evaluation Andy Wingo 2013-06-17 13:49 ` Noah Lavine 2013-06-17 20:14 ` Andy Wingo 2013-06-18 0:39 ` Noah Lavine 2013-06-18 1:06 ` William ML Leslie 2013-06-23 13:46 ` Ludovic Courtès 2013-07-03 18:57 ` order of evaluation, letrec-values, and define-values Mark H Weaver
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).