Defunctionalize the Continuation | Hacker News Reader

Defunctionalize the Continuation

pathsensitive.com

236 pointsDarmani31 comments

Defunctionalisation is a beautifully powerful technique. I've found it fits really neatly with the initial algebra pattern of data processing as repeated conversion of a "description" structure into more useful "implementation" structures.

In particular, my most recent project at work consisted of a system that takes a description of a computation from the user and successively performs optimisation passes on the description until we get a description of something that could run really efficiently, and then evaluating that efficient description into an actual computation that you really can run. If the successively-more-optimised descriptions are all defunctionalised to the greatest possible extent (in effect, deferring any concrete implementation details for as long as possible), you have much broader scope to optimise during later passes (since all the information "remains visible", not hidden away in function calls).

Moreover, this approach is extremely testable: initial algebras are built to be re-interpreted, so you can write reference evaluators for them; while defunctionalisation gives you a way of checking output without needing to run any pesky programs.

That's super interesting. May I ask what domain you're working in, where this sort of problem arises?

This probably isn't it, but it sounds a lot like a compiler. If you're interested in that stuff you might be interested in checking out "Advanced Compiler Design and Implementation" [0] or the /r/programminglanguages subreddit.

[0]: https://www.amazon.com/Advanced-Compiler-Design-Implementati...

Dev at a quant finance research shop. I would love to write more about it, but I've signed some very strict paperwork :( broadly, it's the core of a data analytics system, taking a bunch of quant descriptions of data analysis and "compiling" them into highly efficient minimal-overhead forms that can run on market data in realtime and in sim. Very fun project!

Kudos for providing a nicely-formatted transcript of this talk and not forcing us to watch a video. Learning about defunctionalization (and lambda lifting, which is closely related) was how I first managed to understand what this "first-class functions" language feature/pattern was all about, and why it could be useful. It's something that should be generally taught as part of any introduction to functional programming.

Reminded me of https://en.wikipedia.org/wiki/Immanentize_the_eschaton

