8 ms·

Don’t Think, Just Defunctionalize

118 points by gbrown_ 6y ago

082349872349872 6y ago
Has anyone made a connection between: > Defunctionalizing CPSed code will always produce a type isomorphic to a list, i.e. a stack (or something simpler if there is no recursion) and McBride's derivatives of data structures? (also, on very small machines, like in the card processing days, one had to mutate the input data structure itself as the holder of defunctionalised control information, instead of keeping it in a side structure as done here. On one hand this is a pain, on the other, it can also be useful nowadays, as it opens up parallelisation opportunities.)
- maxiepoo 6y ago
  Yes, this is well known, good catch! If you read McBride's paper "Clowns to the Left of Me, Jokers to the Right" (https://www.cis.upenn.edu/~cis39903/static/clowns.pdf https://www.cis.upenn.edu/~cis39903/static/clowns.pdf) is exactly about systematically deriving the type of defunctionalized stacks for the fold over an ADT. The ordinary derivative is then the special case where you are just mapping a function that doesn't change the type.
vanderZwan 6y ago
> Update: Turns out I inadvertedly plagiarized the talk The Best Refactoring You’ve Never Heard Of by James Koppel. Ah, that's why the title felt familiar. Well, it's been a while since I read/watched that and I could use a refresher anyway, might as well read this article for a different perspective on the same thing :)
- TameAntelope 6y ago
  I think he’sa bit harsh on himself here, both have their own value!
jpcooper 6y ago
I don't agree with the "constant-stack algorithm" comment. Whether you represent the stack implicitly through recursive function calls, explicitly through building up lambdas, or again even more explicitly by using a singly linked list or other suitable data structure, it's still a stack, and the memory complexity is the same. They're all different ways of doing the same thing. Of course there could be a benefit for cases where you have a limited stack size. The author says that there's no need to do this in Haskell, because the stack is allocated on the heap, but I still wonder what the constant factor overhead of doing this with a linked list plus data types is over simple recursive function calls. This whole thing can be summarised as: 1. Represent the stack as a singly linked list (or std::stack). 2. Data type for encoding stack frame: function state and where to return to in function. As an example, this technique is useful if you are doing an in-order tree traversal and want to avoid using the stack. Define a data type to encode the nodes to be looked at, and encode whether you have already been through the left branch of the node or not.
- yakubin 6y ago
  > They're all different ways of doing the same thing. Of course there could be a benefit for cases where you have a limited stack size. The author says that there's no need to do this in Haskell, because the stack is allocated on the heap, but I still wonder what the constant factor overhead of doing this with a linked list plus data types is over simple recursive function calls. When you use (non-tail) recursive function calls, your memory will grow faster than with an explicitly managed stack, because now at each recursion level not only will you store all the things you would store in the explicitly managed stack, but also all the other variables and some intermediate values. Explicitly managed stack, that is implemented efficiently (i.e. mostly contiguous memory, not a linked list like in the example given), will give you better performance and will be easier to debug, because now you can query its size and identify where in the program you're using a given amount of memory; in the debugger you can inspect it as a whole in a multitude of ways (as opposed to the black box of a function where you'll only inspect one recursion level at a time, leaving you with scattered information and without easy to read performance metrics). That said, recursion is usually the simplest thing to write on the first try, when coming up with a solution to a problem. But I do tend to "defunctionalize" later.
