Manual for HACKER

Manual for HACKER

Written by Dylan Holmes

Table of Contents

1 Getting started

1.1 About the program

HACKER is a program that models the way humans think about strategies, and how they re-organize that knowledge as they progress from novice to expert.

The setting for HACKER is a world full of building blocks. When you ask HACKER to build various structures out of blocks, it will attempt to comply by making and executing a plan. Because HACKER is initially a novice, however, it will make many mistakes along the way. (For example, it might try to grab a block at the bottom of a tall pile, or make a plan where some of the steps are out of order.) Whenever HACKER notices a mistake, it will work to figure out exactly what went wrong, then modify the plan to avoid making similar mistakes in the future. In this way, HACKER learns and abstracts.

HACKER has several kinds of knowledge:

  • Knowledge about building blocks, and the sort of things you can do with them. For example, you can stack one block on top of another.
  • General knowledge about strategies. For example, one strategy is: to do something to an entire group, you can individually do something to each member of the group.
  • General knowledge about things that can go wrong. For example, one type of mistake is to try to do something before you've made all the necessary preparations.

It is important to notice that these types of knowledge are entirely separate within HACKER. This separation of knowledge means that HACKER is domain-general: if you want to make your own HACKER program which learns about a new domain, all you have to do is replace the blocks world knowledge with knowledge about some other domain. The rest of HACKER's knowledge — about strategies and bugs — will apply just as well to this new domain.

1.2 Installing HACKER

HACKER is written in the Clojure programming language. To run it, you will need:

  • Java
  • Clojure
  • A copy of the program, which you can download here.

Once you have these things, you can run HACKER by opening a terminal window on your computer and typing

java -cp clojure-1.7.0.jar clojure.main

to initialize the Clojure read-eval-print loop. Then, run

(in-ns ai.logical.hacker)

to enter the HACKER namespace, which import all of the HACKER definitions and enable you to run all of the HACKER functions.

1.3 Activities

To test out the program, run the sample demonstration:


This will set up a scenario that looks like this: blocksworld-2.png

Then, the function will ask HACKER to put block A onto block B. Here is the definition of run-demo-1; it sets up the scene and then poses the problem.

