Implementing a deterministic Prolog interpreter that suppors backtracking (recover from bad choices) and choice points (produce multiple results). Please refer to the lecture notes Programming with Lists and Control in Prolog for more details about this algorithm.
OCaml Implementation
query : clause list -> term list -> term list list
where
the first argument is a program which is a list of clauses.
the second argument is a goal which is a list of terms.
The function returns a list of term lists (results). Each of these results is an instance of the original goal and is a logical consequence of the program. If the given goal cannot be dervied as a logical consequence of the program, then the result is an empty list. See the tests cases below as examples.
For the goal order of the interpreter, always choose the left-most subgoal to solve. For the rule order, apply the rules in the order in which they appear in the program.
Hint: Implement a purely functional recursive solution. Backtracking and choice points naturally fall out of the implementation. The reference solution is 16 lines long.
In [ ]:
let query program goal = (* YOUR CODE HERE *)