COMP 481, Prolog, Ch 4, 5, 6
Ch 4: Lists
Copyright By PowCoder代写 加微信 powcoder
Ch 5: Arithmetic
Ch 6: More Lists
University of the Fraser Valley
COMP 481: Functional and Logic Programming
• Chapter 4
• Recursing Down Lists
• Chapter 5
• A Closer Look
• Arithmetic and Lists
• Comparing Integers
• Chapter 6
• Using Append
• Reversing a List
• Naïve Reverse Using Append
• Reverse Using an Accumulator
— Chapter 4: Lists —
A list contains a finite sequence of elements, e.g.:
[mia, vincent, jules, yolanda]
[mia, robber(honey_bunny), X, 2, mia]
[mia, [vincent, jules], [butch, girlfriend(butch)]]
[ [], dead(zed), [2, [b, chopper]], [2, [b, chopper]] ]
• the contents are offset with square brackets
• elements are separated by comma
• length is the number of elements
• any object can be an element of a list
• can have an empty list [] of length zero
• can have nested lists
• can mix different kinds of elements
• atoms, numbers, complex terms, lists
• as in Haskell, lists have a head and tail
• e.g.: list `[mia, vincent, jules, yolanda]` has:
• head `mia`
• tail `[vincent, jules, yolanda]`
• the empty list has no internal structure, and is special in Prolog
Tail Access
use the Sheffer stroke `|` to decompose a list into parts.
The head and tail of a list can be accessed like so:
?- [X | Y] = [mia, vincent, jules, yolanda]
Y = [vincent, jules, yolanda].
The same access with an empty list will result in `false.`:
?- [X | Y] = [].
Tail Example
More examples with a complex list:
?- [X | Y] = [ [], dead(zed), [2, [b, chopper]], [], Z ].
Y = [dead(zed), [2, [b, chopper]], [], Z].
• the variable `X` is bound to the head
• the variable `Y` is bound to the tail
• textbook / swipl differ from each other slightly
• variable `Z = _7800` (bound to an internal variable) does not display
• we can read value of `Y` and see that it contains a variable `Z`
• imply that the variable `Z` can be instantiated with some other value
We can decompose into more than just head and tail with
the Sheffer stroke:
?- [X, Y | W] = [ [], [2, [b, chopper]], [], Z ].
Y = [2, [b, chopper]],
W = [[], Z].
• access list elements in order using variables separated by comma
• each variable becomes bound to corresponding element of the list
Suppose we only want the 2nd and 4th element.
• no need to list arbitrary variable names of elements we can ignore
• instead make use of the anonymous variable with underscore `_`
?- [_, [X | _], _, Y] = [ [], [2, [b, chopper]], [], Z ].
• use `_` when not interested in the element value
• there is no output for what `_` is bound to
• each occurence of `_` is independent, being bound differently
If we wanted access to the second element (itself, a list) of
the previous example, and to its tail of elements:
?- [_, [_ | X] | _] = [ [], [2, [b, chopper]], [], Z ].
X = [[b, chopper]].
• notice that the second element is the list `[2, [b, chopper]]`
• so, the tail is `[[b, chopper]]`
• doubly nested!
— Member —
A predicate is provided by Prolog called `member/2`.
• the `/2` just means that it takes two arguments
• you can see them all for SWI in their documentation
• https://www.swi-prolog.org/pldoc/man?section=predsummary
The `member(X, L)` predicate:
• takes first argument `X` value
• and checks if this value matches with an element in the list `L`
• evaluates to `true` if some element does match
• evaluates to `false` otherwise
https://www.swi-prolog.org/pldoc/man?section=predsummary
Membership
Implementation
We can practice recursion further by implementing our
own version `membership`:
membership(X, [X | T]).
membership(X, [H | T] :- membership(X, T).
• first fact — base case when `X` is at the head of the list
• second fact — recursive case when `X` may be an element in the tail
This implementation matches every element in the list:
?- membership(2, [1, 3, 2, 4, 2]).
• at any point you can choose to stop by pressing ENTER instead of `;`
What if we only wanted one such match, say, the first one?
• the `!` operator is called a cut
• it acts as a gate to stop backtracking once computation executes it
• use this to have our predicate design stop after finding one match
membership(X, [X|T]) :- !.
membership(X, [H|T]) :- membership(X, T).
• in the first rule, once the base case is applied, it is followed by a cut
• once one element in the input list is found, the predicate execution
does not back out to continue searching for alternatives
• the recursion takes elements from the front of the list
Membership
We can observe the behaviour with `trace`:
?- membership(2, [1, 3, 2, 4, 2]).
Call: (10) membership(2, [1, 3, 2, 4, 2]) ? creep
Call: (11) membership(2, [3, 2, 4, 2]) ? creep
Call: (12) membership(2, [2, 4, 2]) ? creep
Exit: (12) membership(2, [2, 4, 2]) ? creep
Exit: (11) membership(2, [3, 2, 4, 2]) ? creep
Exit: (10) membership(2, [1, 3, 2, 4, 2]) ? creep
• the `Call` steps are trying to find a way to prove the statement
• the `Exit` steps have established the statement as true
Membership
Trace Details
• each recursive call to `membership` removes the head of the list
• this extends the search tree with each successive `Call` step
• once `2` is matched, the head of the list, then the search:
• matches the most current subgoal against the base case rule
• establishes the subgoal statement as true
• Prolog can `Exit`, having achieved the current subgoal
• satisfies each recursive rule as a true statement with each `Exit`
• the original query is proven `true`
Membership
Remove use of cut from implementation as we consider more queries.
Consider the following search for a query that fails:
[trace] 30 ?- membership(5, [1,3,2,4]).
Call: (10) membership(5, [1, 3, 2, 4]) ? creep
Call: (11) membership(5, [3, 2, 4]) ? creep
Call: (12) membership(5, [2, 4]) ? creep
Call: (13) membership(5, [4]) ? creep
Call: (14) membership(5, []) ? creep
Fail: (14) membership(5, []) ? creep
Fail: (13) membership(5, [4]) ? creep
Fail: (12) membership(5, [2, 4]) ? creep
Fail: (11) membership(5, [3, 2, 4]) ? creep
Fail: (10) membership(5, [1, 3, 2, 4]) ? creep
Membership
A query to discover what elements can be in a list:
?- membership(X, [1,3,2,4]).
Membership
Implementation
Lastly, we deal with the warnings from Prolog when we
load the knowledge base for implementing ̀ membership`.
• it is complaining about two singleton variables
• this means that these variables tell us nothing useful,
so they do not need to be named explicitly
• we can replace them with the anonymous variable
membership(X, [X|_]).
membership(X, [_|T]) :- membership(X, T).
• warning exists as anonymous variables help our code be readable
• we can focus on the variables that are relevant to the code
— Recursing Down Lists —
Stroke `|`
Use Sheffer stroke to split multiple lists to create rules that:
• check whether two lists have the same length
• check the first list contains only elements that match `a`
• check the second list contains only elements that match `b`
All three properties checked in
one recursive predicate:
a2b([], []).
a2b([a | Ta],[b | Tb]) :-
a2b(Ta, Tb).
• the base case we have is typically always placed first
(so Prolog can match it first in searches top to bottom)
• the recursive case removes the head from each list,
matching with `a` in the first list, and `b` in the second
Predicate:
We design recursive predicates built up from base cases.
• what would happen on queries that are supposed to fail?
• the recursive rule `a2b([a | Ta], [b | Tb]) :- a2b(Ta, Tb).`
• applied to query `a2b([a,2], [b,c])`
• results in `a2b([2], [c])`
• there is no rule that matches this term
• the query evaluates to `false.` as expected
• applied to query `a2b([a], [b,b])`
• results in `a2b([], [b])`
• same issue as previous example
Using `a2b`
Once loaded, we can start with some simple queries:
?- a2b([a,a], [b,b]).
?- a2b([a,a,a], [b,b,b]).
However, the matching in Prolog is quite powerful:
?- a2b(X, [b,b,b,b]).
X = [a, a, a, a].
?- a2b([a,a,a], Y).
Y = [b, b, b].
We can even list through possible matches for both
arguments, similar to use of `membership` predicate.
?- a2b(X, Y).
X = Y, Y = [] ;
X = [a, a],
Y = [b, b] ;
X = [a, a, a],
Y = [b, b, b] .
— Chapter 5: Arithmetic —
Arithmetic
Arithmetic Examples Prolog Notation
6 + 2 = 8 8 is 6 + 2
6 * 2 = 12 12 is 6 * 2
6 – 2 = 4 4 is 6 – 2
6 – 8 = -2 -2 is 6 – 8
6 ÷ 2 = 3 3 is 6 // 2
7 ÷ 2 = 3 3 is 7 // 2
7 mod 2 = 1 1 is mod(7, 2)
• note the textbook had integer division with `/` operator,
• whereas SWI Prolog has `//` for integer division.
Arithmetic Examples
?- -2 is 6 – 8.
?- 3 is 6 / 2.
?- 3 is 7 / 2.
?- 3 is 7 // 2.
?- 3 is 6 // 2.
?- 3.5 is 7 / 2.
?- 1 is mod(7, 2).
Queries as
Calculations
Replace the solutions in statements with variables so we
can query as a calculation:
?- R is mod(7, 2).
With the basic understanding of arithmetic in Prolog:
• we can write a predicate similar to a function
• use the predicate to get the result of some calculation
• we give two arguments, where the second holds the result
f(X, Y) :- Y is (X + 3)*2
• you can add the above rule interactively with `[user].`
• after entering statements (typically, each on its own line):
• exit this mode by pressing `CTRL-C`
• select abort with `a`
• (you can see other options by pressing `h`)
?- [user].
|: f(X, Y) :- Y is (X+3)*2.
Action (h for help) ? % Execution Aborted
?- f(5, Y).
?- f(12, Y).
Typical precedence rules in arithmetic
are respected in Prolog.
— A Closer Look —
Evaluation
Unfortunately…
• the presentation of familiar operations
• hid that Prolog does not perform those operations
• down to a reduced single value
Actual evaluation is avoided unless queried together
with something that forces arithmetic to evaluate:
• the familiar operations of `+`, `-`, `*`, and `//` are also functors
• an expression such as `3+2` is also a term
(as learned in previous chapters)
Evaluating
It can be frustrating without this understanding to query
?- X = 3+2.
Prolog simply bound the `3+2` term to the variable `X`
To force evaluation, we must use the `is` keyword:
• it acts much like `=` assignment
• it tells Prolog to perform arithmetic and assign result to a variable
• only arithmetic allowed on the right-hand side
Expression
We must also be careful with any variables appearing in
expressions on the right-hand side.
• suppose we pass a variable to our predicate:
?- f(X, 12).
ERROR: Arguments are not sufficiently instantiated
• this is because we would be trying to calculate `12 is (X+3)*2`,
but `X` is not instantiated to a number
Predicates
Binary operators such as `+` can be written in-line
• for user-friendly readability
• They are really just predicates:
• written in the usual way `+(X, Y)`
?- X is +(3, 2).
?- is(X, +(3, 2)).
Because part of the gap between declarative and procedural
• is due to the order of execution,
• extending Prolog to include arithmetic further widens this gap,
• since variables on the right of `is` expressions
must be instantiated with numeric values.
— Arithmetic and Lists —
Calculating
A useful application of arithmetic in Prolog is queries
involving information about data structures such as lists.
• for example, recursively define predicate for length of a list:
1. the empty list has zero length
2. a nonempty list has one more than the length of its tail
len([], 0).
len([_|T], N) :- len(T, X), N is X+1.
?- len( [a, s, d, c, d, s, [2,3], g], W ).
There are other ways to define calculating the length of a
list in Prolog.
Other programming languages store intermediate value,
i.e. an accumulator, and Prolog can do so recursively:
accLen([_ | T], A, L) :-
Anew is A + 1, accLen(T, Anew, L).
accLen([], A, A).
?- accLen( [a,s,d,c,d,s,[2,3],g], 0, L ).
Design for
Calculating
• the recursive design for calculating length from the input list
accumulates result in the second parameter
• the result is stored in the third parameter
• the base case applies when the elements of the list are exhausted
from each recursive step
• in the base, the second argument value
is instantiated to the third argument variable value (A, A)
[trace] 7 ?- accLen([a,b,c], 0, L).
Call: (10) accLen([a, b, c], 0, _1882) ? creep
Call: (11) _3130 is 0+1 ? creep
Exit: (11) 1 is 0+1 ? creep
Call: (11) accLen([b, c], 1, _1882) ? creep
Call: (12) _5404 is 1+1 ? creep
Exit: (12) 2 is 1+1 ? creep
Call: (12) accLen([c], 2, _1882) ? creep
Call: (13) _7678 is 2+1 ? creep
Exit: (13) 3 is 2+1 ? creep
Call: (13) accLen([], 3, _1882) ? creep
Exit: (13) accLen([], 3, 3) ? creep
Exit: (12) accLen([c], 2, 3) ? creep
Exit: (11) accLen([b, c], 1, 3) ? creep
Exit: (10) accLen([a, b, c], 0, 3) ? creep
We can make things a bit cleaner for the user
(who is likely a programmer anyway):
leng(L, Length) :- accLen(L, 0, Length).
?- leng([a,b,c], W).
Accumulation
You may wonder why we care to perform the length
calculation using an accumulator design:
• an `accLen` query will have a search that is tail recursive
(equivalent to a loop construct)
• once a base case is reached, calculations
are performed before recursing to the next level
• a `len` query performs calculations after each recursive step, so the
result is built up while exiting the recursive steps
Compare with a trace of a `len` query…
[trace] 12 ?- len([a,b,c], L).
Call: (10) len([a, b, c], _4600) ? creep
Call: (11) len([b, c], _5834) ? creep
Call: (12) len([c], _6590) ? creep
Call: (13) len([], _7346) ? creep
Exit: (13) len([], 0) ? creep
Call: (13) _6590 is 0+1 ? creep
Exit: (13) 1 is 0+1 ? creep
Exit: (12) len([c], 1) ? creep
Call: (12) _5834 is 1+1 ? creep
Exit: (12) 2 is 1+1 ? creep
Exit: (11) len([b, c], 2) ? creep
Call: (11) _4600 is 2+1 ? creep
Exit: (11) 3 is 2+1 ? creep
Exit: (10) len([a, b, c], 3) ? creep
— Comparing Integers —
Comparison
The familiar inequality statements in math are merely
Boolean predicates.
They are evaluated without any necessary use of `is`:
Arithmetic Examples Prolog Notation
x < y X < Y. x ≤ y X =< Y. x = y X =:= Y. x ≠ y X =\= Y. x ≥ y X >= Y.
x > y X > Y.
Evaluation
However, using comparison forces evaluation of any
arithmetic expressions on either side of these relations.
• note that `=:=` is different from `=` because of forced evaluation:
?- 2+2 = 4.
?- 2+2 =:= 4.
So, keep in mind that `=` is meant to unify both sides.
Evaluation
Because of forced evaluation:
• we must ensure any variables have been instantiated
• to numeric values,
• otherwise, we will have errors
ERROR: Arguments are not sufficiently instantiated
?- X = 2.3, X < 3. ?- X = b, X < 3. ERROR: Arithmetic: `b/0' is not a function We can combine multiple recursive statements to help calculate the maximum value in a list • each recursive rule will also make use of accumulators accMax([H|T], A, Max) :- accMax(T, H, Max). accMax([H|T], A, Max) :- accMax(T, A, Max). accMax([], A, A). Notice the recursion will apply based on the result of comparing the element unified to `H` with the current value of `A`. acc see how we can use `accMax` to calculate the maximum element in a list: ?- accMax([3, 1, 2, 6, 5], 0, M). • a slightly annoying `false.` output after result of `M = 6` if we use the prompt to press `;` as if there were more solutions • we can get rid of these if our code is designed with tail recursion (no more calculations when backing out of recursion) • add a term cut `!` to the end of each recursive `accMax` predicate • use conjunction `,`, i.e. `, !.`, replaces `.` • locks choice at each recursive step to those before execution passes `!` • then when we back out of recursion, Prolog will not backtrack Another example is needed, since our list could have negative values: ?- accMax([-11, -2, -7, -4, -12], 0, M). • we do not want this behaviour • the way around the problem is to initialize the second argument to the head of the list max(List, Max) :- [H|_] = List, accMax(List, H, Max). ?- max([-11, -2, -7, -4, -12], M). • with unification `=`, expressions on either side must consider procedural order of execution (leftmost variables unified first) • there is a built in `max/2` predicate • but it is meant to only be used on the right side of an `is` statement • and it only takes two numeric values — Chapter 6: More Lists — — Append — We will be implementing a predicate `append/3` that • will take three arguments, • with the third argument as a variable • it unifies to the concatenation of the two input argument lists For example, the queries: • `append([a,b], [1,2], [a,b,1,2])` should be true • `append([a,[b]], [1,[2]], [a,[b],1,[2]])` should be true • `append([a,b], [1,2], [a,b,1])` should be false • `append([a,b], [1,2], [1,2,a,b])` should be false Implementing The function already exists in the Prolog library, and we can use a variable in the third argument to get a result: ?- append([a,b,c], [1,2,3], X). X = [a, b, c, 1, 2, 3]. We could also use it to split a list, but we move on to our own implementation, called `app`: app([], L, L). app([H|T], L2, [H|L3]) :- app(T, L2, L3). ?- app([a,b], [1,2], L). L = [a, b, 1, 2]. Design for • the base case just has an empty list appended with any other list `L`, which results in just the same list `L` • the recursive case is more involved than we have seen before • read variables from left-to-right: • `H` is defined in the first list (where it appears first) • `H` is repeated again as head of third list, combined with `L3` tail • the left term • imagines what a result would look like, and the common first element `H` • the right term • recurses on the smaller problem of one less element for lists `T` and `L3` • all that remains of `L3` would be the same elements as in `L2` • in this case, the base rule applies • if we use variable in the third argument, then at this point, `L3` is matched to `L2` A trace shows how the solution is built up from the base predicate: [trace] 5 ?- app([a,b,c], [1,2,3], L). Call: (10) app([a, b, c], [1, 2, 3], _2846) ? creep Call: (11) app([b, c], [1, 2, 3], _4136) ? creep Call: (12) app([c], [1, 2, 3], _4900) ? creep Call: (13) app([], [1, 2, 3], _5664) ? creep Exit: (13) app([], [1, 2, 3], [1, 2, 3]) ? creep Exit: (12) app([c], [1, 2, 3], [c, 1, 2, 3]) ? creep Exit: (11) app([b, c], [1, 2, 3], [b, c, 1, 2, 3]) ? creep Exit: (10) app([a, b, c], [1, 2, 3], [a, b, c, 1, 2, 3]) ? creep L = [a, b, c, 1, 2, 3]. • it is important to see how the matchings are built up • going into recursive calls, we get the complex term `[ a | [b | [c | _5664 ]]]` 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com