PLVol1

Information about PLVol1

Published on November 26, 2007

Author: Altoro

Source: authorstream.com

Content

Prolog Programming slides written by:  Prolog Programming slides written by Dr W.F. Clocksin The Plan:  The Plan An example program Syntax of terms Some simple programs Terms as data structures, unification The Cut Writing real programs What is Prolog?:  What is Prolog? Prolog is the most widely used language to have been inspired by logic programming research. Some features: Prolog uses logical variables. These are not the same as variables in other languages. Programmers can use them as ‘holes’ in data structures that are gradually filled in as computation proceeds. …More:  …More Unification is a built-in term-manipulation method that passes parameters, returns results, selects and constructs data structures. Basic control flow model is backtracking. Program clauses and data have the same form. The relational form of procedures makes it possible to define ‘reversible’ procedures. …More:  …More Clauses provide a convenient way to express case analysis and nondeterminism. Sometimes it is necessary to use control features that are not part of ‘logic’. A Prolog program can also be seen as a relational database containing rules as well as facts. What a program looks like:  What a program looks like /* At the Zoo */ elephant(george). elephant(mary). panda(chi_chi). panda(ming_ming). dangerous(X) :- big_teeth(X). dangerous(X) :- venomous(X). guess(X, tiger) :- stripey(X), big_teeth(X), isaCat(X). guess(X, koala) :- arboreal(X), sleepy(X). guess(X, zebra) :- stripey(X), isaHorse(X). Prolog is a ‘declarative’ language:  Prolog is a ‘declarative’ language Clauses are statements about what is true about a problem, instead of instructions how to accomplish the solution. The Prolog system uses the clauses to work out how to accomplish the solution by searching through the space of possible solutions. Not all problems have pure declarative specifications. Sometimes extralogical statements are needed. Example: Concatenate lists a and b:  Example: Concatenate lists a and b list procedure cat(list a, list b) { list t = list u = copylist(a); while (t.tail != nil) t = t.tail; t.tail = b; return u; } In an imperative language In a declarative language In a functional language cat(a,b)  if b = nil then a else cons(head(a), cat(tail(a),b)) cat([], Z, Z). cat([H|T], L, [H|Z]) :- cat(T, L, Z). Complete Syntax of Terms:  Complete Syntax of Terms Term Constant Variable Compound Term Atom Number alpha17 gross_pay john_smith dyspepsia + =/= ’12Q&A’ 0 1 57 1.618 2.04e-27 -13.6 likes(john, mary) book(dickens, Z, cricket) f(x) [1, 3, g(a), 7, 9] -(+(15, 17), t) 15 + 17 - t X Gross_pay Diagnosis _257 _ Names an individual Stands for an individual unable to be named when program is written Names an individual that has parts Compound Terms:  Compound Terms parents(spot, fido, rover) The parents of Spot are Fido and Rover. Functor (an atom) of arity 3. components (any terms) It is possible to depict the term as a tree: parents rover fido spot Compound Terms:  Compound Terms =/=(15+X, (0*a)+(2<<5)) Some atoms have built-in operator declarations so they may be written in a syntactically convenient form. The meaning is not affected. This example looks like an arithmetic expression, but might not be. It is just a term. << 2 + a * 0 X + 15 =/= 5 More about operators:  More about operators Any atom may be designated an operator. The only purpose is for convenience; the only effect is how the term containing the atom is parsed. Operators are ‘syntactic sugar’. We won’t be designating operators in this course, but it is as well to understand them, because a number of atoms have built-in designations as operators. Operators have three properties: position, precedence and associativity. more… Examples of operator properties:  Examples of operator properties Position Operator Syntax Normal Syntax Prefix: -2 -(2) Infix: 5+17 +(17,5) Postfix: N! !(N) Associativity: left, right, none. X+Y+Z is parsed as (X+Y)+Z because addition is left-associative. Precedence: an integer. X+Y*Z is parsed as X+(Y*Z) because multiplication has higher precedence. These are all the same as the normal rules of arithmetic. The last point about Compound Terms…:  The last point about Compound Terms… Constants are simply compound terms of arity 0. badger means the same as badger() Structure of Programs:  Structure of Programs Programs consist of procedures. Procedures consist of clauses. Each clause is a fact or a rule. Programs are executed by posing queries. An example… Example:  Example elephant(george). elephant(mary). elephant(X) :- grey(X), mammal(X), hasTrunk(X). Procedure for elephant Predicate Clauses Rule Facts Example:  Example ?- elephant(george). yes ?- elephant(jane). no Queries Replies Clauses: Facts and Rules:  Clauses: Facts and Rules Head :- Body. This is a rule. Head. This is a fact. ‘if’ ‘provided that’ ‘turnstile’ Full stop at the end. Body of a (rule) clause contains goals.:  Body of a (rule) clause contains goals. likes(mary, X) :- human(X), honest(X). Head Body Goals Exercise: Identify all the parts of Prolog text you have seen so far. Interpretation of Clauses:  Interpretation of Clauses Clauses can be given a declarative reading or a procedural reading. H :- G1, G2, …, Gn. “That H is provable follows from goals G1, G2, …, Gn being provable.” “To execute procedure H, the procedures called by goals G1, G2, …, Gn are executed first.” Declarative reading: Procedural reading: Form of clause: Slide21:  male(bertram). male(percival). female(lucinda). female(camilla). pair(X, Y) :- male(X), female(Y). ?- pair(percival, X). ?- pair(apollo, daphne). ?- pair(camilla, X). ?- pair(X, lucinda). ?- pair(X, X). ?- pair(bertram, lucinda). ?- pair(X, daphne). ?- pair(X, Y). Worksheet 2:  Worksheet 2 drinks(john, martini). drinks(mary, gin). drinks(susan, vodka). drinks(john, gin). drinks(fred, gin). pair(X, Y, Z) :- drinks(X, Z), drinks(Y, Z). ?- pair(X, john, martini). ?- pair(mary, susan, gin). ?- pair(john, mary, gin). ?- pair(john, john, gin). ?- pair(X, Y, gin). ?- pair(bertram, lucinda). ?- pair(bertram, lucinda, vodka). ?- pair(X, Y, Z). This definition forces X and Y to be distinct: pair(X, Y, Z) :- drinks(X, Z), drinks(Y, Z), X \== Y. Worksheet 3:  Worksheet 3 berkshire wiltshire surrey hampshire sussex kent How to represent this relation? Note that borders are symmetric. (a) Representing a symmetric relation. (b) Implementing a strange ticket condition. WS3:  WS3 border(sussex, kent). border(sussex, surrey). border(surrey, kent). border(hampshire, sussex). border(hampshire, surrey). border(hampshire, berkshire). border(berkshire, surrey). border(wiltshire, hampshire). border(wiltshire, berkshire). This relation represents one ‘direction’ of border: What about the other? (a) Say border(kent, sussex). border(sussex, kent). (b) Say adjacent(X, Y) :- border(X, Y). adjacent(X, Y) :- border(Y, X). (c) Say border(X, Y) :- border(Y, X). WS3:  WS3 valid(X, Y) :- adjacent(X, Z), adjacent(Z, Y) Now a somewhat strange type of discount ticket. For the ticket to be valid, one must pass through an intermediate county. A valid ticket between a start and end county obeys the following rule: WS3:  WS3 border(sussex, kent). border(sussex, surrey). border(surrey, kent). border(hampshire, sussex). border(hampshire, surrey). border(hampshire, berkshire). border(berkshire, surrey). border(wiltshire, hampshire). border(wiltshire, berkshire). adjacent(X, Y) :- border(X, Y). adjacent(X, Y) :- border(Y, X). ?- valid(wiltshire, sussex). ?- valid(wiltshire, kent). ?- valid(hampshire, hampshire). ?- valid(X, kent). ?- valid(sussex, X). ?- valid(X, Y). valid(X, Y) :- adjacent(X, Z), adjacent(Z, Y) Worksheet 4:  Worksheet 4 a(g, h). a(g, d). a(e, d). a(h, f). a(e, f). a(a, e). a(a, b). a(b, f). a(b, c). a(f, c). arc a e d g h f c b path(X, X). path(X, Y) :- a(X, Z), path(Z, Y). Note that Prolog can distinguish between the 0-ary constant a (the name of a node) and the 2-ary functor a (the name of a relation). ?- path(f, f). ?- path(a, c). ?- path(g, e). ?- path(g, X). ?- path(X, h). But what happens if…:  But what happens if… a(g, h). a(g, d). a(e, d). a(h, f). a(e, f). a(a, e). a(a, b). a(b, f). a(b, c). a(f, c). a(d, a). a e d g h f c b path(X, X). path(X, Y) :- a(X, Z), path(Z, Y). This program works only for acyclic graphs. The program may infinitely loop given a cyclic graph. We need to leave a ‘trail’ of visited nodes. This is accomplished with a data structure (to be seen later). Unification:  Unification Two terms unify if substitutions can be made for any variables in the terms so that the terms are made identical. If no such substitution exists, the terms do not unify. The Unification Algorithm proceeds by recursive descent of the two terms. Constants unify if they are identical Variables unify with any term, including other variables Compound terms unify if their functors and components unify. Examples:  Examples The terms f(X, a(b,c)) and f(d, a(Z, c)) unify. Z c a d f b c a X f The terms are made equal if d is substituted for X, and b is substituted for Z. We also say X is instantiated to d and Z is instantiated to b, or X/d, Z/b. Examples:  Examples The terms f(X, a(b,c)) and f(Z, a(Z, c)) unify. Z c a Z f b c a X f Note that Z co-refers within the term. Here, X/b, Z/b. Examples:  Examples The terms f(c, a(b,c)) and f(Z, a(Z, c)) do not unify. Z c a Z f b c a c f No matter how hard you try, these two terms cannot be made identical by substituting terms for variables. Exercise:  Exercise Do terms g(Z, f(A, 17, B), A+B, 17) and g(C, f(D, D, E), C, E) unify? A B + f g Z 17 A B 17 C f g C E D E D Exercise:  Exercise First write in the co-referring variables. A B + f g Z 17 A B 17 C f g C E D E D Exercise:  Exercise A B + f g Z 17 A B 17 C f g C E D E D Z/C, C/Z Now proceed by recursive descent We go top-down, left-to-right, but the order does not matter as long as it is systematic and complete. Exercise:  Exercise A B + f g Z 17 A B 17 C f g C E D E D Z/C, C/Z, A/D, D/A Exercise:  Exercise A B + f g Z 17 A B 17 C f g C E D E D Z/C, C/Z, A/17, D/17 Exercise:  Exercise A B + f g Z 17 A B 17 C f g C E D E D Z/C, C/Z, A/17, D/17, B/E, E/B Exercise:  Exercise A B + f g Z 17 A B 17 C f g C E D E D Z/17+B, C/17+B, A/17, D/17, B/E, E/B Exercise:  Exercise A B + f g Z 17 A B 17 C f g C E D E D Z/17+17, C/17+17, A/17, D/17, B/17, E/17 Exercise – Alternative Method:  Exercise – Alternative Method Z/C A B + f g Z 17 A B 17 C f g C E D E D Exercise – Alternative Method:  Exercise – Alternative Method Z/C A B + f g C 17 A B 17 C f g C E D E D Exercise – Alternative Method:  Exercise – Alternative Method A/D, Z/C A B + f g C 17 A B 17 C f g C E D E D Exercise – Alternative Method:  Exercise – Alternative Method D/17, A/D, Z/C D B + f g C 17 D B 17 C f g C E D E D Exercise – Alternative Method:  Exercise – Alternative Method D/17, A/17, Z/C 17 B + f g C 17 17 B 17 C f g C E 17 E 17 Exercise – Alternative Method:  Exercise – Alternative Method B/E, D/17, A/17, Z/C 17 B + f g C 17 17 B 17 C f g C E 17 E 17 Exercise – Alternative Method:  Exercise – Alternative Method B/E, D/17, A/17, Z/C 17 E + f g C 17 17 E 17 C f g C E 17 E 17 Exercise – Alternative Method:  Exercise – Alternative Method C/17+E, B/E, D/17, A/17, Z/C 17 E + f g C 17 17 E 17 C f g C E 17 E 17 Exercise – Alternative Method:  Exercise – Alternative Method C/17+E, B/E, D/17, A/17, Z/17+E 17 E + f g + 17 17 E 17 + f g + E 17 E 17 17 E 17 E E 17 Exercise – Alternative Method:  Exercise – Alternative Method E/17, C/17+E, B/E, D/17, A/17, Z/C 17 E + f g + 17 17 E 17 + f g + E 17 E 17 17 E 17 E E 17 Exercise – Alternative Method:  Exercise – Alternative Method E/17, C/17+17, B/17, D/17, A/17, Z/C 17 17 + f g + 17 17 17 17 + f g + 17 17 17 17 17 17 17 17 17 17

