a9
symlink that references /cs/www/classes/cs372/spring18/a9
.
a9/tester
(or a9/t
, or make a t9
Bash alias—we'll show you how!).
swipl
.
if-then-else
structure (->
) and disjunction (;
)between
on rotate
, outin
,
and/or btw
, you're probably not understanding how Prolog naturally generates alternatives.
The slides have code for a number of predicates that generate alternatives but sf_gen
on 184-185 was
included specifically to help with outin
and btw
.
once/1
once(Goal)
, which limits Goal
to producing one result. Example:
?- once(nth0(Pos, [a,b,a,c,a], a)). Pos = 0.
For some problems the tester is not sensitive to potential alternatives that don't materialize.
Consider this behavior for lst
, from the first problem below.
?- lst([1,2,3],X). X = 3 ; false.It prompts because somewhere there's at least one more clause that can be tried. The tester won't distinguish between the above behavior and the following behavior:
?- lst([1,2,3],X). X = 3.
append.pl
The purpose of this problem is to help you see that append/3
can be used for lots more than concatenating two lists. You are to write several simple predicates that heed this restriction: the only predicates you can use are length/2
and append/3
. For some predicates, like head
, a single append
goal will be all you need:
head(List,Elem) :- append(...).Additionally, you may use the
[E1, E2, ..., EN]
list syntax, like in append([X,Y],[],Z)
,
but you may not use the [E1, E2, ..., EN | Tail]
notation, introduced on slide 175.
Here are the predicates you are to implement:
head(?List, ?Elem)
expresses the relationship that the first element of List
is Elem
.
It fails if the list is empty.
?- head([a,b,c],H). H = a. ?- head([a,b,c],x). false.
lst(?List, ?Elem)
expresses the relationship that the last element of List
is Elem
.
It fails if the list is empty.
?- lst([1,2,3],X). X = 3 ; false. ?- lst(L,4). L = [4] ; L = [_G2199, 4] ; L = [_G2199, _G2205, 4] ; ...keeps going...
init(?List, ?Init)
expresses the relationship that Init
is all but the last element of
List
. It fails if List
is empty.
?- init([a,b,c,d],I). I = [a, b, c] ; false.
tail(?List, ?Tail)
expresses the relationship that Tail
is all but the first element of
List
. It fails if List
is empty.
?- tail([a,b,c],T). T = [b, c].
min2(+List)
fails if List
is not at least two elements long.
?- min2([1]). false. ?- min2([1,2]). true.
mem(?Elem, ?List)
behaves just like the built-in member/2
:
?- mem(2,[1,2,3]). true ; false. ?- mem(E,[1,2,3]). E = 1 ; E = 2 ; E = 3 ; false.
contains(+List, ?SubList)
expresses the relationship that List
contains SubList
.
?- contains([1,2,3,4,5],[3,4,5]). true ; false. ?- contains([1,2,3,4,5],[10,20]). false. ?- contains([1,2,3],S), S \== []. S = [1] ; S = [1, 2] ; S = [1, 2, 3] ; S = [2] ; S = [2, 3] ; S = [3] ; false.
firstlast(?List, ?FL)
expresses the relationship that FL
is a list containing the first and
last elements of List
. It fails if List
is empty.
?- firstlast(L,[1,2]). L = [1, 2] ; L = [1, _G3410, 2] ; L = [1, _G3410, _G3416, 2] ; ...keeps going...
halves(?List, ?First, ?Last)
expresses the relationship that the first half of List
is
First
and the second half is Last
. It fails if the length of List
is odd.
?- halves([1,2,3,4],F,S). F = [1, 2], S = [3, 4] ; false. ?- halves([1,2,3,4,5],F,S). false. ?- halves([],F,S). F = S, S = [] ; false. ?- halves(L,[a,b],S). L = [a, b, _G4635, _G4638], S = [_G4635, _G4638].Remember the restriction: you may only use
append
and length
in these predicates!
a9/t append.pl -t PREDICATE
to test an individual predicate. As you've seen before, the
-t
follows the problem name.
splits.pl
splits.hs
from assignment 3. Write a predicate
splits(+List,-Split)
that unifies Split
with each "split" of List
in turn. Example:
?- sp
lits([1,2,3],S).
S = [1]/[2, 3] ;
S = [1, 2]/[3] ;
false.
Note that Split
is not an atom. It is a structure with the functor /
. Observe:
?- splits([1,2,3], A/B). A = [1], B = [2, 3] ; A = [1, 2], B = [3] ; false.Here are additional examples. Note that splitting a list with less than two elements fails.
?- splits([],S). false. ?- splits([1],S). false. ?- splits([1,2],S). S = [1]/[2] ; false. ?- atom_chars('splits',Chars), splits(Chars,S). Chars = [s, p, l, i, t, s], S = [s]/[p, l, i, t, s] ; Chars = [s, p, l, i, t, s], S = [s, p]/[l, i, t, s] ; Chars = [s, p, l, i, t, s], S = [s, p, l]/[i, t, s] ; Chars = [s, p, l, i, t, s], S = [s, p, l, i]/[t, s] ; Chars = [s, p, l, i, t, s], S = [s, p, l, i, t]/[s] ; false.My solution uses only two predicates:
append
and \==
.
repl.pl
repl(?E, +N, ?R)
that unifies R
with a list that is N
replications of E
. If N
is less than 0
, repl
fails.
?- repl(x,5,L). L = [x, x, x, x, x]. ?- repl(1,3,[1,1,1]). true. ?- repl(X,2,L), X=7. X = 7, L = [7, 7]. ?- repl(a,0,X). X = []. ?- repl(a,-1,X). false.
pick.pl
pick(+From, +Positions, -Picked)
that unifies Picked
with an atom consisting
of the characters in From
at the zero-based, non-negative positions in Positions
.
?- pick('testing', [0,6], S). S = tg. ?- pick('testing', [1,1,1], S). S = eee. ?- pick('testing', [10,2,4], S). S = si. ?- between(0,6,P), P2 is P+1, pick('testing', [P,P2], S), writeln(S), fail. te es st ti in ng g false. ?- pick('testing', [], S). S = ''.If a position is out of bounds, it is silently ignored. My solution uses
atom_chars
, findall
,
member
, and nth0
.
polyperim.pl
Write a predicate polyperim(+Vertices, -Perim)
that unifies Perim
with the perimeter of the
polygon described by the sequence of Cartesian points in Vertices
, a list of pt
structures.
?- polyperim([pt(0,0),pt(3,4),pt(0,4),pt(0,0)],Perim). Perim = 12.0. ?- polyperim([pt(0,0),pt(0,1),pt(1,1),pt(1,0),pt(0,0)],Perim). Perim = 4.0. ?- polyperim([pt(0,0),pt(1,1),pt(0,1),pt(1,0),pt(0,0)],Perim). Perim = 4.82842712474619.There is no upper bound on the number of points but at least four points are required, so that the minimal path describes a triangle. (Think of it as ABCA, with the final A "closing" the path.) If less than four points are specified,
polyperim
fails with a message:
?- polyperim([pt(0,0),pt(3,4),pt(0,4)],Perim). At least a four-point path is required. false.The last point must be the same as the first. If not, polyperim fails with a message:
?- polyperim([pt(0,0),pt(3,4),pt(0,4),pt(0,1)],Perim). Path is not closed. false.Note: check first for the minimum number of points and then a closed path. This is not a course on geometric algorithms so keep things simple! Calculate the perimeter by simply summing the lengths of all the sides; don't worry about intersecting sides, coincident vertices, etc.
Be sure that polyperim
produces only one result.
switched.pl
switched.rb
from assignment 6. a9/births.pl
has a subset of the baby name data, represented as facts. Here are the first five lines:
$ head -5 a9/births.pl births(1950,'Linda',f,80437). births(1950,'Mary',f,65461). births(1950,'Patricia',f,47942). births(1950,'Barbara',f,41560). births(1950,'Susan',f,38024).
births.pl
holds data for only 1950-1959. Names with less than 70 births are not included in births.pl
.
Your task is to write a predicate switched(+First, +Last)
that prints a table like that produced by
the Ruby version. To save a little typing, switched
assumes that the years specified are in the
20th century.
?- switched(51,58). 1951 1952 1953 1954 1955 1956 1957 1958 Dana 1.19 1.20 1.26 1.29 1.00 0.79 0.67 0.64 Jackie 1.40 1.29 1.14 1.13 1.11 0.94 0.72 0.57 Kelly 4.23 2.74 3.73 2.10 2.32 1.77 0.98 0.51 Kim 2.58 1.82 1.47 1.08 0.61 0.30 0.17 0.12 Rene 1.43 1.32 1.15 1.24 1.13 0.88 0.87 0.89 Stacy 1.06 0.81 0.62 0.47 0.44 0.36 0.29 0.21 Tracy 1.51 1.14 1.02 0.73 0.56 0.55 0.59 0.59 true.If no names are found,
switched
isn't very smart; it goes ahead and prints the header row:
?- switched(52,53). 1952 1953 true.If you want to make your switched smarter, that's fine—we won't test with any spans that produce no names. Also, I'll only test with spans where the first year is less than the last year. Names are left-justified in a ten-wide field. Below is a
format
call that does that.
Note that the dollar sign is included only to clearly show the end of the output.
?- format('~w~t~10|$', 'David'). David $ true.Outputting the ratios is a little more complicated. I use
sformat
, like this:
?- sformat(Out, '~t~2f~6|', 2.32754), write(Out). 2.33 Out = " 2.33".The call above instantiates
Out
to a six-character string (a list of integers that are character codes, and shown with double quotes) and write(Out)
outputs it.
See help(format)
if you're curious about the details of using ~t
but the essence is that you can use
~N|
to specify that a field extend to column N, and then put a ~t
on the left, right, or
both sides of a specifier like ~w
or ~f
to get right, left, or center justification, respectively.
To consult a9/births.pl
when you consult switched.pl
, put the following line in
your switched.pl
.
:-[a9/births].As mentioned in the assignment 8 write-up for
queries.pl
, that construction, :-
followed by
a query, causes the query to be executed when the file is consulted.
Sidebar: Note that :-[a9/births.pl]
. fails with an error. For an extra point on this assignment, add a note to
observations.txt
with a speculative but sound explanation of why [a9/births]
works but
[a9/births.pl]
doesn't. No Googling, etc., please!
You might also use that :- ...
mechanism to cause a couple of tests to be run when the file is loaded.
Below I define test/0
to do a couple of switched
queries, putting a line of dashes between them.
I then invoke it with :-test.
test :- switched(51,58), writeln('-----'), switched(51,52). :-test.That invocation of
test
must follow the definition of switched
and consulting
a9/births.pl
.
You'll see that with swipl switched.pl
the output from evaluating the query
test.
appears before
"Welcome to SWI-Prolog..."
Be sure to comment out lines like :-test.
before turning in your solution.
(That output will cause a9/tester
failures, too, as you'd expect.)
My Prolog solution is significantly smaller than my Ruby solution but it's easy to get sideways on this problem if you don't come up with a good set of helper predicates. I suggest that you give this problem a try on your own but if it starts to get ugly, http://www.cs.arizona.edu/classes/cs372/spring18/a9/switched-hints.pdf shows how I broke it down. The points assigned to this problem are based on the assumption that you will take a look at the hints.
rotate.pl
rotate(+L,?R)
that instantiates R
to each
unique list that is a left rotation of L
.
For example, the list [1,2,3]
can be rotated left to produce [2,3,1]
which in turn can be rotated left again to produce [3,1,2]
.
?- rotate([1,2,3],L), writeln(L), fail. [1,2,3] [2,3,1] [3,1,2] false. ?- rotate([a,b,c,d],R). R = [a, b, c, d] ; R = [b, c, d, a] ; R = [c, d, a, b] ; R = [d, a, b, c] ; false. ?- rotate([1], R). R = [1] ; false. ?- rotate([], R). false.Additionally,
rotate
can be asked whether the second term is a rotation of the first term:
?- rotate([a,b,c],[c,a,b]). true ; false. ?- rotate([a,b,c],[c,b,a]). false.
outin.pl
Write a Prolog predicate outin(+L, ?R)
that generates the elements of the list
L
in an
"outside-in" sequence: the first element, the last element, the second element, the next to last element, etc.
If the list has an odd number of elements, the middle element is the last one generated.
Restriction: You may not use is/2
.
?- outin([1,2,3,4,5],X). X = 1 ; X = 5 ; X = 2 ; X = 4 ; X = 3 ; false. ?- outin([1,2,3,4],X). X = 1 ; X = 4 ; X = 2 ; X = 3 ; false. ?- outin([1],X). X = 1 ; false. ?- outin([],X). false.
btw.pl
Write a Prolog predicate btw(+L, +X, ?R)
that instantiates R
to copies of L
with
X
inserted between each element in turn.
Restriction: You may not use append
or between
.
?- btw([1,2,3,4,5],---,R). R = [1, ---, 2, 3, 4, 5] ; R = [1, 2, ---, 3, 4, 5] ; R = [1, 2, 3, ---, 4, 5] ; R = [1, 2, 3, 4, ---, 5] ; false. ?- btw([1,2],***,R). R = [1, ***, 2] ; false. ?- btw([1],***,R). false. ?- btw([],x,R). false.
fsort.pl
[3,1,5]
represents a stack of three pancakes with diameters of 3", 1" and 5" where the 3"
pancake is on the top and the 5" pancake is on the bottom. If a spatula is inserted below the 1" pancake
(putting the stack [3,1]
on the spatula) and then flipped over, the resulting stack is [1,3,5]
.
In this problem you are to write a predicate fsort(+Pancakes, -Flips)
that instantiates Flips
to a sequence of flip positions that will order Pancakes
, an integer list, from smallest to largest,
with the largest pancake (integer) on the bottom (at the end of the list). fsort
stands for "flip sort".
fsort
does not produce a sorted list—its only result is the flip sequence.
The flip position is defined as the number of pancakes on the spatula. In the above example the flip position is 2.
Flips
would be instantiated to [2]
.
Below are some examples. Note the use of a set of case/2
facts to show a series of examples with one query.
$ cat fsortcases.pl case(a, [3,1,5]). case(b, [5,4,3,2,1]). case(c, [3,4,5,1,2]). case(d, [5,1,3,1,4,2]). case(e, [1,2,3,4]). case(f, [5]). $ swipl ... ?- [fsortcases,fsort]. % fsortcases compiled 0.00 sec, 7 clauses % fsort compiled 0.00 sec, 10 clauses true. ?- case(_,L), fsort(L,Flips). L = [3, 1, 5], Flips = [2] ; L = [5, 4, 3, 2, 1], Flips = [5] ; L = [3, 4, 5, 1, 2], Flips = [3, 5, 2] ; L = [5, 1, 3, 1, 4, 2], Flips = [6, 2, 5, 2, 4, 3] ; L = [1, 2, 3, 4], Flips = [] ; L = [5], Flips = [].Your solution needs only to produce a sequence of flips that results in a sorted stack; the sequences it produces do NOT need to match the sequences shown above. There are some requirements on the flips, however:
2
and the number of pancakes, inclusive.
[5,3,3,4]
.
fsort
must always generate exactly one solution.
"Pancake sorting" is a well-known problem. I first encountered it in 1993's Duke Internet Programming Contest. There's even a Wikipedia article about pancake sorting. (Read it!) I debated whether to go with this problem because it's so well known but it's a fun problem and it's interesting to solve in Prolog, so here it is. I did Google up one "solution" in Prolog but it's got some issues! I strongly encourage you to build your Prolog skills by solving this problem without Google's assistance.
The clauses in my current solution have a total of seventeen goals. I don't use is/2
at all.
I do use max_list
. You might find nth0
to be useful; if you look at slide 123 closely you'll see it can be used to both extract values and find values, among other things. There's an nth1
, too, if you find one-based thinking to be a better choice.
connect.pl
In this problem you are to write a predicate connect/4
that finds and displays a suitable sequence of
cables to connect two pieces of equipment that are some distance apart. Each cable is specified by a three element list.
Here is a list that represents a twelve-foot cable with a male connector on one end and a female connector on the other:
[m,12,f]Let's consider an example of using
connect
to produce a sequence of cables. Imagine that to your left
is a piece of equipment with a male connector. On your right, fifteen feet away, is a piece of equipment with a female connector. To connect the equipment you have two cables:
?- connect([ [m,10,f], [f,7,m] ], m, 15, f).
connect
's first argument is a list with the two cables. The second, third, and fourth arguments respectively represent the gender of the connector of the equipment on the left (male—m
), the distance between the equipment (15 feet),
and the gender of the connector of the equipment on the right (female—f
).
Here's the query and its result:
?- connect([ [m,10,f], [f,7,m] ], m, 15, f). F----------MF-------M true.We see that a connection is possible in this case; a valid sequence of connections is shown. Observe that the first cable was reversed to make the connection. The number of dashes is the length of the cable. There's some slack in the connection—only fifteen feet needs to be spanned but the total length of the cables is seventeen feet. That's fine.
Note that the output has no representation of the pieces of equipment on the left and right that we're connecting with the cables.
Only male/female connections are valid in the world of connect.pl
.
In some cases a connection cannot be made, but connect
always succeeds:
?- connect([[m,10,f], [f,7,m] ], m, 25, f). Cannot connect true. ?- connect([[m,10,f], [f,7,m] ], m, 15, m). Cannot connect true.More examples:
?- connect([[m,1,m],[f,1,f],[m,10,m],[f,5,f],[m,3,f]], m, 20, f). F-FM-MF-----FM----------MF---M true. ?- connect([[m,1,m],[f,1,f],[m,10,m],[f,5,f],[m,3,f]], m, 20, m). Cannot connect true. ?- connect([[m,1,m],[f,1,f],[m,10,m],[f,5,f],[m,3,f]], m, 10, f). F-FM-MF-----FM----------M true. ?- connect([[m,10,f]], m, 1, f). F----------M true.IMPORTANT: The ordering of cables your solution produces for a particular connection need NOT match that shown above. Any valid ordering is suitable. (A Ruby program,
a9/pc.rb
, analyzes the output.)
Note that you do not need to use all the cables or exactly span the distance.
Assume the following:
connect
are valid—you won't see two-element lists, non-numeric or non-positive lengths, ends other than f
and m
, etc.
You can approach this problem using an approach similar to that in the pit-crossing example in the slides. (Note: The pit-crossing slides have yet to be published as this is being written but you can see that example in the Spring 2016 Prolog slides, on 233+.)
My current solution is around 25 goals; about a third of those are related to producing the output.
ints.pl
ints(-L)
that instantiates L
to successively longer lists of the integers.
?- ints(L). L = [0] ; L = [0, 1] ; L = [0, 1, -1] ; L = [0, 1, -1, 2] ; L = [0, 1, -1, 2, -2] ; L = [0, 1, -1, 2, -2, 3] ; L = [0, 1, -1, 2, -2, 3, -3] ; ...
iz.pl
In this problem you are to write a predicate iz/2
, an analog of is/2
that
evaluates expressions involving atoms rather than the arithmetic expressions that is/2
evaluates.
Let's start with some examples:
?- S iz abc+xyz. % + concatenates two atoms. S = abcxyz. ?- S iz (ab + cd)*2. % *N produces N replications of the atom. S = abcdabcd. ?- S iz -cat*3. % - is a unary operator that produces a % reversed copy of the atom. S = tactactac. ?- S iz -cat+dog. S = tacdog. ?- S iz abcde / 2. % / N produces the first N characters % of the atom. S = ab. ?- S iz abcde / -3. % If N is negative, / produces last N % characters S = cde. ?- N is 3-5, S iz (-testing)/N. N = -2, S = et.Two functions,
len
and wrap
, are also supported. len(E)
evaluates to an atom
(not a number!) that represents the length of E
.
?- N iz len(abc*15). N = '45'. ?- N iz len(len(abc*15)). N = '2'.
wrap
adds characters to both ends of its argument. If wrap
is called with two arguments, the second argument is concatenated on both ends of the string:
?- S iz wrap(abc, ==). S = '==abc=='. ?- S iz wrap(wrap(abc, ==), '*' * 3). S = '***==abc==***'.If
wrap
is called with three arguments, the second and third arguments are concatenated to the left and right ends of the string, respectively:
?- S iz wrap(abc, '(', ')'). S = '(abc)'. ?- S iz wrap(abc, '>' * 2, '<' * 3). S = '>>abc<<<'.It is important to understand that
len(xy)
, wrap(abc, ==)
, and wrap(abc, '(', ')')
are simply structures. If iz
encounters a two-term structure whose functor is wrap
(like wrap(abc, ==)
) its value is the concatenation of the second term, the first term, and the second term.
iz
evaluates len
and wrap
like is
evaluates random
and sqrt
.
The atoms comma
, dollar
, dot
, and space
do not evaluate to themselves
with iz/2
but instead evaluate to the atoms ','
, '$'
, '.'
, and
' '
, respectively. (They are similar to e
and pi
in arithmetic expressions evaluated with
is/2
.)
In the following examples note that swipl
is adding some parentheses on the
comma and the dollar sign that stand alone. That adornment disappears when those characters are used in combination with others.
?- S iz comma. S = (','). ?- S iz dollar. S = ($). ?- S iz dot. S = ('.'). ?- S iz space. S = ' '. ?- S iz comma+dollar*2+space+dot*3. S = ',$$ ...'. ?- S iz wrap(wrap(space+comma+space,dot),dollar). S = '$. , .$'. ?- S iz dollarcommadotspace. S = dollarcommadotspace.The final example above demonstrates that these four special atoms don't have special meaning if they appear in a larger atom.
Here is a summary for iz/2
:
-Atom iz +Expr
unifies Atom
with the result of evaluating Expr
, a structure representing
a calculation involving atoms. The following operators are supported:
E1 + E2
E1
and E2
with iz
.
E * N
E
(evaluated with iz
) with itself N
times. (Just like Ruby.)
N
is a term that can be evaluated with is/2
(repeat, is/2
). Assume N >= 0
.
E / N
N
characters of E
if N
is greater than (less than) 0
.
If N
is zero, an empty atom is produced. (An empty atom is shown as two single quotes with nothing between them.)
N
is a term that can be evaluated with is/2
.
The behavior is undefined if abs(N)
is greater than the length of E
.
-E
E
reversed.
len(E)
E
.
wrap(E1,E2)
E2+E1+E2
.
wrap(E1,E2,E3)
E2+E1+E3
.
The behavior of iz
is undefined for all cases not covered by the above.
Things like 1+2
, abc*xyz
, etc., simply won't be tested.
Here are some cases that demonstrate that the right-hand operand of *
and /
can be
an arithmetic expression:
?- X = 2, Y= 3, S iz 'ab' * (X+Y*3). X = 2, Y = 3, S = ababababababababababab . ?- S = '0123456789', R iz S + -S, End iz R / -(2+3). S = '0123456789', R = '01234567899876543210', End = '43210' .
-a+b*3
Prolog creates a tree structure that reflects the precedence and associativity of the operators.
is/2
evaluates a tree as an arithmetic expression. iz/2
evaluates a tree as a "string expression".
Note the contrast when the same tree is evaluated by is
and iz
:
?- X is pi + e*3. % using is X = 11.296438138966929. ?- X iz pi + e*3. % using iz X = pieee .It's important to understand Prolog itself parses the expression and builds a corresponding structure that takes operator precedence into account.
display/1
shows the tree:
?- display(pi + e*3). +(pi,*(e,3)) true.
Processing of syntactically invalid expressions like abc + + xyz
never proceeds as far as a call
to iz
.
Below is some code to get you started. It fully implements the + operation.
$ cat a9/iz0.pl /* Declare iz to be an infix operator. (Remember that the leading :- causes the code to be evaluated as a goal, not consulted as a clause.) */ :-op(700, xfx, iz). A iz A :- atom(A), !. R iz E1+E2 :- R1 iz E1, R2 iz E2, atom_concat(R1, R2, R).Here are examples that use the version of
iz
just above.
?- [a9/iz0]. % Note: no ".pl" true. ?- X iz abc+def. X = abcdef. ?- X iz abc+def, Y iz X+'...'+X. X = abcdef, Y = 'abcdef...abcdef'. ?- X iz a+b+(c+(de+fg)+hij+k)+l. X = abcdefghijkl.Let's look at the code provided above and first consider the second clause:
R iz E1 + E2 :- R1 iz E1, R2 iz E2, atom_concat(R1, R2, R).The first thing you may notice is that the head,
R iz E1 + E2
,
doesn't match the functor(term,term,...)
form we've always seen for the heads of rules.
That's because the op(700, xfx, iz)
call above lets us use iz
as an infix
operator, and that applies in both the head and body of a rule.
Here is a completely equivalent version that doesn't take advantage of the op
specification:
iz(R,E1+E2) :- iz(R1,E1), iz(R2,E2), atom_concat(R1, R2, R).With that equivalence explained, let's focus on the version in
a9/iz0.pl
, which uses the infix form:
R iz E1 + E2 :- R1 iz E1, R2 iz E2, atom_concat(R1, R2, R).Consider the goal
X iz ab+cd
. That goal unifies with the head of the above rule like this:
?- (X iz ab+cd) = (R iz E1+E2). X = R, E1 = ab, E2 = cd.If
E1
is instantiated to ab
then the first goal in the body of the rule would be equivalent to
R1 iz ab
. That goal unifies with the head of this rule:
A iz A :- atom(A), !.This rule represents the base case for the recursive evaluation performed by
iz
.
It says,
"IfAnother way to read it is,A
is an atom then the result of evaluating that atom isA
."
"An atom evaluates to itself."The result is that
R1 iz ab
" instantiates R1
to ab
.
Note that the leaves of the expression's tree are always atoms.
It's important to recognize that because the iz(R, E1+E2)
rule is recursive,
it'll handle every tree composed of +
operations.
Here are the heads (and necks) for all the iz
rules that I've got in my solution:
R iz E1+E2 :- R iz E1*NumExpr :- R iz -E :- R iz E1 / NumExpr :- R iz len(E) :- R iz wrap(E,Wrap) :- R iz wrap(E,First,Last) :-Via recursion, those heads handle all possible combinations of operations, like this one:
?- X iz wrap((-(ab+cde*4)/6+xyz), 'Start>','<'+(end*3+zz*2)). X = 'Start>edcedcxyz<endendendzzzz'.If you find yourself wanting to add a bunch of rules like
R iz (E1+E2+E2) :- ... R iz (E1*E2) / NumExpr :- ...then STOP! You're not recognizing that a set of rules based on the heads above will cover ALL the operations.
atomic_list_concat
predicateiz0.pl
above uses atom_concat
but atomic_list_concat(+List, -Atom)
is a more general predicate:
?- atomic_list_concat([ab,c,def,ghij], S). S = abcdefghij.
?- X iz abc+-abc. % No space between + and - ERROR: Syntax error: Operator expected ERROR: X iz abc ERROR: ** here ** ERROR: +-abc .To make it work, add a space or parenthesize:
?- X iz abc+ -abc. X = abccba. ?- X iz abc+(-abc). X = abccba.This issue only arises with unary operators, of course.
iz-extra.txt
iz
to handle.
They can be operators, or functions like len
and wrap
. Perhaps use op/3
to define a new operator!
Include the required clauses in iz.pl
and create iz-extra.txt
, a plain text file that
talks about your creation(s) and also shows them in action with swipl
.
observations.txt
Submit a plain text file named observations.txt
with...
(a) (1 point extra credit) An estimate of how many hours it took you to complete this assignment. Put that estimate on a line by itself, like this:
Hours: 3.5There should be only one
"Hours:"
line in observations.txt
. (It's fine if you care to provide per-problem times, and that data is useful to us, but report it in some form of your own invention that doesn't contain the string "Hours:"
. Thanks!)
Feedback and comments about the assignment are welcome, too. Was it too long, too hard, too detailed? Speak up! I appreciate all feedback, favorable or not.
(b) (1-3 points extra credit) Cite an interesting course-related observation (or observations) that you made while working on the assignment. The observation should have at least a little bit of depth. Think of me thinking "Good!" as one point, "Excellent!" as two points, and "Wow!" as three points. I'm looking for quality, not quantity.
Use a9/turnin
to submit your work. You can run a9/turnin
as often as you want. We'll grade your final pre-deadline submission.
Just like on assignment 8 I'll use my plsize
script to show you the "sizes" of my solutions. (Recall that the script counts left parentheses and commas, which I claim is a reasonable proxy for program size for Prolog source code.)
Here's what I see as of press time, with comments stripped:
$ a9/plsize $(grep -v txt a9/delivs) append.pl: 65 splits.pl: 7 repl.pl: 15 pick.pl: 19 polyperim.pl: 53 switched.pl: 106 rotate.pl: 10 outin.pl: 9 btw.pl: 13 fsort.pl: 54 connect.pl: 100 ints.pl: 22 iz.pl: 76
Aside from ->
and ;
you can use any elements of Prolog that you desire, but the assignment is written with the intention that it can be completed easily using only the material presented on Prolog slides presented through Wednesday, April 25.
Point values of problems correspond closely to the "assignment points" mentioned in the syllabus. For example, a 10-point problem would correspond to about 1% of your final grade in the course.
Feel free to use comments to document your code as you see fit, but note that no comments are required, and no points will be awarded for documentation itself. (In other words, no part of your score will be based on documentation.)
In Prolog, %
is comment to end of line.
Multi-line comments with /* ... */
, just like in Java, are supported, too.
Remember that late assignments are not accepted and that there are no late days; but if circumstances beyond your control interfere with your work on this assignment, there may be grounds for an extension. See the syllabus for details.
My estimate is that it will take a typical CS junior 10-15 hours to complete this assignment.
Our goal is that everybody gets 100% on this assignment AND gets it done in an amount of time that is reasonable for them.
Assignments are not take-home tests! We hope you'll make use of Piazza, email and office hours if you run into trouble. We're happy to help you get started with any or all of these problems but in any event, if you put 10 hours into this assignment and don't seem to be close to completing it, it's definitely time to touch base with us. Specifically mention that you've reached ten hours. Give us a chance to speed you up!
mishaps.pl
"A butt by the family cow was one of the five different mishaps that befell Farmer Brown, his wife, his daughter, his teenage son, and his farmhand one summer morning. From the rhyme that follows, can you determine the mishap that happened to each of the five, and the order in which the events occurred?
"The garter snake was surprised in a patch And bit a grown man's finger. One person who weeded a flower bed Received a nasty stinger. The farmer's mishap happened first; Son Johnny's happened third. When Mr. Reston was kicked by the mule, He said, "My word! My word!" The sting of the bee was the fourth mishap To befall our rural cast. Neither it nor the wasp attacked Mrs. Brown Whose mishap wasn't the last."
For mishaps.pl
you are to encode as Prolog goals the pertinent information in the above rhyme and then write a predicate mishaps/0
that uses those goals to solve the puzzle.
a9/mishaps-out.txt
shows a run of mishaps/0
with the exact output you are to produce, but you might enjoy the challenge of solving the puzzle using Prolog before looking at the expected output or trying the tester.
The challenge of this problem is of course the encoding of the information as Prolog goals. Solutions must both produce the correct output and accurately encode the information as stated in the rhyme to earn full credit. The tester will check for correct output; we'll check manually for accurate encoding.
You might start like this:
mishaps(Mishaps) :- Mishaps = [ ... ].A similar start for the Zebra puzzle is this:
zebra(Houses) :- Houses = [house(norwegian, _, _, _, _), _, house(_, _, _, milk, _), _, _].Querying
zebra(H)
produces only one possible value for H
, the list of houses:
?- zebra(H). H = [house(norwegian, _G1222, _G1223, _G1224, _G1225), _G1227, house(_G1233, _G1234, _G1235, milk, _G1237), _G1239, _G1242].Let's add a
member
goal that encodes the statement that the Englishman lives in the red house:
zebra(Houses) :- Houses = [house(norwegian, _, _, _, _), _, house(_, _, _, milk, _), _, _], member(house(englishman, _, _, _, red), Houses).Now we get four possible values for
H
: (blank lines added)
?- zebra(H). H = [house(norwegian, _G2194, _G2195, _G2196, _G2197), house(englishman, _G2218, _G2219, _G2220, red), house(_G2205, _G2206, _G2207, milk, _G2209), _G2211, _G2214] ; H = [house(norwegian, _G2194, _G2195, _G2196, _G2197), _G2199, house(englishman, _G2206, _G2207, milk, red), _G2211, _G2214] ; H = [house(norwegian, _G2194, _G2195, _G2196, _G2197), _G2199, house(_G2205, _G2206, _G2207, milk, _G2209), house(englishman, _G2218, _G2219, _G2220, red), _G2214] ; H = [house(norwegian, _G2194, _G2195, _G2196, _G2197), _G2199, house(_G2205, _G2206, _G2207, milk, _G2209), _G2211, house(englishman, _G2218, _G2219, _G2220, red)]. ?- findall(r, zebra(H), Results), length(Results,N). Results = [r, r, r, r], N = 4.If we add a goal that states that the Spaniard owns the dog, we go up to twelve possible values for
H
:
zebra(Houses) :- Houses = [house(norwegian, _, _, _, _), _, house(_, _, _, milk, _), _, _], member(house(englishman, _, _, _, red), Houses), member(house(spaniard, dog, _, _, _), Houses). ?- findall(r, zebra(H), Results), length(Results,N). Results = [r, r, r, r, r, r, r, r, r|...], N = 12.Some goals will make the number of possible values for the list of houses go up, and other goals will make the number of possible values go down. If we properly encode all the information, we'll end up with only one possible value for the list of houses.
Follow a similar process when adding goals to represent information about the mishaps. That is, add goals to
mishaps/1
one at a time. Query mishaps(M)
after each addition.
If you inadvertently introduce a contradiction for the Zebra puzzle, like length(Houses,6)
, you'll see this:
?- zebra(H). false.Similarly, if you add a goal to
mishaps/1
and find that mishaps(M)
then fails, you'll need to step back and consider why that new goal creates a situation with no possible solutions. You might try leaving the new goal in place and commenting one or more earlier goals to find the conflict.
When you've got mishaps/1
working—producing a single possibility for the list of mishaps—use it
to write mishaps/0
.
Remember: Solutions must both produce the correct output and accurately encode the information as stated in the rhyme to earn full credit. The tester will check for correct output; we'll check manually for accurate encoding. We'll be happy to take a look at your code prior to the deadline to see if we see any issues with the encoding.