Interpreter podmnožiny Prologu pomocí Warren Abstract Machine
Get acquainted with the Prolog programming language [1,2], and the Warren Abstract Machine (WAM) [2] for the execution of Prolog.
Implement interpreter and REPL for a subset of Prolog using WAM.
Your subset must support at least Horn clauses and cuts.
Verify the functionality of your implementation by testing with a relevant set of sample codes.
[1] STERLING, Leon; SHAPIRO, Ehud Y. The art of Prolog: advanced programming techniques. MIT press, 1994.
[2] KOGGE, Peter M. The architecture of symbolic computers. McGraw-Hill, Inc., 1990.
Full text of the bachelor thesis (in english) can be found at https://dspace.cvut.cz/handle/10467/116064.
Standard CMake toolchain is used. For compilation, use:
mkdir build
cd build
cmake ..
And then build the project with make
After the project has been built, a binary wam_test
will be created.
Executing the wam_test
like so ./wam_test
will run the unit tests present. Framework used for testing is doctest.
Along with the wam_test
, the wam
binary will also be generated after building. This is the binary used to run the interpreter.
Running the binary without any flags like this:
./wam
will start the REPL. In this state, queries containing the unification and is operator can be evaluated, e.g. X=Y,Y=elephant
or X is 1 + 2
.
After evaluation, the result will be displayed:
?> X = Y, Y = elephant
true.
X = elephant
Y = elephant
?> X is 1 + 2
true.
X = 3
?> 1 + 1 is 1 + 2
false.
Of course, standard Prolog queries like bigger(mouse,bug)
can also be entered, but will always fail without a loaded file.
REPL can be terminated by entering halt
.
A source code file can be loaded into the REPL by running the binary with a --file <filepath>
flag, like this for example
./wam --file file.pl
Assume the file.pl
looks like this:
bigger(elephant,mouse).
bigger(mouse,bug).
same(bug,bug).
Now, a query in the form of bigger(mouse,bug)
can be run and succeed:
?> bigger(mouse,bug).
true.
Example files can be found in the examples/
directory.
Assume the aforementioned source code and a query bigger(X,Y)
.
The machine will answer the first possible proof sequence.
For our case, the answer would look like this:
?> bigger(X,Y).
true.
X = elephant
Y = mouse
The REPL then prompts the user. If a semicolon is entered ;, the process is restarted to look for another proof sequence. In case of any other input, the evaluation of the query is done and REPL prompts the user to enter a new query.
In our example:
?> bigger(X,Y).
true.
X = elephant
Y = mouse
;
true.
X = mouse
Y = bug
;
false.
To only dump the bytecode produced by compiling a source file without executing it, the --dump
flag is used. Running
./wam --file file.pl --dump
yields the following output:
...
bigger/2: mark
retry-me-else bigger/21[83]
allocate 0
get-constant elephant A1
get-constant mouse A2
return
bigger/21: retry-me-else __quit[94]
allocate 0
get-constant mouse A1
get-constant bug A2
return
same/2: mark
retry-me-else __quit[94]
allocate 0
get-constant bug A1
get-constant bug A2
return
__quit: backtrack
In practice, the --dump
flag will display some bytecode generated even when no source file is specified, as there are some predicates being linked to the source file prior to the actual compilation. These are represented in the output by the three dots.
The is operator implemented generates the arithmetic instructions completely in compile time, using only WAM instructions. That works for queries like
?> X is 1 + 2
true.
X = 3
or
?> X is Y + 1, Y is 1
X = 2
Y = 1
However, assume a program which contains a following rule addOne(X,Y):- Y is X + 1
.
When a query addOne(1+1,Y)
is called, the code has already been generated, and at compile time, the addOne
predicate had no way of knowing that the X might be an expression.
Hence it tries to compute Y is +(1,1) + 1
, which fails.
Even with these limitations, the is operator can be used to simplify writing programs, like this factorial example:
fact(0, 1).
fact(N, Res) :-
N1 is N - 1,
fact(N1, Tmp),
Res is Tmp * N.
Which yields the expected results
?> fact(0,X).
true.
X = 1
?> fact(4,X).
true.
X = 24
?> fact(5,X).
true.
X = 120
?> fact(6,X).
true.
X = 720
Disclaimer: The stepper in its current state is highly experimental and unfinished.
By running ./wam --step
, after entering a query, the machine won't execute the whole program, but will display the bytecode (currently executed instruction is highlighted) and the machine's state.
By pressing enter, the code can be stepped through, seeing how the state changes. Currently, the stepper is very rough around the edges, without a proper UI and is mainly meant as a developer tool. It may, however, be used to debug programs or to gain an understanding of how the program is executed.