10 ms·

Defunctionalize the Continuation

236 points by Darmani 7y ago

Smaug123 7y ago
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.
- neonate 7y ago
  That's super interesting. May I ask what domain you're working in, where this sort of problem arises?
  - anchpop 7y ago
    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-Implementation-Muchnick-ebook/dp/B003VM7GGK/ https://www.amazon.com/Advanced-Compiler-Design-Implementati...
  - Smaug123 7y ago
    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!
0815test 7y ago
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.
catern 7y ago
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.
- Twisol 7y ago
  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 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.)
  - sctb 7y ago
    There are also some blog posts over at Serokell about tagless final in Haskell: https://serokell.io/blog/tagless-final https://serokell.io/blog/tagless-final.
- lmm 7y ago
  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?
  - Rusky 7y ago
    Presumably you execute it with an instance that does serialization instead of interpretation.
    - shadytrees 7y ago
      This is correct. (Something else to add on here: Initial and final encodings are bijective – theoertically, anything one can do, the other can too.)
renox 7y ago
Thanks, I learned something new today.
ufo 7y ago
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!
agbell 7y ago
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.
deleted 7y ago
[deleted]
JackFr 7y ago
Reminded me of https://en.wikipedia.org/wiki/Immanentize_the_eschaton https://en.wikipedia.org/wiki/Immanentize_the_eschaton
- DonHopkins 7y ago
  Reminded me of https://www.youtube.com/watch?v=l4nOHdUntyM 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
andonisus 7y ago
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)?
peter_l_downs 7y ago
James is a fantastic person and an excellent teacher. Jimmy, if you're reading the comments, hello and thank you!
divs1210 7y ago
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/ https://github.com/divs1210/xodarap/
peconn 7y ago
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.
- chongli 7y ago
  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.
newen 7y ago
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.
mechrophile 7y ago
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

236 points by Darmani 7y ago

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.

neonate 7y ago
That's super interesting. May I ask what domain you're working in, where this sort of problem arises?
- anchpop 7y ago
  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-Implementation-Muchnick-ebook/dp/B003VM7GGK/ https://www.amazon.com/Advanced-Compiler-Design-Implementati...
- Smaug123 7y ago
  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!

0815test 7y ago

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.

catern 7y ago

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.

Twisol 7y ago
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 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.)
- sctb 7y ago
  There are also some blog posts over at Serokell about tagless final in Haskell: https://serokell.io/blog/tagless-final https://serokell.io/blog/tagless-final.
lmm 7y ago
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?
- Rusky 7y ago
  Presumably you execute it with an instance that does serialization instead of interpretation.
  - shadytrees 7y ago
    This is correct. (Something else to add on here: Initial and final encodings are bijective – theoertically, anything one can do, the other can too.)

renox 7y ago

Thanks, I learned something new today.

ufo 7y ago

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!

agbell 7y ago

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.

deleted 7y ago

[deleted]

JackFr 7y ago

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

DonHopkins 7y ago
Reminded me of https://www.youtube.com/watch?v=l4nOHdUntyM 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

andonisus 7y ago

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)?

peter_l_downs 7y ago

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

divs1210 7y ago

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/ https://github.com/divs1210/xodarap/

peconn 7y ago

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.

chongli 7y ago
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.

newen 7y ago

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.

mechrophile 7y ago

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