PLE treasure hunt -- Lambda-Prolog

List reverse

In lecture we defined a predicate append X Y Z which checks if Z is the result of appending the lists X and Y. Use append to write another predicate reverse X Y which checks if Y is the result of reversing the order of list X. (Hint: reverse is recursive. If the tail of X reversed to Z, how could you express Y?)

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?

Dynamic scoping

Suppose we have these declarations:

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?

Red vs. green cuts

Prolog has an imperative construct called a cut (written '!') which inhibits backtracking. Its purpose is efficiency and conciseness, at the cost of non-declarative programming.

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 true

These 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 P succeeds, but C fails, the if will immediately fail. This kind of use is called a green cut: it has no effect on the meaning of the program, only its efficiency. Again, we can reorder these definitions if we want.

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 red cut, because it does effect the meaning of the program. And we can longer safely reorder these definitions. The idea is to use the information in the ordering itself to eliminate redundancy.

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 = a

The 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?

Loops

Looping in Prolog can be simulated with the 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