source: project/wiki/eggref/4/pll @ 33203

Last change on this file since 33203 was 33203, checked in by svnwiki, 3 years ago

Anonymous wiki edit for IP [177.104.48.1]:

File size: 9.8 KB
Line 
1PLL is a set of implementations of Prolog in Scheme. It is not
2supposed to be efficient, but rather as a simple way to teach the
3fundamentals of Logic Programming and the internal working of a
4Prolog interpreter (conceptually only -- a real implementation would
5be radically different). This interpreter is based on a simple
6implementation of the AMB operator.
7
8PLL is very small (less than 500 lines of code, including different
9versions of the interpreter).
10
11Each variant is built on top of the other.
12
13- Pure prolog: no variables, no assertions, only plain Prolog and  SLD-resolution.
14
15- Prolog w/built-ins: with an extensible set of built-in predicates.  Only the built-ins within a list are allowed.
16
17- Prolog w/Scheme functions: call any Scheme function from Prolog.
18
19- Prolog w/local vars: this version has support for "IS" and local  Prolog variables.
20
21- Prolog w/meta-predicates: this version has support for "assert"  and "retract".
22
23- Prolog w/cut: this version supports cuts.
24
25One last implementation is missing, that would allow for writing
26and reading the database (so it would be possible to store and
27retrieve programs). This is very simple to implement and planned
28for the near future.
29
30== Loading PLL
31
32
33Just
34  (use (pll))
35
36== VARIABLES
37
38
39Traditionally, Prolog systems treat symbols beginning
40with uppercase letters as variables: X, Y, Variable are
41variables, while x, y, constant are constants.
42
43Lisp-based Prologs usually do this differently: the variables
44are the symbols that begin with a question mark: {{?x}}, {{?y}},
45{{?variable}}, etc. We do the same in this implementation.
46
47
48== CALLING THE INTERPRETER
49
50
51Our Prolog use the following syntax:
52
53
54 (pure-prolog PROGRAM GOAL)
55
56
57The program is a list of assertions. The program
58
59         p(x).
60         p(Z) :- q, r(Z).
61
62         
63is written as a list of assertions. Each assertion is a list
64where the head represents the left side (the consequent), and
65the tail is a list of the goals to be met in order to prove
66the consequent. For example,
67
68
69        '(( (p x) ))
70          ( (p ?z) q (r ?z)))
71
72
73The GOAL is a list of goals:
74
75
76        p(1), q(X).
77
78
79is written as
80
81
82        '((p 1) (q ?x))
83
84EXAMPLE: Suppose we want to enter the following program:
85
86
87 f(0).
88 f(Z) :- g(Z).
89 h(3).
90 h(4).
91 p(Z,Y,S) :- f(Z),g(Y),h(S)
92 g(10).
93
94
95And ask the question
96
97
98 p(10,D,A), q(A).
99
100
101We can do this:
102
103 (define facts '(( (f 0) )
104                 ( (f ?z) (g ?z) )
105                 ( (h 3) )
106                 ( (h 4) )
107                 ( (q 4) )
108                 ( (p ?z ?y ?s) (f ?z) (g ?y) (h ?s) )
109                 ( (g 10) )))
110 (define goals '((p 10 ?d ?a) (q ?a)))
111
112
113And call
114
115 (pure-prolog facts goals)
116
117Or, directly enter the facts and goal (as we do in the examples
118that are included in {{prolog-examples.scm}}):
119
120 (pure-prolog '(( (f 0) )
121                ( (f ?z) (g ?z))
122                ( (h 3) )
123                ( (h 4) )
124                ( (q 4) )
125                ( (p ?z ?y ?s) (f ?z) (g ?y) (h ?s))
126                ( (g 10) ))
127              '((p 10 ?d ?a) (q ?a)))
128
129
130The result will be a list of substitutions that satisfy
131the goal:
132
133 ((?a . 4) (?d . 10))
134
135=== GETTING MULTIPLE ANSWERS
136
137
138This can be done with the `amb+` operator.
139
140 (pure-prolog '(((f 1))
141                ((f 2)))
142              '((f ?x)))
143
144 ((?x 1))
145
146If we call `(amb+)`, then we get another solution:
147
148
149 ((?x 2))
150
151== DIFFERENT INTERPRETERS
152
153The different interpreters included are:
154
155- {{pure prolog}}      (prolog only)
156- {{prolog+built-ins}} (with built-in predicates with side-effect)
157- {{prolog+scheme}}    (with an FFI to Scheme, but NO built-ins)
158- {{prolog+local}}     (with "IS" and local vars; on top of prolog+scheme)
159- {{prolog+meta}}      (with assert and retract; on top of prolog+local)
160- {{prolog+cut}}       (with cut (!); on top of prolog+meta)
161
162So the features are added one on top of the other, except for the
163built-ins feature, which is not included in the later interpreters.
164
165In the source code, there is one initial implementation (pure-prolog)
166with short comments explaining how it works. Each interpreter after
167that one has comments only on the modified parts.
168
169=== Pure Prolog
170
171This is the most basic of all. You can only statet facts as
172we described above, nothing else. Call it as
173
174 (pure-prolog facts goals)
175
176
177For example, we define a graph by declaring its edges, then
178define a {{reach/2}} predicate.
179
180 edge(a,b).
181 edge(a,c).
182 edge(c,b).
183 edge(c,d).
184 edge(d,e).
185 reach(A,B) :- edge(A,B).
186 reach(A,B) :- edge(A,X), reach(X,B).
187
188
189We could then as "{{reach(b,e)}}" and find that ''b'' doesn't reach
190''e''.
191
192In PLL:
193
194 (define graph '( ((edge a b))
195                  ((edge a c))
196                  ((edge c b))
197                  ((edge c d))
198                  ((edge d e))
199                  ((reach ?a ?b) (edge ?a ?b))
200                  ((reach ?a ?b) (edge ?a ?x)
201                                 (reach ?x ?b))))
202
203 (pure-prolog graph '( (reach b e) ))
204 #f
205
206
207=== Prolog with built-in "procedures"
208
209This adds some predicates with side-effects.
210
211Define a list of Scheme functions that you want to be
212accessible from Prolog:
213
214
215 (define write-it
216   (lambda (args sub)
217     (cond ((not (null? args))
218            (if (matching-symbol? (car args))
219                (display (assoc (car args) sub))
220                (display (car args)))
221            (write-it (cdr args) sub))
222           (else #t))))
223
224Here "{{sub}}" is the current substitution, where Prolog will find
225the values of variables.
226
227 (define built-ins `((write . ,write-it)))
228
229
230So {{(write a b c ...)}} will be translated to
231
232 (write-it (a b c ...) sub)
233
234Then, whenever one of these predicates show up in the
235goal, Prolog will execute them:
236
237
238 father(john,johnny).
239 father(old-john,john).
240 grandpa(A,B) :- father(A,X), father(X,B).
241
242
243Our goal is
244
245 grandpa(old-john,Who), write("grandson is: "), write(Who).
246
247In our Prolog, this is expressed as follows:
248
249
250 (prolog+built-ins '( ((father john johnny))
251                      ((father old-john john))
252                      ((grandpa ?a ?b) (father ?a ?x) (father ?x ?b)) )
253                   '( (grandpa old-john ?who)  (write "Grandson is: " ?who) ))
254
255 Grandson is: johnny
256 (((?who . johnny)) ())
257
258The first line was the effect of having a {{(write ...)}} in the goal.
259The second is the answer.
260
261=== Prolog with any scheme function
262
263This interpreter has no sandbox -- it will recognize and execute
264any Scheme function when it sees one.
265
266Suppose we want to run this Prolog program, and use a Scheme
267function "{{print}}" in the goal:
268
269 a(5).
270 b(3).
271 b(5).
272
273Goal:
274
275 a(X), b(Y), X=Y, print(X, " " Y).
276
277
278In our Prolog, we have:
279
280 (prolog+scheme '( ((a 5))
281                   ((b 3))
282                   ((b 5)))
283                '( (a ?x) (b ?y) ((= ?x ?y)) ((print ?x " " ?y))))
284
285 5 5
286 ((?y . 5) (?x . 5))
287
288
289The first line is the effect of the print. The second line is
290Prolog's answer.
291
292=== With local variables
293
294
295 (prolog+local '( ((f ?x ?y)
296                   (is ?y (* 2 ?x))
297                   ((print 'OK: ?y))))
298               '( (f 3 ?a) ))
299
300 OK:6
301 ((?a . 6))
302
303=== With assert and retract
304
305This adds the meta-predicates {{assert}} and {{retract}}.
306
307
308 (prolog+meta '(( (f ?x) (asserta (h 1)))
309                ( (g ?x) (h ?x)))
310              '((f ?w) (g ?z)))
311
312
313The result will be {{((?z . 1))}}
314
315
316{{retract}} has the opposite effect. The Prolog program we show now is
317
318 f(2).
319 f(3).
320 g(1) :- retract(f(2)).
321
322And the goal is
323
324 g(1), f(X).
325
326
327In PPL's Schemish-Prolog, this is
328
329
330 (define prolog-retract '( ((f 2))
331                           ((f 3))
332                           ((g 1) (retract ((f 2))))
333                           ((g 1) (f 3))))
334 (prolog+meta prolog-retract '((g 1) (f ?x)))
335
336
337{{(g 1)}} causes retract to be evaluated, so the goal succeeds
338with ''X=3'', and not ''X=2'':
339
340
341 ((?x 3))
342
343
344=== With cut
345
346This adds the cut operator. For example, in Prolog we could write
347
348 a(X) :- b(X), !, c(X).
349 b(1).
350 b(2).
351 c(2).
352
353The goal {{a(X)}} fails, because after the interpreter chooses {{b(1)}},
354it cannot backtrack, and {{c(1)}} is not true.
355
356In our Prolog, we write:
357
358 (prolog+cut '(( (a ?x) (b ?x) ! (c ?x) )
359               ( (b 1) )
360               ( (b 2) )
361               ( (c 2) ))
362             '((a ?x)))
363
364 #f
365
366If we remove the cut, then this goal will succeed with ''X=2''.
367
368The cut can be used also in the goal.
369
370== BUGS AND MISSING FEATURES
371
372
373* There is no way to save and load the database
374
375* There is no simple way to get all possible answers (substitutions) for a
376  query in a list.
377
378* This manual is too short.
379
380== A BIBLIOGRAPHY
381
382The following is a list of some books related to Prolog programming and
383implementations of Prolog.
384
3851. '''William Clocksin, Chris Mellish'''. ''"Programming in Prolog"''.
386   Springer, 2003. [ a very basic text ]
387   
3882. '''Michael Covington, Donald Nute, André Vellino''' ''"Prolog Programming
389   in Depth"''. Scott, Foresman and Company, 1988. [ quick introduction
390   to Prolog, followed by some advanced programming techniques and
391   application ]
392
3933. '''Leon Sterling, Ehud Shapiro'''. ''"The Art of Prolog"''. MIT Press, 1994.
394   [ solid introduction to Prolog, including the execution model --
395   strongly recommended for those who want to understand the
396   internals of the interpreter ]
397   
3984. '''Richard O'Keefe'''. ''"The Craft of Prolog"''. MIT Press, 1990. [ advanced
399   programming techniques ]
400   
4015. '''Harold Abelson, Gerald Jay Sussman''' ''"Structure and Interpretation
402   of Computer Programs"''. Addison-Wesley, 1996. [ explains and implements in
403   Scheme the AMB operator and a small Prolog interpreter ]
404   
4056. '''Peter Norvig'''. ''"Paradigms of Artificial Intelligence
406   Programming"''. Morgan Kaufmann, 1992. [ part of the book explains
407   unification and contains another Prolog implementation, in Common
408   Lisp ]
409   
4107. '''Jacques Chazarain''', ''"Programmer Avec Scheme"''. International Thomson
411   Publishing France, 1996 (in French). [ a very good book on
412   Scheme. chapters 15-19 focus on Prolog ]
413   
4148. '''J. A. Campbell'''. ''"Implementations of PROLOG"''. Ellis Horwood, 1984.
415   [ a study of implementation techniques. quite advanced. ]
Note: See TracBrowser for help on using the repository browser.