Simtel MSDOS 1992 September/Simtel20_Sept92.cdr/msdos/aijournl/ai_nov86.arc/PROCED.NOV

Text File | 1986-09-25 | 5KB | 166 lines

                Procedural Programming vs. PROLOG
                          by Marc Kenig
                November 1986 AI EXPERT magazine


                            Listing 1

PROLOG and Lisp programs. The PROLOG version involves a 'generate
and test' strategy to find the greatest roman numeral value
'Z' less than 'X'.It can be extended to larger values by
simply adding more 'roman' facts. To extend the Lisp version,
however, both functions must be extended.


Lisp       Prolog
(ROMAN
 (LAMBDA (X)     roman(50,"L").
   (SELECTQ X     roman(40,"XL").
     (50 '(L))  (40 '(X L))     roman(10,"X").
     (10 '(X))  (9  '(I X)))       fact database     roman(9,"IX").
     (5  '(V))  (4  '(I V)))     roman(5,"V").
     (1  '(I))  (0  '())     roman(4,"IV").
     (ROMRUL X))     roman(1,"I").
))     roman(0," ").)

(ROMRUL
 (LAMBDA (X)      romrul(X,Y) :-
    (COND ((LESSP 40 X)     X roman Y
    (APPEND (ROMAN 40) (ROMAN (MINUS X 40))))      romrul(X,Y) :-
  ((LESSP 10 X) rules     roman(Z,X1),     --GENERATE
    (APPEND (ROMAN 10) (ROMAN (MINUS X 10))))     Z<X,      --TEST
  ((LESSP 5 X)     Y1 is X mod Z,
    (APPEND (ROMAN 5)  (ROMAN (MINUS X 5))))     romrul(Y1,Z1),
   ((LESSP 1 X)      append(X1,Z1,Y).
    (APPEND (ROMAN 1)  (ROMAN (MINUS X 1))))
    )
))


(ROMAN 49)   roman(49,X)
               X = ["XLIX"] ;
(X L I X)

Note:   Running/querying each program. The clever though
unpredictable PROLOG output is due to unchecked backtracking.



                            Listing 2

Corrected version of PROLOG program with cut added as a subgoal
to curtail unwanted backtracking.


roman(50,"L").
roman(40,"XL").
roman(10,"X").
roman(9,"IX").
roman(5,"V").
roman(4,"IV").
roman(1,"I").
roman(0," ").

romrul(X,Y) :- roman(X,Y) , !

romrul(X,Y) :- roman(Z,Y),
       Z<X,
       Y1 is X mod Z,
       romrul(Y1,Z1),
               !,
       append(X1,Z1,Y).



                            Listing 3

The "for" and infinite loops both rely on backtracking and
recursion to to implement a loop in PROLOG. The sub-goal inf
causes PROLOG to look in it's rule database and find the
definition of inf infinitely.



         FOR loop                                      Infinite loop
         --------                                      -------------

for(X,[X,Z]) :- X=<Z.
for(X,[Y,Z]) :- W is Z+1,                              inf :- write('hi '),
                W=<Z,                                         inf.
                FOR(X,[W,Z]).

?- for(X,[1,10]), write(X), write(' ').                ?- inf.
1 2 3 4 5 6 7 8 9 10                                   hi hi hi hi hi hi.....
yes.



   Listing 4 - The many ways to query the SAME relation.

Definition of relation append:

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

has four distinct uses based on the arguments supplied.
                                   |
?- append([a,b], [c,d], X).        |     ?- append([a,b], X, [a,b,c,d]).
                                   |
  X = [a,b,c,d]                    |       X = [c,d]
                                   |
  4a- List concatenation           |    4b - Splitting the list after [a,b]
_______________________________________________________________________________
                                   |
?- append(X, Y, [a,b,c,d])         |     ?- append([a,b], [c,d], [a,b,c,d]).
   |
  X = []                           | yes
  Y = [a,b,c,d]                    |
  X = [a]                          |     ?- append([a,b], [w,d], [a,b,c,d]).
  Y = [b,c,d]                      |
  X = [a,b]                        |     no
  Y = [c,d]                        |
  X = [a,b,c]                      |
  Y = [d]                          |
  X = [a,b,c,d]                    |
  Y = []                           |
   |     4d - Verifying proper concatenation
4c - All possible sub-lists pairs  |          of lists


                            Listing 5

An interactive PROLOG "binary search" guessing game with a sample
run. The adjust rule exchanges the high and low search limits
based on the user's input.

game(X)        :- guessing(1,X).
guessing(X,Y)  :- average(X,Y,Z) , talk(Z), ttyget(X1),
                  adjust(X,Y,Z,[X1]).

average(X,Y,Z) :- Z1 is X+Y, Z is Z1/2.

talk(X)        :- nl, write('Is '), display(X),
                  write(' G)reater  L)ess than or E)qual to your number? ').

adjust(X,Y,Z,"L") :- guessing(Z,Y).
adjust(X,Y,Z,"G") :- guessing(X,Z).
adjust(X,Y,Z,"E") :- !, nl, write('I win!').
adjust(X,X,X,_)   :- !, nl, write('Must be '),display(X).

?- game(50).

Is 25 G)reater L)ess than or E)qual to your number?  G

Is 13 G)reater L)ess than or E)qual to your number?  L

Is 19 G)reater L)ess than or E)qual to your number?  G

Is 16 G)reater L)ess than or E)qual to your number?  E

I win!

?-
19 G)reater L)ess than or E)qual to your number?  G

Is 16 G)reater L)ess than or E)qual to your