Related presentations


Other presentations created by Altoro

Robot Different Types
07. 01. 2008
0 views

Robot Different Types

guzman
18. 04. 2008
0 views

guzman

PublicFinancevsPubli cChoice
13. 04. 2008
0 views

PublicFinancevsPubli cChoice

2779JacobFrenkel
10. 04. 2008
0 views

2779JacobFrenkel

Chapter 02 Warming the Earth
07. 04. 2008
0 views

Chapter 02 Warming the Earth

ElectronicRetailersA ssociation9
27. 03. 2008
0 views

ElectronicRetailersA ssociation9

mining
26. 03. 2008
0 views

mining

Austria
21. 03. 2008
0 views

Austria

poc presentationv ny
28. 09. 2007
0 views

poc presentationv ny

PPT Jon Sigurdson
12. 10. 2007
0 views

PPT Jon Sigurdson

Workshop Wintersport
12. 10. 2007
0 views

Workshop Wintersport

2006 2007 Calender
06. 09. 2007
0 views

2006 2007 Calender

Protein for Athletes
06. 09. 2007
0 views

Protein for Athletes

a23
12. 09. 2007
0 views

a23

lecture 18 bread fermentation
04. 10. 2007
0 views

lecture 18 bread fermentation

ustman
09. 11. 2007
0 views

