Tomáš Petříček, 309 (3rd floor)
petricek@d3s.mff.cuni.cz
https://tomasp.net | @tomaspetricek
https://d3s.mff.cuni.cz/teaching/nprg077
Natural language processing in the late 1960s & early 1970s
SHRDLU, PLANNER
"Find a block which is taller than the one you are holding and put it into the box."
Naive method
Generate & test
all permutations
Better approaches
Try adding only reasonable options
Naive is fine for us!
Universally quantified over formula, existentially over body
\(\forall x \forall y (grandparent(x, y) \leftarrow \exists z (parent(x, z) \wedge parent(z, y)))\)
Transformed using standard logical operations
\(\forall x \forall y (grandparent(x, y) \vee \neg \exists z (parent(x, z) \wedge parent(z, y)))\) \(\forall x \forall y (grandparent(x, y) \vee \forall z \neg (parent(x, z) \wedge parent(z, y)))\) \(\forall x \forall y \forall z (grandparent(x, y) \vee \neg parent(x, z) \vee \neg parent(z, y))\)
We need to use free variables when applying rule!
A = f(A)
A = 1 + A, B is A.
set_prolog_flag(occurs_check, true).
`
Program is a list of clauses which are:
1) Rules (head + body) 2) Facts (head)
A term can be:
1) Variable
2) Atom
3) Predicate
(* Recursive term definition *)
type Term =
| Atom of string
| Variable of string
| Predicate of
string * Term list
| Call of Term * Term list
(* Facts have empty Body *)
type Clause =
{ Head : Term
Body : Term list }
(* Create a fact clause *)
let fact p =
{ Head = p; Body = [] }
(* Create a rule clause *)
let rule p b =
{ Head = p; Body = b }
Encoded as F# types!
Atom vs. variable
Atom is a single data item, thing that exists.
Variable is a placeholder that we want to assign a term to.
unify
and unifyLists
functionslet rec unifyLists l1 l2 =
match l1, l2 with
| [], [] ->
(* empty substitution*)
| h1::t1, h2::t2 ->
match unify h1 h2 with
| Some(s) -> (*
1. substitution 's' to
unify 'h1' and 'h2'
2. now unifiy 't1' and 't2'
recursively & compose
3. if not possible, fail *)
| _ -> (* fail *)
| _ -> (* fail *)
and unify t1 t2 =
match t1, t2 with
| Atom(a1), Atom(a2) -> (* does 'a1' match 'a2'? *)
| Variable(v), t | t, Variable(v) ->
(* return a substitution *)
| Predicate(p1, args1), Predicate(p2, args2) ->
(* if p1 = p2, unify arguments recursively *)
| _ -> None
Split into two functions for better readability
unify
matches terms
unifyLists
matches two lists using unify
% Number: 0
zero
% Number: 1
one = s(zero)
% Number: 5
five = s(s(s(s(s(zero)))))
% Empty list
empty
% List [1]
cons(one, empty)
% List [1; 5]
cons(one, cons(five, empty))
Nothing extra is needed!
Good enough for a tiny implementation.
Terribly inefficient and limited if you want to calculate anything!
match
Odd
or Even
seq {..}
or eager [..]
or arrays [|..|]
Implementing basic unification of terms
Recursively match atoms, variables and predicates
Composing and applying substitutions
To handle multiple occurrences of a variable correctly
Searching clauses & variable renaming
Find applicable rules and relevant facts in program
Generating and proving goals recursively
The key trick! Generate and solve goals in a loop
Adding numbers to TinyProlog
Representing, calculating and pretty printing
Lazy search and support for lists
Refactoring for readability and more pretty printing
Generating magic squares in TinyProlog
In which we find out how slow our implementation is :-)
Implementing call and functional maplist
Adding special predicate for higher-order programming
Adding support for occurs checks
If you want to make it slower and more correct
Implementing Prolog-style cut operator
Super-bonus if you are into Prolog programming...
A tiny declarative logic programming language
Tomáš Petříček, 309 (3rd floor)
petricek@d3s.mff.cuni.cz
https://tomasp.net | @tomaspetricek
https://d3s.mff.cuni.cz/teaching/nprg077
http://alain.colmerauer.free.fr/alcol/ArchivesPublications/PrologHistory/19november92.pdf
https://www.metalevel.at/prolog/clpz
https://github.com/Naereen/Tiny-Prolog-in-OCaml/
https://yanniss.github.io/next-paradigm-onward19.pdf
https://tgifernando.files.wordpress.com/2013/01/sld_resolution-4spp.pdf