One interesting aspect of logic programming languages like Prolog is that many commonly used relations are naturally tail recursive, even though the correspondi

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.