Prolog Notes
I dug out a few text files of explanations that would be useful for our project, from how to work with Linux for those who are not familiar with it to how to implement backtracking recursively and how to debug SML code. I compiled them into this document for material related to the Prolog Interpreter and a second document with ML Notes.
Unix/Linux
There always are at least a couple people in class who don’t know Linux. There are a ton of Unix/Linux primers on the web, as well as courses on Linux. Here’s a link that looks useful at first glance:
http://www.ks.uiuc.edu/Training/Tutorials/Reference/unixprimer.html
If you are reasonably familiar with Unix and want to use some of those tools on a PC, I suggest installing Cygwin from
http://www.cygwin.com/
It implements a POSIX library on top of Win32 and then contains ports for just about any Unix/Linux tool out there to that library. With Cygwin, Windows becomes much more usable as a development platform.
For connecting to classes.csc.lsu.edu from your PC, if you don’t install Cygwin, I suggest PuTTY:
http://www.chiark.greenend.org.uk/~sgtatham/putty/
You can simply download the executable. There is also PSCP, a remote file copy program. If you use Cygwin, you can use ssh and scp, respectively.
SML/NJ
For running sml and pml on a PC, you need to install SML/NJ from http://www.smlnj.org/
first as we discussed in class. The version installed on classes.csc is 110.79. The version I used on my laptop for creating the Windows heap image is 110.71, but the latest version should work, too. The batch file for running SML will be installed in
C:Program FilesSMLNJinsml.bat
Then you need to download and unpack the skeleton code from Moodle. After unpacking it, you’ll find a file
1
Prolog.heappml.x86-win32
Copy the file sml.bat from the SML installation, into pml.bat and change the path of the heap image so it loads pml.x86-win32. When you then run pml.bat, you’ll be starting the SML version with the Prolog interpreter preloaded.
Code Structure for Project
For getting started with the Prolog code, I suggest reading the files Syntax.sig and Syntax.sml and then reading the code from Stansifer’s ML primer.
Here’s a short description of the files I made available:
Main.sml
Loads all the pieces of the Prolog interpreter into an empty sml system. After you start sml, you can load everything by typing ‘use "Main.sml";’ at the prompt. If the boolean EXPORT_ML is true, it generates a heap image.
pml
Shell script to start sml with the Prolog parser and the reference implementa-
tion pre-loaded. The heap image starts the Prolog top-level loop.
Prolog.lex
Lexical analyzer written in ML-Lex.
Prolog.lex.sml
Output generated by ML-Lex.
Prolog.grm
Parser written in ML-Yacc.
Prolog.grm.sig
Parser interface generated by ML-Yacc.
Prolog.grm.sml
Parser implementation generated by ML-Yacc.
Prolog.grm.desc
Human-readable form of parser table generated by ML-Yacc.
Parser.sml
Glue code to combine the lexical analyzer and the parser.
Makefile
Makefile for building scanner, parser, and heap image.
Syntax.sig
Interface for parse tree data structure.
2
Syntax.sml
Implementation of parse tree data structure and some simple helper functions.
TopLevel.sml
Top-level loop, initializes Prolog database, reads and interprets a Prolog clause in a loop until EOF.
testsuite/flintstones.*, testsuite/monty-python.*
Sample Prolog programs. The *.pro files are how you could type them in at the Prolog prompt. The *.sml files contain calls to the underlying interpreter without using the top-level, so you can run them from the shell prompt or read them in with ‘use "testsuite/monty-python.sml";’.
You don’t need to know the details of the scanner and parser at all. The only code you need to understand are the interface to the parse trees (Syntax.sig) and how your interpreter is called from the top level (TopLevel.sml). The tree data structure consists of the two datatypes Term and HornClause. The variable db is the Prolog database, and the functions declared in Syntax.sig are useful for initializing the database, asserting an assertion, and for printing. The TopLevel is the function prolog (), which calls your interpreter by passing a clause to the function Prolog (). It’s this function Prolog (), that you need to implement. A skeleton of this function is in Prolog.sml. The rest of your code will go in this file above the function Prolog ().
Your function Prolog must be of type HornClause -> unit. The structure of this function is as follows (without error checks for malformed Horn clauses):
fun Prolog (Headed (Fun ("init", nil), nil)) =
(* Initialize database with built-in predicate init. *)
(db := []; OutLine "Database erased.")
| Prolog (x as (Headed _)) =
(* Add the fact or rule x to the database. *)
(db := !db @ [x]; OutLine("assert: " ^ PrintClause x))
| Prolog (Headless y) =
(* Query the database. *)
(OutLine ("query: " ^ PrintClause (Headless y));
OutQuery (y, !db)
)
where OutQuery would take the list of terms from the query and the contents of the database, runs the search, and prints the results. This code contains all the direct accesses to the database you need. In the rest of your code, you shouldn’t use any assignments.
The Prolog interpreter consists of three larger pieces of code: unification, resolution (i.e., database search), and printing the results. The first things to implement are the substitution data structure and unification. For this part you have most of the code structure given from Stansifer’s ML Primer.
The best way to start would be to type in that code, experiment with it, change the data structure to our term representation, and then find out what bug there is in the code. Stansifer uses ML modules (structures, functors, and signatures) to make his unification implementation generic, so it can be used with any term data structure. That’s overkill for our purposes, so it’s best to rip that
3
out and only implement the functions. Wherever Stansifer uses Terms.TV that corresponds to Var in our Term datatype, and where he uses Terms.TO that corresponds to Fun.
Substitution Implementation
Here is the code for substitutions similar to Stansifer’s code with some explanation and examples.
To deal with renaming of variables, your substitutions should take a pair of variable name and instance number as argument (i.e., what’s inside a Var in our Term datatype) and return a Term, i.e.,
type Substitution = string * int -> Term
I.e., instead of passing, say Var("x",0") as argument to a substitution, you only pass ("x",0). This is just for type-checking purposes. If you’d let a substitution take a Var as argument, the type inferencer will complain that the match is not exhaustive, that you’s also need to define a case for Fun.
You don’t need this type declaration, though. You can let ML figure out the type for you. The empty substitution simply substitutes each variable for itself:
fun empty x = Var x
or, if you want to declare that it’s of type Substitution, you could write
val empty : Substitution = fn x => Var x
These definitions of empty are equivalent. If you use the first definition, SML will tell you that the
type is string * int -> Term.
Other substitutions are constructed using the functions upd and comp below. The function value applies a substitution to a term:
fun value S (Var v) = S v
| value S (Fun (f, args)) = Fun (f, map (value S) args)
Suppose, s is the substitution [X -> t'] then (value s t) substitutes every occurrence of the variable X in t for t'.
Now we can define the composition of two substitutions for convenience:
fun comp (S, R) v = value S (R v)
or
So comp takes a pair of substitutions S and R as arguments and returns a new substitution (fn v => value S (R v)). E.g., if R is the substitution [X -> t1, Y -> Z] and S is the substitution [X -> t2, Z -> t3], then comp (S,R) is the substitution [X -> t1, Y -> t3, Z -> t3].
BTW, for testing you can easily define substitutions by hand. E.g., assuming that the variables t1, t2, and t3 would be some terms, the above substitutions S and R are:
fun S v = if v = ("X",0) then t2 else if v = ("Z",0) then t3 else Var v
fun R v =
fun comp (S, R) = fn v => value S (R v)
4
if v = ("X",0) then t1 else if v = ("Y",0) then Var("Z",0) else Var v
Now, for convenience, we can define an update function that adds a new variable binding to an existing substitution:
fun upd (v, t) S = comp (fn w => if w = v then t else Var w, S)
E.g., if we take the substitution R from above, (upd (("Z",0), t3) R) should give you the same
result as (comp (S,R)) above.
In case it helps you understand what these functions are doing, here are their types in terms of the
type Substitution:
val empty : Substitution
val value : Substitution -> Term -> Term
val comp : Substitution * Substitution -> Substitution
val upd : (string * int) * Term -> Substitution -> Substitution
After copying this substitution implementation, you can copy the rest of Stansifer’s code from the exception declaration and the function pairup on. You don’t need the function top from his substitution implementation. I’ll let you figure out what to use instead. For the call to the function exists in the modern SML versions, you need to use List.exists and instead of the function fold you need to use foldr, but the parameters for foldr are in a different order. To see the type of foldr, simply type foldr; at the SML prompt.
Backtracking
Backtracking in the Prolog search is best implemented using exceptions. If we found that a goal matches the head of a rule in the database, we’d perform the necessary substitutions on the body of the rule and try to solve the subgoals. If solving these subgoals fails, we could raise an exception. When the exception is caught, we’d simply try the next rule in the exception handler.
If we only pass down the substitutions as arguments (instead of modifying a global data structure), raising an exception will automatically undo all the substitutions. If we find a solution, we need to pass the resulting substitution back up.
Here is an example of using exception handling for backtracking.
In the call ‘change coins amount’, coins is a list of coin values and amount is the total amount for which the change is computed. The function change tries to find a list of coins such that they add up to the total amount. The function change is of type int list -> int -> int list.
exception Change;
fun change _ 0 = nil
| change nil _ = raise Change
| change (coin::coins) amt =
if coin > amt then
change coins amt
else
(coin :: change (coin::coins) (amt-coin))
handle Change => change coins amt;
5
E.g., the call ‘change [5,2] 16’ will return [5,5,2,2,2].
The first argument of change, i.e., the list [5,2], is matched against the pattern (coin::cons). So coin = 5 and coins = [2]. For this algorithm to find the smallest number of coins, the list of coins should be sorted in decreasing order. If the largest coin, 5 in this case, is greater than the remaining amount, then change is called recursively with the tail of that list. The call in the then-branch would be ‘change [2] amt’. If it would work to use the large coin, it’s tried out (in the else-branch). There first the recursive call ‘change [5,2] (amt-5)’ is tried. I.e., the large coin is used and we recursively try to give change for the remainder. If it doesn’t work to give exact change for amt-5, eventually the exception would be raised. Then we try to use the rest of the coins instead using the call ‘change [2] amt’.
In Prolog terminology, we are setting up a choice point for the call ‘change (coin::coins) (amt-coins)’ by associating it with an exception handler. If the branch ‘(coin::coins) (amt-coin)’ doesn’t work, then we’ll try the branch ‘coins amt’ next.
The other two recursive calls, the one in the then-branch and the one in the handle-clause, don’t have an exception handler attached. So if the exception is thrown in the recursive call, it’s passed up to the caller.
请加QQ：99515681 邮箱：99515681@qq.com WX：codinghelp
