[HN Gopher] Tail recursion, but modulo cons
___________________________________________________________________
Tail recursion, but modulo cons
Author : todsacerdoti
Score : 44 points
Date : 2022-02-28 07:31 UTC (15 hours ago)
(HTM) web link (jfmengels.net)
(TXT) w3m dump (jfmengels.net)
| seles wrote:
| 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
| wgd wrote:
| 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...
| YeGoblynQueenne wrote:
| 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].
| triska wrote:
| 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 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.
___________________________________________________________________
(page generated 2022-02-28 23:01 UTC)