5 ms·
Tail recursion, but modulo cons
- seles 5y agoThis kind of feels like using continuations, here is a Haskell demo of the concept: myMap = myMapHelper id myMapHelper cont f [] = cont [] myMapHelper cont f (x:xs) = myMapHelper (cont . (f x :)) f xs Of course this actually makes things slower in Haskell, either due to the growing continuation or existing optimizations in Haskell
- wgd 5y agoThere's a fascinating relationship between tail recursion and continuations, because any non-tail-recursive function call can in principle be made tail-recursive through conversion to explicit continuation-passing style. For added fun, that continuation can then be defunctionalized [1] back into a data structure. It can be argued that TRMC as implemented in the linked post is simply a special case of this more general transformation. [1] https://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html https://www.pathsensitive.com/2019/07/the-best-refactoring-y...
- Rusky 5y agoIndeed, it's a special case that relies on associativity, which is why it also works for + and *: https://www.cs.ox.ac.uk/jeremy.gibbons/publications/continued.pdf https://www.cs.ox.ac.uk/jeremy.gibbons/publications/continue...
- seles 5y agoCool, I had heard of defunctionalizing CPS before but never dared to try it. I tried to follow along defunctionalizing map, but it is a bit different since it has a return value, whereas in the video it is a void. What I ended up with was equivalent to building a list and then reversing it. So it did infact work (all functions were tail callable). This was mentioned in the article as inferior to the author's final product though. So I think it is a bit different to a special case of CPS defunctionalization optimization. Although there may have been other ways to deal with the return value in continuations...
- wahern 5y ago> because any non-tail-recursive function call can in principle be made tail-recursive through conversion to explicit continuation-passing style. I mean, the call stack is literally just a convention for storing continuation state. The C standard describes the effect of calling another function "suspend[ing]" execution of the current function.[1] What differentiates CPS from regular recursive programming is that this behavior isn't maximally transparent, and typically is also less efficient in machine code. All of these modes of behavior were mostly well understood early on, but it took several years for the literature to rigorously distinguish and define them, and then complete the circle by declaring equivalencies that nobody ever seriously doubted in the first place. The upshot is we're like in the 4rd or 5th cycle of people rediscovering things like asynchronous programming. During previous epochs people just beefed over different but functionally similar terminology: e.g. interrupts vs polling (in that case, a carry over from hardware terminology). Unix's awkward signals and then threading APIs being a legacy of those (not very distant) debates. One of the first battles was whether to build recursion into languages at all, rather than requiring explicit management of call state, relying on global space for the fast path that didn't require recursion. Today the dispute is CPS vs blocking, but it's the same basic dichotomy and arguably we're just rehashing the same battle over again, without even changing the terminology. The blocking/polling/recursion camp seems to invariably win out. The whole purpose of general purpose programming languages is to hide basic code flow management, particularly call state, behind an abstraction, and in the vast majority of code written in these languages, even highly concurrent code, such state bookkeeping is obnoxious noise when it leaks through too heavily. It's ironic when some language aficionados (Rust, Javascript, etc) justify it by saying it's about maximizing performance or making things explicit, ignoring the fact that almost all of this "efficient" and "transparent" code is running within a process (also variously described as "threads" and "coroutines" in bygone eras) isolated with hardware-supported virtual memory, all of which are predicated on transparent, blocking behavior. IOW, preferences have already been established and then punctuated multiple times, now we're just haggling over the finer details. [1] C11 6.2.4p6: "... Entering an enclosed block or calling a function suspends, but does not end, execution of the current block...."
- yccs27 5y ago> any non-tail-recursive function call can in principle be made tail-recursive through conversion to explicit continuation-passing style This sounds great, but in the end you just construct your own call stack under the guise of chaining continuations together. The real optimization happens when the continuations have structure, so that you can merge the composition of multiple continuations into one. And once you represent the continuation with its data, you just get "accumulator-passing style".
- YeGoblynQueenne 5y agoInteresting, I didn't know that was a big secret in functional programming. In Prolog-like logic programming it is as far as I know standard, so for example you can write a tail-recursive call like this: ?- listing([maplist/2,maplist_/2]). :- meta_predicate apply:maplist(1,?). apply:maplist(Goal, List) :- maplist_(List, Goal). apply:maplist_([], _). apply:maplist_([Elem|Tail], Goal) :- call(Goal, Elem), maplist_(Tail, Goal). true. The code listing is from the SWI-Prolog implementation. See below [1] for a detailed explanation of the Prolog syntax. Here's an example of calling maplist/2 with the predicate number/1 as the "Goal": ?- maplist(number, [1,2,3]). true. ?- maplist(number, [1,2,c]). false. number/1 fails if its input is not a number. In the listing of maplist/2, note how [Elem|Tail] is in the _first_ literal of the second clause (maplist_([Elem|Tail], Goal)), rather than in the third, recursive literal (maplist_(Tail, Goal)). This is a piece of Prolog black magick and always very difficult to explain, not least because it's not visible in the standard debugger, but the Elem in [Elem|Tail] is a _new_ variable that is instantiated ("bound") _after_ the recursion is over, from the result of calling the Goal passed in as the second argument to maplist_/2 (call(Goal, Elem)). Once the recusion "hits" the base-case (maplist([], _)) at the end of deconstructing the input list, the stack "unwinds" and calculates the result of each call to Goal (call(Goal, Elem)) then binds it to Elem. Thus, List is constructed _in the right order_ and there is no need to reverse it at the end. Indeed, during recursion, List is bound to a list "with holes" as in the article. _______________ [1] This is to explain the source code in the listing above. First, by convention we write the names of predicates in Prolog followed by their arity (their number of arguments), so maplist is maplist/2 and maplist_ is maplist_/2. The "apply:" prefix is the identifier of the module where the predicates maplist/2 and maplist_/2 are defined. maplist(1,?) means that maplist/2 is a "meta_predicate" that takes as argument the symbol of another predicate with an arity of 1. The "?" in maplist(1,?) means that the second argument of maplist/2 does not take any arguments. maplist/2 is the high-level "interface" predicate that takes as arguments a Goal (the name of a predicate that must accept a list as its single argument) and a List. The predicate maplist_/2 is the lower-level "auxiliary" predicate used to abstract the implementation from the user-level code. The syntax [Elem|Tail] used in maplist_ "cons" the head of a list (Elem) to its tail (Tail), so [a|[b,c]] is the list [a,b,c].
- triska 5y agoOne interesting aspect of logic programming languages like Prolog is that many commonly used relations are naturally tail recursive, even though the corresponding functions in functional languages are not naturally tail recursive. For instance, the map example shown in the article is naturally defined as a Prolog predicate: maplist(_, [], []). maplist(Goal, [X|Xs], [Y|Ys]) :- call(Goal, X, Y), maplist(Goal, Xs, Ys). The rule is tail recursive, because the recursive invocation is the final goal in the clause. Therefore, if Goal is deterministic, tail call optimization can be applied, making the entire predicate run in O(1) local stack, independent of the length of the list. Sample invocation: ?- maplist(char_code, "abcdefghijk", Cs). Cs = [97,98,99,100,101,102,103,104,105,106,107]. In Prolog, this is possible precisely because we can refer to data structures that are not yet fully known. The article refers to this as a "hole". In the case above, we can talk about a term of the form [X|Xs], i.e., '.'(X, Xs), and [Y|Ys] in the clause head even though neither Y nor Ys is yet known. append/3 is another example of a relation that is naturally tail recursive in Prolog, but not naturally tail recursive in functional programming languages. The "padding" example in the article can be directly translated to a Prolog definite clause grammar (DCG). For example: :- use_module(library(dcgs)). pad(0, _, Str) --> seq(Str). pad(s(N), Padding, Str) --> seq(Padding), pad(N, Padding, Str), seq(Padding). Sample queries and answers: ?- phrase(pad(s(s(0)), " ", "hello"), Ls). Ls = " hello ". ?- phrase(pad(s(s(0)), Ps, "hello"), " hello "). Ps = " " ; false. Tested with Scryer Prolog.
- melony 5y agoDoesn't Haskell have the same List pattern matching/de-structuring for the "holes"?
- yawaramin 5y agoJust as a point of reference, OCaml recently landed TRMC into the core compiler: https://github.com/ocaml/ocaml/pull/9760 https://github.com/ocaml/ocaml/pull/9760 It should ship in version 5.
- melony 5y agoIs this similar to Racket's stack replacement infinite tail recursion mechanism?
- ska 5y agoIsn't that just standard TCO (scheme, unusually, mandates this in the standard)?
- melony 5y agoNo, Racket's work for non tail call recursion too. The standard recursive factorial won't overflow in Racket. According to: https://news.ycombinator.com/item?id=30420605 https://news.ycombinator.com/item?id=30420605
- jfmengels1 5y agoIndeed, though from a conversation with the author, it's only implemented for a subset of what was described in the post, specifically only for data construction. (Conversation: https://twitter.com/let_def/status/1485313834764095488 https://twitter.com/let_def/status/1485313834764095488)
- deleted 5y ago[deleted]
- thaumasiotes 5y ago> Yeah, if you run this function, you will notice that the result is in the reverse order of what they should be ([ 3, 2, 1 ] instead of [ 1, 2, 3 ] for instance). And that’s because the last x will be at the very start of the accumulator, and inversely the first x will be at the very end. > So… we’ll just add a small List.reverse on the accumulator at the very end… It will hurt performance quite a bit but correctness is more important. > Surely we can do better than this, right?! Let’s take a look at how List.map is implemented in the core library. > That’s surprisingly simple. The order is right because the list is being visited in reverse order (that’s what foldr does, in contrast to foldl). But we need to look at the implementation of List.foldr to see if we can reuse the same idea for our custom functioOH GOD CLOSE THE TAB! > Ugh… if you’ve opened the link, you know that we have gone far from the elegant solution described at the beginning. But List.foldr is using almost exactly the same strategy that is considered and rejected in the early draft of mapHelper. Visit the list in reverse order and then reverse the result. (Technically, reverse the input list and then visit it in reverse order, instead of visiting the input list in reverse order and then reversing the output. foldr's output isn't a list.) The only difference is that List.foldr will visit the first ~2000 elements of the list in correct order, just in case, and if the list is still going it will give up and reverse it at that point. How far is that from the solution described at the beginning?
- jfmengels1 5y agoThe mapHelper version that was rejected changed the order. The one that did `List.reverse` had the correct order, and this one is equivalent to the List.foldr solution. The only difference is List.foldr's implementation is more performant (up to a certain number of elements as you say). If this is not what you asked, then I did not understand the question.
- thaumasiotes 5y agoYour post goes in several stages. First you create an accumulator version of map that reverses the result: > It’s a bit more verbose, but it’s not that bad. Honestl… Sorry, what did you say? Wrong order? Oh, right… Then you modify that version to accumulate a reversed result, but reverse it (into the correct order) before returning it: > we’ll just add a small List.reverse on the accumulator at the very end… It will hurt performance quite a bit but correctness is more important. Then you reject that solution: > Surely we can do better than this, right?! Let’s take a look at how List.map is implemented in the core library. > The order is right because the list is being visited in reverse order (that’s what foldr does, in contrast to foldl). But we need to look at the implementation of List.foldr to see if we can reuse the same idea for our custom functioOH GOD CLOSE THE TAB! You then complain that the implementation of foldr is too complex to generalize. But it's the same thing you've already explained: accumulate the result, but reverse the list so that when you report the result it's in the right order. This will easily generalize to any other function you care to write. The standard progression, by the way, as other comments in the thread have pointed out, goes from a recursive solution, to a tail-recursive solution, to a tail-recursive solution with an accumulator, to a tail-recursive solution written in continuation-passing style. Continuations provide the structure to hold your "holes" until they can be filled in. Why didn't you mention this?
- ir193 5y agois it reasonable to have a keyword for tail-recusive return? basically it means I'm writing a tail recursive function and give me compile error if it occurs at non-tai-recursive positions
- jfmengels1 5y agoPotentially yes. The question then arise: does it ever make sense not to add that keyword, and should you get linter/compiler warnings when it's not used? In which case, there will be little gain. My mind is not yet made up on this to be honest. I feel like it would be valuable, but it feels weird when I think about it some more.
- gampleman 5y agoI’m wondering in the Elm context if the compiler implemented this technique could it make a non stack safe recursion a compile time error? And if it did, how restrictive would that be in practice?
- jfmengels1 5y agoI think it could yes if you had a keyword for adding the guarantee. If you didn't have a keyword, then all functions would have to be made stack-safe, which is I think a lot to ask the users in some cases, especially when the language doesn't give you all the tools for it (I think CPS does not work for instance in Elm, currently investigating that a bit). If you have a keyword, then it would be as restrictive as you'd want it to be I imagine?
- seanhunter 5y agoI wish every article that wanted an example of recusion didn't immediately reach for fibbonacci or factorial, both of which are much better expressed by just calculating iteratively from the bottom and then memoizing the results for future calls. When I started to learn programming, for ages I thought recursion was just stupid because every single example I saw in a textbook could better be written without recursion. For goodness sake if you want to write an example of recursion, walk a tree. That's a great example of a use of recursion given that the iterative version is much clumsier to express.
- tome 5y agoFibonacci is better memoized because it changes an exponential time algorithm into a linear time one, but I don't see why factorial would be better memoized.
- seanhunter 5y agoIf you memoize you turn either of them into constant time. So it's an improvement to factorial (albeit less dramatic) and in practise if you later on reach for a higher factorial than you have previously calculated you don't need to start from scratch which is a real-world speedup although the O is still linear. That said obviously the decision of whether to memoize depends on whether the function is going to be called more than once. If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods.
- thaumasiotes 5y ago> If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods. I don't think that's true; you're pretty much always better off calculating Fibonacci numbers by starting from F_0 and counting up than by using the closed-form solution.
- tome 5y ago
- bjoli 5y agoGuile and racket does stack resizing, so one can do recursion until they run out of memory. This is pretty neat, as it changes how we write code. No more accumulators and reverses, since the simple way to write things is usually faster.