[This] is an example par excellence of the power of using meaning to solve linguistic problems
MIT computer scientist
STUDENT was another early language understanding program, written by Daniel Bobrow as his Ph.D. research project in 1964. It was designed to read and solve the kind of word problems found in high school algebra books. An example is:
If the number of customers Tom gets is twice the square of 20% of the number of advertisements he runs, and the number of advertisements is 45, then what is the number of customers Tom gets?
STUDENT could correctly reply that the number of customers is 162. To do this, STUDENT must be far more sophisticated than ELIZA; it must process and "understand" a great deal of the input, rather than just concentrate on a few key words. And it must compute a response, rather than just fill in blanks. However, we shall see that the STUDENT program uses little more than the pattern-matching techniques of ELIZA to translate the input into a set of algebraic equations. From there, it must know enough algebra to solve the equations, but that is not very difficult.
The version of STUDENT we develop here is nearly a full implementation of the original. However, remember that while the original was state-of-the-art as of 1964, AI has made some progress in a quarter century, as subsequent chapters will attempt to show.
The description of STUDENT is:
-
Break the input into phrases that will represent equations.
-
Break each phrase into a pair of phrases on either side of the = sign.
-
Break these phrases down further into sums and products, and so on, until finally we bottom out with numbers and variables. (By "variable" here, I mean "mathematical variable," which is distinct from the idea of a "pattern-matching variable" as used in
pat-matchin chapter 6). -
Translate each English phrase into a mathematical expression. We use the idea of a rule-based translator as developed for ELIZA.
-
Solve the resulting mathematical equations, coming up with a value for each unknown variable.
-
Print the values of all the variables.
For example, we might have a pattern of the form (If ?x then ?y), with an associated response that says that ?x and ?y will each be equations or lists of equations.
Applying the pattern to the input above, ?y would have the value (what is the number of customers Tomgets).
Another pattern of the form (?x is ?y) could have a response corresponding to an equation where ?x and ?y are the two sides of the equation.
We could then make up a mathematical variable for (what) and another for (the number of customers Tom gets).
We would recognize this later phrase as a variable because there are no patterns to break it down further.
In contrast, the phrase (twice the square of 20 per cent of the number of advertisements he runs) could match a pattern of the form (twice ?x) and transform to (* 2 (the square of 20 per cent of the number of advertisements he runs)), and by further applying patterns of the form (the square of ?x) and (?x per cent of ?y) we could arrive at a final response of (* 2 (expt (* (/ 20 100) n) 2)), where n is the variable generated by (the number of advertisements he runs).
Thus, we need to represent variables, expressions, equations, and sets of equations.
The easiest thing to do is to use something we know: represent them just as Lisp itself does.
Variables will be symbols, expressions and equations will be nested lists with prefix operators, and sets of equations will be lists of equations.
With that in mind, we can define a list of pattern-response rules corresponding to the type of statements found in algebra word problems.
The structure definition for a rule is repeated here, and the structure exp, an expression, is added.
lhs and rhs stand for left-and right-hand side, respectively.
Note that the constructor mkexp is defined as a constructor that builds expressions without taking keyword arguments.
In general, the notation (:constructorfn args) creates a constructor function with the given name and argument list.1
(defstruct (rule (:type list)) pattern response)
(defstruct (exp (:type list)
(:constructor mkexp (lhs op rhs)))
op lhs rhs)
(defun exp-p (x) (consp x))
(defun exp-args (x) (rest x))We ignored commas and periods in ELIZA, but they are crucial for STUDENT, so we must make allowances for them.
The problem is that a "," in Lisp normally can be used only within a backquote construction, and a "." normally can be used only as a decimal point or in a dotted pair.
The special meaning of these characters to the Lisp reader can be escaped either by preceding the character with a backslash (,) or by surrounding the character by vertical bars (| , |).
(pat-match-abbrev '?x* '(?* ?x))
(pat-match-abbrev '?y* '(?* ?y))
(defparameter *student-rules* (mapcar #'expand-pat-match-abbrev
'(((?x* |.|) ?x)
((?x* |.| ?y*) (?x ?y))
((if ?x* |,| then ?y*) (?x ?y))
((if ?x* then ?y*) (?x ?y))
((if ?x* |,| ?y*) (?x ?y))
((?x* |,| and ?y*) (?x ?y))
((find ?x* and ?y*) ((= to-find-1 ?x) (= to-find-2 ?y)))
((find ?x*) (= to-find ?x))
((?x* equals ?y*) (= ?x ?y))
((?x* same as ?y*) (= ?x ?y))
((?x* = ?y*) (= ?x ?y))
((?x* is equal to ?y*) (= ?x ?y))
((?x* is ?y*) (= ?x ?y))
((?x* - ?y*) (- ?x ?y))
((?x* minus ?y*) (- ?x ?y))
((difference between ?x* and ?y*) (- ?y ?x))
((difference ?x* and ?y*) (- ?y ?x))
((?x* + ?y*) (+ ?x ?y))
((?x* plus ?y*) (+ ?x ?y))
((sum ?x* and ?y*) (+ ?x ?y))
((product ?x* and ?y*) (* ?x ?y))
((?x* * ?y*) (* ?x ?y))
((?x* times ?y*) (* ?x ?y))
((?x* / ?y*) (/ ?x ?y))
((?x* per ?y*) (/ ?x ?y))
((?x* divided by ?y*) (/ ?x ?y))
((half ?x*) (/ ?x 2))
((one half ?x*) (/ ?x 2))
((twice ?x*) (* 2 ?x))
((square ?x*) (* ?x ?x))
((?x* % less than ?y*) (* ?y (/ (- 100 ?x) 100)))
((?x* % more than ?y*) (* ?y (/ (+ 100 ?x) 100)))
((?x* % ?y*) (* (/ ?x 100) ?y)))))The main section of STUDENT will search through the list of rules for a response, just as ELIZA did.
The first point of deviation is that before we substitute the values of the pat-match variables into the response, we must first recursively translate the value of each variable, using the same list of pattern-response rules.
The other difference is that once we're done, we don't just print the response; instead we have to solve the set of equations and print the answers.
The program is summarized in figure 7.1.
 |
