Do we need to know about Quilts for the final?

Though my understanding of Prolog has come a long way in the last 24 or so hours, one concept I am still a little unclear on is that of the "most general unifier." Could anyone provide a relatively simple example with two terms that unify under two different unifiers, one of them being the most general. Despite his painfully formal treatment of the concept, I think Sethi really could have used this in the text.

Edited by author 03-14-2004 02:29 PM
Amir -- I don't have the exact Sethi description in front of me, but in general, the difference is that objects can have methods and access control (e.g. "private"). In reality, this is just a bit of syntactic sugar, but conceptually, this means that objects can be thought of as "active" things responding to messages, while records are just passive data.

copypaper -- dear God no.

Taybo -- Sure. Unifying
    f(A,B) = f(C,D).
{ A = B = C = D = 3 } is more specific than { A = B = C = D = X }, which in turn is more specific than (Update: this is false -- see later post) { A = C = f(X, Y), B = D = f(Z, W) }, which is more specific than { A = C = X, B = D = Y }, which is the most general unifier (MGU). As I tried to say in the review, you can substitute into the MGU to obtain any other unifier, but not the other way around. Practically, if you build up your substitution recursively, you will end up with the MGU by default:
    f(A, B) = F(C, D)
    { A = C = X } // unifying A and C
    f(X, B) = F(X, D)
    { A = C = X, B = D = Y } // unifying B and D
    f(X, Y) = f(X, Y)

What is the difference between "array" and "record" again?

Mickey -- I'm not sure I understand your question. Think of the differences between structs and arrays in C.

Edited by author 03-14-2004 01:43 PM
{ A = B = C = D = X }, which in turn is more specific than { A = C = f(X, Y), B = D = f(Z, W) },

Hey Sean, I don't quite understand why you can make the above assertion. Like you said in the review, you should be able to substitute into a more general unifier to obtain a more specific one. How does it work in this case since you have functors in the second unifier? Substituions are function from Variables to Terms...

Thanks dawg.

Good catch. I'm wrong here. Neither of these is more specific than the other, but both are legal substitutions, and both are more specific than the MGU.

Edited by author 03-14-2004 04:26 PM
what is the difference between map and reduction function on page 352(Chapter 9 ML stuff).
Thanks

Duy--

The map funtion takes in a function and a list as arguments and applies the function to each item in the list.

The reduce function takes in a function and a list and applies the function to the first item in the list and a recursive call to reduce with the function and the tail of the list as arguments.

Think of reduce as a generalization of "sum-all" or "product-all." The difference is that the function can be something else besides add or multiply.

More important than just understanding what these functions do is understanding how and why they work. I suggest tracing through them on some sample input.

yo
i needs some help with understanding #7c and d on previous final.
c) can f(f(X)) unify with X?
    If X can be substituted for f(f(X)) then yes, but the question is: is
    the substitution even possible. Can X unify with an expression
    containing X?? And even if X can unify with an expression
    containing X will the meaning of it be valid in this case. i.e. if we
    sub f(f(x)) for X in both expressions we then get f(f(f(f(x)))) and
    f(f(x)) these two do not seem equivalent.
d) can f(g(X,Y),h(X)) unify with f(Z,h(g(Z,X)))?
     if Z = g(X,Y) and X = g(Z,X) then yes, but as above is the
     substitution if g(Z,X) for X legal or valid as the expression g(Z,X)
     contains X?

duy -- for extra understanding through extra pain, infer the types of map and reduce.

abster -- (c) See the section in Sethi on the "occurs check", and note that this is a way to create infinite, recursively-defined data structures, e.g.
    X = [1,2|X]
is an endless list of [1,2,1,2,...]. Also note that X = f(f(X)) doesn't have to be strange at all -- f() can be the identity function. (d) same.

so what you are saying is that they both unify?

Edited by author 03-14-2004 05:27 PM
abster -- Maybe, maybe not -- it depends on the rules. I encourage you to read Sethi on this, as he does a pretty good job explaining, and there are advantages and disadvantages to either approach. If you don't like Sethi on this, the first link for a google search turns up a good explanation.

I did read that section and what i get out of it is that yes they unify, but you cant guarantee that the computation will terminate.

Then you are enlightened, grasshopper ;). (btw, my experiments show that GNU prolog will go into an infinite loop for (c), and crash for (d), so while they may unify in theory, this fact isn't too useful in practice)

Last touch up question.

Would you please discuss, the history of evolution and emphasis on why , not when or who. Or at least point me in the direction of where I could do some reading on that.

Thanks, much appreciated.

Amir