siraben 6y ago
wrt. defunctionalization, another resource that requires only basic understanding of functional programming (lambdas and ADTs) and equational reasoning to understand it is lecture 4 of [0]. The procedure is quite straightforward if approached from a program derivation standpoint; first convert the program into CPS (see end of lecture 1). That is, solve the equation `progCont e k = k (prog e)` given prog. Then convert the closures into first-order structures by identifying the free variables they capture and deriving the closure-free version. I really like Bartosz's blog post on defunctionalization and Freyd's theorem[1]. It's probably better to understand Freyd's theorem in the usual categorical presentation as Bartosz dualizes many things (because instead of a huge product of all environments we have a huge coproduct of possible environments, then select the "best"/"minimal" one using some universal cone as opposed to a maximal product). Truly, defunctionalization is one of those things that can satisfy curiosity on many levels of abstraction from assembly to categories. [0] http://www.cs.nott.ac.uk/~pszjlh/pcalc.html http://www.cs.nott.ac.uk/~pszjlh/pcalc.html [1] https://bartoszmilewski.com/2020/08/03/defunctionalization-and-freyds-theorem/ https://bartoszmilewski.com/2020/08/03/defunctionalization-a...
joosters 6y ago
Is this a technique that an optimizing compiler could automatically make use of? i.e. is it practical for a compiler to look at a (limited-size) function and be able to tell if refactoring it into a tail-calling version is possible? (I'm sure the general case becomes 'halting problem' hard, but limiting the analyzed function size / cpu time might perhaps still manage to refactor enough code to be useful?)
- mratsim 6y ago
  CPS for functional language is the equivalent of SSA for imperative language, an excellent Intermediate Representation to apply optimization on.
rabbut 6y ago
> (In the following, I assume that tail-calls, i.e. those where a function end with another function call, but without modifying its result, do not actually use stack space. Once all recursive function calls are tail calls, the code is equivalent to an imperative loop, as we will see.) No, it’s not “tail call”, it’s “tail recursion” or “tail-end recursion”. “Tail call” could be interpreted as any call from a function’s end, even one that adds to the stack.
- balfirevic 6y ago
  Tail call doesn’t have to be recursive.
- joppy 6y ago
  “Tail call” has a specific meaning in computer science, and it is possible to execute such a call without adding to the stack. Tail calls may not be directly recursive, they may be mutually recursive, or not even recursive at all.
- mst 6y ago
  > “Tail call” could be interpreted as any call from a function’s end, even one that adds to the stack That's why he said "I assume that tail-calls ... do not actually use stack space". Also, 'tail recursion' is more likely to be read by people as referring to a tail call to the same function as is currently executing, whereas 'tail call' refers to the general case.
- chriswarbo 6y ago
  > “Tail call” could be interpreted as any call from a function’s end, even one that adds to the stack. Tail calls might add to the stack, or they might not; but they don't need to (whether or not they do depends on the particular language, implementation and possibly compiler options). If a call needs to use stack space (or equivalent, e.g. growing the term size in a rewrite system), then it's certainly not a tail call. > No, it’s not “tail call”, it’s “tail recursion” or “tail-end recursion”. I wouldn't be so dogmatic about terminology, especially since it's at odds with others' usage. This article is a particularly poor choice to get hung up on too, since most of the examples use a pair of mutually-recursive functions (go+eval or up+down), which both call each other and themselves (depending on which branch is taken). How do they fit into your overly-precise terminology? What about the top-level 'map' definitions themselves? Most of them consist of a single call to the go/down function: that doesn't need to add to the stack. Would you insist on naming that 'tail recursion' or 'tail-end recursion', even though there are no calls back into these functions from anywhere else?
bflesch 6y ago
Is there an error in this sentence or am I misunderstanding something: "But in other languages or environments, the stack space may have a hard limit, and it may be advised to not use unbounded stack space." - I'd say it might be advised to use unbounded stack space, and the current text uses double negation.
- Smaug123 6y ago
  I think you're misunderstanding, although it's not phrased super crisply. It means: "you should avoid algorithms which may attempt to use arbitrarily large amounts of stack space".
mratsim 6y ago
Interesting to see more CPS in the wild. Nim may have first-class continuations in the not too far future as well https://github.com/nim-lang/RFCs/issues/295 https://github.com/nim-lang/RFCs/issues/295 I'm still evaluating and comparing CPS vs coroutines as the base primitive.
contingencies 6y ago
The fonts on this page changed at least three times while I was reading it. Never seen that before. Points for effort!
CJefferson 6y ago
One of my biggest irritations is the tiny size of default stacks in 64-bit OSes. They don't really seem to have grown significantly while both physical memory and address space size have grown massively. I write a bunch of algorithms which would most naturally be written recursively, but I have to go out of my way to make sure they have enough stack. Is there a good reason not to give the main thread of every program on a 64-bit OS 1GB of virtual address space?
- tempodox 6y ago
  On a Unix-like OS you can do ulimit -s <stack-size-in-KiB> At least you only have to set it once per shell instance; put it in your shell init file (bashrc or whatever).
  - CJefferson 6y ago
    The problem is, it's hard to distribute libraries which want lots of stack space, because not everyone will do that. In Rust (where threadsafety is easy and cheap), I tend to just spin up a thread of known (large) stack size, and do computations there.
    - tempodox 6y ago
      I see. And the end user might not even know that library is built into the tool they use, or know how to alter the stack size limit on their machine. So I can't think of a better solution either.
  - ufo 6y ago
    Can a process increase their own stack limit or do they need to spawn a child process with a higher limit?
- ufo 6y ago
  The other question I always had is why do we need to have a fixed limit for the stack. Why can't it grow automatically as needed, just like the heap?
taeric 6y ago
Having recently learned the so called natural correspondence between binary trees and forests, I'm curious that I don't see that get a lot of love. Combined with threaded trees, completely stack free traversal of a tree is possible. For a forest, post order traversal is possible without a stack. My guess is that is a technique that has just died with the abundance of memory we have in modern machines?
abeppu 6y ago
What's needed to automate / mechanize defunctionalization? In worked examples like this one, and the Reynolds paper mentioned (which I haven't read in quite a while), it seems like the author has to know which functions get pulled out into the same data types and eval definition, which seems to be based on tracing how the functions get moved around and eventually called. For arbitrary programs, this can be quite hard -- e.g. perhaps I generate administrative lambdas of more than one flavor, and put them in a common data structure, and based on some invariant not encoded in the type system, I know which flavor of function is being read back or evaluated when. I'm aware in a broad way that compilers / program transformation systems have used defunctionalization, but I don't quite see how without some sort of rich static analysis. Can anyone point me at what I'm missing?
ufo 6y ago
While the more obvious application of defunctionalization is to avoid stack overflow from using the implicit machine stack, another application is if you want to make your algorithm asynchronous. In many languages, it's hard to create an asynchronous recursive function that can yield from inside some deep recursion, and then resume later from where it stopped. On the other hand, if your program is rewritten to use an explicit stack plus a state machine then it's trivial to do things like pausing the execution, or printing some debug message between each step.
lobocinza 6y ago
You can disable suggestions through a extension or ad blocker and follow Youtube channels in a RSS reader. Youtube recommendations are aggressive and will keep recommending sensationalist videos related to your watch history. I don't think that content is curated besides the Youtube ad-friendly bias. I frequently clear my history to start fresh. All platforms uses some kind of collaborative filtering and have the same problem.

