> 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.)
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) 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.
> 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 :)
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.
> 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.
"Defunctionalising" makes sense for performance. Ability to debug is a pro. I wanted to point out the similarity between these separate methods. In any case though, I would hope that an optimising compiler would not push onto the stack variables which are not used later in the function. Repeatedly pushing a pointer to the structure you're working on is indeed an overhead of recursive calls.
call stack growth only matters in languages that don’t have a way to recover gracefully from call stack overflow, e.g. C.
You want to convert recursive implementations into iterative implementations in those languages because you can actually handle malloc() failing instead of corrupting your call stack.
You’re right that you’re still implementing a stack no matter what, just moving it from the call stack to the heap.
Yes. My in-order tree traversal example corresponded to how I would implement it in a C-like language. As long as the person setting the question can confirm that the maximum depth is well below the stack size, it stays recursive, though.
By the way, Haskell has stack problems as well when evaluating thunks. Hence the strict foldl’.
Right... probably nearly every language has a poor call stack overflow recovery story, not only because of non-heap stacks but I don’t think it’s relatively straightforward to get the program back into a well defined state after call stack overflow. Those errors can happen on any line of code so unless every line of code is guaranteed to be atomic and a coherent state can be derived from the intermediate states, the program will be in an undefined state.
Calculating the nth member of the Fibonacci sequence is a commonly-used example of where a naive, literal-translation-to-code recursive solution is inordinately costly - so now I am trying to figure out if the method described in this article, applied mechanically to the literal recursive solution, results in an efficient solution, or merely tranfers the data complexity of its stack frames to the heap (I think you are suggesting it would result in the latter, which seems plausible to me.)
The mechanical transformation described in the article does not change the asymptotic complexity of the program. It just changes it from using an implicit (recursion) stack, to using an explicit stack.
The neat thing about that transformation, in my opinion, is that it works even for complicated algorithms. Sometimes you really do need to rewrite something to use an explicit stack, and that can be quite tricky to get right!
Remember that a linked list is not necessary worse than a stack if you use it like a stack. Linked lists are essentially the same as stacks (for a sufficiently smart compiler/runtime) if you never mutate at the middle/end and you can garbage-collect the head immediately when it's popped, letting you store the list in a contiguous structure.
Linked lists are generally implemented using pointers to other linked list nodes which reside in memory not necessarily adjacent to the original node. If the nodes are in adjacent memory, then you still have the indirection of using pointers, and the extra memory used by storing the pointers for each node. In that case, why not use a stack defined over contiguous memory in the first place?
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.
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?)
> (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.
“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.
> “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.
> “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?
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.
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".
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?
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.
I don't know either -- I understand in 32-bit OSes, as you need continuous memory space and that can be lacking (early Rust experimented with "segmented stacks", where the stack can be split, and took it out as it was too hard to do). However, in 64-bit OSes, just set up a GB of address space for the stack and be done with it.
I think this is partly Stockholm syndrome. Having a finite stack will cut off infinite recursion before it consumes the whole memory, and infinite recursion is often an error (e.g. if we get some branching logic wrong, our base case may never be taken). Over time this has become self-reinforcing:
- Recursive algorithms may hit stack limits, which makes them less attractive, so programmers are less likely to choose them
- Error rates presumably remain pretty constant, so this avoidance decreases the proportion of recursive programs that are deliberately so, and increases the proportion of recursive programs that are accidentally so
- Stack limits remain justified, due to how rarely programmers are choosing recursive approaches, and how often stack overflows help us to stop buggy programs
I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction (e.g. we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute, to stop buggy programs, those which need more time can spawn children; etc.).
I appreciate that low-level languages are operating under some pretty tight constraints (both in what's available to them, and the performance their users expect). What I find very strange is how many high-level scripting languages impose such stack limits, and don't even eliminate tail-calls. The raison d'etre for such languages is to be more ergonomic and powerful than bare-metal languages, and they don't mind sacrificing a lot of performance to do so (using interpreters, boxed values, dynamic dispatch, etc.); yet they're somehow fine with inheriting these weird restrictions from C & co.?
“we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute”
In JCL (https://en.wikipedia.org/wiki/Job_Control_Language), you can specify how much CPU time a program can spend, how many pages it can output before the OS kills it, and have to specify what files it reads and writes.
That was useful at a time when CPU time, memory and disk space were scarce and expensive, and still would be useful when sandboxing untrusted code.
It's nice to have the option of specifying such limits, but not all programs are batch jobs. For example, the correct CPU time cap for a HTTP server is infinity. Likewise, if that server were written as a recursive function then the correct stack size would be infinity:
> I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction
This is the part that irks me the most. If I have an algorithm that is neatly written as a recursive algorithm and mechanically rewrite it to use an explicit stack, that doesn't change the fact that an infinite loop is still a bug. It's just that it's going to manifest as the process using all the available RAM instead of as a stack overflow.
> yet they're somehow fine with inheriting these weird restrictions from C & co.?
Sometimes that's because the interpreter itself uses recursion. That can be convenient for whoever is implementing the interpreter, at the cost of inheriting the stack limit from C.
That said, there are also languages that enforce a recursion limit even when they don't use the C stack at all. In which case I ask the exact same question as you do.
I tend to think of it as a handy feature of recursive algorithms that encourages me to use them. Just twice in my life have I wanted to exceed the default stack size in Python, but many times have my programs crashed with a helpful stack trace when they would otherwise have locked up in an infinite loop. I do however work in a subfield where it's pretty acceptable to just say "yaaa, don't do that" to unbounded input sizes, so ymmv.
The same thing applies to anything which 'handles events', including servers, games, GUIs, CLIs, etc. In general, any time we might write a "main loop" like:
foo = lambda z: ....
bar = lambda x: ....
baz = lambda y: ....
def main():
z = init
while true:
x = foo(z)
y = bar(x)
z = baz(y)
This is equivalent to having each step perform a tail-call to the next one:
foo = lambda z: bar(....)
bar = lambda x: baz(....)
baz = lambda y: foo(....)
main = lambda : foo(init)
The latter form has better encapsulation, requires no mutable state, doesn't have stale/out-of-date variables, etc.
The fact that infinite recursion is seen as a bug, yet "while true:" loops are common, is a symptom of this negative feedback loop which keeps people from learning and using recursive solutions.
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?
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?
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.
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.
45 comments
[ 4.0 ms ] story [ 110 ms ] thread> 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.)
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) 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.
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 :)
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.
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.
You want to convert recursive implementations into iterative implementations in those languages because you can actually handle malloc() failing instead of corrupting your call stack.
You’re right that you’re still implementing a stack no matter what, just moving it from the call stack to the heap.
By the way, Haskell has stack problems as well when evaluating thunks. Hence the strict foldl’.
https://wiki.haskell.org/Stack_overflow
The neat thing about that transformation, in my opinion, is that it works even for complicated algorithms. Sometimes you really do need to rewrite something to use an explicit stack, and that can be quite tricky to get right!
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
[1] https://bartoszmilewski.com/2020/08/03/defunctionalization-a...
(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?)
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.
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.
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?
Nim may have first-class continuations in the not too far future as well https://github.com/nim-lang/RFCs/issues/295
I'm still evaluating and comparing CPS vs coroutines as the base primitive.
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?
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.
- Recursive algorithms may hit stack limits, which makes them less attractive, so programmers are less likely to choose them
- Error rates presumably remain pretty constant, so this avoidance decreases the proportion of recursive programs that are deliberately so, and increases the proportion of recursive programs that are accidentally so
- Stack limits remain justified, due to how rarely programmers are choosing recursive approaches, and how often stack overflows help us to stop buggy programs
I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction (e.g. we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute, to stop buggy programs, those which need more time can spawn children; etc.).
I appreciate that low-level languages are operating under some pretty tight constraints (both in what's available to them, and the performance their users expect). What I find very strange is how many high-level scripting languages impose such stack limits, and don't even eliminate tail-calls. The raison d'etre for such languages is to be more ergonomic and powerful than bare-metal languages, and they don't mind sacrificing a lot of performance to do so (using interpreters, boxed values, dynamic dispatch, etc.); yet they're somehow fine with inheriting these weird restrictions from C & co.?
In JCL (https://en.wikipedia.org/wiki/Job_Control_Language), you can specify how much CPU time a program can spend, how many pages it can output before the OS kills it, and have to specify what files it reads and writes.
That was useful at a time when CPU time, memory and disk space were scarce and expensive, and still would be useful when sandboxing untrusted code.
It's nice to have the option of specifying such limits, but not all programs are batch jobs. For example, the correct CPU time cap for a HTTP server is infinity. Likewise, if that server were written as a recursive function then the correct stack size would be infinity:
This is the part that irks me the most. If I have an algorithm that is neatly written as a recursive algorithm and mechanically rewrite it to use an explicit stack, that doesn't change the fact that an infinite loop is still a bug. It's just that it's going to manifest as the process using all the available RAM instead of as a stack overflow.
> yet they're somehow fine with inheriting these weird restrictions from C & co.?
Sometimes that's because the interpreter itself uses recursion. That can be convenient for whoever is implementing the interpreter, at the cost of inheriting the stack limit from C.
That said, there are also languages that enforce a recursion limit even when they don't use the C stack at all. In which case I ask the exact same question as you do.
The fact that infinite recursion is seen as a bug, yet "while true:" loops are common, is a symptom of this negative feedback loop which keeps people from learning and using recursive solutions.
My guess is that is a technique that has just died with the abundance of memory we have in modern machines?
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?
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.