Self-test 2 Solutions

Unification and lists 2
 
  Do the following unify and (if so) what are the variable instantiations?
   
 
  1. | ?- Var = [1, 2, 3].


    2. Yes. Var=[1,2,3]

  2. | ?- Var = [Head, Tail].


    3. Yes. Var = [Head,Tail].

  3. | ?- [_|Tail] = Var.


    4. Yes. Var = [_A|Tail]

  4. | ?- [Head|Tail] = [Head|Tail].


    5. Yes. SICStus Prolog v.3 merely replies true; other Prologs may reply with something like:
    Head = _216, Tail = _217 (where _216 and _217 are both internal variables).

  5. | ?- [Hd1, Hd2|LH_Tail] = [Head|RH_Tail].


    6. Yes. Head = Hd1, RH_Tail = [Hd2|LH_Tail]

    Notice here that RH_Tail is given as instantiated to [Hd2|LH_Tail].

  6. | ?- [LH_Hd1, LH_Hd2, LH_Hd3] = [RH_Hd1, RH_Hd2, RH_Hd3|Tail].


    7. Yes. Tail = [], RH_Hd1 = LH_Hd1, RH_Hd2 = LH_Hd2, RH_Hd3 = LH_Hd3

    Notice here that although the left-hand list has three members, it still unifies with the right-hand list (which seems to have four members) because the tail of the list after the list constructor ("|") can be instantiated to the empty list ("[]").
     
     

Commentary
Unification of lists is usually kept simple (as with: [a, b, c] = [Head|Tail]). However. examples with more than one head are a source of difficult to both novices and more experienced Prolog programmers. If you wish to use such kinds of examples in your programs, you can always use the Prolog interpreter to test the unifications you believe your program will handle.

You should not be particularly discouraged if you only got half of the previous questions correct.

Describe what will happen if you attempt the following and why it will happen:

  1. | ?- S = [a|S].
  2. | ?- [Hd1, Hd2|Tail] = [Head|Tail].
  3. | ?- [Hd, Tl] = [Hd|Tl].
The key point to remember when looking at these examples is that an uninstantiated variable will become instantiated with the =/2 operator. The first example is the key to the remainder. Here, the variable S is unified with a list of which the same variable S is a part. The instantiation of S becomes infinite. Some Prolog interpreters will simply fail to give any response, but usually they will give something like: 
     S = [a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a...
What has happened is that the tail of the list has been instantiated to the whole of the list, which of course includes itself.

A similar thing happens with the example: [Hd1, Hd2|Tail] = [Head|Tail] where Tail in the right-hand list is required to be instantiated with [Hd2|Tail].

The example: [Head, Tl] = [Head|Tl] is apparently more complex. However, it falls into the same kind of pattern, with the variable Tl from the left-hand list being unified with the tail of the second list. The tail of the list is that part after the list constructor ("|") and is always itself a list. So if the Prolog you are using gives any kind of response to such a goal, it would give: 

     Tl = [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[...
These examples look particularly horrid. They are given here to illustrate one of the reasons that Prolog programs sometimes fail to give the expected results.