CSc 520 - Principles of Programming Languages
44 : Logic Programming -- Executing Prolog

Christian Collberg

Department of Computer Science

University of Arizona

1 Executing Prolog

• Now that we know about matching, we can take a closer look at how Prolog tries to satisfy goals.
• In general, to solve a goal
  
  1#1
  
  
  Prolog will first try to solve the sub-goal 2#2.
• It solves a sub-goal 2#2 it will look for a rule
  
  3#3
  
  
  in the database, such that 2#2 and 4#4 will match.
• Any variable substitutions resulting from the match will be stored in a variable 5#5.

2 Executing Prolog...

• A new goal will be constructed by replacing 2#2 with 6#6, yielding
  
  7#7
  
  
  If 8#8 the new goal will be shorter and we'll be one step closer to a solution to 9#9!
• Any new variable bindings from 5#5 are applied to the new goal, yielding 10#10.
• We recursively try to find a solution to 10#10.

3 Executing Prolog...

11#11

4 Executing Prolog

Execute-Alg

5 Northern Exposure Example

12#12

6 Maggie (Janine Turner)

0.513#13

7 Northern Exposure Example...

14#14

8 Northern Exposure Example...

15#15

9 Northern Exposure Example...

Execute-NE-1

10 Northern Exposure Example...

Execute-NE-2

11 Northern Exposure Example...

Execute-NE-3

12 Northern Exposure Example...

Execute-NE-4

13 Northern Exposure Example...

Execute-NE-5

14 Northern Exposure Example...

Execute-NE-6

15 Northern Exposure Example...

Execute-NE-7

16 Northern Exposure Example...

• We skip a step here.
• pastime(mike, golf) unifies with
  16#16
  .
• However, job(mike, doctor) fails, and we backtrack all the way up to the original query.

17 Northern Exposure Example...

Execute-NE-8

18 Northern Exposure Example...

Execute-NE-9

19 Northern Exposure Example...

Execute-NE-10

20 Northern Exposure Example...

Execute-NE-11

21 Readings and References

• Read Clocksin-Mellish, Section 4.1.
• See http://www.moosefest.org for information about the annual Moosefest.
• See http://members.lycos.co.uk/janineturner/engl/index.html for pictures of Janine Turner, who plays Maggie.
• See http://home.comcast.net/~mcnotes/mcnotes.html for show transcripts.

22 Prolog So Far...

• A term is either a
  • a constant (an atom or integer)
  • a variable
  • a structure
• Two terms match if
  • there exists a variable substitution 5#5 which makes the terms identical.
• Once a variable becomes instantiated, it stays instantiated.
• Backtracking undoes variable instantiations.
• Prolog searches the database sequentially (from top to bottom) until a matching clause is found.