ustman

Slavery
11. 12. 2007
0 views

Slavery

The Model Hockey Program
06. 09. 2007
0 views

The Model Hockey Program

WAWF Deployment Review
07. 11. 2007
0 views

WAWF Deployment Review

soybeans2007
07. 11. 2007
0 views

soybeans2007

Association HEP Training
06. 09. 2007
0 views

Association HEP Training

Portion Distortion
12. 09. 2007
0 views

Portion Distortion

compositae2006r
07. 12. 2007
0 views

compositae2006r

The Cold War and Domino Theory
19. 12. 2007
0 views

The Cold War and Domino Theory

nelson NATO
25. 12. 2007
0 views

nelson NATO

Fri 04 Killar
29. 12. 2007
0 views

Fri 04 Killar

Oslo 1
02. 01. 2008
0 views

Oslo 1

fruit diseases05
04. 01. 2008
0 views

fruit diseases05

HARRY S TRUMAN
28. 12. 2007
0 views

HARRY S TRUMAN

hayek45
12. 09. 2007
0 views

hayek45

ETC 2004 10 25
06. 09. 2007
0 views

ETC 2004 10 25

CT303 NetworkingDevices
28. 12. 2007
0 views

CT303 NetworkingDevices

IDIS
10. 12. 2007
0 views