Reminded me of https://www.youtube.com/watch?v=l4nOHdUntyM

    Ow, we want the funk (we're gonna turn this mother out)
    Give up the funk
    Ow, we need the funk (we're gonna turn this mother out)
    We gotta have that funk

Note that you don't have to defunctionalize to be serializable or perform other manipulations. Tagless final style extensible-interpreter techniques allows direct-style programs to be serialized and manipulated.

That sounds interesting too. Any chance you have a link or two handy for reference? I've seen Oleg Kiselyov's bibliography on the tagless-final style (http://okmij.org/ftp/tagless-final/index.html), but there's quite a lot there.

Referencing his "Typed Tagless Final Interpreters: Lecture Notes", it seems like a tagless-final interpreter is just a regular function whose result depends on the domain you intend to evaluate it in. It seems like the easiest thing to do is define a domain in which the tagless-final primitive operations map to an initial type, then serialize that. (So tagless-final seems at least as expressive as the initial representation, and by the "initial" concept, I would expect it to be no more expressive.)

There are also some blog posts over at Serokell about tagless final in Haskell: https://serokell.io/blog/tagless-final.

How so? Tagless final style usually requires a monad instance; how can you describe the result of a call to fmap in a serializable way without executing it?

Presumably you execute it with an instance that does serialization instead of interpretation.

This is correct. (Something else to add on here: Initial and final encodings are bijective – theoertically, anything one can do, the other can too.)

But you can't serialize a function - that's the whole point of the post.

But if you're writing an interpreter, you can serialize the result of 'evaluating' the structure of your 'function' made out of components that are being interpreted by your code, thus turning your 'function' (when evaluated with one set of code) into a data structure (when evaluated by something that serializes each of the components making up your function)

At that point you've already evaluated it and can't recover the original program - you're serializing the result of interpretation, not the computation to be interpreted. Since that computation might contain arbitrary functions, the only way to serialize that would be if you had a way of serializing arbitrary functions.

Applicative Functors/Selective Applicative Functors should be more suitable to serialization than monads, because they do not contain lambdas and expose the underlying structure, allowing you to inspect,modify it, etc.:

https://www.cs.ox.ac.uk/jeremy.gibbons/publications/delivery... http://simonmar.github.io/bib/papers/haxl-icfp14.pdf https://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors...

Applicatives still contain lambdas in the same sense that monads do, no?

I think you can think of applicative like specifying the abstract syntax tree for the operation you want to perform and then giving it to an evaluator, as opposed to a monad where you code the implementation more directly, but deliver it opaquely as a lambda to the system.

Jimmy's transcripts are great. I have been reading through his blog in preparation for a podcast interview and at first, I was a bit skeptical that a transcript could replace a talk but now I find I am liking the format.

Over the years there have been countless times when I had to convert an easy to understand recursive program into a messy state machine or a heap of callbacks, for one reason or the other.

I always did these conversions in an ad-hoc fashion but this approach based on CPS + defunctionalization is definitely much clearer and easier on the brain!

I'm having trouble working through the recursion -> iteration process with functions that return a value. For instance, what if instead of printing the tree, we were summing the tree, as in a fibonacci sequence?

recursive:

  def fib(n):
      n = min(n, 0)
      if n > 1: 
          return fib(n-1) + fib(n-2)
      else: 
          return n

CPS:

  def fib(n, kont):
      n = min(n, 0)
      if n > 1: 
          return fib(n - 1, lambda x: x + fib(n - 2, kont))
      else: 
          return n

but then I get stuck at defunctionalizing. I can't figure out where the logic of combining values from the reduction step should go, or how to properly structure the continuation data structure.

  # BROKEN -- where do I combine the values?

  def fib(n, kont):
      n = min(n, 0)
      if n > 1: 
          return fib(n-1, {"val": n, "next": kont})
      else:
          return kapply(kont, n)

  def kapply(kont, n):
      if kont: return fib(kont["val"] - 2, kont["next"])
      return n

This sounds really interesting, but I'm getting a bit confused trying to apply it to a simpler problem. Say I start with this recursive function to filter a list:

  def my_filter_recursive(l, f):                                                  
      if l:                                                                       
          x, *xs = l                                                              
          if f(x):                                                                
              return [x] + my_filter_recursive(xs, f)                             
          else:                                                                   
              return my_filter_recursive(xs, f)                                   
      else:                                                                       
          return []

In Continuation Passing Style it becomes:

  def my_filter_cps(l, f, kont):                                                  
      if l:                                                                       
          x, *xs = l                                                              
          if f(x):                                                                
              my_filter_cps(xs, f, lambda y: kont([x] + y))                       
          else:                                                                   
              my_filter_cps(xs, f, lambda y: kont(y))                             
      else:                                                                       
          kont([])

Then I think with defunctionalisation it becomes:

  def my_filter_defun(l, f, kont):
      if l:
          x, *xs = l
          if f(x):
              my_filter_defun(xs, f, KontAdd(x, kont))
          else:
              my_filter_defun(xs, f, KontSkip(kont))
      else:
          kont.apply([])
  
  class KontAdd:
      def __init__(self, var, kont):
          self.var = var
          self.kont = kont
      def apply(self, acc):
          self.kont.apply([self.var] + acc)
  
  class KontSkip:
      def __init__(self, kont):
          self.kont = kont
      def apply(self, acc):
          self.kont.apply(acc)
  
  class KontPrint:
      def apply(self, acc):
          print(acc)

Is that right? It seems that we've basically just moved the recursion from one place to another.

It seems that we've basically just moved the recursion from one place to another.

Yes, the point is to move the recursion from the code into the data structures. These data structures can then be stored and retrieved conveniently. It's a technique for making micro eDSLs to solve common problems.

Having said that, it's a lot more applicable to some languages than others. Python, lacking algebraic data types and static typing, does not make it very convenient to use this technique.

Hello peconn,

This is right, although you could replace KontSkip(kont) with just kont. Defunctionalization does not just "move the recursion from one place to another." Rather, it doesn't change the recursion at all.

Also, your example is actually harder than the one in the talk, because it can involve an arbitrary amount of work after the last call to my_filter_recursive.

Like in the example in the talk, you still need merge the various calls to apply, and use tail-call elimination.

Merging:

    def apply(kont, acc):
        if isinstance(kont, KontAdd):
           apply(kont.kont, [kont.var] + acc)
        else:
           print(acc)

You will now actually need two levels of tail-call elimination because there are two recursions, rather than one as in the example in the talk. apply becomes this:

    def apply(kont, acc):
      while True:
            if isinstance(kont, KontAdd):
               kont = kont.kont
               acc = [kont.var] + acc
            else:
               print(acc)
               break

You can then inline this into my_filter_cps and do tail-call elimination again.

  def my_filter_defun(l, f, kont):
    while True:
      if l:
          x, *xs = l
          if f(x):
              l = xs
              kont = KontAdd(x, kont)
          else:
              l = xs
      else:
        acc = []
        while True:
          if isinstance(kont, KontAdd):
             kont = kont.kont
             acc = [kont.var] + acc
          else:
             print(acc)
             break

One little beef with CPS (for an interpreter) is that use it cause a hit on performance. Defunctionalization could be use to improve on that?

Very nice! I wrote a library (not long ago) for stackless recursion in Clojure, which uses core.async and the go macro to automatically turn recursive calls into defunctionalized continuations - no (structural) refactoring required! [1]

It's not as fast as a plain iterative version would be, though, and the article gave me some ideas to experiment with.

[1] https://github.com/divs1210/xodarap/

This is a very nice technique. I tried it for a couple of algorithms and while the author said that it a pretty mechanical to go from a recursive function to an iterative one, I think the non-mechanical work required to go from recursive to the CPS style is about the same as the work required to go directly from recursive to iterative. At least that was my experience.

James is a fantastic person and an excellent teacher. Jimmy, if you're reading the comments, hello and thank you!

If the old hacker news server in this example were to crash, wouldn't that mean they lost the context of their continuation)? Wouldn't this mean it is better to use the discrete data as the continuation (which they achieved by realizing all the continuations in code)?

Thanks, I learned something new today.

Reply on news.ycombinator.com