`append X Y Z`

which
checks if `append`

to write
another predicate `reverse X Y`

which checks if
`reverse`

is recursive. If the tail
of
Now write `reverse`

using a Haskell function. You can use
the built-in list append operator "++". Which do you find more
readable? Which is more powerful? Is there a necessary tradeoff
here?

magic_number 3. magic_number_plus_one X :- magic_number Y, X is Y+1. foo X :- (magic_number 2 => magic_number_plus_one X)What is the result of

`magic_number_plus_one X`

? What is
the result of `foo X`

? What does this say about modularity
in Lambda-Prolog?

For example, suppose we want to define our own `if`

construct:

type if o -> o -> o -> o. if P C A :- P, C. % true if both P and C are true if P C A :- not P, A. % true if P is false and A is trueThese two definitions can be reordered, as we would expect in a declarative language.

However, this solution is inefficient, because if `P`
succeeds, then `C` fails, there is no reason to try the
second rule and check `not P`

. We can use cuts to indicate
this:

if P C A :- P, !, C. if P C A :- not P, !, A.Now if

`if`

will immediately fail. This kind of use is called a
However, we know that Prolog tries rules in the order in which they
are declared. Therefore if we ever get to the second rule we know
that `P` is false. So we can omit the check:

if P C A :- P, !, C. if P C A :- A.The remaining cut is now called a

However, red cuts are frowned upon, not only because they violate
declarative style, but because they can inadvertently prevent
multi-way use of a relation. For example, what is wrong with this
definition of `min X Y Z`

, which presumably checks if
`Z` is the minimum of `X` and `Y`?

type min int -> int -> int -> o. min X Y X :- X <= Y, !. min X Y Y.After all,

`min 2 5 Z`

and `min 5 2 Z`

both
correctly give `Z : 2`

. How can we fix it?
In Haskell, where there is no backtracking, we can think of cuts being
automatically placed at the equals sign. For example, we could write
`if`

correctly as:

if p c a | p = c if p c a = aThe straightforward translation of our buggy

`min`

would be:
min x y z | (x < y) && (x == z) = True. min x y z | (y == z) = True.Now it may be more clear why it is broken. What is a simple way to fix it in Haskell?

`repeat`

predicate:
type repeat o. repeat. repeat :- repeat.The first line means that repeat always succeeds. However, if a failure occurs later, backtracking will cause Prolog to consider the second line, which again succeeds, and so on. Thus

`repeat`

is a kind of infinite choice point, which will
evaluate what follows it, over and over again, until that code
succeeds. To end the loop, we use a cut, which prevents any more
backtracking.
Write a loop which reads all of the lines in a file, i.e. calls
`read X`

until `eof X`

succeeds.

PLE Home page Last modified: Tue Jan 30 22:22:48 EST 1996