[ANN] Release of pulley.cps 0.2.0

[Nathan Davis]

I'm pleased to annouce the release of verion 0.2.0 of pulley.cps. pulley.cps is a macro-based source-to-source transforming compiler that transforms Clojure code into Continuation Passing Style (CPS), as well as a supporting run-time library.

The main feature of this release is the addition of exception support — you can now use try, throw, and catch just like you would in regular Clojure code. There are various other enhancements as well, mostly to support the exception code, as documented in the changelog.

Nathan Davis

[Francesco Bellomi]

Hi Nathan,

I think it's an awesome project, thanks for sharing this.

I see that currently only full continuations are supported. Would it be possible/feasible/easy to support delimited continuations? (ie. with ranges different from the outermost CPS context)

Also, it would be interesting to have a comparison with core.async's CPS machinery: is pulley.cps expected to be more efficient performance-wise? Is it implemented using similar or comparable techniques?

thanks,

Francesco

[Nathan Davis]

On Tuesday, September 22, 2015 at 6:37:13 AM UTC-5, Francesco Bellomi wrote:

Hi Nathan,

I think it's an awesome project, thanks for sharing this.

Thanks.  I appreciate the feedback.
 

I see that currently only full continuations are supported. Would it be possible/feasible/easy to support delimited continuations? (ie. with ranges different from the outermost CPS context)

I haven't done much research into delimited continuations yet, so my understanding may be wrong.  However, here's my analysis of the current situation.

As currently implemented, pulley.cps uses "sort of" full continuations.  I say "sort of" because continuations are implicitly limited by the trampoline.  So anytime a new trampoline is introduced (i.e., you call CPS code from a non-CPS function), the continuation is limited to that trampoline.  However, there is currently no way to explicitly delimit the continuation.

In light of the above, it seems to me that reset(f) could be implemented as simply as a non-CPS function that invokes the (presumably CPS'd) function f.  I don't think this would be the ideal implementation, but it does seem to suggest it is at least possible.

I'd be interested in hearing from you (and others) what use-cases you see for delimited continuations.  The overviews of the topic I've seen so far seem to neglect this entirely or only address it abstractly.  A few concrete examples would be a useful "jump-start".

Also, it would be interesting to have a comparison with core.async's CPS machinery: is pulley.cps expected to be more efficient performance-wise? Is it implemented using similar or comparable techniques?

core.async handles continuations as a state machine.  On the other hand, pulley.cps implements continuations via closures.  The two representations are isomorphic, so theoretically anything you can express in one you can express in the other.  However, state machines (at least as implemented in core.async) must be constructed with complete knowledge of all the possible states involved.  Since go-blocks are implemented via macro, and macros are limited to local transformations (and analysis), continuations (state transitions) within core.async are limited to the same go-block.

In contrast, closures can come from different functions or even namespaces.  So continuations in pulley.cps can cross local boundaries.  That is, even though pulley.cps transforms code blocks in isolation, closures allow these blocks to coordinate and participate in the CPS protocol.

This has  some practical ramifications.  For example, you can't compose go-blocks the same way you compose regular functions.  In fact, you can't call a function in a go-block and, within that function, suspend the go-block.  You can of course compose core.async processes, but it has a distinct look and feel from function composition.

On the other hand, functions transformed by pulley.cps compose just like regular functions — because they are functions.  In the examples directory, there is an implementation of a cooperative multitasking engine.  Unlike core.async, you can suspend tasks from pretty much any function.  There are still some limitations, but these are dynamic as opposed to static, and have to do with what I said previously about continuations being implicitly delimited.

As far as performance goes, I haven't directly compared core.async to pulley.cps code yet, but I fully expect core.async to be a hands-down winner at this point.  core.async is more mature and has had more performance tuning than pulley.cps.  I have done some limited benchmarking against regular clojure code.  All I can say is that for compute-intensive code with tight loops in CPS code, pulley.cps performs pretty poorly.  You can expect a CPS version of such code to be 1 to 2 orders of magnitude slower than a non-CPS version.

Interestingly, in included benchmark.clj (which benchmarks a few ways of computing the factorial function), one of the CPS implementations actually out-performed the non-CPS equivalent implemented via loop on OpenJDK 7 for large n.  While for large n there is less time spent in CPS code and more time doing the actual multiplication, it is an interesting result because it means there was apparently some optimization it was able to perform on the CPS code that it wasn't able to do on the loop verion.  On OpenJDK 8, the CPS code is consistently slower in all cases (though, as expected, the slow-down decreases as n increases).
 

[Francesco Bellomi]

Thanks for taking the time to write such a detailed answer, I really appreciated it.

Delimited continuations are useful since they return a value, and thus may be reused and composed, and used to build complex control mechanisms.

In my opinion the coolest use of delimited continuations are Effects

http://math.andrej.com/wp-content/uploads/2012/03/eff.pdf

a way to separate pure computations and side effects that is more intuitive and more composable than monads.

Brandon Bloom has written a (prototype) implementation of effect handlers for clojure, based on the core.async CPS machinery

https://github.com/brandonbloom/cleff

Francesco

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/ugnV06e0Vlo/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Francesco Bellomi

[Nathan Davis]

Thanks, Francesco.  I'll definitely take a look at those resources.

Nathan Davis