Previous Table of Contents Next


6.4.8. Reading Clauses from the Terminal

Prolog programmers occasionally want to type in clauses to the interpreter directly. It may seem natural to do this by simply typing the clause at the query prompt. However, because of the way that Prolog parses terms read in (see section 6.3.11.5), it parses a rule a :- b as a term :-(a,b) and takes it as a query on a (probably nonexistent) predicate :-.

The trick to know for typing in clauses directly is that the file called user is connected to the user’s terminal. Thus to enter clauses from the terminal, it is possible to just consult the file user with the query [user], type in the clauses, and then end with an end-of-file indication. After the end-of-file, the interpreter returns to its top-level query loop, having processed the clauses.

6.4.9. Using the Dash in a Symbol

A common mistake, especially for Lisp programmers, is to try to use the dash (-) in a symbol such as a predicate or constant name. A dash is not a valid character to use in an identifier, but it is a valid symbol in its own right (see section 6.3.11.3). This leads to some subtle bugs.

When used in a predicate name at the beginning of a clause, the bug manifests itself as the user defining the dash predicate. For instance, the clause

   new-value(X) :- read(X).

is parsed the same as the clause

   ‘-’(new,value(X)) :- read(X).

This may go undetected even if the user calls the new-value predicate because the user will really still be calling the - predicate. With enough such names, the multiple clauses for the hidden - predicate will begin to interfere with one another, and the user will begin having obscure problems.

If, in a debugger trace of an execution of a Prolog predicate, you start encountering calls to the - predicate, this should be an indication that you have run afoul of this bug. The solution, of course, is to traverse your program and replace the incorrect dashes with underscores.

6.5. Examples

Seeing examples of a programming language is sometimes the greatest help in learning the language. I therefore present in the following sections five longer examples of Prolog code: a balanced tree package, a prime number finder, a utility for checking C programs for memory leaks, an implementation of the popular computer game Life, and a simple pure Lisp interpreter.

6.5.1. A Balanced Tree Package

In every programming language, we often want to associate keys with values. We could do this in Prolog by lists with elements of the form value(Key, Val), but this is the equivalent of using a linear list. Much more efficient for this purpose is a balanced tree, or Adelson-Velski’i-Landis (AVL) tree.

This Prolog treatment is based on Wirth’s work (1976). A tree is represented either as the empty tree emptytree or as a tree of the form tree(Key, Val, Height, Left, Right), where Key and Val are the key and value of this node, Left and Right are the trees containing keys that are less (respectively, greater) than Key, and Height is the height of the tree. The user does not have to know about the representation, however; she can just call init/1 to get an empty tree and call predicates such as add/4 to add nodes and find/3 to find values of keys.

