15 ms·

how would you manage to figure out the order of execution for an arbitrary set of events firing when the program is defined as a direct linear series of operati

how would you manage to figure out the order of execution for an arbitrary set of events firing when the program is defined as a direct linear series of operations? surely the paradigm is so vastly different that getting a compiler to figure it out would be impossible?

barrkel 17y ago
CPS transformation is mechanical; don't take my word for it, there's plenty of documentation: http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://muaddibspace.blogspot.com/2009/02/cps-transformation-using-delimited.html http://muaddibspace.blogspot.com/2009/02/cps-transformation-... There is data tying the whole program together: the continuation, which is a closure. Assuming a bastardised version of Python with C#-style lambdas, so that () => {} is a function taking no arguments and that has no statements in its body, and result => {} is a function taking a single argument, etc: Direct form: def A(x): x = B(x) C(x) def B(x): factor = SyncCall() return x * factor CPS form: def A(x,continuation): B(x, result => { x = result C(x,continuation) }) def B(x,continuation): AsyncCall(result => { factor = result continuation(x * factor) }) Things are actually more complicated than they look here, you may need more than one continuation for things like exceptions etc., but hopefully you get the gist. Key things in CPS: * Method calls aren't actually method calls; they are jumps with arguments. There is no call stack - the return location is itself passed to the method you're calling * This means that the stack is implied in the variables that the continuation closures capture. So, the caller of A, where it has to return to when it's done, is stored in the "continuation" argument; and that location needs to be captured such that it is part of the state of the closure passed to B, so that it can ultimately be passed to C. * Since the stack is stored implicitly in the closure, it is simple for the implementation of AsyncCall to initiate the I/O, stuff the return location (the last argument, "continuation" I've called it above) away such that it can be retrieved when the I/O completes, and then go off and do some other productive work - such as check for completed I/Os and call their continuations. If you have green threads, the state for the continuation is implicitly part of the stack, only with green threads, you own the data that forms the stack, and can reliably do interesting things with it. The stack itself is a kind of argument that gets implicitly passed around in imperative programs, e.g. it is passed in the ESP register on x86. The top of the stack contains the continuation pointer; and 'RET' is the jump instruction which jumps to the continuation. But using the stack for an implied kind of CPS limits some of the other things you can do with continuations, as it enforces a contiguous linear flow, rather than what you can do with call/cc etc. when the closure data that's part of the continuation is stored on the heap instead.
- etherealG 17y ago
  wow, that's really interesting. thanks. do you know of any production level languages that feature this kind of approach?
  - barrkel 17y ago
    Scheme is implemented via a CPS transform, so a server built around this approach ought to be quite possible on a good Scheme implementation, or a Lisp implementation that supports the moral equivalent of call/cc. Functional languages are also frequently implemented using CPS as an intermediate form. Smalltalk also supports continuations, as I understand it; the Seaside framework for Smalltalk is a server implementation oriented towards continuations, though I think they use it for picking up where you left off in between multiple request/responses, not necessarily for I/O optimization. I could be mistaken. F# has a feature it calls async workflows; I haven't delved into it much, but it looks like it's trying to make writing async code as close to direct style code as possible. But the full benefit comes from the compiler being able to rewrite all functions on the call chain between you and the function that performs the I/O, so I suspect it may be limited. Ideally, the CLR itself would support CPS transformation into its Begin/End-style async support, like I advocate here: http://blog.barrkel.com/2006/07/fun-with-asynchronous-methods-and.html http://blog.barrkel.com/2006/07/fun-with-asynchronous-method... (I've been banging on this drum quietly for some time now...)
  - silentbicycle 17y ago
    Just as a minor addition to what barrkel says below, there's a good explanation of CPS transformation, and its use in compiling, in the first edition of EOPL. I've heard the second and third editions had some of that material cut (too advanced?) - I don't know if that's true, but the first edition is typically much cheaper. FWIW.
- kd5bjo 17y ago
  Twisted's @inlineCallbacks decorator basically does this for you; whenever you yield a deferred (Twisted's representation of an ongoing operation), the rest of the generator is registered as the callback for when the operation is finished. Your example becomes: @defer.inlineCallbacks def A(x): x = yield B(x) C(x) @defer.inlineCallbacks def B(x): factor = yield AsyncCall() defer.returnValue(x * factor)