(defn run-demo-1 []
  (let [scene
        (-> (scene-init)
            (add-block (block 'A 1))
            (add-block (block 'B 1))

    (hacker-solve scene 
    ;; Set up the scenario
    '[make [on A TABLE]]
    '[make [on B TABLE]]

    ;; Ask to put make block A on block B.
    '[make [on A B]]

Without hesitation, HACKER performs the movement to achieve the goal. The scene now looks like:


The second demonstration becomes slightly more complex. To run the second demonstration, call


Here, we have a new scene set up like this:


HACKER is asked to make block B on block C.

(defn run-demo-2
  ([] (t2 true))

  (when restart? (restart!))
  (let [scene
        (-> (scene-init)
            (add-block (block 'A 1))
            (add-block (block 'B 1))
            (add-block (block 'C 1))

    (hacker-solve scene
                  ;; Set up the scenario
                  '[make [on B TABLE]]]
                  '[make [on C TABLE]]]
                  '[make [on A B]]]

                  ;; Ask to make block B on block C.
                  '[make [on B C]]]


HACKER will try to reach for block B and move it, but will fail because block A is stacked on top of it. This causes HACKER to call its bug-classifier to see what the matter is.

2 How HACKER works

The following sections describe how each line of code in HACKER works.

2.1 What novice HACKER knows

HACKER's knowledge is stored in five databases:

The Answer Library
which contains programs that HACKER has written to solve its problems. Sometimes, HACKER will modify programs in the answer library to fix a bug.
The Hacker Notebook
where HACKER keeps comments about the programs that it has written, so that it can remember what each line is for. Referring to the Hacker Notebook helps prevent HACKER from making certain kinds of mistakes when revising programs.
Programming techniques
which contains very general problem-solving strategies. HACKER uses these when it doesn't know how to solve a problem already and has to devise a new strategy.
Patch types
which is a separate list of strategies for fixing bugs in code.1
Blocksworld knowledge
is domain-specific knowledge about how building blocks work, and the sort of things you can do with them.

The Answer Library and Hacker Notebook in particular will change as HACKER gains more blocks-world expertise. The following section of code sets up these variables, and describes their initial values (i.e. what HACKER knows in the very beginning).

(def answer-library (atom [])) 
(def hacker-notebook (atom [])) 
(def blocksworld-knowledge (atom [])) 
(def programming-techniques (atom [])) 
(def patch-types (atom [])) 

(def ^:const default-answer-library
   '[to [make [on :a :b]]
     [program make-on
      [line :line1 [put-on :a :b]]]]

   '[to [test [place-for :x :y]]
     [program wrapper-test-place-for
      [line :line2 [test-place-for :x :y]]]]

   '[to [test [cleared-top :x]]
     [program wrapper-test-cleared-top
      [line :line3 [test-cleared-top :x]]]]

   '[to [test [not [= :x :y]]]
     [program wrapper-test-inequality
      [line :line4 [test-not= :x :y]]]]

   '[to [test [on :x :y]]
     [program wrapper-test-on
      [line :line4 [test-on :x :y]]]]

   '[to [test [possibly :condition]]
     [program wrapper-possibly
      [line :line4 [possibly :condition]]]]


(def ^:const default-hacker-notebook
   '[goal make-on [make [on :a :b]]]
   '[purpose :line1 [make [on :a :b]] make-on]


(def ^:const default-blocksworld-knowledge

   ;; To put x on y, there must be a place for x on y.
   '[fact [prerequisite [put-on :x :y] [place-for :x :y]]]

   ;; An :expression requires the top of :object to be cleared
   ;; if executing the :expression causes the :object to move.
   ;; ("have" is an existential quantifier.)
   '[fact [prerequisite :expr [cleared-top :object]]
     [have [] [moves :expr :object]]]

   ;; Executing [put-on :x :y] causes :x to move.
   '[fact [moves [put-on :x :y] :x]]

   ;; [cleared-top :x] means that there is no object :y on :x.
   '[fact [meaning-of [cleared-top :x]
           [not [exists [:y] [on :y :x]]]]]

   ;; To show that x is not on y, it is enough to show that x is on
   ;; some different object z.
   '[fact [suffices-for [not [on :x :y]]
           [exists [:z] [not [= :z :y]] [on :x :z]]]]


(def ^:const default-programming-techniques

   ;; A test for [not [= :x :y]] is just [not [= :x :y]]
   '[fact [code [test [not [= :x :y]]]
           [not [= :x :y]]]]

   ;; A test for whether an expression is possible is to check whether
   ;; its negation is protected.
   '[fact [code [test [possibly :expr]]
           [not [protected? [not :expr]]]]]

   ;; If an argument has a synonymous meaning, you can replace the
   ;; argument with its synonym.
   '[fact [code [:function :argument] :script]
     [have [:meaning] [meaning-of :argument :meaning]
      [replace-code :script [:function :meaning]]]]

   ;; If an argument has a sufficient condition, you can replace the
   ;; argument with the sufficient condition.
   '[fact [code [:function :argument] :script]
     [have [:condition] [suffices-for :argument :condition]
      [replace-code :script [:function :condition]]]]

   ;; To remove all instances of variables matching pattern, iterate
   ;; over all variables matching pattern, and make them not-pattern.
   '[fact [code [achieve [not [exists :vars :expr]]]
           [until :vars [cannot [assign :vars :expr]]
            [make [not :expr]]]]]

   ;; To make one of the objects satisfy a condition, choose one of
   ;; the objects for which it is possibly to satisfy the condition,
   ;; then make it satisfy the condition.
   '[fact [code [make [exists :vars :qualification :action]]
           [choose :vars 
             [test :qualification]
             [test [possibly :action]]] [make :action]]]



(def ^:const default-patch-types
   '[fact [patch [!prerequisite-missing :program :line# :prerequisite]
           [add-newline! :program
            [achieve :prerequisite]


To reset HACKER's knowledge to its default state, you can run the function restart!.

(defn restart! []
  (swap! answer-library (constantly default-answer-library)) 
  (swap! hacker-notebook (constantly default-hacker-notebook)) 
  (swap! blocksworld-knowledge (constantly default-blocksworld-knowledge))
  (swap! programming-techniques (constantly default-programming-techniques))
  (swap! patch-types (constantly default-patch-types))

2.2 Setting up a blocks world scene

A few simple functions are used to set up blocks world scenes.

(def *table* 'TABLE)

(defn block
  ([name width]
     {:width width :name name})
     (block width (gensym "block"))))

(defn table []
  {:width Double/POSITIVE_INFINITY
   :name *table*})

(defn scene-init
  "Create a new blocks world scenario, containing only a table."
  {:facts []
   :blocks {*table* (table)}})

(defn add-block
  ([scene block]
     (alter-val scene :blocks #(assoc % (:name block) block))))

For example, you can use Clojure's threading macro to set up a scene containing a TABLE2, two small blocks (A,B) of length one and one large block (C) of length three, as follows:

(-> (scene-init)
    (add-block (block 'A 1))
    (add-block (block 'B 1))
    (add-block (block 'C 3)))

As created in this scene, the blocks are currently "floating" — not resting on any particular object. You can ask HACKER to put a block on the table using a command like the following (more on this later):

(hacker-solve your-scene-here '(make (on A TABLE)))

2.3 How HACKER represents problems

2.3.1 Every problem has a scene and a callstack.

2.3.2 The callstack

Because problems often generate subproblems, HACKER makes use of a simulated call stack containing function pointers.

Basically, the stack consists of a list of subroutines that are currently running. A subroutine is a program (with variables filled in), along with a number which tells you which line of the code is currently being run. Every time a program calls another subroutine, that subroutine gets added to the top of stack. The top-most subroutine is the one that is currently active.

There are several functions for interrogating or manipulating the stack:

(def current-program (comp peek :callstack))

(defn current-line [state]
  (let [[program-name line# [& lines]] (current-program state)]
    (nth lines line#)))

(defn prev-line [state]
  (let [[program-name line# [& lines]] (current-program state)]
    (nth lines (dec line#))))

(defn current-program-name [state]
  (let [[program-name line# [& lines]] (current-program state)]

(defn goto-next-line 
  "Return a new state object where the latest function pointer has
  advanced one line forward."
  (let [[program-name line# [& lines]] (current-program state)]
    ;; TODO: perhaps clear the "return" and/or "error" flags.
    (alter-val state :callstack
               (fn [stack]
                 (conj (pop stack) [program-name (inc line#) lines])))))

(defn end-of-program? [state]
  (let [[program-name line# [& lines]] (current-program state)]
    (<= (count lines) line#)))

As part of its debugging process, HACKER may need to modify either programs stored on the state's callstack or programs stored in its Answer Library.

(defn add-newline! [state program-name expr purpose]
   (let [new-line# (keyword (gensym "line"))]

     (swap! answer-library
             (for [[_ goal [_ name & lines :as program] :as entry] 
               (if-not (= name program-name)
                 ['to goal (apply conj
                                  ['line new-line# expr]

     (swap! hacker-notebook #(conj %
                                   ['purpose new-line# expr purpose]))

     (assoc state :return true)

 (defn replace-line-here 
   "Replace the current line in the currently running program with
   expr, but don't alter the code for the program in the database."
   [expr state]
   (let [
         [_ line# _](current-line state)]

     (let [state*

     (alter-val state :callstack
                (fn [stack]
                  (conj (pop (vec stack))
                        (let [[_ _ lines :as top] (last stack)]
                          (conj (vec (take 2 top))
                                (for [[_line line## goal] lines]
                                  [_line line## (if (= line## line#) expr goal)]))))))]



 (defn replace-line!
   "Modify the program with the given name by replacing the line named
   line# with the expression in expr."
   [program-name line# expr]
   (swap! answer-library
          (constantly (for [[_to goal [_program name & lines :as program] :as entry] @answer-library]
                        (if-not (= name program-name)

                          [_to goal (apply conj [_program name]
                                           (for [l lines]
                                             (if (= line# (second l))
                                               [(first l) (second l) expr] 



2.3.3 Errors and return values

States may optionally have an error that is currently being thrown, and/or a current return value. Retrieve them using standard hash-map keys:

(:error state)
(:return state)

You can also check to see whether the state's most recent subroutine has returned successfully by using the predicate successful-return?. As you can see, successful-return? returns true if the state hasn't thrown an error and has a true(ish) return value.

(defn successful-return?
  "Returns true if the state is not in error mode, and if (pred
return-val) is true."
  ([state] (successful-return? state (comp not not)))
  ([state pred]
     (and (not (:error state))
          (pred (:return state)))))

2.4 Solving a problem

2.4.1 The execute function decides what to do with the current problem

The heart of HACKER is the program execute. Execute takes a particular state and decides what to do with it:

  • If the state has an error, HACKER passes it to the bug classifier by calling execute-debug-classifier.

  • If the topmost program on the stack has finished running, HACKER pops it off the stack and executes the next program.

  • Otherwise, HACKER looks at the call stack to see what its current problem is.

    • First, HACKER checks to see if the problem is something it can solve in one step. (There are certain basic actions, called primitive operations, which HACKER can immediately perform. These are actions such as putting a block onto another block.)
    • If the problem is too complex to be solved in one step, HACKER checks the Answer Library to see if it already knows a program that can solve the current problem. If HACKER can match the current problem to a solution in its Answer Library, HACKER tries out the solution.
    • If HACKER has tried all of the solutions in its library and none of them has worked, HACKER passes the state to the code writer by calling execute-code-writer. The code-writer attempts to write a program to solve the current problem.
    • If both the Answer Library and the code writer fail to produce a solution, HACKER is stuck.
(defn execute
  ([state] (execute state false))
  ([state silently?]

   (:error state)
   (execute-bug-classifier state)

   (empty? (:callstack state)) state
   (end-of-program? state) (recur (alter-val state :callstack pop) silently?)

   (let [[program-name line# [& lines]] (peek (get state :callstack))
         goal (nth (current-line state) 2)
         state* (goto-next-line state)
         _ (when (and (not silently?)

                      (#{'make} (first goal))

                      ) (print-current-line! state))
     (cond (primitive-operator? goal)
           (recur (execute-primitive-operator state goal) silently?)

           (= 'have (first goal))
           (parse-existential state goal)

           ;; find and iterate over all canned subroutines
           ;; for solving this problem
           (let [
                   (fn [answer]
                         [ptn (pattern-match (take 2 answer) ['to goal])]
                       (pattern-bind ptn answer))))
                  (remove nil?)

                   (fn [[_ _ [_ program-name & lines]]]
                     (alter-val state* :callstack
                                #(conj % [program-name 0 lines]))


             (if (empty? strategies)
               ;; TODO: ask the code-writer to code up a solution
               ;; TODO : call exec on this so that it gets
               ;; passed to the debugger before returning
               (execute-code-writer state)

               ;; TODO: Iteratively evaluate each strategy,
               ;; returning the first result without a fatal
               ;; error. If all results have fatal errors, throw
               ;; a fatal error.
               (execute (first strategies))



(defn hacker-solve
  ([scene expr & exprs]

     (let [state {:scene scene
                  :callstack [['USER_INPUT 0
                               (for [e (cons expr exprs)]
                                 ['line (gensym "line") e])
       (execute state)


2.4.2 Performing basic one-step actions (primitives)

(defn primitive-operator? [expr]
  (->> expr

(defn execute-primitive-operator [state [f & args :as expr]]
  (let [;;proceed one line forward in the current subroutine
        state* (goto-next-line state)]

     (= f 'and)
       ;;(println "AND" (vec args))
       (assoc state* :return
              (every? successful-return?
                      (map (partial (eval 'hacker-solve) (:scene state))


     (= f 'not)
     (assoc state* :return
            (not (successful-return?
            (execute (:scene state) (first args)))))

     (= f 'test-not=)
     (assoc state* :return (not (apply = args)))

     (= f 'choose)
     (execute-choice state* expr)

     (= f 'possibly)
     (assoc state* :return true) ;;; TODO: Protection mechanism

     (= f 'until)
     ((eval 'execute-until-loop) state (cons f args))

     (= f 'assign)
     ((eval 'execute-assign) state (cons f args))

     (= f 'cannot)
     (let [x ((eval 'hacker-solve) (:scene state) (first args))]
     (if (successful-return? x)
         (assoc state* :error [!failed-conditional (first args)]
                :return (:return x)
                ) state*
     (apply (eval f) state* args))


The following code supplies blocks world utility functions which comprise the primitive functions:

(defn toppings
  "Return a list of names of objects on the given surface."
  [scene surface]
  (filter (fn [expr]
                [[f x y pos] expr]
              (and (= 'on f)
                   (= surface y) ;; todo: reference by name/object
          (:facts scene)))

(defn vacancies
  ([scene surface object]
     (let [intervals (vacancies scene surface)
           width (get-in scene [:blocks object :width] 0)

       (->> intervals
            (filter (fn [[a b]] (<= width (- b a))))
            (map (fn [[a b]]
                   (if (Double/isInfinite b) a
                     (/ (+ a b (- width)) 2)
  ([scene surface]
     (let [toppings (toppings scene surface)
           (map (fn [[_ obj _ n]]
                  [n (+ n (get-in scene [:blocks obj :width] 0))])
                (sort-by second toppings))

           left-endpoint (when object-endpoints
                           (apply min 0 (map first object-endpoints)))
           right-endpoint (when object-endpoints
                            (apply max Double/POSITIVE_INFINITY (map second object-endpoints)))

           fenceposts (flatten (concat [0]
                                       [(get-in scene [:blocks surface :width])]))


       (remove (partial apply =) ;; remove zero-width intervals
               (partition 2 fenceposts))


(defn test-place-for [state object surface]
  (assoc state :return
         (-> state
             (vacancies surface object)
             first nil? not)))

(defn test-cleared-top [state surface]
  (assoc state :return
         (-> state
             (toppings surface)

(defn test-on [state x y]
  (->> state
       (filter (partial pattern-match ['on x y]))
       (assoc state :return))
(defn place-for? [scene object surface]
  (first (vacancies scene surface object)))

(defn put-on [state object surface]
  (println "* Putting" object "on" surface)
  (let [;;_ (println object surface)
        scene (get state :scene)
        tops (toppings scene object)


    ;;;(println "PUT ON" object surface)
    (if-let [[_ stuff] (first tops)] ;; if the object has stuff on it
      ;; Can't move an object if it has stuff on it.
      (assoc state :error
             [!unsatisfied-prerequisite ['not ['on stuff object]]])

      (if-let [x (first (vacancies scene surface object))]
        (assoc state :scene
                ;; remove object from all other surfaces
                (alter-val :facts
                           (partial remove
                                    #(let [[fn x] %]
                                       (and (= 'on fn)
                                    (= x object)))))

                ;; place object on new surface
                (alter-val :facts
                           #(conj %
                                  (list 'on object surface x)
            ;;                      (list 'on object surface) ;; TODO: DXH DANGER HERE


        (assoc state :error
               [!fatal-error 'ERROR_NO_SPACE_ON_BLOCK surface])))))

2.4.3 Searching for variables that make an expression true

To solve an assignment operator such as

(assign [:x :y] (on :x :y))

HACKER will first find all possible interpretations of the variables :x and :y. Then, it will check each interpretation to see if any is true3. It will return the first set of successful bindings, or nil if no solution exists.

The find-all-interpretations routine handles to the problem of finding all possible values of the variables.

(defn unbound-vars
  "Returns a list of all variables in the expression."
  (if (coll? expr)
    (distinct (mapcat unbound-vars expr))
    (when (variable? expr) [expr])

(defn find-all-interpretations
  "Returns a list of all possible ways to bind the unbound variables
in expr to objects in state, without checking whether the bindings
make logical sense."
  ([state expr]
     (let [
           vars (unbound-vars expr)
           universe (-> state

       (loop [open vars accumulated [expr]]

         (if (empty? open)
            (rest open)
            (for [e accumulated
                  x universe]
              (pattern-bind {(first vars) x} e))))))))
(defn execute-assign [state expr]
  (let [[_assign variables expr*] expr
        state* (goto-next-line state)

        candidates (->> expr*
                        (find-all-interpretations state*)
                        (map (comp
                              (partial (eval 'hacker-solve) (:scene state*))
                              (partial vector 'test)))

                        (filter :return))

        candidate (when-let [x (first candidates)]
                    (->> x :return
                         (pattern-match expr*)
                         (filter-keys (set variables))))

        ;;_ (println "ASSIGN" expr* (->> expr* (find-all-interpretations state)))

    (assoc state* :return candidate)


The assignment operator is a kind of existential quantifier. Other existential quantifiers work in a similar way:

(defn parse-existential [state goal]
  (if-let [[_ vars expr] goal]

    (let [matching-facts
          (map (comp #(pattern-align % expr) second)

      (assoc state :return
             (some (comp not nil?) matching-facts)))))

The source code for the original HACKER was written in the domain-specific PLANNER language. This language was able to simultaneously search for bindings that made an expression true, while also modifying the expression based on the bindings it found. To replicate this functionality in a stateless/functional way, I wrote the parse-in-environment function.

(To see an example of parse-in-environment in action, run the demo program.)

(defn parse-in-environment
  "If the fact has any qualifications or environmental conditions,
  returns a (potentially empty) list of all the ways of making them
  hold. Otherwise, returns a singleton list containing fact."
  [state fact]

  (let [[_fact goal & environment] fact]
    (if-let [e (first environment)]
      (let [;;_ (clojure.pprint/pprint ["ENV" fact e] )
            [_have vars condition & exprs :as existential] e
      (->> @blocksworld-knowledge
           (map (fn [[_fact x :as entry]]

                  (when-let [bind (pattern-match* condition x)]
                    (if-let [e (first exprs)]
                      (let [reverse-bind (exchange-keyvals (apply dissoc bind vars))
                            command (pattern-bind reverse-bind (pattern-bind bind (thread-in goal e)))

                            ;_ (println [condition x (pattern-match* condition x)])

                        (apply (eval (first command)) (rest command))



           (remove nil?)           



2.4.4 Diagnosing and repairing a malfunctioning program

Whenever the main loop execute runs into a problem, it activates sequence of repair actions. The execute-bug-classifier function is the first step in repairing a malfunctioning program; it identifies the source of the bug. Once the source of the bug is determined, the patch writer is employed to fix the specific problem.

(defn execute-bug-classifier [state]

   (= !failed-conditional (first (:error state)))

   (= !fatal-error (first (:error state)))

   (let [_   (println "error" (:error state))
         [_ line# goal :as badline] (prev-line state)
         (->> @blocksworld-knowledge
              (map (fn [answer]
                     (when-let [ptn (pattern-match 
                                        (take 2 (second answer))
                                        ['prerequisite goal])]
                       (pattern-bind ptn answer)

              (remove nil?)

         (for [fact* (take 2 matching-prereqs)
               fact (find-all-interpretations state fact*)]
           (let [[_fact [_prereq _ goal*] & preconditions] fact]

             (when (or (empty? preconditions)
                        (hacker-solve (:scene state)
                                      (first preconditions))))
               [(hacker-solve (:scene state) ['test goal*]) goal*])

       ;; (map (partial take 2) @blocksworld-knowledge))

     (if-let [bug-cause (some (fn [[ret goal]] (and (successful-return? ret not) goal))
                              (remove nil? test-prereqs))]

       (execute-patch (assoc state :error ['!prerequisite-missing (current-program-name state) (second (prev-line state))  bug-cause]))

       (alter-val state :error (partial vector !fatal-error)))



The patch writer makes use of the Patch Types library to find a solution for the bug in the currently running program. To make the repairwork general, the patch writer employs current-program-bindings; current-program-bindings returns a hashmap describing the relationship between the instantiated program running on the stack (e.g. (make-on A B)) and its general instance in the Answer Library (e.g. (make-on :x :y)).

(defn find-program-by-name [program-name]
  (->> @answer-library
       (map (fn [[_ _ [_ name & _ :as program]]]
              (when (= name program-name)
       (some identity)))

(defn refresh-program
  "Replace the top program on the stack with its most up-to-date
  version, and reset the function pointer to the start of that
  [variables state]

  (if-let [[_ program-name & lines]
        (pattern-bind (exchange-keyvals variables)
                      (find-program-by-name (current-program-name state)))

    (-> state
        (alter-val :callstack
                   (fn [stack]
                     (conj (pop stack) 
                           [program-name 0 (map vec lines)])))

        (dissoc :error)


(defn current-program-bindings
  "Return a list of bindings made by the top function pointer on the stack."
  (let [program (current-program state)
        [_ _ & lines]  (find-program-by-name (first program))]
    (pattern-match* (nth program 2) lines)
(defn execute-patch [state]
  (println "patching error: " (:error state))

  (let [[bug-type program-name line# arg :as error] (:error state)
        variables (current-program-bindings state)
        var-error (pattern-bind variables error)
        (->> @patch-types
             (map (fn [answer]
                    (when-let [ptn (pattern-match
                                  (take 2 (second answer))
                                  ['patch var-error])]
                      (pattern-bind ptn answer))))
             (remove nil?)



    (if-not variables
      (assoc state :error [!fatal-error "Patcher can't unbind variables."])
      (-> (some identity matching-patches) ;; TODO: search over /all/ patches
          (nth 2)
          ((partial hacker-solve (:scene state)))
          (when (execute (refresh-program variables state)))


3 Appendix

3.1 Utility functions

3.2 Pattern-matching

HACKER uses pattern-matching to match specific problems with general solutions. Matching takes place between two expressions. A successful match will return a map of bindings. For example, you can match the following two expressions:

(pattern-match '(put-on :x :y) '(put-on A B))

You can use the function pattern-bind to replace every variable in an expression with its bound counterpart.

(def variable? keyword?)

(defn merge-bindings
  [bind-1 bind-2]
  (when (and bind-1 bind-2)

    (loop [b1 bind-1 b2 bind-2 accumulate nil]
       (empty? b1)
       (merge b2 accumulate)
       (empty? b2)
       (merge b1 accumulate)

       (let [k (first (keys b1))]
         (when (or (not (get b2 k))
                   (= (get b1 k) (get b2 k)))
           (recur (dissoc b1 k)
                  (dissoc b2 k)
                  (assoc accumulate k (get b1 k)))))))))

(defn pattern-match
  "Match two s-expressions, returning a map of bindings. Pattern
  variables are indicated by keywords."

  ([ptn expr]
     (pattern-match ptn expr {}))

  ([ptn expr bindings]

      (and (coll? ptn) (coll? expr))
      (if (or (empty? ptn) (empty? expr))
        (if-let [x (pattern-match (first ptn) (first expr) bindings)]
          (recur (rest ptn) (rest expr) x)))

      (variable? ptn)
      (merge-bindings bindings {ptn expr})

      (and (not (coll? expr)) (not (coll? ptn)))
      (when (= ptn expr) bindings)


(defn pattern-match*
  "Match two s-expressions, returning a map of bindings. Pattern
  variables are indicated by keywords --- or by single-letter symbols."

  ([ptn expr]
     (pattern-match* ptn expr {}))

  ([ptn expr bindings]

      (and (coll? ptn) (coll? expr))
      (if (or (empty? ptn) (empty? expr))
        (if-let [x (pattern-match* (first ptn) (first expr) bindings)]
          (recur (rest ptn) (rest expr) x)))

      (or (variable? ptn) (and (symbol? ptn) (= 1 (count (str ptn)))))
      (merge-bindings bindings {ptn expr})

      (and (not (coll? expr)) (not (coll? ptn)))
      (when (= ptn expr) bindings)


(defn pattern-bind [bind expr]
  (if (coll? expr) 
;;    (if (every? variable? expr) expr ;; hack for existential quantifiers
    (map (partial pattern-bind bind) expr)
    (get bind expr expr)))

(defn pattern-bind* [bind expr]
  (if (coll? expr)
    (if (= 'have (first expr))
      (conj (pattern-bind* bind (drop 2 expr)) (second expr) (first expr))
      (map (partial pattern-bind* bind) expr))
    (get bind expr expr)))

(defn pattern-align
  "Attempts to match the pattern with the expression using
  pattern-match. If successful, returns the bound match. If
  unsuccessful, returns nil."
  [ptn expr]
  (when-let [b (pattern-match ptn expr)]
    (pattern-bind b expr)))

(defn pattern-search
  "Returns a list of all expressions in coll which match ptn, having
  been bound."
  [ptn coll]
  (remove nil?
          (map (partial pattern-align ptn) coll)))



For example, if the bug is that you try to take an action before making all the necessary preparations, you can add a new line to the beginning of the program where you make the necessary preparations first.


All scenes contain an infinitely wide TABLE by default


This is a generate-and-test paradigm.

Author: Dylan Holmes

Created: 2015-07-02 Thu 17:09

Emacs 24.5.1 (Org mode 8.3beta)