118 points by gbrown_ 6y ago

Has anyone made a connection between: > Defunctionalizing CPSed code will always produce a type isomorphic to a list, i.e. a stack (or something simpler if there is no recursion) and McBride's derivatives of data structures? (also, on very small machines, like in the card processing days, one had to mutate the input data structure itself as the holder of defunctionalised control information, instead of keeping it in a side structure as done here. On one hand this is a pain, on the other, it can also be useful nowadays, as it opens up parallelisation opportunities.)

maxiepoo 6y ago
Yes, this is well known, good catch! If you read McBride's paper "Clowns to the Left of Me, Jokers to the Right" (https://www.cis.upenn.edu/~cis39903/static/clowns.pdf https://www.cis.upenn.edu/~cis39903/static/clowns.pdf) is exactly about systematically deriving the type of defunctionalized stacks for the fold over an ADT. The ordinary derivative is then the special case where you are just mapping a function that doesn't change the type.

vanderZwan 6y ago

> Update: Turns out I inadvertedly plagiarized the talk The Best Refactoring You’ve Never Heard Of by James Koppel. Ah, that's why the title felt familiar. Well, it's been a while since I read/watched that and I could use a refresher anyway, might as well read this article for a different perspective on the same thing :)

TameAntelope 6y ago
I think he’sa bit harsh on himself here, both have their own value!

jpcooper 6y ago

I don't agree with the "constant-stack algorithm" comment. Whether you represent the stack implicitly through recursive function calls, explicitly through building up lambdas, or again even more explicitly by using a singly linked list or other suitable data structure, it's still a stack, and the memory complexity is the same. They're all different ways of doing the same thing. Of course there could be a benefit for cases where you have a limited stack size. The author says that there's no need to do this in Haskell, because the stack is allocated on the heap, but I still wonder what the constant factor overhead of doing this with a linked list plus data types is over simple recursive function calls. This whole thing can be summarised as: 1. Represent the stack as a singly linked list (or std::stack). 2. Data type for encoding stack frame: function state and where to return to in function. As an example, this technique is useful if you are doing an in-order tree traversal and want to avoid using the stack. Define a data type to encode the nodes to be looked at, and encode whether you have already been through the left branch of the node or not.