barrkel 17y ago

CPS transformation is mechanical; don't take my word for it, there's plenty of documentation: http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://www.springerlink.com/content/dk7n7mbjx7blbelj/ http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://moscova.inria.fr/~xleroy/publi/cps-dargaye-leroy.pdf http://muaddibspace.blogspot.com/2009/02/cps-transformation-using-delimited.html http://muaddibspace.blogspot.com/2009/02/cps-transformation-... There is data tying the whole program together: the continuation, which is a closure. Assuming a bastardised version of Python with C#-style lambdas, so that () => {} is a function taking no arguments and that has no statements in its body, and result => {} is a function taking a single argument, etc: Direct form: def A(x): x = B(x) C(x) def B(x): factor = SyncCall() return x * factor CPS form: def A(x,continuation): B(x, result => { x = result C(x,continuation) }) def B(x,continuation): AsyncCall(result => { factor = result continuation(x * factor) }) Things are actually more complicated than they look here, you may need more than one continuation for things like exceptions etc., but hopefully you get the gist. Key things in CPS: * Method calls aren't actually method calls; they are jumps with arguments. There is no call stack - the return location is itself passed to the method you're calling * This means that the stack is implied in the variables that the continuation closures capture. So, the caller of A, where it has to return to when it's done, is stored in the "continuation" argument; and that location needs to be captured such that it is part of the state of the closure passed to B, so that it can ultimately be passed to C. * Since the stack is stored implicitly in the closure, it is simple for the implementation of AsyncCall to initiate the I/O, stuff the return location (the last argument, "continuation" I've called it above) away such that it can be retrieved when the I/O completes, and then go off and do some other productive work - such as check for completed I/Os and call their continuations. If you have green threads, the state for the continuation is implicitly part of the stack, only with green threads, you own the data that forms the stack, and can reliably do interesting things with it. The stack itself is a kind of argument that gets implicitly passed around in imperative programs, e.g. it is passed in the ESP register on x86. The top of the stack contains the continuation pointer; and 'RET' is the jump instruction which jumps to the continuation. But using the stack for an implied kind of CPS limits some of the other things you can do with continuations, as it enforces a contiguous linear flow, rather than what you can do with call/cc etc. when the closure data that's part of the continuation is stored on the heap instead.

etherealG 17y ago
wow, that's really interesting. thanks. do you know of any production level languages that feature this kind of approach?
- barrkel 17y ago
  Scheme is implemented via a CPS transform, so a server built around this approach ought to be quite possible on a good Scheme implementation, or a Lisp implementation that supports the moral equivalent of call/cc. Functional languages are also frequently implemented using CPS as an intermediate form. Smalltalk also supports continuations, as I understand it; the Seaside framework for Smalltalk is a server implementation oriented towards continuations, though I think they use it for picking up where you left off in between multiple request/responses, not necessarily for I/O optimization. I could be mistaken. F# has a feature it calls async workflows; I haven't delved into it much, but it looks like it's trying to make writing async code as close to direct style code as possible. But the full benefit comes from the compiler being able to rewrite all functions on the call chain between you and the function that performs the I/O, so I suspect it may be limited. Ideally, the CLR itself would support CPS transformation into its Begin/End-style async support, like I advocate here: http://blog.barrkel.com/2006/07/fun-with-asynchronous-methods-and.html http://blog.barrkel.com/2006/07/fun-with-asynchronous-method... (I've been banging on this drum quietly for some time now...)
- silentbicycle 17y ago
  Just as a minor addition to what barrkel says below, there's a good explanation of CPS transformation, and its use in compiling, in the first edition of EOPL. I've heard the second and third editions had some of that material cut (too advanced?) - I don't know if that's true, but the first edition is typically much cheaper. FWIW.
kd5bjo 17y ago
Twisted's @inlineCallbacks decorator basically does this for you; whenever you yield a deferred (Twisted's representation of an ongoing operation), the rest of the generator is registered as the callback for when the operation is finished. Your example becomes: @defer.inlineCallbacks def A(x): x = yield B(x) C(x) @defer.inlineCallbacks def B(x): factor = yield AsyncCall() defer.returnValue(x * factor)