Reddit Reddit reviews Compiling with Continuations

We found 5 Reddit comments about Compiling with Continuations. Here are the top ones, ranked by their Reddit score.

Computers & Technology
Books
Computer Programming
Software Design, Testing & Engineering
Software Development
Compiling with Continuations
Check price on Amazon

5 Reddit comments about Compiling with Continuations:

u/jdreaver · 72 pointsr/ProgrammingLanguages

Oh wow, I just went down the rabbit hole of CPS, SSA, and ANF while developing my compiler for a strict Haskell-like functional programming language.

I read the outstanding book by Appel on compiling using CPS, and was all ready to go to refactor my pre-LLVM IR to be CPS. Then I did more research and realized that while a number of optimizations are very natural in CPS, compiling CPS to machine code is not as simple. It felt like a really daunting project, and after wrestling with my CPS transformations for about a week I filed a CPS IR away in the "research again someday" bucket.

The best intermediate representation for a functional language I've found is A-Normal Form (ANF). Here is the original paper on the subject. The argument goes that ANF is much more compact and easier to understand than CPS, and still enables almost all of the same optimizations. Some recent work with join points in GHC and a few other papers/theses I read (linked below) convinced me that ANF was going to be my choice of IR.

I highly recommend sticking with LLVM. It is a very mature ecosystem and it gives you so much "for free". I think it's neat that my optimization pipeline will look like:

  1. Core -> Core optimizations
  2. Some small ANF optimizations
  3. Compilation to LLVM where I can have LLVM do some optimizations as well before spitting out machine code

    Even now, I only have some very rudimentary optimizations implemented for ANF, but turning on -O3 when compiling to LLVM makes my toy programs just as fast as equivalent programs I wrote in C. I feel like using LLVM gives you the best of both worlds between ANF and SSA; you hand-write your ANF transformations in your compiler, and let LLVM do the neat things that can be done with SSA optimizations. Note: I am no compiler expert. Maybe I'm being naive in thinking the LLVM optimizations after ANF optimizations give me that much. I'd be happy for someone else to chime in here :)

    Lastly, you mention ease of use and the ability to get started as important criteria. In that case something like ANF to LLVM is the obvious choice.

    Good luck!

    ---

    If anyone is interested, I gathered a lot of resources while researching CPS/ANF/SSA. I'll just dump them here:

    Andrew Appel wrote a book called Compiling with Continuations
    (https://www.amazon.com/Compiling-Continuations-Andrew-W-Appel/dp/052103311X),
    where he explains how continuations can be used as the back end of a compiler.
    Lots of stuff since then has been written on how using continuations makes lots
    of optimizations a lot simpler, and how it is pretty much equivalent to SSA.

    More stuff:

u/poincareDuality · 10 pointsr/compsci

For designing programming languages, my favorites are

u/ErrorIsNullError · 6 pointsr/ProgrammingLanguages

TPL is great for type theory stuff.

I'm working through Compiling with Continuations right now, and it's pretty good as a practical way to specify semantics that also has a history as useful in compilers. Matt Might's writeup gives a flavor.

u/segv00 · 3 pointsr/compsci

if you can get a copy of Appel's Compiling with Continuations, that will explain the whole thing (probably in way too much detail too).

otherwise there are two libraries, for common lisp, which transform code from "direct style" to continuation passing style:

  • cl-cont
  • arnesi (at least the cps transformer in it)

    while reading code that does it isn't quite the same as explaining it, maybe that will help anyway
u/dagit · 1 pointr/fsharp

> Delimited continuations are better than undelimeted (as I have read)

I wouldn't say they are better, but they are different in small ways. Delimited continuations are more complex, but with that complexity comes a notion of scope. Depending on what you're doing, that extra capability may or may not be better (okay, so usually it's better in real programs). So if you're designing a language or library that implements continuations you still have a trade-off between the added complexity of delimited continuations vs undelimited continuations.

Have you seen Andrew Appel's book "Compiling with Continuations"? I have not read it personally, but my understanding is that it is highly relevant to your question. Perhaps you can find an online preview to see if it would help you.

I think you would benefit a lot from "wrapping up" your continuations in a computation expression. In Haskell land, they have a continuation monad and it makes writing things in terms of continuations more convenient. For instance, here is an article meant to introduce beginning Haskell programmers to the Cont monad: https://wiki.haskell.org/All_About_Monads#The_Continuation_monad

The idea is that you create a continuation at each lexical point you may want (or need) to return to (say for instance, you want to return to the top level of the interpreter when you detect a division by zero). Creating the continuation gives you the 'escape hatch' that you may call later in the exceptional case. I think the haskell example makes this clear by calling the continuations "exit1" and "exit2".

I hope that helps.