yakubin 6y ago
> They're all different ways of doing the same thing. Of course there could be a benefit for cases where you have a limited stack size. The author says that there's no need to do this in Haskell, because the stack is allocated on the heap, but I still wonder what the constant factor overhead of doing this with a linked list plus data types is over simple recursive function calls. When you use (non-tail) recursive function calls, your memory will grow faster than with an explicitly managed stack, because now at each recursion level not only will you store all the things you would store in the explicitly managed stack, but also all the other variables and some intermediate values. Explicitly managed stack, that is implemented efficiently (i.e. mostly contiguous memory, not a linked list like in the example given), will give you better performance and will be easier to debug, because now you can query its size and identify where in the program you're using a given amount of memory; in the debugger you can inspect it as a whole in a multitude of ways (as opposed to the black box of a function where you'll only inspect one recursion level at a time, leaving you with scattered information and without easy to read performance metrics). That said, recursion is usually the simplest thing to write on the first try, when coming up with a solution to a problem. But I do tend to "defunctionalize" later.

siraben 6y ago

wrt. defunctionalization, another resource that requires only basic understanding of functional programming (lambdas and ADTs) and equational reasoning to understand it is lecture 4 of [0]. The procedure is quite straightforward if approached from a program derivation standpoint; first convert the program into CPS (see end of lecture 1). That is, solve the equation `progCont e k = k (prog e)` given prog. Then convert the closures into first-order structures by identifying the free variables they capture and deriving the closure-free version. I really like Bartosz's blog post on defunctionalization and Freyd's theorem[1]. It's probably better to understand Freyd's theorem in the usual categorical presentation as Bartosz dualizes many things (because instead of a huge product of all environments we have a huge coproduct of possible environments, then select the "best"/"minimal" one using some universal cone as opposed to a maximal product). Truly, defunctionalization is one of those things that can satisfy curiosity on many levels of abstraction from assembly to categories. [0] http://www.cs.nott.ac.uk/~pszjlh/pcalc.html http://www.cs.nott.ac.uk/~pszjlh/pcalc.html [1] https://bartoszmilewski.com/2020/08/03/defunctionalization-and-freyds-theorem/ https://bartoszmilewski.com/2020/08/03/defunctionalization-a...

joosters 6y ago

