EXERCISE SHEET 2

{This time is much the same as last, except that since most of what you'll be asked to do involves unification, don't bother hitting a ; when you're told the instantiations of variables, as there won't be any more anyway. Just hit a return.}

{Before that, we'll have a little go with the two basic input/output predicates, 'read' and 'write'. read(X) reads in the next term, which is ended (a more technical term for this is 'delimited') by a full stop. write(X) writes the term X out, normally on the screen.}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    [user].
    pw:-
        read(X),
        ok(X).
    pw:-
        write('Wrong!'),
        nl,
        pw.

    ok(hello).
    ok(cheerio).
    ^D

{Now you've defined a predicate called pw, which will read from the keyboard and only succeed when you give one of the two passwords.}

1

    pw.

{You'll now get a prompt (you might, the first time, get 2 - don't worry about it...). Try the following answers to the questions. When it succeeds, type 'pw.' again to restart it.}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    hi.

    help.

    cheerio.

    'hello'.

    'hello '.

    hello
    .

    X.

{Having found out the serious limitations of this password program, let's leave it now and go on to unification. See if you can figure out what Prolog will do with the following:}

1
2
3
4
5
6
7
8
9

    apple=apple.

    apple=banana.

    apple=Banana.

    Apple=banana.

    Apple=Banana.

{You saw in Exercise Sheet 1 the "internal names" of variables, which are printed as eg. _0, ie. an underline followed by a number. If two variables you see have the same internal name, then they've been unified together and instantiating one instantiates the other to the same thing.}

{OK, let's start unifying some terms together (\== reads 'do not unify with':}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    f(X) = f(82).

    f('cherry') = f(X).

    f(damson) = f(_).

    f(apple) = f(apple, _).

    f(apple) \== f(X).

    f(damson, cherry) \== f(X, banana).

{You may have to think about the result of that one...}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    f(grape) = ff(U).

    f(X, h(Y)) = f(19, h(P)).

    f(X, g(orange)) = f(Y, g(Y)).

    s(X, X) = s(_, lemon).

    f(g(Z), h(W)) = f(W, V).

    f(f(M)) = f(f(f(f(f)))).

{That last one was an exercise in bracket-counting. For this next one (a similar exercise if you have a lot of time) you might like to know that to interrupt processing you type a ^C (stands for control-C. For those who don't know, this means pressing character C or c while the Control key is pressed down), and when it asks you for what to do, type A or a (and a carriage return) for abort.}

1

    X = p(6, X).

{So far, it's not been TOO hard, but from here on it gets more complicated...}

1
2
3

    f(X, g(H, 9), L) = f(L, g(8, 9), melon).

    f(g(9, L)) = f(L(9, K)).

{Yes, that was supposed to happen...}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    f(X, Y, Z) = f(Y, Z, x).

    s(t(W), N, V, R) = s(R, t(strawberry), N, V).

    s(s(M, R), quince, s(L, R)) = s(s(R, grape), L, s(_, _)).

    s(V, S2, G, try(Q, S2), U, p(D)) = s(U, Q, V, try(D, new), Fa, Fa).

    s(X, 2+3, 11, KK, si(B)) = s(B, X, N, N, N).

    s(R, 2+3, 11, KK, si(B)) = s(B, R, N, N, X).

{From here on, it gets sufficiently hard for me to have to write the two parts of the unification on separate lines, on order to help you. Rarely will you see this kind of complex unification in programs, so if you can manage these then you've cracked the problem.}

1
2
3
4
5
6
7
8

    c(M, h(C), g(Y), U, M,    s(M, N), C) =
    c(_, L,    M,    4, g(L), s(P, P), U).

    d(h(U), raspberry, g(X, Y), N3,      S,       N3, S) =
    d(X,    T,     M,       h(t(U)), g(Y, X), U,  M).

    s(S,  v(P, Q, R), P,    h(Q), s(D0), t(S,    7)) =
    s(D0, v(P, P, 7), h(P), P,    s(Q),  t(h(R), R)).

{This finishes our exercise on matching (or unification).}