Prolog Flashcards
B :- A
Implication, A -> B
,
And
;
Or
Atom
- A sequence of letters, digits or underscores that starts with a lowercase letter (car)
- A sequence of letters, digits or underscores that are enclosed in single quotes (‘car’)
- A string of special characters (:- or ,) (without the quotes, thus not a Python string format)
Number
Any sequence of numbers, possibly containing a dot
Variable
A sequence of letters, digits or underscores that starts with an upper case letter or an underscore (Car)
_ is the anonymous variable
A term is defined recursively:
- Each constant and variable is a term
- f(t1, …, tk) is a term is each ti is a term and f is an atom
— (this is a compound term with functor f and arity k indicated as has_wheels/1)
— a term is a ground when it contains no variables
Predicate
Any constant or compound term
Fact
A predicate immediately followed by a dot
Rule
A predicate is a rule if:
- given by A0 :- A1, …, An. With n>=0 and each Ai a predicate.
A0 is the head, A1, …, An is the body of the rule
Clause
Any fact or rule,
Are universal
Definition of a predicate
The set of all facts and rules that use a certain predicate P,
if there is no definition in a certain program, P is called undefined
Built in predicate
Defined by SWI Prolog (member/2)
Query
Defined as ?-p
Where p is some predicate known as a goal
Constant
Atoms and numbers
Two terms t1 and t2 match iff
- t1 and t2 are identical constants
- If t1 is a variable and t2 is not, then t1 is instantiated with t2
— the same applies for the reverse of when both are variables - If t1 and t2 are compound terms, they match if:
— they have the outermost functor (t1 =(r1,…,rk) and t2=(s1,…,sk))
— each term ri matches with each term si
- the variables instantiations are compatible, variables can’t be assigned different terms which are not variables
=/2
Matching predicate, binds variables using the most general unifier
=/2
Can be used to check terms that do not match
/+
Negationwith finite failure
/+ f is true in program P iff f cannot be derived from P and the program terminates
/+ G can be derived from P iff the search tree of P for G is finitely failed
Its not saying f is false, it is saying there is not enough information to prove f is true
A search tree for a program for a goal is called finitely failed when:
- No successful branch in the tree
- no infinite branch
=:=
Checks if computation on the left is equal to computation on the right
(4+3=:=5+2 evaluated to True)
==
Checks if the computation on the left differs from the computation on the right
4+3==5+2 evaluates to false
4+3==2+2 evaluates to true
is operator
Has an arithmetic expression on the right side, evaluates it and unifies the result with the variables in the left side
Left side:
- variable
- it checks if this value matches the evaluated result of the expression the right
(X is 2+2 evaluates X=4)
Lists
Store compound terms
Symbol:
[] (empty list has no head or tail)
Have a head (term) and a tail (list)
Head is the first element alone, tail is the rest of the body
[Head|Tail]
[|]/2 operator
Allows to concatenate terms in lists
[|] (a,[]) evaluates to [a]
Strings
- Atoms: Used for identifiers and comparison, not manipulation
- car(‘Ferarri’) - Are lists of characters
- ‘hello’ -> [h,e,l,l,o] - List of character codes, which are used when parsing
- String type
String type (swi prolog)
- Represent text as a unit, but can be composed, decomposed or converted
- indicated by double quotes
Recursion
A recursive definition is defined in terms of itself
A method of solving a problem where the solution depends on solutions to smaller instances of the same problem
Include termination condition
Reachable
A predicate pred2 is reachable from predicate pred1 in a program P if:
- There is a rule in P the head of which uses pred1 and the body which contains pred2. Or
- There is a predicate pred3 such that pred3 is reachable from pred1 in P, and pred2 is reachable from pred3 in P
pred1(X):- pred2(X)
pred1(X):- pred3(X)
pred3(X):- pred2(X)
When is a predicate pred defined recursively?
If there is at least one rule in the definition of pred in P from which pred itself is reachable
Left recursion
The base case comes after the recursive case
AVOID IT
Non termination
The program won’t terminate because it ends in an infinite branch
Depth first search
Used by prolog, start at the root node and explore as far as possible along each branch before backtracking
What does it mean for a goal to be derived or proven in prolog?
A goal G can be derived or proven from a program P if Prolog finds a successful trace in the search tree of P for G
Declaritive meaning
The logical meaning of the program, ignoring prolongs specific search strategy
Procedural meaning
The answer computed by prolog, considering its specific search strategy
(Can differ from declarative meaning)
Incompleteness
Property of prolog proof search, does not always find derivation, even if derivation exists
Incorrectness
Lack of an occurs check in prolog
