Tail recursion, but modulo cons | Hacker News Reader

Tail recursion, but modulo cons

jfmengels.net

76 pointstodsacerdoti36 comments

One 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.

Doesn't Haskell have the same List pattern matching/de-structuring for the "holes"?

I 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.

Fibonacci 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.

If 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.

> 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.

Are you sure? The closed form solution can be evaluated in logarithmic time whereas counting up takes linear time.

Here's an article talking about it:

https://towardsdatascience.com/why-is-the-closed-form-of-the...

It covers a couple of points (all of this is me summarizing the article I just linked; I'm not an expert in numeric computing):

- The closed-form expression for Fibonacci numbers involves an irrational number. But we can't do computations on irrational numbers; we're stuck with rational approximations. (Such as IEEE floating point.) Since computing an early Fibonacci number involves raising ϕ to a high exponent, the error involved in giving ϕ a finite representation rapidly compounds, corrupting the result. (According to this article, errors will become visible after F_100. That's quickly enough that you'd be justified in just having a lookup table for the first 100 Fibonacci numbers, which would be much faster than computing them as needed.)

- You can represent the Fibonacci recurrence relation directly in matrix form. This is just the counting-up method written down a different way. Each Fibonacci number is the product of the constant matrix [[1 1] [1 0]] with the vector consisting of the previous two Fibonacci numbers.

- You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic.

> You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic.

Right, and repeated squaring can give you the answer to the exponentiation in logarithmic time.

> If you memoize you turn either of them into constant time.

At the risk of stumbling into the No True Memoization fallacy, I wouldn't consider that memoizing -- at least not in the dynamic programming sense. To get O(1), you're not temporarily tabling the results during a single run of the algorithm; rather you're building a semi-permanent database of answers and (effectively, in an amortized sense) discarding the algorithm altogether. I think that's formally known as the "just Google it" approach to optimization. :) From a DP perspective you can get O(N) from memoization on open-form Fibonacci, and no gain on open-form factorial, because the lookup table is ephemeral.

This is probably the most "hackernews" conversation I've ever had but as far as I've ever seen the term used, "memoization" is not restricted to temporarily tabling the results during a single run of the algorithm but used to mean any caching of results of an expensive pure function for future use. You seem to call that a "semi-permanent database of answers". Here is the original memoization paper [1] where he is using a constant-time table lookup exactly as I envisage in this case rather than only tabling results during a single invocation of the algorithm. Ironically he uses it to memoize a recursively-defined factorial function.

[1] https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...

lol, yes, we are at Peak HN right now. :) Michie (1968) wins the debate, without a doubt! Thanks for sharing your point of view, and the article.

Factorial was taken as an example (in this post) exactly because it is such a common textbook example, which also happens to be bad example in the sense that it is not stack-safe.

As for walking a tree, I agree, but this optimization does not work well with trees shrug, making lists a nicer example in my opinion.

As a teaching method, I feel that factorial is a relatively good example because it is fairly easy to grok in your head or on paper. Recursing through a tree adds a lot of mental overhead, so I feel like it could be a follow-up example to factorial, but it's probably too hard as an initial example. Also, switching to a stack-safe function using recursion is again much easier for factorial than it would be for traversing a tree.

Maybe this is a neurodiversity thing but for me going backwards to calculate something like a factorial recursively is hard to think about. It's exactly the same as if someone was trying to teach something about structural integrity in architecture and they said "OK you want to build a staircase. Imagine you're hovering in the air and you start to build stairs down..." I can't concentrate on whatever point they're trying to make with the example because I can't really get over the fact that it's easier to build from the bottom and not hover in the air in the first place.

Maybe try to imagine it from the architects point of view first, instead of from the brick layers? Like in an isometric drawing, for instance?

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

The 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.

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

Oh ok. I didn't mean to "reject" the solution, since that's what I see done most of the time in practice, because of the current limitations of the language regarding stack safety.

For foldr, I mean that specific implementation - which fully prioritizes performance and uses several levels of unwrapping, etc. - is hard to reuse for functions we wish to maintain. Using List.foldr is fine (when applicable, which is not always), but copy-pasting its implementation to adapt it to our need isn't, from a maintenance point of view.

On the topic of continuation-passing style, I don't personally believe that the solution I've highlighted uses CPS. At least from my shallow understanding, CPS uses functions, which my solution doesn't. CPS can easily emulate TRMC, but TRMC works differently (and is more performant though is applicable to less situations).

My understanding of CPS is maybe shallow, so I could be missing some understanding, but to me they're different and therefore not part of my explanation.

> Continuations provide the structure to hold your "holes" until they can be filled in

That's one mental model to view it, but there isn't actually any "real" hole to fill with CPS, whereas with TRMC there is (at least for data construction).

Guile 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.

This 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

There'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-y...

Indeed, 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/continue...

Cool, 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...

> 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...."

> 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".

Just as a point of reference, OCaml recently landed TRMC into the core compiler: https://github.com/ocaml/ocaml/pull/9760

It should ship in version 5.

Is this similar to Racket's stack replacement infinite tail recursion mechanism?

Isn't that just standard TCO (scheme, unusually, mandates this in the standard)?

No, 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

Indeed, 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)

is 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

Potentially 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.

I’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?

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

Interesting, 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].

Reply on news.ycombinator.com