| Figure 7.1: Glossary for the STUDENT Program |
(ed: this should be a markdown table)
Before looking carefully at the program, let's try a sample problem: "If z is 3, what is twice z?" Applying the rules to the input gives the following trace:
Input: (If z is 3, what is twice z)
Rule: ((if ?x |,| ?y) (?x ?y))
Binding: ((?x . (z is 3)) (?y . (what is twice z)))
Input: (z is 3)
Rule: ((?x is ?y) (= ?x ?y))
Result: (= z 3)
Input: (what is twice z ?)
Rule: ((?x is ?y) (= ?x ?y))
Binding:((?x . what) (?y . (twice z)))
Input: (twice z)
Rule: ((twice ?x) (* 2 ?x))
Result: (* 2 z)
Result: (= what (* 2 z))
Result: ((= z 3) (= what (* 2 z)))There are two minor complications.
First, we agreed to implement sets of equations as lists of equations.
For this example, everything worked out, and the response was a list of two equations.
But if nested patterns are used, the response could be something like ((= a 5) ((= b (+ a 1)) (= c (+ a b)))), which is not a list of equations.
The function create-list-of-equations transforms a response like this into a proper list of equations.
The other complication is choosing variable names.
Given a list of words like (the number of customers Tom gets), we want to choose a symbol to represent it.
We will see below that the symbol customers is chosen, but that there are other possibilities.
Here is the main function for STUDENT.
It first removes words that have no content, then translates the input to one big expression with translate-to-expression, and breaks that into separate equations with create-list-of-equations.
Finally, the function solve-equations does the mathematics and prints the solution.
(defun student (words)
"Solve certain Algebra Word Problems."
(solve-equations
(create-list-of-equations
(translate-to-expression (remove-if #'noise-word-p words)))))The function translate-to-expression is a rule-based translator.
It either finds some rule in *student-rules* to transform the input, or it assumes that the entire input represents a single variable.
The function translate-pair takes a variable/value binding pair and translates the value by a recursive call to translate-to-expression.
(defun translate-to-expression (words)
"Translate an English phrase into an equation or expression."
(or (rule-based-translator
words *student-rules*
:rule-if #'rule-pattern :rule-then #'rule-response
:action #'(lambda (bindings response)
(sublis (mapcar #'translate-pair bindings)
response)))
(make-variable words)))
(defun translate-pair (pair)
"Translate the value part of the pair into an equation or expression."
(cons (binding-var pair)
(translate-to-expression (binding-val pair))))The function create-list-of-equations takes a single expression containing embedded equations and separates them into a list of equations:
(defun create-list-of-equations (exp)
"Separate out equations embedded in nested parens."
(cond ((null exp) nil)
((atom (first exp)) (list exp))
(t (append (create-list-of-equations (first exp))
(create-list-of-equations (rest exp))))))Finally, the function make-variable creates a variable to represent a list of words.
We do that by first removing all "noise words" from the input, and then taking the first symbol that remains.
So, for example, "the distance John traveled" and "the distance traveled by John" will both be represented by the same variable, distance, which is certainly the right thing to do.
However, "the distance Mary traveled" will also be represented by the same variable, which is certainly a mistake.
For (the number of customers Tom gets), the variable will be customers, since the, of and number are all noise words.
This will match (the customers mentioned above) and (the number of customers), but not (Tom's customers).
For now, we will accept the first-non-noise-word solution, but note that exercise 7.3 asks for a correction.
(defun make-variable (words)
"Create a variable name based on the given list of words"
;; The list of words will already have noise words removed
(first words))
(defun noise-word-p (word)
"Is this a low-content word which can be safely ignored?"
(member word '(a an the this number of $)))The next step is to write the equation-solving section of STUDENT. This is more an exercise in elementary algebra than in AI, but it is a good example of a symbol-manipulation task, and thus an interesting programming problem.
The STUDENT program mentioned the function solve-equations, passing it one argument, a list of equations to be solved.
solve-equations prints the list of equations, attempts to solve them using solve, and prints the result.
(defun solve-equations (equations)
"Print the equations and their solution"
(print-equations "The equations to be solved are:" equations)
(print-equations "The solution is:" (solve equations nil)))The real work is done by solve, which has the following specification: (1) Find an equation with exactly one occurrence of an unknown in it. (2) Transform that equation so that the unknown is isolated on the left-hand side. This can be done if we limit the operators to +, -, *,and /. (3) Evaluate the arithmetic on the right-hand side, yielding a numeric value for the unknown. (4) Substitute the numeric value for the unknown in all the other equations, and remember the known value. Then try to solve the resulting set of equations. (5) If step (1) fails-if there is no equation with exactly one unknown-then just return the known values and don't try to solve anything else.
The function solve is passed a system of equations, along with a list of known variable/value pairs.
Initially no variables are known, so this list will be empty.
solve goes through the list of equations searching for an equation with exactly one unknown.
If it can find such an equation, it calls isolate to solve the equation in terms of that one unknown.
solve then substitutes the value for the variable throughout the list of equations and calls itself recursively on the resulting list.
Each time solve calls itself, it removes one equation from the list of equations to be solved, and adds one to the list of known variable/value pairs.
Since the list of equations is always growing shorter, solve must eventually terminate.
(defun solve (equations known)
"Solve a system of equations by constraint propagation."
;; Try to solve for one equation, and substitute its value into
;; the others. If that doesn't work, return what is known.
(or (some #'(lambda (equation)
(let ((x (one-unknown equation)))
(when x
(let ((answer (solve-arithmetic
(isolate equation x))))
(solve (subst (exp-rhs answer) (exp-lhs answer)
(remove equation equations))
(cons answer known))))))
equations)
known))isolate is passed an equation guaranteed to have one unknown.
It returns an equivalent equation with the unknown isolated on the left-hand side.
There are five cases to consider: when the unknown is alone on the left, we're done.
The second case is when the unknown is anywhere on the right-hand side.
Because '=' is commutative, we can reduce the problem to solving the equivalent equation with left- and right-hand sides reversed.
Next we have to deal with the case where the unknown is in a complex expression on the left-hand side. Because we are allowing four operators and the unknown can be either on the right or the left, there are eight possibilities. Letting X stand for an expression containing the unknown and A and B stand for expressions with no unknowns, the possibilities and their solutions are as follows:
(1) X*A=B => X=B/A |
(5) A*X=B => X=B/A |
(2) X+A=B => X=B-A |
(6) A+X=B => X=B-A |
(3) X/A=B => X=B*A |
(7) A/X=B => X=A/B |
(4) X-A=B => X=B+A |
(8) A-X=B => X=A-B |
Possibilities (1) through (4) are handled by case III, (5) and (6) by case IV, and (7) and (8) by case V. In each case, the transformation does not give us the final answer, since X need not be the unknown; it might be a complex expression involving the unknown. So we have to call isolate again on the resulting equation. The reader should try to verify that transformations (1) to (8) are valid, and that cases III to V implement them properly.
(defun isolate (e x)
"Isolate the lone x in e on the left hand side of e."
;; This assumes there is exactly one x in e,
;; and that e is an equation.
(cond ((eq (exp-lhs e) x)
;; Case I: X = A -> X = n
e)
((in-exp x (exp-rhs e))
;; Case II: A = f(X) -> f(X) = A
(isolate (mkexp (exp-rhs e) '= (exp-lhs e)) x))
((in-exp x (exp-lhs (exp-lhs e)))
;; Case III: f(X)*A = B -> f(X) = B/A
(isolate (mkexp (exp-lhs (exp-lhs e)) '=
(mkexp (exp-rhs e)
(inverse-op (exp-op (exp-lhs e)))
(exp-rhs (exp-lhs e)))) x))
((commutative-p (exp-op (exp-lhs e)))
;; Case IV: A*f(X) = B -> f(X) = B/A
(isolate (mkexp (exp-rhs (exp-lhs e)) '=
(mkexp (exp-rhs e)
(inverse-op (exp-op (exp-lhs e)))
(exp-lhs (exp-lhs e)))) x))
(t ;; Case V: A/f(X) = B -> f(X) = A/B
(isolate (mkexp (exp-rhs (exp-lhs e)) '=
(mkexp (exp-lhs (exp-lhs e))
(exp-op (exp-lhs e))
(exp-rhs e))) x))))Recall that to prove a function is correct, we have to prove both that it gives the correct answer when it terminates and that it will eventually terminate.
For a recursive function with several alternative cases, we must show that each alternative is valid, and also that each alternative gets closer to the end in some way (that any recursive calls involve 'simpler' arguments).
For isolate, elementary algebra will show that each step is valid-or at least nearly valid.
Dividing both sides of an equation by 0 does not yield an equivalent equation, and we never checked for that.
It's also possible that similar errors could sneak in during the call to eval.
However, if we assume the equation does have a single valid solution, then isolate performs only legal transformations.
The hard part is to prove that isolate terminates.
Case I clearly terminates, and the others all contribute towards isolating the unknown on the left-hand side.
For any equation, the sequence will be first a possible use of case II, followed by a number of recursive calls using cases III to V.
The number of calls is bounded by the number of subexpressions in the equation, since each successive call effectively removes an expression from the left and places it on the right.
Therefore, assuming the input is of finite size, we must eventually reach a recursive call to isolate that will use case I and terminate.
When isolate returns, the right-hand side must consist only of numbers and operators.
We could easily write a function to evaluate such an expression.
However, we don't have to go to that effort, since the function already exists.
The data structure exp was carefully selected to be the same structure (lists with prefix functions) used by Lisp itself for its own expressions.
So Lisp will find the right-hand side to be an acceptable expression, one that could be evaluated if typed in to the top level.
Lisp evaluates expressions by calling the function eval, so we can call eval directly and have it return a number.
The function solve-arithmetic returns an equation of the form (= var number).
Auxiliary functions for solve are shown below.
Most are straightforward, but I will remark on a few of them.
The function prefix->infix takes an expression in prefix notation and converts it to a fully parenthesized infix expression.
Unlike isolate, it assumes the expressions will be implemented as lists.
prefix->infix is used by print-equations to produce more readable output.
(defun print-equations (header equations)
"Print a list of equations."
(format t "~%~a~{~% ~{ ~a~}~}~%" header
(mapcar #'prefix->infix equations)))
(defconstant operators-and-inverses
'((+ -) (- +) (* /) (/ *) (= =)))
(defun inverse-op (op)
(second (assoc op operators-and-inverses)))
(defun unknown-p (exp)
(symbolp exp))
(defun in-exp (x exp)
"True if x appears anywhere in exp"
(or (eq x exp)
(and (listp exp)
(or (in-exp x (exp-lhs exp)) (in-exp x (exp-rhs exp))))))
(defun no-unknown (exp)
"Returns true if there are no unknowns in exp."
(cond ((unknown-p exp) nil)
((atom exp) t)
((no-unknown (exp-lhs exp)) (no-unknown (exp-rhs exp)))
(t nil)))
(defun one-unknown (exp)
"Returns the single unknown in exp, if there is exactly one."
(cond ((unknown-p exp) exp)
((atom exp) nil)
((no-unknown (exp-lhs exp)) (one-unknown (exp-rhs exp)))
((no-unknown (exp-rhs exp)) (one-unknown (exp-lhs exp)))
(t nil)))
(defun commutative-p (op)
"Is operator commutative?"
(member op '(+ * =)))
(defun solve-arithmetic (equation)
"Do the arithmetic for the right hand side."
;; This assumes that the right hand side is in the right form.
(mkexp (exp-lhs equation) '= (eval (exp-rhs equation))))
(defun binary-exp-p (x)
(and (exp-p x) (= (length (exp-args x)) 2)))
(defun prefix->infix (exp)
"Translate prefix to infix expressions."
(if (atom exp) exp
(mapcar #'prefix->infix
(if (binary-exp-p exp)
(list (exp-lhs exp) (exp-op exp) (exp-rhs exp))
exp))))Here's an example of solve-equations in action, with a system of two equations.
The reader should go through the trace, discovering which case was used at each call to isolate, and verifying that each step is accurate.
> (trace isolate solve)
(isolate solve)
> (solve-equations '((= (+ 3 4) (* (- 5 (+ 2 x)) 7))
(= (+ (* 3 x) y) 12)))
The equations to be solved are:
(3 + 4) = ((5 - (2 + X)) * 7)
((3 * X) + Y) = 12
(1 ENTER SOLVE: ((= (+ 3 4) (* (- 5 (+ 2 X)) 7))
(= (+ (* 3 X) Y) 12)) NIL)
(1 ENTER ISOLATE: (= (+ 3 4) (* (- 5 (+ 2 X)) 7)) X)
(2 ENTER ISOLATE: (= (* (- 5 (+ 2 X)) 7) (+ 3 4)) X)
(3 ENTER ISOLATE: (= (- 5 (+ 2 X)) (/ (+ 3 4) 7)) X)
(4 ENTER ISOLATE: (= (+ 2 X) (- 5 (/ (+ 3 4) 7))) X)
(5 ENTER ISOLATE: (= X (- (- 5 (/ (+ 3 4) 7)) 2)) X)
(5 EXIT ISOLATE: (= X (- (- 5 (/ (+ 3 4) 7)) 2)))
(4 EXIT ISOLATE: (= X (- (- 5 (/ (+ 3 4) 7)) 2)))
(3 EXIT ISOLATE: (= X (- (- 5 (/ (+ 3 4) 7)) 2)))
(2 EXIT ISOLATE: (= X (- (- 5 (/ (+ 3 4) 7)) 2)))
(1 EXIT ISOLATE: (= X (- (- 5 (/ (+ 3 4) 7)) 2)))
(2 ENTER SOLVE: ((= (+ (* 3 2) Y) 12)) ((= X 2)))
(1 ENTER ISOLATE: (= (+ (* 3 2) Y) 12) Y)
(2 ENTER ISOLATE: (= Y (- 12 (* 3 2))) Y)
(2 EXIT ISOLATE: (= Y (- 12 (* 3 2))))
(1 EXIT ISOLATE: (= Y (- 12 (* 3 2))))
(3 ENTER SOLVE: NIL ((= Y 6) (= X 2)))
(3 EXIT SOLVE: ((= Y 6) (= X 2)))
(2 EXIT SOLVE: ((= Y 6) (= X 2)))
(1 EXIT SOLVE: ((= Y 6) (= X 2)))
The solution is:
Y = 6
X = 2
NILNow let's tackle the format string "~%~a~{~% ~{ ~ a ~}~}~*%"* in print-equations. This may look like random gibberish, but there is actually sense behind it.
format processes the string by printing each character, except that "~" indicates some special formatting action, depending on the following character.
The combination "~%" prints a newline, and "~a" prints the next argument to format that has not been used yet.
Thus the first four characters of the format string, "~%~a", print a newline followed by the argument header.
The combination "~{" treats the corresponding argument as a list, and processes each element according to the specification between the "~{" and the next "~}".
In this case, equations is a list of equations, so each one gets printed with a newline ("~%") followed by two spaces, followed by the processing of the equation itself as a list, where each element is printed in the "~a" format and preceded by a blank.
The t given as the first argument to format means to print to the standard output; another output stream may be specified there.
One of the annoying minor holes in Lisp is that there is no standard convention on where to print newlines! In C, for example, the very first line of code in the reference manual is
printf("hello, world\n");This makes it clear that newlines are printed after each line.
This convention is so ingrained in the UNIX world that some UNIX programs will go into an infinite loop if the last line in a file is not terminated by a newline.
In Lisp, however, the function print puts in a newline before the object to be printed, and a space after.
Some Lisp programs carry the newline-before policy over to format, and others use the newline-after policy.
This only becomes a problem when you want to combine two programs written under different policies.
How did the two competing policies arise?
In UNIX there was only one reasonable policy, because all input to the UNIX interpreter (the shell) is terminated by newlines, so there is no need for a newline-before.
In some Lisp interpreters, however, input can be terminated by a matching right parenthesis.
In that case, a newline-before is needed, lest the output appear on the same line as the input.
Exercise 7.1 [m] Implement print-equations using only primitive printing functions such as terpri and princ, along with explicit loops.
Now we move on to examples, taken from Bobrow's thesis. In the first example, it is necessary to insert a "then" before the word "what" to get the right answer:
> (student '(If the number of customers Tom gets is twice the square of
20 % of the number of advertisements he runs |,|
and the number of advertisements is 45 |,|
then what is the number of customers Tom gets ?))
The equations to be solved are:
CUSTOMERS = (2 * (((20 / 100) * ADVERTISEMENTS) *
((20 / 100) * ADVERTISEMENTS)))
ADVERTISEMENTS = 45
WHAT = CUSTOMERS
The solution is:
WHAT = 162
CUSTOMERS = 162
ADVERTISEMENTS = 45
NILNotice that our program prints the values for all variables it can solve for, while Bobrow's program only printed the values that were explicitly asked for in the text. This is an example of "more is less"-it may look impressive to print all the answers, but it is actually easier to do so than to decide just what answers should be printed. The following example is not solved correctly:
> (student '(The daily cost of living for a group is the overhead cost plus
the running cost for each person times the number of people in
the group |.| This cost for one group equals $ 100 |,|
and the number of people in the group is 40 |.|
If the overhead cost is 10 times the running cost |,|
find the overhead and running cost for each person |.|))
The equations to be solved are:
DAILY = (OVERHEAD + (RUNNING * PEOPLE))
COST = 100
PEOPLE = 40
OVERHEAD = (10 * RUNNING)
TO-FIND-1 = OVERHEAD
TO-FIND-2 = RUNNING
The solution is:
PEOPLE = 40
COST = 100
NILThis example points out two important limitations of our version of student as compared to Bobrow's.
The first problem is in naming of variables.
The phrases "the daily cost of living for a group" and "this cost" are meant to refer to the same quantity, but our program gives them the names daily and cost respectively.
Bobrow's program handled naming by first considering phrases to be the same only if they matched perfectly.
If the resulting set of equations could not be solved, he would try again, this time considering phrases with words in common to be identical.
(See the following exercises.)
The other problem is in our solve function.
Assuming we got the variables equated properly, solve would be able to boil the set of equations down to two:
100 = (OVERHEAD + (RUNNING * 40))
OVERHEAD = (10 * RUNNING)This is a set of two linear equations in two unknowns and has a unique solution at RUNNING = 2, OVERHEAD = 20.
But our version of solve couldn't find this solution, since it looks for equations with one unknown.
Here is another example that student handles well:
> (student '(Fran's age divided by Robin's height is one half Kelly's IQ |.|
Kelly's IQ minus 80 is Robin's height |.|
If Robin is 4 feet tall |,| how old is Fran ?))
The equations to be solved are:
(FRAN / ROBIN) = (KELLY / 2)
(KELLY - 80) = ROBIN
ROBIN = 4
HOW = FRAN
The solution is:
HOW = 168
FRAN = 168
KELLY = 84
ROBIN = 4
NILBut a slight variation leads to a problem:
> (student '(Fran's age divided by Robin's height is one half Kelly's IQ |.|
Kelly's IQ minus 80 is Robin's height |.|
If Robin is 0 feet tall |,| how old is Fran ?))
The equations to be solved are:
(FRAN / ROBIN) = (KELLY / 2)
(KELLY - 80) = ROBIN
ROBIN = 0
HOW = FRAN
The solution is:
HOW = 0
FRAN = 0
KELLY = 80
ROBIN = 0
NILThere is no valid solution to this problem, because it involves dividing by zero (Robin's height).
But student is willing to transform the first equation into:
FRAN = ROBIN * (KELLY / 2)and then substitutes to get 0 for FRAN.
Worse, dividing by zero could also come up inside eval:
> (student '(Fran's age times Robin's height is one half Kelly's IQ |.|
Kelly's IQ minus 80 is Robin's height |.|
If Robin is 0 feet tall |,| how old is Fran ?))
The equations to be solved are:
(FRAN * ROBIN) = (KELLY / 2)
(KELLY - 80) = ROBIN
ROBIN = 0
HOW = FRAN
>>Error: There was an attempt to divide a number by zeroHowever, one could claim that nasty examples with division by zero don't show up in algebra texts.
In summary, STUDENT behaves reasonably well, doing far more than the toy program ELIZA. STUDENT is also quite efficient; on my machine it takes less than one second for each of the prior examples. However, it could still be extended to have more powerful equation-solving capabilities. Its linguistic coverage is another matter. While one could add new patterns, such patterns are really just tricks, and don't capture the underlying structure of English sentences. That is why the STUDENT approach was abandoned as a research topic.
Bobrow's Ph.D. thesis contains a complete description of STUDENT. It is reprinted in Minsky 1968. Since then, there have been several systems that address the same task, with increased sophistication in both their mathematical and linguistic ability. Wong (1981) describes a system that uses its understanding of the problem to get a better linguistic analysis. Sterling et al. (1982) present a much more powerful equation solver, but it does not accept natural language input. Certainly Bobrow's language analysis techniques were not very sophisticated by today's measures. But that was largely the point: if you know that the language is describing an algebraic problem of a certain type, then you don't need to know very much linguistics to get the right answer most of the time.
Exercise 7.2 [h] We said earlier that our program was unable to solve pairs of linear equations, such as:
100 = (OVERHEAD + (RUNNING * 40))
OVERHEAD = (10 * RUNNING)The original STUDENT could solve these equations. Write a routine to do so. You may assume there will be only two equations in two unknowns if you wish, or if you are more ambitious, you could solve a system of n linear equations with n unknowns.
Exercise 7.3 [h] Implement a version of Bobrow's variable-naming algorithm.
Instead of taking the first word of each equation, create a unique symbol, and associate with it the entire list of words.
In the first pass, each nonequal list of words will be considered a distinct variable.
If no solution is reached, word lists that share words in common are considered to be the same variable, and the solution is attempted again.
For example, an input that contains the phrases "the rectangle's width" and "the width of the rectangle" might assign these two phrases the variables v1 and v2.
If an attempt to solve the problem yields no solutions, the program should realize that v1 and v2 have the words "rectangle" and "width" in common, and add the equation (= v1 v2) and try again.
Since the variables are arbitrary symbols, the printing routine should probably print the phrases associated with each variable rather than the variable itself.
Exercise 7.4 [h] The original STUDENT also had a set of "common knowledge" equations that it could use when necessary.
These were mostly facts about conversion factors, such as (1 inch = 2.54 cm).
Also included were equations like (distance equal s rate times time), which could be used to solve problems like "If the distance from Anabru to Champaign is 10 miles and the time it takes Sandy to travel this distance is 2 hours, what is Sandy's rate of speed?" Make changes to incorporate this facility.
It probably only helps in conjunction with a solution to the previous exercise.
Exercise 7.5 [h] Change student so that it prints values only for those variables that are being asked for in the problem.
That is, given the problem "X is 3.
Y is 4.
How much is X + Y ?" it should not print values for X and Y.
Exercise 7.6 [m] Try STUDENT on the following examples. Make sure you handle special characters properly:
(a) The price of a radio is 69.70 dollars. If this price is 15% less than the marked The number of soldiers the Russians have is one half of the number of guns
(b) The number of soldiers the Russians have is one half of the number of guns they have. The number of guns they have is 7000. What is the number of soldiers they have?
(c) If the number of customers Tom gets is twice the square of 20 % of the number of advertisements he runs, and the number of advertisements is 45, and the profit Tom receives is 10 times the number of customers he gets, then what is the profit?
(d) The average score is 73. The maximum score is 97. What is the square of the difference between the average and the maximum?
(e) Tom is twice Mary's age, and Jane's age is half the difference between Mary and Tom. If Mary is 18 years old, how old is Jane?
(f) What is 4 + 5* 14/7?
(g) x x b = c + d. b x c = x. x = b + b. b = 5.
Exercise 7.7 [h]Student's infix-to-prefix rules account for the priority of operators properly, but they don't handle associativity in the standard fashion.
For example, (12 - 6 - 3) translates to (- 12 (- 6 3)) or 9, when the usual convention is to interpret this as (- (- 12 6) 3) or 3.
Fix student to handle this convention.
Exercise 7.8 [d] Find a mathematically oriented domain that is sufficiently limited so that STUDENT can solve problems in it.
The chemistry of solutions (calculating pH concentrations) might be an example.
Write the necessary *student-rules*, and test the resulting program.
Exercise 7.9 [m] Analyze the complexity of one-unknown and implement a more efficient version.
Exercise 7.10 [h] Bobrow's paper on STUDENT (1968) includes an appendix that abstractly characterizes all the problems that his system can solve. Generate a similar characterization for this version of the program.
Answer 7.1
(defun print-equations (header equations)
(terpri)
(princ header)
(dolist (equation equations)
(terpri)
(princ " ")
(dolist (x (prefix->infix equation))
(princ " ")
(princ x))))Answer 7.9 one-unknown is very inefficient because it searches each subcomponent of an expression twice.
For example, consider the equation:
(= (+ (+ x 2) (+ 3 4)) (+ (+ 5 6) (+ 7 8)))To decide if this has one unknown, one-unknown will call no-unknown on the left-hand side, and since it fails, call it again on the right-hand side.
Although there are only eight atoms to consider, it ends up calling no-unknown 17 times and one-unknown 4 times.
In general, for a tree of depth n, approximately 2n calls to no-unknown are made.
This is clearly wasteful; there should be no need to look at each component more than once.
The following version uses an auxiliary function, find-one-unknown, that has an accumulator parameter, unknown. This parameter can take on three possible values: nil, indicating that no unknown has been found; or the single unknown that has been found so far; or the number 2 indicating that two unknowns have been found and therefore the final result should be nil.
The function find-one-unknown has four cases: (1) If we have already found two unknowns, then return 2 to indicate this.
(2) If the input expression is a nonatomic expression, then first look at its left-hand side for unknowns, and pass the result found in that side as the accumulator to a search of the right-hand side.
(3) If the expression is an unknown, and if it is the second one found, return 2; otherwise return the unknown itself.
(4) If the expression is an atom that is not an unknown, then just return the accumulated result.
(defun one-unknown (exp)
"Returns the single unknown in exp, if there is exactly one."
(let ((answer (find-one-unknown exp nil)))
;; If there were two unknowns, return nil;
;; otherwise return the unknown (if there was one)
(if (eql answer 2)
nil
answer)))
(defun find-one-unknown (exp unknown)
"Assuming UNKNOWN is the unknown(s) found so far, decide
if there is exactly one unknown in the entire expression."
(cond ((eql unknown 2) 2)
((exp-p exp)
(find-one-unknown
(exp-rhs exp)
(find-one-unknown (exp-lhs exp) unknown)))
((unknown-p exp)
(if unknown
2
exp))
(t unknown)))1Page 316 of Common Lisp the Language says, "Because a constructor of this type operates By Order of Arguments, it is sometimes known as a BOA constructor."