Is this a technique that an optimizing compiler could automatically make use of? i.e. is it practical for a compiler to look at a (limited-size) function and be able to tell if refactoring it into a tail-calling version is possible? (I'm sure the general case becomes 'halting problem' hard, but limiting the analyzed function size / cpu time might perhaps still manage to refactor enough code to be useful?)

mratsim 6y ago
CPS for functional language is the equivalent of SSA for imperative language, an excellent Intermediate Representation to apply optimization on.

rabbut 6y ago

> (In the following, I assume that tail-calls, i.e. those where a function end with another function call, but without modifying its result, do not actually use stack space. Once all recursive function calls are tail calls, the code is equivalent to an imperative loop, as we will see.) No, it’s not “tail call”, it’s “tail recursion” or “tail-end recursion”. “Tail call” could be interpreted as any call from a function’s end, even one that adds to the stack.

balfirevic 6y ago
Tail call doesn’t have to be recursive.
joppy 6y ago
“Tail call” has a specific meaning in computer science, and it is possible to execute such a call without adding to the stack. Tail calls may not be directly recursive, they may be mutually recursive, or not even recursive at all.
mst 6y ago
> “Tail call” could be interpreted as any call from a function’s end, even one that adds to the stack That's why he said "I assume that tail-calls ... do not actually use stack space". Also, 'tail recursion' is more likely to be read by people as referring to a tail call to the same function as is currently executing, whereas 'tail call' refers to the general case.
chriswarbo 6y ago
> “Tail call” could be interpreted as any call from a function’s end, even one that adds to the stack. Tail calls might add to the stack, or they might not; but they don't need to (whether or not they do depends on the particular language, implementation and possibly compiler options). If a call needs to use stack space (or equivalent, e.g. growing the term size in a rewrite system), then it's certainly not a tail call. > No, it’s not “tail call”, it’s “tail recursion” or “tail-end recursion”. I wouldn't be so dogmatic about terminology, especially since it's at odds with others' usage. This article is a particularly poor choice to get hung up on too, since most of the examples use a pair of mutually-recursive functions (go+eval or up+down), which both call each other and themselves (depending on which branch is taken). How do they fit into your overly-precise terminology? What about the top-level 'map' definitions themselves? Most of them consist of a single call to the go/down function: that doesn't need to add to the stack. Would you insist on naming that 'tail recursion' or 'tail-end recursion', even though there are no calls back into these functions from anywhere else?

bflesch 6y ago

Is there an error in this sentence or am I misunderstanding something: "But in other languages or environments, the stack space may have a hard limit, and it may be advised to not use unbounded stack space." - I'd say it might be advised to use unbounded stack space, and the current text uses double negation.

Smaug123 6y ago
I think you're misunderstanding, although it's not phrased super crisply. It means: "you should avoid algorithms which may attempt to use arbitrarily large amounts of stack space".

mratsim 6y ago

Interesting to see more CPS in the wild. Nim may have first-class continuations in the not too far future as well https://github.com/nim-lang/RFCs/issues/295 https://github.com/nim-lang/RFCs/issues/295 I'm still evaluating and comparing CPS vs coroutines as the base primitive.

contingencies 6y ago

The fonts on this page changed at least three times while I was reading it. Never seen that before. Points for effort!

CJefferson 6y ago

One of my biggest irritations is the tiny size of default stacks in 64-bit OSes. They don't really seem to have grown significantly while both physical memory and address space size have grown massively. I write a bunch of algorithms which would most naturally be written recursively, but I have to go out of my way to make sure they have enough stack. Is there a good reason not to give the main thread of every program on a 64-bit OS 1GB of virtual address space?

tempodox 6y ago
On a Unix-like OS you can do ulimit -s <stack-size-in-KiB> At least you only have to set it once per shell instance; put it in your shell init file (bashrc or whatever).
- CJefferson 6y ago
  The problem is, it's hard to distribute libraries which want lots of stack space, because not everyone will do that. In Rust (where threadsafety is easy and cheap), I tend to just spin up a thread of known (large) stack size, and do computations there.
  - tempodox 6y ago
    I see. And the end user might not even know that library is built into the tool they use, or know how to alter the stack size limit on their machine. So I can't think of a better solution either.
- ufo 6y ago
  Can a process increase their own stack limit or do they need to spawn a child process with a higher limit?
ufo 6y ago
The other question I always had is why do we need to have a fixed limit for the stack. Why can't it grow automatically as needed, just like the heap?

taeric 6y ago

Having recently learned the so called natural correspondence between binary trees and forests, I'm curious that I don't see that get a lot of love. Combined with threaded trees, completely stack free traversal of a tree is possible. For a forest, post order traversal is possible without a stack. My guess is that is a technique that has just died with the abundance of memory we have in modern machines?

abeppu 6y ago

What's needed to automate / mechanize defunctionalization? In worked examples like this one, and the Reynolds paper mentioned (which I haven't read in quite a while), it seems like the author has to know which functions get pulled out into the same data types and eval definition, which seems to be based on tracing how the functions get moved around and eventually called. For arbitrary programs, this can be quite hard -- e.g. perhaps I generate administrative lambdas of more than one flavor, and put them in a common data structure, and based on some invariant not encoded in the type system, I know which flavor of function is being read back or evaluated when. I'm aware in a broad way that compilers / program transformation systems have used defunctionalization, but I don't quite see how without some sort of rich static analysis. Can anyone point me at what I'm missing?

ufo 6y ago

While the more obvious application of defunctionalization is to avoid stack overflow from using the implicit machine stack, another application is if you want to make your algorithm asynchronous. In many languages, it's hard to create an asynchronous recursive function that can yield from inside some deep recursion, and then resume later from where it stopped. On the other hand, if your program is rewritten to use an explicit stack plus a state machine then it's trivial to do things like pausing the execution, or printing some debug message between each step.

lobocinza 6y ago

You can disable suggestions through a extension or ad blocker and follow Youtube channels in a RSS reader. Youtube recommendations are aggressive and will keep recommending sensationalist videos related to your watch history. I don't think that content is curated besides the Youtube ad-friendly bias. I frequently clear my history to start fresh. All platforms uses some kind of collaborative filtering and have the same problem.