## 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.