Prolog translation of Lisp's tail-recursion

Question

I have a question that is a followup to a previous topic, Should I avoid tail recursion in Prolog and in general?

In the above linked article , user false provided this code example and this explanation ...

Back in the 1970s, the major AI language was LISP. And the corresponding definition would have been ...

  (defun addone (xs)
    (cond ((null xs) nil)
      (t (cons (+ 1 (car xs))
           (addone (cdr xs))))))

... which is not directly tail-recursive: The reason is the cons: In implementations of that time, its arguments were evaluated first, only then, the cons could be executed. So rewriting this as you have indicated (and reversing the resulting list) was a possible optimization technique.

In Prolog, however, you can create the cons prior to knowing the actual values, thanks to logic variables. So many programs that were not tail-recursive in LISP, translated to tail-recursive programs in Prolog.

The repercussions of this can still be found in many Prolog textbooks.

My question is : what is a good Prolog translation of the above LISP code ?

EDIT: added the example of the lisp code in action and the lisp documentation describing the various lisp functions .

example of addone in action

1 > (addone '(1 2 3))

(2 3 4)

2 > (addone '('()))

> Error: The value 'NIL is not of the expected type NUMBER.
> While executing: CCL::+-2, in process listener(1).
> Type :POP to abort, :R for a list of available restarts.
> Type :? for other options.

3 > (addone '(a b c))

> Error: The value A is not of the expected type NUMBER.
> While executing: CCL::+-2, in process listener(1).
> Type :POP to abort, :R for a list of available restarts.
> Type :? for other options.

3 > ^C

documentation of lisp features

cons object-1 object-2 => cons

Creates a fresh cons , the car of which is object-1 , and the cdr of which is object-2 .

Examples

  (cons 1 2) =>  (1 . 2)
  (cons 1 nil) =>  (1)
  (cons nil 2) =>  (NIL . 2)
  (cons nil nil) =>  (NIL)
  (cons 1 (cons 2 (cons 3 (cons 4 nil)))) =>  (1 2 3 4)
  (cons 'a 'b) =>  (A . B)
  (cons 'a (cons 'b (cons 'c '()))) =>  (A B C)
  (cons 'a '(b c d)) =>  (A B C D)

(car x) => object

If x is a cons , car returns the car of that cons . If x is nil , car returns nil .

(cdr x) => object

If x is a cons , cdr returns the cdr of that cons . If x is nil , cdr returns nil .

cond {clause}* => result*

clause::= (test-form form*)

Test-forms are evaluated one at a time in the order in which they are given in the argument list until a test-form is found that evaluates to true .

If there are no forms in that clause, the primary value of the test-form [ed: the first value of the test-form , or nil if there are no values] is returned by the cond form. Otherwise, the forms associated with this test-form are evaluated in order, left to right, as an implicit progn, and the values returned by the last form are returned by the cond form.

Once one test-form has yielded true, no additional test-forms are evaluated. If no test-form yields true, nil is returned

See http://www.lispworks.com/documentation/HyperSpec/Body/m_cond.htm#cond for more information .

defun function-name lambda-list form* => function-name

See http://www.lispworks.com/documentation/HyperSpec/Body/m_defun.htm#defun for more information .

t => T

t =>  T 
(eq t 't) =>  T
(case 'b (a 1) (t 2)) =>  2

Answer 1

Here's a rendition in Prolog of the given Lisp algorithm. Note that Lisp is functional and a Lisp function can return values. This isn't the case in Prolog, so you need two arguments.

A direct implementation, which is not relational, would be:

addone([], []).
addone([H|T], [H1|T1]) :-
    H1 is H + 1,
    addone(T, T1).

Note that the [H1|T1] argument in the head of the second predicate clause corresponds to (cons H1 T1) in Lisp.

This can also be done using maplist, which steps a little bit away from the original Lisp implementation, but Lisp does have list mapping functions which could be used to create a Lisp implementation that would look more like this:

addone_element(X, X1) :- X1 is X + 1.
addone(List, List1) :- maplist(addone_element, List, List1).

In Prolog this can be made more relational using CLP(FD) which is useful for reasoning over integers:

:- use_module(library(clpfd)).

addone([], []).
addone([H|T], [H1|T1]) :-
    H1 #= H + 1,
    addone(T, T1).

And the maplist version:

addone_element(X, X1) :- X1 #= X + 1.
addone(List, List1) :- maplist(addone_element, List, List1).

Answer 2

A direct translation:

(defun addone (xs)
    (cond ((null xs) nil)
          (t (cons (+ 1 (car xs))
                   (addone (cdr xs))))))

is

addone( XS, RESULT) :-
   (   XS = [],              % null XS ? then:
       RESULT = []           % 
   ;
       XS = [CAR | CDR],     % else:
       R is 1 + CAR,         % calculate the two
       addone( CDR, S)       %          fields         % almost TR,
       RESULT = [R | S],     % and cons them up        % save for this cons
   ).

But, transformed,

(defun addone (xs)
    (let ((result))
      (cond ((null xs) (setf result nil))
            (t         (setf result (cons (+ 1 (car xs))
                                          (addone (cdr xs))))))
      result))
=
(defun addone (xs)
    (let ((result))
      (cond ((null xs) (setf result nil))
            (t         (setf result (list nil))
                       (setf (car result) (+ 1 (car xs)))
                       (setf (cdr result) (addone (cdr xs)))))
      result))
=
(defun addone (xs &optional (result (list nil)))        ; head sentinel
      (cond ((null xs))
            (t         (setf (cdr  result) (list nil))
                       (setf (cadr result) (+ 1 (car xs)))
                       (addone (cdr xs) (cdr result))))    ; almost TR
      (cdr result))                                    ; returned but not used
=
(defun addone (xs &aux (result (list nil)))
    (labels ((addone (xs result)
              (cond ((null xs))
                    (t (setf (cdr  result) (list nil))
                       (setf (cadr result) (+ 1 (car xs)))
                       (addone (cdr xs) (cdr result))))))   ; fully TR
        (addone xs result))
    (cdr result))

it is, fully tail recursive,

addone( XS, RESULT) :-
   (   XS = [], 
       RESULT = []
   ;
       XS = [CAR | CDR],
       RESULT = [R | S],     % cons two empty places, and
       R is 1 + CAR,         %   fill'em 
       addone( CDR, S)       %   up                          % fully TR
   ).

Boxing / head sentinel is used so we can have settable pointers in Common Lisp, but in Prolog this isn't needed -- Prolog's logical variables are directly settable (once), named pointers.

This is also the reason why Prolog's transformation is so much smaller and easier than Lisp's. All it took was moving one line of code up a notch or two (and it could've been one just the same).