Listing 6.3. A Balanced tree package.

   %%%%%%%%%%%%%%%%%%%%
   % Find
   %%%%%%%%%%%%%%%%%%%%

   % find(Tree, Key, Val):  Key appears, associated with Val, in Tree
   find(tree(Key,Val,_,_,_), Key, Val) :-
    !.
   find(tree(Thiskey,_,_,Left,Right), Key, Val) :-
    Key < Thiskey,
    !,
    find(Left, Key, Val).
   find(tree(_,_,_,_,Right), Key, Val) :-
    find(Right, Key, Val).


   %%%%%%%%%%%%%%%%%%%%
   % Add
   %%%%%%%%%%%%%%%%%%%%

   % add(Tree, Key, Val, Newtree):  add Key associated
   % with Val to Tree, yielding Newtree.
   add(emptytree, Key, Val, tree(Key,Val,1,emptytree,emptytree)).
   add(tree(Thiskey,Thisval,_,Left,Right), Key, Val, Newtree) :-
    Key < Thiskey,
    add(Left, Key, Val, Newleft),
    height(Newleft, LH),
    height(Right, RH),
    construct_balanced(Thiskey, Thisval, Newleft, Right,
                  LH, RH, Newtree).
   add(tree(Thiskey,Thisval,_,Left,Right), Key, Val, Newtree) :-
    Key > Thiskey,
    add(Right, Key, Val, Newright),
    height(Left, LH),
    height(Newright, RH),
    construct_balanced(Thiskey, Thisval, Left, Newright,
                  LH, RH, Newtree).

   % height(Tree, H):  H is the height of Tree.
   height(emptytree, 0).
   height(tree(_,_,H,_,_), H).

   % construct_balanced(K, V, L, R, LH, RH, Newtree):  construct
   % a balanced tree Newtree out of K, V, L, and R,
   % where L and R are trees, all the keys of L are less than K,
   % all the keys of R are greater than K, V is the value to be
   % associated with K, and LH and RH are the heights of L and R.
   construct_balanced(K, V, L, R, H, H, tree(K,V,H1,L,R)) :-
    !,
    H1 is H+1.
   construct_balanced(K, V, L, R, LH, RH, Newtree) :-
    LH is RH+1, % left is one taller
    !,
    H1 is LH+1,
    Newtree = tree(K,V,H1,L,R).
   construct_balanced(K, V, L, R, LH, RH, Newtree) :-
    RH is LH+1, % right is one taller
    !,
    H1 is RH+1,
    Newtree = tree(K,V,H1,L,R).
   % Otherwise, tree would be out of balance if constructed as above.
   construct_balanced(K, V, L, R, LH, RH, Newtree) :-
    LH > RH, % by more than one
    L = tree(LK,LV,LH,LL,LR),
    height(LL, LLH),
    height(LR, LRH),
    LLH > LRH, % left subtree is 1 taller than right
    !,
    H is LLH + 1,
    Newtree = tree(LK,LV,H,LL,tree(K,V,LLH,LR,R)).
   construct_balanced(K, V, L, R, LH, RH, Newtree) :-
    LH > RH, % by more than one, but right subtree of L
             %  is taller than left
    !,
    L = tree(LK,LV,LH,LL,tree(LRK,LRV,LRH,LRL,LRR)),
    H is LRH+1,
    Newtree =
     tree(LRK,LRV,H,
     tree(LK,LV,LRH,LL,LRL),
     tree(K,V,LRH,LRR,R)
    ).
   % Otherwise, tree would be out of balance, and right
   % subtree taller than left
   construct_balanced(K, V, L, R, LH, RH, Newtree) :-
    R = tree(RK,RV,RH,RL,RR),
    height(RL, RLH),
    height(RR, RRH),
    RRH > RLH, % left subtree is taller than right
    !,
    H is RRH + 1,
    Newtree = tree(RK,RV,H,tree(K,V,RRH,L,RL),RR).
   construct_balanced(K, V, L, R, LH, RH, Newtree) :-
    R = tree(RK,RV,RH,tree(RLK,RLV,RLH,RLL,RLR),RR),
    H is RLH+1,
    Newtree =
     tree(RLK,RLV,H,
      tree(K,V,RLH,L,RLL),
      tree(RK,RV,RLH,RLR,RR)
    ).

   %%%%%%%%%%%%%%%%%%%%
   % newval
   %%%%%%%%%%%%%%%%%%%%

   % newval(Tree, Key, Val, Newtree):  replace the value of Key
   % in Tree by Val, yielding Newtree.
   newval(tree(Key,_,H,L,R), Key, Newval, tree(Key,Newval,H,L,R)) :-
    !.
   newval(tree(Thiskey,V,H,Left,Right), Key, Newval,
   tree(Thiskey,V,H,Newleft,Right)) :-
    Key < Thiskey,
    !,
    newval(Left, Key, Newval, Newleft).
   newval(tree(Thiskey,V,H,Left,Right), Key, Newval,
   tree(Thiskey,V,H,Left,Newright)) :-
    newval(Right, Key, Val, Newright).
   newval(emptytree, Key, Newval, _) :-
    write(‘No value currently defined for ‘), write(Key), nl,
    fail.

   %%%%%%%%%%%%%%%%%%%%
   % top-level utilities
   %%%%%%%%%%%%%%%%%%%%

   % find_or_add(Tree, Key, Val, Newtree):  confirm that Key is
   % in Tree associated with Val, or else add it yielding Newtree.
   find_or_add(Tree, Key, Val, Newtree) :-
    find(Tree, Key, Val),
    !,
    Newtree = Tree.
   find_or_add(Tree, Key, Val, Newtree) :-
    add(Tree, Key, Val, Newtree).

   init(emptytree).


   %%%%%%%%%%%%%%%%%%%%
   % test predicates
   %%%%%%%%%%%%%%%%%%%%

   writetree(emptytree, _).
   writetree(tree(K,V,H,L,R), Indent) :-
    Indent2 is Indent+2,
    writetree(L, Indent2),
    writeblanks(Indent),
    write(K), write(‘/’), write(V), write(‘/’), write(H), nl,
    writetree(R, Indent2).

   % testree(L, Tree):  build a balanced tree out of the keys
   % in list L, associating each key with itself as a value,
   % printing out the intermediate stages along the way.
   testree([], _).
   testree([K|Ks], Tree) :-
    nl, write(‘Adding ‘), write(K), nl, nl,
    add(Tree, K, K, Newtree),
    writetree(Newtree, 2),
    testree(Ks, Newtree).

   writeblanks(0) :-
    !.
   writeblanks(N) :-
    put(32),
    N1 is N-1,
    writeblanks(N1).


Previous Table of Contents Next