IDIS

lect04Slides
14. 12. 2007
0 views

lect04Slides

missions
24. 02. 2008
0 views

missions

360
12. 09. 2007
0 views

360

3 4apr07 SDD Chief
29. 11. 2007
0 views

3 4apr07 SDD Chief

Talk EX8 6
12. 03. 2008
0 views

Talk EX8 6

LoD
24. 12. 2007
0 views

LoD

Roch Stuart
24. 02. 2008
0 views

Roch Stuart

sp10002 3
19. 02. 2008
0 views

sp10002 3

FY2006TourismMediaPl an
10. 10. 2007
0 views

FY2006TourismMediaPl an

Thompson
12. 09. 2007
0 views

Thompson

SMI Innov
17. 06. 2007
0 views

SMI Innov

Salvo Presentation
17. 06. 2007
0 views

Salvo Presentation

SALTO Inclusion 2005
17. 06. 2007
0 views

SALTO Inclusion 2005

athletics
17. 06. 2007
0 views

athletics

JohnBare 11sept07
04. 12. 2007
0 views

JohnBare 11sept07

pizza talk 2006
12. 09. 2007
0 views

pizza talk 2006

Selectividad2007
17. 06. 2007
0 views

Selectividad2007

Phil Borgeaud final
06. 09. 2007
0 views

Phil Borgeaud final

Chelsie and Samantha
02. 11. 2007
0 views

Chelsie and Samantha

ACHA Rules of Emphasis 8 12 06
06. 09. 2007
0 views

ACHA Rules of Emphasis 8 12 06

Renuka Ramnath
12. 09. 2007
0 views

Renuka Ramnath

Overview of Japan Steel Industry
09. 10. 2007
0 views

Overview of Japan Steel Industry

the10mostbeautifulsu rahs
02. 10. 2007
0 views

the10mostbeautifulsu rahs

prez2
21. 11. 2007
0 views

prez2

PlanningMinorityComm unities
26. 02. 2008
0 views

PlanningMinorityComm unities

PPT for recruits 03 2
06. 09. 2007
0 views

PPT for recruits 03 2

siklejog2
17. 06. 2007
0 views

siklejog2

Amuse Promotional materials
12. 10. 2007
0 views

Amuse Promotional materials

GDSv15Training
03. 01. 2008
0 views

GDSv15Training