recursion in prolog (on lists)

Question

can someone please help me just w/ the basics on performing recursive prolog functions..

append([],X,X). % base
append([X|Y],Z,[X|W]) :- append(Y,Z,W). %recursive

% base case
addup([], 0). % sum of the empty list of numbers is zero

% recursive case: if the base-case rule does not match, this one must:
addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   % add up the numbers in RestOfList
    Total is FirstNumber + TotalOfRest.

Can someone explain either in English or in C/C++/Java whatever.. how the steps. I actually would prefer to see something like append or reverse.. I'm mostly just manipulating lists of variables instead of integers.. (I've tried to work through append like 10 times.. ugh).

Answer 1

You want to see it in C++?

int const a[] = {1,2,3,4,5};
size_t const N = sizeof(a) / sizeof(int);

void addup(size_t depth, int &total)
{
    if (depth == N)   // base case; sum of no numbers is zero
        total = 0;
    else {            // recursive case
        int first_number = a[depth];
        size_t rest_of_list = depth+1;
        int total_rest;
        addup(rest_of_list, total_rest);
        total = first_number + total_rest;
    }
}

I'll immediately admit that this is horridly ugly C++, but it's direct translation of the Prolog program, except that lists are simulated using arrays and a depth counter.

Answer 2

Recursion in prolog is pretty much identical to recursion in any other language. The trick with prolog is that

• every variable is local, and,
• once unified, variables cease to be variables. They can never change value.

This means that you'll often need to build what I'll call "worker" predicates that do that the actual work required and carry around 1 or more variables that act as working storage. Here is an implementation of sum/2 to sum a list of integers:

% sum/2
sum( [] , 0 ).
sum( [X|Xs] , Total) :-
  sum(Xs,X,Total).

% sum/3 (worker predicate)
sum( [], Total, Total ).
sum( [X|Xs] , Subtotal , Total ) :-
  NewSubTotal is Subtotal + X ,
  sum( Xs , NewSubTotal , Total ).

Here is an implementation in ANSI C that closely mirrors the above prolog code:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
// linked list structure
typedef struct listnode
{
  int              value ;
  struct listnode *next  ;
} LISTNODE ;

// core recursive worker function
int sum_core( int subtotal , LISTNODE *list )
{
  LISTNODE *head ;
  LISTNODE *tail ;
  int       list_item ;

  if ( list == NULL ) return subtotal ;

  head      = list        ;
  tail      = list->next  ;
  list_item = head->value ;

  return sum_core( subtotal + head->value , tail ) ;

}

// external interface
int sum( LISTNODE *list )
{
  LISTNODE *head      ;
  LISTNODE *tail      ;
  int       list_item ;

  if ( list == NULL ) return 0 ;

  head      = list        ;
  tail      = list->next  ;
  list_item = head->value ;

  return sum_core( list->value , tail ) ;

}

int main ( int argc , char * argv[] )
{
  LISTNODE *list ;
  int       total ;

  list                   = malloc(sizeof(LISTNODE)) ; list->value             = 1 ;
  list->next             = malloc(sizeof(LISTNODE)) ; list->next->value       = 2 ;
  list->next->next       = malloc(sizeof(LISTNODE)) ; list->next->next->value = 3 ;
  list->next->next->next = NULL ;

  total = sum( list ) ;

  return ;
}

Answer 3

The free online book "Learn Prolog Now" has a section dedicated to explaining the steps that append performs:

http://cs.union.edu/~striegnk/learn-prolog-now/html/node47.html#subsec.l6.defining.append

Answer 4

append(A, B, R) means that R is the result of appending A to B.

The base case

append([], X, X).

says that if A = [] and B = X then R = X = B: an empty list A appended to some other list B is equal to B.

The recursive case

append([X | Y], Z, [X | W]) :- append(Y, Z, W).

says that if A = [X | Y] is a non-empty list to append to B = Z, and if W is Y appended to Z, then R = [X | W].

Another way of saying it is: to append a non-empty list A to another list B, first append the tail of A to B and then add the head of A to the front of the list.