CTM: Exercise 3-11
Posted by Urban Hafner
The problem
Limitations of difference lists. What goes wrong when trying to append the same difference list more than once?
My solution
Assume you have the two difference lists (a|b|c|X)#X and (d|e|f|Y)#Y. To append them you bind X to (d|e|f|Y). Using the Append function from 3.4.4 what you get is (a|b|c|d|e|f|Y)#Y. But this changes the first difference list into (a|b|c|d|e|f|Y)#(d|e|f|Y).
If you then try to use the first difference list in another append with, say (x|y|Z)#Z you will get a unification error because what you try to do in the Append function is unify (d|e|f|Y) with (x|y|Z). This will of course fail. But in the first append of the difference list the unification was X=(d|e|f|Y) which of course succeeds always as X is an unbound variable.
