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.
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!
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.
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.
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.)
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?
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.:
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.
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.
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.
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.
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
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.
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.
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.
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)?
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.