Transcript Ch.3 [B] - CSE - University of South Carolina

Lists, Operators, Arithmetic
Notes for Ch.3 of Bratko
For CSCE 580 Sp03
Marco Valtorta
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Representation of Lists
• Prolog provides a convenient representation of lists
• [ ann,tennis,tom,skiing]
– ann is the head of the list above
– [ tennis,tom,skiing] is its tail
• The head of a list is its first element
• The tail of a list is the list without its first element
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Lists as Terms
• The empty list: [ ] (a constant)
• Any other list is a structure whose principal functor is
the list constructor, which is represented by the dot (.)
in Prolog
• Any non-empty list matches .( Head,Tail)
• [ ann, tennis, tom, skiing] is a “cosmetic improvement”
(“syntactic sugar”) for
.( ann, .( tennis, .(tom, .(skiing, [ ]))))
• See Fig. 3.1 for a tree representation of this term
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
More List Notation
• Prolog converts the internal representation of a list
to its “neater” form:
• ?- L = .( ann, .( tennis, .( tom, .(skiing, []) ) ) ).
L = [ann, tennis, tom, skiing]
• 3 ?- L = .( .( ann, []), .( .( tom, []), [])).
.
L = [[ann], [tom]]
.
.
ann
UNIVERSITY OF SOUTH CAROLINA
[]
.
[]
tom [ ]
Department of Computer Science and Engineering
More List Notation
• L = [a | Tail]
• [ a,b,c] = [ a | [ b,c]] = [ a,b | [c]] = [ a,b,c | [ ]]
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Some Operations on Lists
• Membership: checking whether some object is an
element of a list
• Concatenation of two lists, obtaining a third list,
which is the juxtaposition of the first two
• Adding an element to a list
• Deleting an element from a list
• Checking whether a list is a sublist of another
• Generating permutations of a list
• There are built-in versions of some of these
predicates in SWI: see section 4.29 (p.114)
• pr3_1.pl
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
pr3_1.pl
• Note the non-determinism and reversibility of many
of these operations
• member is built-in; we call ours memb
• Note that member can be used to generate lists
• Alternate member:
memb1( X,L) :- conc( L1,[ X | L2], L).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Operator Notation
• 2*a + b*c
• Infix notation is a convenience for external
presentation
• The principal functor is (one of the) highest
precedence operator(s)
• Fig.3.8 is a table of predefined operators; it is a
subset of the predefined operators in SWI (Section
E.4, p.255)
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Operator Precedence
• Xfx vs. xfy vs. yfx
(a – b) – c or a – (b – c)?
• Since – is defined as yfx, a – (b – c)
• Is not not p correct? Yes, because not is defined as
fy
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Arithmetic
• Try: ?- X = 1 + 2.
Surprise!
• Try ?- X is 1 + 2.
is is not reversible!
• Notation: -Number is +Expr
• Moreover, Expr must have a value and Number should
be unbound. Do not use is to test for equality
• See Section 4.26 (p.109) and Appendix E3 of manual
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Equality
• = for unification: tries to match terms by finding a
unifier
• =:= for equality: forces arithmetic evaluation, but no
substitution is made
• Try ?- 1+2 = 2+1 (fails)
?- 1+2 =:= 2+1 (succeeds)
?- 1+A = B+2 (succeeds)
?- 1+A =:= B+2 (fails)
5 ?- 1+A =:= B+2.
ERROR: Arguments are not sufficiently instantiated
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Euclid’s Algorithm
• euclid.pl
• Another non-reversible program
2 ?- gcd( 10, 55, D).
D=5
3 ?- gcd( 10, Y, 5).
ERROR: Arguments are not sufficiently instantiated
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Just for Fun… Correctness
• gcd( X,X,X). Obvious
• Clause 2. Induction. Assume X < Y.
– case 1: Y = nX. Obvious
– case 2: Y = nX + r. Any divisor D of Y and X is also a divisor of r.
Since r < X, the last subgoal in the body of the clause is (eventually)
gcd(X,r,D). We only need to show that, if D is a GCD of X and r, it
is also a GCD of X and Y. Any divisor of X and r is also a divisor
of r. So, the set of divisors of Y and X is the same as the set of
divisors of X and r. So, the Greatest CD of X and Y is the same as
the GCD of X and r. But r < X, so the last subgoal in the body of
the clause is (eventually) set up with X, r, D.
• Clause 3. Induction. Assume Y < X. Analogous to clause 2 case.
• See Knuth, vol.1, Section 1.1.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Length
• A case study in evaluated vs. non-evaluated terms: length.pl
• length is built-in. It is reversible. Warning: dirty secrets of
SWI-Prolog ahead!
length(List, Length) :$length(List, Length), !.
length(List, Length) :var(Length),
length2(List, Length).
length2([], 0).
length2([_|List], N) :length2(List, M),
succ(M, N).
UNIVERSITY OF SOUTH CAROLINA
% written in C
Department of Computer Science and Engineering
Length II
• len1 is interpreted. It is reversible, but it will loop
infinitely if asked for multiple lists of some length!
• len2 fixes this (at the cost of using a cut)
• len3 returns a not interpreted term
• len4 does the same with a shorter second clause
• len5 uses len4 and then interprets the result
• len6 is to len5 what len2 is to len1
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Axiomatizing Arithmetic
• Unary (“tally”) arithmetic: Giuseppe Peano’s axioms, also
known as “Peano’s Postulates.”
• See Russell and Norvig, Section 8.3 for an informal presentation
of the axioms.
• See http://www-groups.dcs.stand.ac.uk/~history/Mathematicians/Peano.html for a
biographical sketch of Giuseppe Peano)
• Binary arithmetic: UseDefK7.ppt
– Note: examples are in Cilog, a dialect of Prolog, based
on an exercise in Poole et al.’s AI Textbook
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Peano’s Postulates
(P1) 0 is a natural number
(P2) If x is natural number, there is another natural number
denoted by x’ (and called the successor of x)
(P3) 0 != x’ for any natural number x
(P4) If x’ = y’, then x = y
(P5) If Q is a property that may or may not hold of the
natural numbers, and if (I) 0 has the property Q, and (II)
whenever a natural number x has the property Q, then x’
has the property Q, then all numbers have the property Q
(Principle of Induction)
(Mendelson,E. Introduction to Mathematical Logic. Princeton, NJ: Van
Nostrand, 1965.)
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering