11

I imagine many compiler implementers for typical imperative languages simply weren't that familiar with CPS and CPS-based compilation techniques. In the functional programming community both CPS and CPS-based compilation are very well-known techniques - the latter from Guy Steele's work. Nevertheless, even in the FP community, most compilers don't use CPS-...


6

The claim is that after applying β-reduction to an expression in A-normal form you can be left with an expression no longer in A-normal form. The only explicit definition I can find of A-normal form is not consistent with the definition Kennedy seems to be (implicitly) using in this paper. Wikipedia defines A-normal form as the subset of lambda calculus ...


4

So, it turns out, the paper describing the construction I mentioned in the comments answers in the affirmative: Our technique of removing a dynamic prompt is rather general and thus can be used for the design of many other delimited control operators, which permit capturing the continuation up to an arbitrary (not necessarily the closest one) enclosing ...


4

OK, so following the advice given by @Andrej Bauer (in the comments to my question) and @Derek Elkins (in his answer), it seems that we can actually do if-statements in CPS! I will attempt to write out the suggested answer: The idea is to do booleans in pure Lambda calculus, e.g. using Church encoding. The CPS version would be like this: true(a, b, ...


4

I think you are over-attributing things to CPS. First, CPS lets you model exceptions, generators, and functional calls, but it doesn't create them. For example, modeling exceptions with CPS only gives me exception-like behavior in code that is itself in CPS. I can, of course, use CPS as an implementation mechanism, an intermediate language, for exceptions ...


3

I agree with @jmite that the best resources on continuations are likely to come from the Scheme community. Here's a brief tutorial that looks very good: Jeremy H Brown, Advanced Scheme. The tutorial also discusses Scheme's hygienic macros which might also interest you since Clojure has a similarly powerful macro facility. For monads I originally tried to ...


3

I would focus on learning a functional language in order to learn these. There's no need for it to be Haskell. It could be Scheme or ML, or even Coq or Agda. Frankly, Clojure will probably do. But to me, monads and continuations are only programming tools. They don't let you do any new computations, they just let you do them in a different way. So ...


3

I had only a quick look at the paper, but I believe that they are referring to moving from $$ t_1 \to t_2 \cdots \to t_n $$ to $$ t_1 \to t_2 \cdots \to \lnot \lnot t_n $$ where $\lnot t = (t \to r)$ for some fixed return type $r$. In the paper, they choose $r = \sf Type$. So, we get $$ t_1 \to t_2 \cdots \to (t_n \to {\sf Type}) \to {\sf Type} $$...


3

Are Spaghetti Stacks Parent-Pointer Trees? Yes, spaghetti stacks are parent-pointer trees. You can think of a spaghetti stack as having the same structure as a collection of single-linked lists which share structure. When viewed as a whole, the collection of lists form a tree. But when viewed individually, each list forms a stack. Each process in the ...


2

The code you posted takes a few shortcuts. The mismatch with the rules of the CPS transform comes form your code being in Haskell, which features integers (0,1,2), arithmetics (+,-), definitions by cases, and recursion, while the CPS transform only covers the pure lambda calculus, without all the bells and whistles that come with a "usual" programming ...


2

I'm not a compiler expert, so take what I say with a grain of salt, I hope that a real compiler expert will chime in. I was told that: CPSed code tends to jump non-locally a lot, which ruins cache locality, hence performance. CPS requires more expensive garbage collection than conventional compilation which can typically store a lot of stuff on the stack (...


1

A set $S$ is closed under an operation $f$ if, whenever $x\in S$, $f(x)\in S$ also.


Only top voted, non community-wiki answers of a minimum length are eligible