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

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