Prolog Flashcards

1
Q

B :- A

A

Implication, A -> B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

,

A

And

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

;

A

Or

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Atom

A
  1. A sequence of letters, digits or underscores that starts with a lowercase letter (car)
  2. A sequence of letters, digits or underscores that are enclosed in single quotes (‘car’)
  3. A string of special characters (:- or ,) (without the quotes, thus not a Python string format)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Number

A

Any sequence of numbers, possibly containing a dot

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Variable

A

A sequence of letters, digits or underscores that starts with an upper case letter or an underscore (Car)

_ is the anonymous variable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

A term is defined recursively:

A
  1. Each constant and variable is a term
  2. 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Predicate

A

Any constant or compound term

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Fact

A

A predicate immediately followed by a dot

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Rule

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Clause

A

Any fact or rule,
Are universal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Definition of a predicate

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Built in predicate

A

Defined by SWI Prolog (member/2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Query

A

Defined as ?-p
Where p is some predicate known as a goal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Constant

A

Atoms and numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Two terms t1 and t2 match iff

A
  1. t1 and t2 are identical constants
  2. 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
  3. 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
17
Q

=/2

A

Matching predicate, binds variables using the most general unifier

18
Q

=/2

A

Can be used to check terms that do not match

19
Q

/+

A

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

20
Q

A search tree for a program for a goal is called finitely failed when:

A
  • No successful branch in the tree
  • no infinite branch
21
Q

=:=

A

Checks if computation on the left is equal to computation on the right

(4+3=:=5+2 evaluated to True)

22
Q

==

A

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

23
Q

is operator

A

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)

24
Q

Lists

A

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]

25
Q

[|]/2 operator

A

Allows to concatenate terms in lists

[|] (a,[]) evaluates to [a]

26
Q

Strings

A
  1. Atoms: Used for identifiers and comparison, not manipulation
    - car(‘Ferarri’)
  2. Are lists of characters
    - ‘hello’ -> [h,e,l,l,o]
  3. List of character codes, which are used when parsing
  4. String type
27
Q

String type (swi prolog)

A
  • Represent text as a unit, but can be composed, decomposed or converted
  • indicated by double quotes
28
Q

Recursion

A

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

29
Q

Reachable
A predicate pred2 is reachable from predicate pred1 in a program P if:

A
  1. There is a rule in P the head of which uses pred1 and the body which contains pred2. Or
  2. 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)

30
Q

When is a predicate pred defined recursively?

A

If there is at least one rule in the definition of pred in P from which pred itself is reachable

31
Q

Left recursion

A

The base case comes after the recursive case

AVOID IT

32
Q

Non termination

A

The program won’t terminate because it ends in an infinite branch

33
Q

Depth first search

A

Used by prolog, start at the root node and explore as far as possible along each branch before backtracking

34
Q

What does it mean for a goal to be derived or proven in prolog?

A

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

35
Q

Declaritive meaning

A

The logical meaning of the program, ignoring prolongs specific search strategy

36
Q

Procedural meaning

A

The answer computed by prolog, considering its specific search strategy

(Can differ from declarative meaning)

37
Q

Incompleteness

A

Property of prolog proof search, does not always find derivation, even if derivation exists

38
Q

Incorrectness

A

Lack of an occurs check in prolog