Porting PAIP to clojure - Chapter 4: GPS - The General Problem Solver
Table of Contents
- 1 PAIP to clojure - chapter 4
- 1.1 Description
- 1.2 Specification
- 1.3 Implementation
- 1.4 Testing
- 1.5 Analysis
- 1.6 Back to implementation - A more general version 2
1 PAIP to clojure - chapter 4
I continue to translate PAIP to clojure.
As always, it is possible to follow the post even without reading PAIP, but I encourage you to do so.
This chapter covers the GPS program, the
General Problem Solver. As always, the focus lies on the iterative process of developing
an (ai-) progam. Norvig presents 5 stages of an programming project, after which the
sections of the chapter are numbered:
- Description
- Specification (in algorithmic terms)
- Implementation
- Testing
- Debugging/Analysis (optional repeat)
1.1 Description
GPS was the first program which separated its problem-solving strategy from its knowledge of particular
problems. It used means-ends analysis as problem-solving strategy. In means-ends analysis, you know in what
state you are right now and in what state you will be when you have solved your problem, but you consider
what is between your state now and the goal-state and how this distance can be overcome.
An Example:
I have to write a blog-post. What Do I need to do to write an blog-post? I have to type it.
What do I need to type it? I have to sit in front of my pc.
What do I need to do to sit in front of my pc ? Go to the PC ….
It is obvious that we have to be able to answer "What do I need to … "or, like the book points out "What is the difference between…" from the set of all possible actions. And each actions could have itself preconditions, for which actions have to be taken befor it can be taken. This is a very brief description, I encourage you to read the section in PAIP for the full discussion.
It is obvious that we have to be able to answer "What do I need to … "or, like the book points out "What is the difference between…" from the set of all possible actions. And each actions could have itself preconditions, for which actions have to be taken befor it can be taken. This is a very brief description, I encourage you to read the section in PAIP for the full discussion.
1.2 Specification
After having a (rough) Idea of how the means-ends analysis works, it is time to come to the second step: specification.
In this stage, we refine the description to something that is representible in the implementation language.
I tink, the stage of specification is best described as follows:
Find the most natural mapping between the problem and the implementation language!
So, let's see how means-ends analysis can be represented in clojure:
So, let's see how means-ends analysis can be represented in clojure:
- A state can be represented as a set of conditions, for example #{unknown poor} and #{rich famous}. We need 2 states: the current state and the goal state (try to guess which of the two above is the goal-state…?)
- The allowable actions can naturally be represented as a collection of actions, which can be worke
- An action needs a Name, a descriptions of what states a person has to be in in order to take the action and a description of what states of the person will change after taking the action. An action can therefore be described by a map (or later by a record) with a :action and a :precond field. The changes of the state of the acting person are trickier. Consider an action "Become rich" that has as precond being poor and changes that to being rich. It could also remove states or add new ones. The change of one state to the other can easily be represented in terms of removing the old one and adding the new one. Thus the Action will have two more fields, a :del-list and a :add-list which contains states which will be added or removed from the current state after taking the action.
- Last, but not least, we have to specify the entry point of the application, the GPS-function. We need a start-state, a goal-state and the allowed actions. It can be represented as a function which takes a start-state and a goal states, and works with the ops var.
1.3 Implementation
First, let's have a look at a sample operations list. I find it easier to implement the program, if I see
with what data it works with:
Notice the use of the with-auto-declare macro, which I described in a previous post. This let me avoid to add a declare, everytime I make a forward declaration. If a symbol starts with _, a forward-declaration will be automagically added for it.
(ns PAIP2clojure.Chapter4) (def school-ops [ {:action "drive-son-to-school" :preconds #{ "son-at-home" "car-works"} :add-list #{ "son-at-school"} :del-list #{ "son-at-home"}} {:action "shop-installs-battery" :preconds #{"car-needs-battery" "shop-knows-problem" "shop-has-money"} :add-list #{"car-works"}} {:action "tell-shop-problem" :preconds #{"in-communication-with-shop"} :add-list #{"shop-knows-problem"}} {:action "telephone-shop" :preconds #{"know-phone-number"} :add-list #{"in-communication-with-shop"}} {:action "look-up-number" :preconds #{"have-phone-book"} :add-list #{"know-phone-number"}} {:action "give-shop-money" :preconds #{"have-money"} :add-list #{"shop-has-money"} :del-list #{"have-money"}}]) (def ^:dynamic *ops* school-ops)
=> #'PAIP2clojure.Chapter4/*ops*In the implementation, I choose not follow Norvigs route and modify the current state in the function, which would require something like an atom or agent in clojure. Instead I changed the implementation to be side-effect free and hence more ideomatic clojure. Here is the implementation from the book:
(defvar *state* nil "The current state: a list of conditions.") (defvar *ops* nil "A list of available operators.") (defstruct op "An operation" (action nil) (preconds nil) (add-list nil) (del-list nil)) (defun GPS (*state* goals *ops*) "General Problem Solver: achieve all goals using *ops*." (if (every #'achieve goals) 'solved)) (defun achieve (goal) "A goal is achieved if it already holds, or if there is an appropriate op for it that is applicable." (or (member goal *state*) (some #'apply-op (find-all goal *ops* :test #'appropriate-p)))) (defun appropriate-p (goal op) "An op is appropriate to a goal if it is in its add list." (member goal (op-add-list op))) (defun apply-op (op) "Print a message and update *state* if op is applicable." (when (every #'achieve (op-preconds op)) (print (list 'executing (op-action op))) (setf *state* (set-difference *state* (op-del-list op))) (setf *state* (union *state* (op-add-list op))) t))I had to change the return value of achieve and apply-op to an updated current-state, instead of returning a truth value and destructively modifying the current state as side effect. Also, I couldn't use every? because the state has to be updated after every application of achieve. Thus I made a helper function every-accum? which takes a 2-argument function, a start-state and a collection and reduces the collection applying the function. When one result is nil, the function returns nil.
Notice the use of the with-auto-declare macro, which I described in a previous post. This let me avoid to add a declare, everytime I make a forward declaration. If a symbol starts with _, a forward-declaration will be automagically added for it.
(use 'clojure.set) (use 'auto-declare.core) (with-auto-declare _ (defn GPS [state goals] (let [new-state (_every-accum? _achieve state goals)] (if (nil? new-state) 'not-solved 'solved))) (defn achieve "return the new-state after the goal is achieved or nil if it could not be archieved" [current-state goal] (if (contains? current-state goal) current-state (some (partial _apply-op current-state) (filter #(_appropriate? goal %) *ops*)))) (defn appropriate? [goal op] (contains? (:add-list op) goal)) (defn every-accum? [func start coll] (reduce #(if (nil? %1) nil (func %1 %2)) start coll)) (defn apply-op [current-state op] (let [new-current-state (every-accum? achieve current-state (:preconds op))] (if (nil? new-current-state) nil (do (println (str "executing " (:action op))) (-> new-current-state (difference (:del-list op)) (union (:add-list op))))))))
=> #'PAIP2clojure.Chapter4/apply-opOk, now comes the 4. stage: Testing
1.4 Testing
Let's test the implementation with the ops defined above and see how it works.
Norvig presents three sample applications:
But how does it actually work? Trace is a good way to find out.
As you see, it tries to achieve the goals in reverse order, because it has to solve the subproblems first. The first action it can execute is look-up-number. After this, it knows the telefone-number, can phone the shop, the shop can repair the car and it can solve the problem of driving the son to school because the car works.
(GPS #{"son-at-home" "car-needs-battery" "have-money" "have-phone-book"} #{"son-at-school"})
executing look-up-number executing telephone-shop executing tell-shop-problem executing give-shop-money executing shop-installs-battery executing drive-son-to-school executing look-up-number executing telephone-shop executing tell-shop-problem executing give-shop-money executing shop-installs-battery executing drive-son-to-school solved => solved
(GPS #{"son-at-home" "car-needs-battery" "have-money"}
#{"son-at-school"})
=> not-solved
(GPS #{"son-at-home" "car-works"}
#{"son-at-school"})
executing drive-son-to-school => solvedThe second example has no solution, because the person does not have a phone-book and thus can't come in communication with the shop and the shop cant repair the car, so he can't drive his son to school
But how does it actually work? Trace is a good way to find out.
(dotrace [GPS achieve appropriate? apply-op every-accum?]
(GPS #{"son-at-home" "car-needs-battery" "have-money" "have-phone-book"} #{"son-at-school"}))
TRACE t3410: (GPS #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} #{"son-at-school"})
TRACE t3411: | (every-accum? #<Chapter4$eval3393$fn__3396 PAIP2clojure.Chapter4$eval3393$fn__3396@6bb0b0a0> #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} #{"car-works" "son-at-home"})
TRACE t3412: | | (achieve #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} "car-works")
TRACE t3413: | | | (every-accum? #<Chapter4$eval3393$fn__3396 PAIP2clojure.Chapter4$eval3393$fn__3396@6bb0b0a0> #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} #{"shop-knows-problem" "car-needs-battery" "shop-has-money"})
TRACE t3414: | | | | (achieve #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} "shop-knows-problem")
TRACE t3415: | | | | | (every-accum? #<Chapter4$eval3393$fn__3396 PAIP2clojure.Chapter4$eval3393$fn__3396@6bb0b0a0> #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} #{"in-communication-with-shop"})
TRACE t3416: | | | | | | (achieve #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} "in-communication-with-shop")
TRACE t3417: | | | | | | | (every-accum? #<Chapter4$eval3393$fn__3396 PAIP2clojure.Chapter4$eval3393$fn__3396@6bb0b0a0> #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} #{"know-phone-number"})
TRACE t3418: | | | | | | | | (achieve #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} "know-phone-number")
TRACE t3419: | | | | | | | | | (every-accum? #<Chapter4$eval3393$fn__3396 PAIP2clojure.Chapter4$eval3393$fn__3396@6bb0b0a0> #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} #{"have-phone-book"})
TRACE t3420: | | | | | | | | | | (achieve #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"} "have-phone-book")
TRACE t3420: | | | | | | | | | | => #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"}
TRACE t3419: | | | | | | | | | => #{"car-needs-battery" "have-phone-book" "have-money" "son-at-home"}
executing look-up-number
TRACE t3418: | | | | | | | | => #{"car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home"}
TRACE t3417: | | | | | | | => #{"car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home"}
executing telephone-shop
TRACE t3416: | | | | | | => #{"car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"}
TRACE t3415: | | | | | => #{"car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"}
executing tell-shop-problem
TRACE t3414: | | | | => #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"}
TRACE t3421: | | | | (achieve #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"} "car-needs-battery")
TRACE t3421: | | | | => #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"}
TRACE t3422: | | | | (achieve #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"} "shop-has-money")
TRACE t3423: | | | | | (every-accum? #<Chapter4$eval3393$fn__3396 PAIP2clojure.Chapter4$eval3393$fn__3396@6bb0b0a0> #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"} #{"have-money"})
TRACE t3424: | | | | | | (achieve #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"} "have-money")
TRACE t3424: | | | | | | => #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"}
TRACE t3423: | | | | | => #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "have-money" "son-at-home" "in-communication-with-shop"}
executing give-shop-money
TRACE t3422: | | | | => #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "shop-has-money" "son-at-home" "in-communication-with-shop"}
TRACE t3413: | | | => #{"shop-knows-problem" "car-needs-battery" "know-phone-number" "have-phone-book" "shop-has-money" "son-at-home" "in-communication-with-shop"}
executing shop-installs-battery
TRACE t3412: | | => #{"shop-knows-problem" "car-needs-battery" "car-works" "know-phone-number" "have-phone-book" "shop-has-money" "son-at-home" "in-communication-with-shop"}
TRACE t3425: | | (achieve #{"shop-knows-problem" "car-needs-battery" "car-works" "know-phone-number" "have-phone-book" "shop-has-money" "son-at-home" "in-communication-with-shop"} "son-at-home")
TRACE t3425: | | => #{"shop-knows-problem" "car-needs-battery" "car-works" "know-phone-number" "have-phone-book" "shop-has-money" "son-at-home" "in-communication-with-shop"}
TRACE t3411: | => #{"shop-knows-problem" "car-needs-battery" "car-works" "know-phone-number" "have-phone-book" "shop-has-money" "son-at-home" "in-communication-with-shop"}
executing drive-son-to-school
TRACE t3410: => solved
=> solved
The output is rather lengthy, but you can find your way through. Really great about tracing is, that
you see all applications of the functions with their arguments and results printed hierachically, so that the
caller of a function is less deeply nested.
Therefore, it really helps in debugging and understanding code without manually adding debug statements or stepping
through breakpoints etc.
I am showing here the output when all functions are traced. Turning out tracing on a few functions make the
output more readable, but you miss a bit about the whole picture.
As you see, it tries to achieve the goals in reverse order, because it has to solve the subproblems first. The first action it can execute is look-up-number. After this, it knows the telefone-number, can phone the shop, the shop can repair the car and it can solve the problem of driving the son to school because the car works.
1.5 Analysis
It turns out, that the GPS is not very general, at least our implementation is not.
Norvig does a great analysis explaining the reasons why the program can not handle many situations.
I will give a short summary of the discussion, describing the problems and a miminal explanation why the program fails.
- Running around the block - GPS don't have any notion of actions, that add nothing to the :add-list, like 'running-around-the-block'. There has to be a state like "got-some-exercise" in the :add-list
- Clobbered Sibling Goal - In the current implementation, GPS solves every goal independent and in sequence. That means, if solving the second problem undoes a previous goal, GPS will falsly return success. In the school-ops world, consider #{have-money son-at-school}. The program has to be modified, so that it checks after achieving all goals that the state is still a subset of the goal-state
- Leaping before you look - sometimes, gps will fail, but executes some action before it recognizes that. In the current implementation, planning and execution are interleaved. This will be addressent by returning the list of actions instead of just printing the actions.
- Recursive Subgoal Problem - suppose we would add another operator to the school-ops "ask-phone-number" with the precondition of being in communication with the shop. GPS will try to achieve know-phone-number with ask-phone-number, which requires to be in communication with the shop, which requires knowing the phone-number … It tries to solve the problem in terms of itself. To address this, we have to add a goal-stack, and let GPS give-up if it recognizes a circle.
- Lack of Intermediate Information - As at the leaping before you look problem, it is better to return a list of actions instead of just solved. This makes it easier for other parts of the program to interact with GPS
1.6 Back to implementation - A more general version 2
Before we come to the implementation of the program, it helps to get a good debugging tool, so that we can
see what it is doing:
Also note, that in apply-op append and remove-if are used. They are needed because in this version, the order of the conditions in the current state counts (because they contain (Executing action) elements.
Again, I will not follow the implementation given in PAIP. Especially I want to avoid the side-effects in achieve-all and the mixing of actual conditions and (Executing action) forms, which would prevent to represent states with sets. It turned out, that I needed only three small changes from the first version of the program:
The Chapter in PAIP ends with a discussion of how general the GPS really is. It turns out, that it has severe limitations and I encourage everyone to read the sections in the book. Many of this issues will be addressed in later chapters using more sophisticated techniques, such as full-fledged search and backtracking, like prolog does.
Puh, that was more work than I thought. But I hope that I managed to translate it to ideomatic clojure which is not to hard to follow. Feel free to comment, if you have questions, anything is not clear, you enounter bugs or have some other advice.
Chapter 5 is next to come. It contains an implementation of the ELIZA program.
(def ^:dynamic *dbg-ids*) (defn debug ([id str] (debug id 0 str)) ([id indent str] (when (contains? *dbg-ids* id) (do (dotimes [i indent] (print " ")) (println str)))))
=> #'PAIP2clojure.Chapter4/debugHere is the common-lisp code. It first transforms all the ops to a new form, which has an '(Executing action) in its add list.
(defun executing-p (x) "Is x of the form: (executing ...) ?" (starts-with x 'executing)) (defun starts-with (list x) "Is this a list whose first element is x?" (and (consp list) (eql (first list) x))) (defun convert-op (op) "Make op conform to the (EXECUTING op) convention." (unless (some #'executing-p (op-add-list op)) (push (list 'executing (op-action op)) (op-add-list op))) op) (defun op (action &key preconds add-list del-list) "Make a new operator that obeys the (EXECUTING op) convention." (convert-op (make-op :action action :preconds preconds :add-list add-list :del-list del-list))) ;;; ============================== (mapc #'convert-op *school-ops*)The new version of GPS will return the new state instead of printing the actions and removes all non-atoms from the state so that only (Executing action) forms are left
(defvar *ops* nil "A list of available operators.") (defstruct op "An operation" (action nil) (preconds nil) (add-list nil) (del-list nil)) (defun GPS (state goals &optional (*ops* *ops*)) "General Problem Solver: from state, achieve goals using *ops*." (remove-if #'atom (achieve-all (cons '(start) state) goals nil))) (defun achieve-all (state goals goal-stack) "Achieve each goal, and make sure they still hold at the end." (let ((current-state state)) (if (and (every #'(lambda (g) (setf current-state (achieve current-state g goal-stack))) goals) (subsetp goals current-state :test #'equal)) current-state))) (defun achieve (state goal goal-stack) "A goal is achieved if it already holds, or if there is an appropriate op for it that is applicable." (dbg-indent :gps (length goal-stack) "Goal: ~a" goal) (cond ((member-equal goal state) state) ((member-equal goal goal-stack) nil) (t (some #'(lambda (op) (apply-op state goal op goal-stack)) (find-all goal *ops* :test #'appropriate-p))))) (defun member-equal (item list) (member item list :test #'equal)) (defun apply-op (state goal op goal-stack) "Return a new, transformed state if op is applicable." (dbg-indent :gps (length goal-stack) "Consider: ~a" (op-action op)) (let ((state2 (achieve-all state (op-preconds op) (cons goal goal-stack)))) (unless (null state2) ;; Return an updated state (dbg-indent :gps (length goal-stack) "Action: ~a" (op-action op)) (append (remove-if #'(lambda (x) (member-equal x (op-del-list op))) state2) (op-add-list op))))) (defun appropriate-p (goal op) "An op is appropriate to a goal if it is in its add list." (member-equal goal (op-add-list op)))The function achieve-all abstracts away the (every #'achieve …) from the first version and checks whether the resulting state is still a subset of the goal-state. Also, it updates the current state for each application of achieve (destructively modifying..)
Also note, that in apply-op append and remove-if are used. They are needed because in this version, the order of the conditions in the current state counts (because they contain (Executing action) elements.
Again, I will not follow the implementation given in PAIP. Especially I want to avoid the side-effects in achieve-all and the mixing of actual conditions and (Executing action) forms, which would prevent to represent states with sets. It turned out, that I needed only three small changes from the first version of the program:
- The state is now divided in the current-state and a list-of-actions taken so far. Thanks to clojure's destructuring, it is easy to take the state apart again.
- there is a goal-stack which contains all goals tried so far. achieve gives up if it encounters a goal that is in the goal-stack to avoid stack-overflow-errors.
- every-time an action is executed, it is appendet to the list-of-actions.
(use 'clojure.set) (use 'auto-declare.core) (with-auto-declare _ (defn GPS [state goals] (let [[new-state list-of-actions] (_every-accum? (partial achieve []) [state []] goals)] (if (nil? new-state) nil list-of-actions))) (defn achieve "return the new-state after the goal is achieved or nil if it could not be archieved" [goal-stack [current-state list-of-actions] goal] (debug :gps (count goal-stack) (str "Goal " goal)) (cond (contains? current-state goal) [current-state list-of-actions] (contains? goal-stack goal) [nil list-of-actions] :else (some (partial _apply-op goal-stack goal [current-state list-of-actions]) (filter #(_appropriate? goal %) *ops*)))) (defn appropriate? [goal op] (contains? (:add-list op) goal)) (defn every-accum? [func start coll] (reduce #(if (nil? %1) nil (func %1 %2)) start coll)) (defn apply-op [goal-stack goal state op] (debug :gps (count goal-stack) (str "Consider: " (:action op))) (let [[new-current-state new-list-of-actions](every-accum? (partial achieve (conj goal-stack goal)) state (:preconds op))] (if (nil? new-current-state) [nil new-list-of-actions] (do (debug :gps (count goal-stack) (str "Action " (:action op))) [(-> new-current-state (difference (:del-list op)) (union (:add-list op))) (conj new-list-of-actions (:action op))])))))
=> #'PAIP2clojure.Chapter4/apply-opThis implementation solves the problems mentioned above. The next parts of Chapter 4 show how the program performs in new domains. Feel free to port the ops in these domains to clojure and report whether the program worked or not. Here is one example domain: monkey and bananas:
(def ^:dynamic *banana-ops* [{:action "climb-on-chair" :preconds #{"chair-at-middle-room" "at-middle-room" "on-floor"} :add-list #{"at-bananas" "on-chair"} :del-list #{"at-middle-room" "on-floor"}} {:action "push-chair-from-door-to-middle-room" :preconds #{"chair-at-door" "at-door"} :add-list #{"chair-at-middle-room" "at-middle-room"} :del-list #{"chair-at-door" "at-middle-room"}} {:action "walk-from-door-to-middle-room" :preconds #{"at-door" "on-floor"} :add-list #{"at-middle-room"} :del-list #{"at-door"}} {:action "grasp-bananas" :preconds #{"at-bananas" "empty-handed"} :add-list #{"has-bananas"} :del-list #{"at-door"}} {:action "drop-ball" :preconds #{"has-ball"} :add-list #{"empty-handed"} :del-list #{"has-ball"}} {:action "eat-bananas" :preconds #{"has-bananas"} :add-list #{"empty-handed" "not-hungry"} :del-list #{"has-bananas" "hungry"}}]) (def ^:dynamic *ops* *banana-ops*)
=> #'PAIP2clojure.Chapter4/*ops*
(binding [*dbg-ids* #{:gps }] (GPS #{"at-door" "on-floor" "has-ball" "hungry" "chair-at-door"} #{"not-hungry"}))
Goal not-hungry
Consider: eat-bananas
Goal has-bananas
Consider: grasp-bananas
Goal empty-handed
Consider: drop-ball
Goal has-ball
Action drop-ball
Goal at-bananas
Consider: climb-on-chair
Goal chair-at-middle-room
Consider: push-chair-from-door-to-middle-room
Goal chair-at-door
Goal at-door
Action push-chair-from-door-to-middle-room
Goal at-middle-room
Goal on-floor
Action climb-on-chair
Action grasp-bananas
Action eat-bananas
=> ["drop-ball" "push-chair-from-door-to-middle-room" "climb-on-chair" "grasp-bananas" "eat-bananas"]
The Chapter in PAIP ends with a discussion of how general the GPS really is. It turns out, that it has severe limitations and I encourage everyone to read the sections in the book. Many of this issues will be addressed in later chapters using more sophisticated techniques, such as full-fledged search and backtracking, like prolog does.
Puh, that was more work than I thought. But I hope that I managed to translate it to ideomatic clojure which is not to hard to follow. Feel free to comment, if you have questions, anything is not clear, you enounter bugs or have some other advice.
Chapter 5 is next to come. It contains an implementation of the ELIZA program.
