| ITEC 380 |
| 2013fall |
| ibarland aaray |
|
|
|
home—lectures—recipe—exams—hws—D2L—breeze (snow day)
% Write: mem
% Write: len (length of a list) (remind yourself of scheme version):
%
% len(Data,N) : true if `Data` contains `N` items.
len([],0).
len([_|R],X) :- len(R,Y), X is Y+1.
% A note on numbers:
%
coolerThan(X,Y) :- X > Y.
%
% prolog has no problem with coolerThan(4,7).
% But what about coolerThan(4,X) --
% What do you expect the answer should be?
%%% arithmetic is weird in Prolog:
% Try writing the predicate
% biggerByOne(X,Y) if X-1 = Y.
%
% One attempt would be:
biggerByOne(X,X-1).
% Alas, this won't do:
% biggerByOne(4,3). % no
% biggerByOne(4,4-1). % yes (!) -- prolog pattern-matches, but no arith!
% to do arithmetic in prolog, you have to use the keyword "is":
%
biggerByOne(X,Y) :- Y is X-1.
%
% This is pretty good: As you'd expect:
% :- biggerByOne(5,4).
% :- not(biggerByOne(5,6)).
% biggerByOne(3,X) will give solution "X=2", like you'd expect.
% HOWEVER:
% biggerByOne(Y,2) will won't give "Y=3"; it gives an error!
% When you use 'is', every variable on the right-hand-side
% *has to already have* a value.
% Here's some motivation, as to why this should be the case:
%
% f(X,Y) : true when Y = g(X),
% where g(X)=x^5 - 101x^4 -10x^3 +9x - 909
% (Note how we turn a numeric function g : R->R
% into a boolean predicate f : RxR -> boolean)
%
f(X,Y) :- Y is X*X*X*X*X - 101*X*X*X*X - 10*X*X*X + 1010*X*X + 9*X - 909.
%
% What if we query f(X,0) -- this means
% prolog has to be smart enough to handle 5th-degree polynomials.
% While you can imagine prolog designers lookup up the quartic formula
% and supporting it in the language,
% it turns out there is *no* closed-form solution for degree 5 and higher (!!)
% [This is a surprising result of math -- Galois.]
% NB I happened to construct f so that it has nice roots though:
% f = (x-1)(x+1)(x-3)(x+3)(x-101)
% Define factorial in Prolog:
% (define (! n)
% (if (zero? n)
% 1
% (* n (! (sub1 n)))))
%
% Here's what we want to say:
%
% fact(0,1).
% fact(N,NF) := NF = N*Z, fact(N-1,Z).
% However, it gives an error! --
% prolog sees "NF = N*Z",
% and it's expecting too much to try to find *all* values of NF,Z
% which would make this true.
% Even writing "NF is N*Z" doesn't help, since Z isn't instantiated.
% Instead, we'll have alter our spec, so that Z gets
% instantiated before we mention N*Z.
fact(N,NF) :- Nless1 is N-1,
fact(Nless1,Z),
NF is N*Z.
fact(0,1).
% Let's try it.
% Uh-oh, infinite loop! Why?
% Solution: swap the order.
%
% Now it seems better.
% But what does fact(3,7) do? What about fact(3,N), if we reject 6?
%
% Solution: add "N>1" to the recursive case.
% Why does it fix Q2?
%
% We see that (esp with numbers), prolog isn't as purely declarative
% as we'd like. Instead, we're forced to think about how it implements
% its matching engine :-( Arguably, that's a shortcoming of Prolog.
% (Note that Mathematica goes to great lengths to handle numbers,
% although it's more functional than declarative.)
%
home—lectures—recipe—exams—hws—D2L—breeze (snow day)
| ©2013, Ian Barland, Radford University Last modified 2013.Nov.22 (Fri) |
Please mail any suggestions (incl. typos, broken links) to ibarland  radford.edu |
 |