Courses/CS 332L/Data structures and unification
From CSWiki
Look again at the Symbolic Differentiation program.
The first predicate (called differentiate/3)
differentiate(F, X, G) :- deriv(F, X, FD), simplify(FD, G).
may be read either declaratively or procedurally.
Declarative reading:
- The result of differentiating F with respect to X is G if (:-) the deriv of F with respect to X is FD and the simplification of FD is G.
Procedural Reading
- To differentiate F with respect to X: (:-) first take the derivative of F with respecct to X to get FD; then simplify FD to get G, which is returned.
Although Prolog likes to think of itself as a declarative language (and it was one of the first), since any program that runs on a computer results from a step by step process followed by the computer, every programming language is ultimately procedural. So we will use the declarative reading of Prolog when we can, but for the most part we will think of our programs as traditionally procedural.
Contents |
[edit] Data structures
[edit] Lists
All Prolog data structures are trees. Prolog has a simple way to build data structures: just write them down. As we saw last time,
[a, b, c]
is a list. What this really amounts to is a tree data structure. The tree node for lists is represented by ".".
. . . [a, b, c]
/ \ / \ / \
a . a . a [b, c]
/ \ / \
b . b [c]
/ \
c []
Since we write lists using "|", it would make sense to use "|" as the tree element. For historical reasons, we use ".". Consider the following.
?- X = .(a, [b, c]). X = [a, b, c] ?- X = [a | [b, c]]. X = [a, b, c]
In other words,
[a, b, c] [a | [b, c]] .(a, [b, c]) [a, b | [c]] .(a, .(b, [c])) [a, b | [c | []]] .(a, .(b, .(c, [])))
are all the same thing. They are the tree data structure shown above.
So if you are ever confused about what a list really looks like, draw the tree for it. That's what's really there.
[edit] Arithmetic operators
Prolog automatically translates expressions using arithmetic operators into trees. Thus
x+y
is the tree
+
/ \
x y
And
x + y * z
is the tree
+
/ \
x *
/ \
y z
Why isn't it the following?
*
/ \
+ z
/ \
x y
The answer is that Prolog "knows" that "+" binds less tightly than "*" and that
x + y * z
really means
x + (y * z)
However if you wrote
(x + y) * z
Prolog would construct the second tree.
You can always be explicit about how tress are constructed by using parentheses.
You can also use functional notation. We did that with "." and lists. We can do that with "+" and "*". The following constructs the first tree above.
?- X = +(x, *(y, z)). X = x+y*z
This constructs the second tree.
?- X = *(+(x, y), z). X = (x+y)*z
Prolog is somewhat unusual in that it lets you use ".", "+", "*", and other operators as function symbols.
[edit] Unification
The "=" symbol is not assignment as in Java. It asks Prolog to attempt to unify the terms on the left and right. Unification means matching structures and assigning variables.
?- f(A, b) = f(a, B). A = a, B = b
By the way, what is
f(a, b)
It is
f
/ \
a b
So
f(A, b)
is
f
/ \
A b
and
f(a, B)
is
f
/ \
a B
Unification ask whether the structures are the same, and if so to assign the matching variables and values.
What about
?- f(a, b) = f(a, c). No
Since b and c don't match, unification fails.
In all the examples we saw above, one side had a single variable. A variable can match anything, even a data structure.
?- X = +(x, *(y, z)). X = x+y*z
matches the entire tree to the variable X. (This is very much like a pointer in Java.) We could have written it the other way.
?- +(x, *(y, z)) = X. X = x+y*z
As the first example shows, variables can appear on both sides of the "=" sign.
Consider
?- f(X, W) = f(Y, Z), g(a, h(X, Y)) = g(X, Z). X = a, W = h(a, a), Y = a, Z = h(a, a)
The first part establishes that
X = Y W = Z
The second part establishes that
X = a Z = h(X, Y)
The result is what you see above.
This could have been written the other way around. The result would be the same.
?- g(a, h(X, Y)) = g(X, Z), f(X, W) = f(Y, Z). X = a, Y = a, Z = h(a, a), W = h(a, a)
The first part establishes that
X = a Z = h(a, Y)
The second part establishes that
Y = X, but X = a, so Y = a. W = Z, but Z = h(a, Y) and Y = a, so W = Z = h(a, a)
[edit] Example of symbolic differentiation
In our symbolic differentiation program one of the deriv/3 rules was the following.
deriv(F^C, X, C*F^(C-1)*G) :- integer(C), !, deriv(F, X, G).
This is the rule for differentiating something when it is raised to an integer power.
This rule is really about transforming one data structure into another. It says that if the data structure we want to differentiate is
^
/ \
F C
and if C is an integer, then the result of differentiating is the following data structure.
*
/ \
* G
/ \
C ^
/ \
F -
/ \
C 1
Prolog interprets X*Y*Z to be (X*Y)*Z, which is why the second * is the top node of the tree. In this case, since multiplication is associative, it doesn't matter which * is the top node.
The right hand side of this rule says first that the rule only applies if C is an integer. Then it tells you that G is defined as the derivative of F with respect to X.
