COMP 481, Chapter 9, Prolog
Ch 9: A Closer Look at Terms
Copyright By PowCoder代写 加微信 powcoder
University of the Fraser Valley
COMP 481: Functional and Logic Programming
• Comparing Terms
• Arithmetic Terms
• Lists as Terms
• Types of Terms
• The Structure of Terms
• Properties of Operators
• Defining Operators
Documentation
In the next slide, look up the operations in documentation
and see how well you can understand the descriptions
against the textbook explanations.
There are many issues the textbook treats lightly.
• read in the order of the docs before the textbook
• see how well you understand the docs first!
• deal with differences in implementation for SWI-
Predicate Description
= unification
\= true if arguments cannot be unified
== identical (not unification =)
\== not identical
+ addition
< arithmetic smaller than =< arithmetic equal to or smaller than =:= arithmetic equality =\= arithmetic not equal > arithmetic larger than
>= arithmetic larger than or equal to
. (not in SWI-Prolog) list constructor
[|] (SWI-Prolog) list constructor
— Comparing Terms —
Use of single quote in Prolog is to define procedure name.
• without use of single quotes,
be extra careful with the names for procedures
• no first capital letter, for example
• with single quote, we can define procedure names more liberally
?- [user].
|: ‘..as+'(sure).
?- ‘..as+'(X).
When we compare two objects for identity
• if the name of a predicate is fine without single quotes,
• then it will be considered identical to the same with single quotes:
?- a == a.
?- a == ‘a’.
?- a == b.
• the arrow `->` executes similar to an `if-else-then` construct
• code before the `;` will run if the condition is true
• code after the `;` will run if the condition is false
The textbook describes that uninstantiated variables are
considered identical, but not so in SWI-Prolog:
?- (X == Y) -> write(“okay”) ; write(“nope”).
?- (X = Y), (X == Y) -> write(“okay”) ; write(“nope”).
23 ?- (X == X) -> write(“okay”) ; write(“nope”).
?- X = a, a == X.
Instantiation
• as you can see, the variables must be instantiated to be considered
as identical
• the docs have quite a few more examples to consider
(if you scroll down in the annotation posts)
• note that identical comparison is stronger than unification
• if the query `term1 == term2` succeeds,
then the query `term1 = term2` will succeed as well
A quick look at lambda function notation used in a way to
suppress the output of variables in queries:
• https://www.swi-prolog.org/pldoc/doc_for?object=(/)/2
?- {}/(X = a, X == a).
?- {}/(X = b, X == a).
?- {X}/(X = a, X == a).
?- {X}/(X = b, X == a).
https://www.swi-prolog.org/pldoc/doc_for?object=(/)/2
Try a few queries to convince yourself that `\==` results in
the negation of `==`.
• use queries involving variables with an operation
• instantiate variable values first, use AND `,`, followed by comparison
• try different order for the operands
• at time of comparison, the terms on either side are compared
— Arithmetic Terms —
Differently written terms, inline versus written as functors:
?- 2+3 == +(2,3).
?- +(2,3) == 2+3.
?- 2-3 == -(2,3).
?- *(2,3) == 2*3.
?- 2*(7+2) == *(2,+(7,2)).
Neither side of the identical test evaluates its expression to
a single value:
?- X = 2+3, Y = +(2,3), X == Y.
X = Y, Y = 2+3.
• the `==` operation really is comparing the expressions
• Prolog considers the various ways of writing these terms as identical
Give the other arithmetic comparisons a try, but make note
of when both sides are forced to evaluate.
• contrast against our investigations of the “identical” comparison:
?- 0.5*2.0 == 1.0.
?- 0.5*2.0 =:= 1.0.
• make sure you realize `=:=` is evaluating the expressions before
comparison
• this is also the case for `<` and `>` comparisons
• it does not make sense to compare an ordering for how we
write expressions themselves
Comparisons
Use parentheses to break ties with order of operations:
?- 2 =:= 3 == =:=(2, 3).
ERROR: Syntax error: Operator priority clash
ERROR: 2 =:
ERROR: ** here **
ERROR: = 3 == =:=(2, 3) .
?- (2 =:= 3) == =:=(2, 3).
• the error is because Prolog cannot decide which to execute first:
• (2 =:= 3) == =:=(2, 3).
• 2 =:= (3 == =:=(2, 3)).
Operations
A summary of the comparison operations involving
— Lists as Terms —
Do Not Use
`.` as in the
Some reasoning for SWI-Prolog’s reassignment of `.`
functionality:
• https://www.swi-prolog.org/pldoc/man?section=ext-list-motivation
So, this section describes a traditional notation
that SWI-Prolog no longer uses.
• we can still consider nested lists as representing trees
https://www.swi-prolog.org/pldoc/man?section=ext-list-motivation
Construction
There are many ways to use `[|]` as a list constructor to
create the same list:
?- [1,2,3,4] == [1,2,3,4|[]].
?- [1,2,3,4] == [1,2,3|[4]].
?- [1,2,3,4] == [1,2|[3,4]].
?- [1,2,3,4] == [1|[2,3,4]].
Constructor
as Functor
View the `[|]` list constructor as a functor of arity `2`:
?- ‘[|]'(a,[]) == [a].
?- ‘[|]'(1,[]) == [1].
?- ‘[|]'(f(d,e),[]) == [f(d,e)].
?- ‘[|]'(a, ‘[|]'(b, [])) == [a, b].
?- ‘[|]'(‘[|]'(a, []), []) == [[a]].
Traditional vs
SWI-Prolog
The notation for this is quite a bit more verbose than the
traditional version.
• nevertheless, there is a synonymous description of `[|]` expressions
viewed as trees in the SWI-Prolog documentation:
• https://www.swi-prolog.org/pldoc/man?section=ext-lists
A swipl session handles unification with lists just fine:
?- X = ‘[|]'(a, ‘[|]'(b, ‘[|]'(f(d,e), []))).
X = [a, b, f(d, e)].
Nice that we do not have to tell Prolog to give the reduced
and simpler-to-read presentation of a list.
https://www.swi-prolog.org/pldoc/man?section=ext-lists
— Types of Terms —
There are predicates that test whether arguments are of a
certain type.
We have the following types of terms in Prolog:
• complex terms
• simple terms
• variables
• constants
Hierarchies are a bit easier to read in a tree:
We have the following predicates for testing whether some
object fits a certain category:
Predicates
Predicate Description
‘atom/1’ argument is an atom
‘integer/1’ argument is an integer, e.g.: 4, 10, or -6
‘float/1’ argument is a floating-point number, e.g.: 1.3, or 5.0
‘number/1’ argument is a number, i.e.: an integer or a float
‘atomic/1’ argument is a constant
‘var/1’ argument is a variable
‘nonvar/1’ argument is instantiated
Let us look at `atom` first:
?- atom(a).
?- atom(4).
?- atom(loves(vincent,mia)).
Pretty straightforward, but what about if the argument is a
What about if the argument is a variable?
?- atom(X).
?- X = a, atom(X).
?- atom(X), X = a.
• if a variable is instantiated to an atom, then the call is the same as
using the unified value (the atom) in the argument
• since Prolog performs execution of clauses in left to right order, it is
important that the instantiation is done before the test for `atom`
The other predicate tests function similarly.
• `atomic` is true if the argument is either an atom or a number
• it is false when the argument is neither
?- atomic(mia).
?- atomic(9).
?- atomic(loves(vincent,mia)).
?- atomic(X).
Instantiation
The two predicates `var` and `nonvar`
• negations of each other
• test for uninstantiated/instantiated variable argument
?- X = a, var(X).
?- var(X).
?- X = a, nonvar(X).
?- nonvar(X).
Instantiation
Complex terms with variables nested in them are not
themselves altogether an uninstantiated variable:
?- var(loves(_,mia)).
?- nonvar(loves(_,mia)).
The order of instantiation matters:
?- X = a, var(X).
?- var(X), X = a.
— The Structure of Terms —
The predicate `functor/3` takes three arguments:
• a functor, suppose we call it `f`
• a variable to return name of the functor given in the first argument
• a variable for returning the number of arguments that `f` takes
?- functor(f(a,b), F, A).
?- functor(a, F, A).
?- functor([a,b,c], X, Y).
X = ‘[|]’,
Consider that Prolog will do its best to give you a solution
to the query:
?- functor(T, f, 8).
T = f(_, _, _, _, _, _, _, _).
It has no names for the eight arguments requested.
Suppose we have `f(a, b).` as a fact in a knowledge base.
?- functor(T, f, 2), call(T).
T = f(a, b).
The use of `call/1` will try to search for a solution to `T` as
a query, which was unified to the functor `f`.
We can adapt the use of `functor` to make a predicate to
test for complex terms:
complexterm(X) :-
nonvar(X),
functor(X, _, A),
• the only thing we care about in the above query is that
the number of arguments is at least 1
The predicate `arg` itself takes three arguments:
• an integer for the argument to access from functor `f` (defined next)
(unfortunately, indexing starts at 1 and not 0)
• a functor, call it `f`
• a variable for unification with argument number requested from `f`
?- arg(2, loves(vincent, mia), X).
…or use it to instantiate an argument for the functor:
?- arg(2, loves(vincent, X), mia).
To try to access a non-existent argument will output false:
?- arg(2, happy(yolanda), X).
Another very useful query is `’=..’/2`:
• the single quotes denote that it is a binary operator
• the left argument is a functor
• the right argument is a variable
The variable unifies to a list with functor name as head
element and arguments of the functor as tail.
?- cause(vincent, dead(zed)) =.. X.
X = [cause, vincent, dead(zed)].
?- X =.. [a, b(c), d].
X = a(b(c), d).
?- footmassage(Y, mia) =.. X.
X = [footmassage, Y, mia].
Processing
Recursively
Since `=..` operation returns an argument list on the
right-hand side, list processing strategies can be applied.
• to demonstrate, we define a `copy_term` predicate
• the predicate does exactly what its name describes
• the problem is that the term may be complex,
so we must also copy anything nested
• Prolog is very easy to work with combining our skills in recursion
The first two kinds of objects are easy to encode:
copy_term2(X, X) :- atom(X).
copy_term2(X, _) :- var(X).
When the term is complex, we must deal with recursion to
again copy any nested terms.
copy_term2(X, Y) :-
nonvar(X),
functor(X, F, A),
functor(Y, F, A),
X =.. [F|ArgsX],
Y =.. [F|ArgsY],
copy_terms_in_list(ArgsX, ArgsY).
copy_terms_in_list([],[]).
copy_terms_in_list([HIn|TIn], [HOut|TOut]) :-
copy_term2(HIn, HOut),
copy_terms_in_list(TIn, TOut).
(do not forget the previous two predicates)
Implemented
The `copy_term` and `copy_terms_in_list` already
implemented in Prolog, so we gave them slightly different
names; save it in a separate file, load, and give it a try.
— Properties of Operators —
Infix operators (a.k.a binary operators) are functors that
can be written between their two arguments.
• we have the Prolog infix operators:
Prolog uses internal representation for expressions:
• e.g.: our easy-to-read form vs Prolog’s form
• `11 is 2+2*3`
• `is(11, +(2, *(2,3)))`
There are also prefix operators:
• `?-` is a unary prefix
(historically used as “query” operator, now synonymous with `:-`)
• you can use this in any line of a `*.pl` file to have Prolog
execute a query for you
• it will run the query when you load the file in interactive swipl
and output results as if you had typed the query interactively
• execution order of the file is as usual: top-to-bottom, left-to-right
• it will only give the result of one successful completion,
and not all possibilities with backtracking
`:-` Operator
“The directive initialization/1 can be used to run arbitrary Prolog goals.
The specified goal is started after loading the file in which it appears
has completed… SWI-Prolog compiles code as it is read from the file,
and directives are executed as goals. This implies that directives may
call any predicate that has been defined before the point where the
directive appears. It also accepts `?-
• https://www.swi-prolog.org/pldoc/man?section=consulting
https://www.swi-prolog.org/pldoc/man?section=consulting
An interesting way to implement use of `?-` in a loaded file
when you want backtracking to display all possibilities.
% iterate over all possible variable values,
% and then stop (without message of failure)
% the `fail` term forces backtracking
% the `var(X)` is true when there is no solution
?- stuff(X), write(“X = “), writeln(X), fail; var(X).
Precedence
Prolog parses operators and executes nested expressions
based on a precedence ordering.
This is defined with numbers, where lower numbered
operators take precedence over higher numbered ones.
• `8 is 2+2*3`
• `is(8, +(2, *(2,3)))`
• we are familiar with `*` taking precedence over `+`
• above example shows `+` takes precedence over `is`
• notice the internal representation
with nested parentheses respects the priorities
• if `is` took precedence over `+`
• internal representation would be `+(is(8, 2), *(2, 3))`
Left vs Right
Associativity
Operations with the same precedence are resolved by
“left” versus “right” associativity.
Arithmetic operators only work in an expression on the
right of `is` or in some other operator forcing evaluation.
• addition `+` is left-associative:
• ?- 2 + 3 + 4 = +(2, +(3, 4)).
• ?- 2 + 3 + 4 = +(+(2, 3), 4).
(we could just as well use `==` to compare expressions)
Exponent `^` (or equivalently `**`) is right-associative:
?- X is 2^3^2.
?- X is (2^3)^2.
The operators `+` and `^` are not the same precedence
level, so the priority will always overrule:
?- X is 2 + 2^3.
?- X is (2 + 2)^3.
No Priority
Resolution
Parentheses absolutely must be part of an expression for:
• equal priority, but the left and right associativity conflict,
• there is no associativity to resolve the order:
?- 2 =:= 3 == =:=(2,3).
ERROR: Syntax error: Operator priority clash
ERROR: 2 =:
ERROR: ** here **
ERROR: = 3 == =:=(2,3) .
?- (2 =:= 3) == =:=(2,3).
?- 2 =:= (3 == =:=(2,3)).
ERROR: Arithmetic: `(=:=)/2′ is not a function
— Defining Operators —
Prolog lets you define your operators.
• maybe we want a postfix `is_dead`,
e.g.: `is_dead(zed)` written as `zed is_dead`
The syntax for operator definitions is:
:- op(Precedence, Type, Name).
Precedence
• `Precedence` is a number between 0 and 1200
(lower values execute first)
• `Type` is an atom used to configure the arity and associativity
• e.g.: `yfx` configures as an infix operator `f` with left associativity
• the priority of `y` expression has lower than or equal to `f`
• the priority of `x` expression has lower priority than `f`
• see table for possible configurations
• https://www.swi-prolog.org/pldoc/man?section=opsummary
• e.g.: operator `is_dead` could be defined as:
• `:- op(500, xf, is_dead).`
• note that you must also define the operation itself, say
`is_dead(whatever).` as a fact
https://www.swi-prolog.org/pldoc/man?section=opsummary
Precedence
Give the following a try in a separate file,
maybe call it `ops.pl`:
:- op(500, xf, is_dead).
kill(marsellus, zed).
is_dead(whatever).
is_dead(X) :- kill(_, X).
• `:-` introduces a directive (by executing Prolog on load)
• until one satisfying unification makes the statement true
• you can think of the `op` execution as configuring your interactive
session by defining a new way of using `is_dead`
Then load it into swipl session and try a postfix query:
?- zed is_dead.
?- whatever is_dead.
?- just is_dead.
Questions?
Week 14��Ch 9: A Closer Look at Terms�
Using Documentation
Prolog Operators
— Comparing Terms —
Defining Names with Single Quotes
if-else Construct
Identical Variables
Identity Stronger than Instantiation
Lambda Functions
Compare Terms
— Arithmetic Terms —
Comparing Terms (1)
Comparing Terms (2)
Order of Comparisons
Equality Operations
— Lists as Terms —
Do Not Use `.` as in the Textbook
List Construction
List Constructor as Functor
Traditional vs SWI-Prolog
— Types of Terms —
Testing Types
Type Hierarchy
Predicates for Testing
Check for an Atom
Testing Variables for Type
Testing for Atomic
Test for Variable Instantiation (1)
Test for Variable Instantiation (2)
— The Structure of Terms —
Functor Metadata
Variable Matched with Predicate
Solve a Functor
Testing Number of Arguments
Matching Arguments
Wrong Index
All Parts of a Term
Processing Recursively
Copy Simple Terms
Copy Complex Terms
Already Implemented
— Properties of Operators —
Infix Operators
Query Operator
`:-` Operator
Automatic Execution on Load
Precedence
Left vs Right Associativity
Priority Examples
No Priority Resolution
— Defining Operators —
Define Operators
Precedence Syntax
Defining Operand with Precedence
Using the Postfix Operand
Thank You!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com