propagator.org

   1 #+TITLE: Concurrent Propagator in Clojure
   2 #+OPTIONS: num:nil ^:nil toc:2
   3 #+LaTeX_CLASS: normal
   4
   5 A concurrent propagator system implemented in [[http://clojure.org][Clojure]].  This simple
   6 project builds on the scheme propagator system from Gerald Sussman's
   7 [[http://dspace.mit.edu/handle/1721.1/44215][The art of the Propagator]].
   8
   9 #+begin_quote
  10   We develop a programming model built on the idea that the basic
  11   computational elements are autonomous machines interconnected by
  12   shared cells through which they communicate. Each machine
  13   continuously examines the cells it is interested in, and adds
  14   information to some based on deductions it can make from information
  15   from the others. This model makes it easy to smoothly combine
  16   expression-oriented and constraint-based programming; it also easily
  17   accommodates implicit incremental distributed search in ordinary
  18   programs. This work builds on the original research of Guy Lewis
  19   Steele Jr. and was developed more recently with the help of Chris
  20   Hanson.
  21 #+end_quote
  22
  23 Major differences between this system and the one implemented in /The
  24 art of the Propagator/ are that,
  25 1) this implementation admits parallel execution through the use of
  26    Clojure's [[http://clojure.org/agents][agents]].
  27 2) this version does not implement the backtracking system which
  28    breaks the locality of the propagator system
  29
  30 Source code and documentation are available as a [[http://github.com/technomancy/leiningen][leiningen]] project,
  31 and can be checked out using [[http://git-scm.com/][git]] from [[http://gitweb.adaptive.cs.unm.edu/propagator.git][here]] with
  32 : git clone http://gitweb.adaptive.cs.unm.edu/propagator.git
  33
  34 (note: this is an exploratory, educational implementation and isn't
  35 suitable for any sort of /production/ application.)
  36
  37 * code
  38   :PROPERTIES:
  39   :tangle:   src/propagator.clj
  40   :END:
  41 tangled to [[file:src/propagator.clj]]
  42
  43 #+begin_src clojure
  44   (ns
  45       #^{:author "Eric Schulte",
  46          :license "GPLV3",
  47          :doc "Simple concurrent propagator system."}
  48     propagator
  49     (:use clojure.contrib.repl-utils clojure.contrib.math))
  50
  51   (defmacro cell "Define a new cell."
  52     [name state]
  53     `(def ~name (agent ~state)))
  54
  55   (defn set-cell "Set the value of a cell" [cell value]
  56     (send cell (fn [_] value)))
  57
  58   (defmacro propagator "Define a new propagator."
  59     [name in-cells out-cells & body]
  60     `(do
  61        (defn ~(with-meta name
  62                 (assoc (meta name)
  63                   :in-cells in-cells :out-cells out-cells))
  64          ~in-cells ~@body)
  65        (doseq [cell# ~in-cells] (add-neighbor cell# ~name))
  66        ~name))
  67
  68   (defmacro run-propagator
  69     "Run a propagator, first collect the most recent values from all
  70   cells associated with the propagator, then evaluate."
  71     [propagator]
  72     `(let [results# (apply ~propagator (map deref (:in-cells ^#'~propagator)))]
  73        (doseq [cell# (:out-cells ^#'~propagator)]
  74          (when (not (= @cell# results#))
  75            (send cell# (fn [_#] results#))))
  76        results#))
  77
  78   (defmacro add-neighbor "Add a neighbor to the given cell."
  79     [cell neighbor]
  80     `(add-watcher
  81       ~cell :send
  82       (agent nil :validator (fn [_#] (do (future (run-propagator ~neighbor)) true)))
  83       (fn [_# _#])))
  84 #+end_src
  85 * extension: graphing the propagator network
  86 Draw a graph of a propagator network in a JFrame, tangles to
  87 [[file:src/graphs.clj]].
  88
  89 #+begin_src clojure :tangle src/graphs.clj
  90   (in-ns 'propagator)
  91   (use 'vijual)
  92   (import '(javax.swing JFrame JPanel)
  93           '(java.awt Color Graphics)
  94           '(java.awt.image BufferedImage))
  95
  96   ;; saving graph information
  97   ;; record keeping for graphing propagators
  98   (def prop-graph {})
  99   (defmacro remember-prop [name in-cells out-cells]
 100     `(def prop-graph
 101           (assoc prop-graph
 102             (quote ~name)
 103             {:in-cells (map (fn [x#] (name x#)) (quote ~in-cells))
 104              :out-cells (map (fn [x#] (name x#)) (quote ~out-cells))})))
 105
 106   (defmacro propagator "Define a new propagator."
 107     [name in-cells out-cells & body]
 108     `(do
 109        (remember-prop ~name ~in-cells ~out-cells)
 110        (defn ~(with-meta name
 111                 (assoc (meta name)
 112                   :in-cells in-cells :out-cells out-cells))
 113          ~in-cells ~@body)
 114        (doseq [cell# ~in-cells] (add-neighbor cell# ~name))
 115        ~name))
 116
 117   ;; stuff for graphing
 118   (def dim [300 300])
 119
 120   (def frame (JFrame.))
 121
 122   (defn view "Display a graph generated by vijual" [img]
 123     (let [mult 1.5
 124           width (* (.getWidth img) mult)
 125           height (* (.getHeight img) mult)
 126           offset 50
 127           panel (doto (proxy [JPanel] []
 128                         (paint [g]
 129                                (.drawImage g img offset offset nil))))]
 130       (doto frame (.add panel) .pack (.setSize (+ offset width) (+ offset height)).show)))
 131
 132   (defn graph-propagators []
 133     (vec (set
 134           (apply concat
 135                  (map (fn [key]
 136                         (let [hsh (get prop-graph key)]
 137                           (concat
 138                            (map #(vec (list % (name key))) (get hsh :in-cells))
 139                            (map #(vec (list (name key) %)) (get hsh :out-cells)))))
 140                       (keys prop-graph))))))
 141
 142   (defn view-network []
 143     (view (draw-directed-graph-image (graph-propagators))))
 144
 145   (defn clear-network []
 146     (def prop-graph {})
 147     (def frame (JFrame.)))
 148 #+end_src
 149
 150 * usage
 151 These examples can be pasted into the repl.
 152
 153 ** doubling a number -- simplest
 154 #+begin_src clojure
 155   (cell in-c 0)
 156   (cell out-c 0)
 157   (propagator doubler [in-c] [out-c] (* 2 in))
 158   ;; then any updates to in
 159   (set-cell in-c 1)
 160   ;; will propagate to out
 161   @out-c
 162 #+end_src
 163
 164 ** square roots -- heron
 165 #+begin_src clojure :tangle src/heron.clj
 166   (in-ns 'propagator)
 167   (cell guess 1)
 168   (cell x 9)
 169   (cell done false)
 170   (cell margin 0.1)
 171
 172   (propagator enough [x guess] [done]
 173     (Thread/sleep 1000)
 174     (if (< (abs (- (* guess guess) x)) @margin) true false))
 175
 176   (propagator heron [x done guess] [guess]
 177     (Thread/sleep 1000)
 178     (if done
 179       guess
 180       (/ (+ guess (/ x guess)) 2.0)))
 181 #+end_src
 182
 183 ** web server
 184 Alright, this will use Clojure's [[http://github.com/mmcgrana/ring][Ring]] web server middle-ware.
 185
 186 So, I guess the best demo here would be some reading/writing through a
 187 MVC setup.
 188
 189 The =app= will dispatch the incoming data to input cell by the route
 190 at the end of the url, then there can be a couple of output cells
 191 which will render different views of the related data.
 192
 193 #+begin_src clojure :tangle src/web.clj
 194   (load-file "/home/eschulte/src/propagator/src/propagator.clj")
 195   (in-ns 'propagator)
 196   (use 'ring.adapter.jetty)
 197   (use 'clojure.contrib.seq-utils)
 198   (import 'java.util.Date 'java.text.SimpleDateFormat)
 199
 200   ;; cells
 201   (cell names '())
 202   (cell input "")
 203
 204   (propagator adder [input names] [names]
 205               (when (> (count (seq input)) 0)
 206                 (set (cons (str input " :1") names))))
 207
 208   (defn app [req]
 209     (or
 210      ;; page to accept input
 211      (when (= "/" (:uri req))
 212        {:status 200
 213         :headers {"Content-Type" "text/html"
 214                   "Title" "3000"}
 215         :body (apply str
 216                      "<form name=\"\" action=\"add\" method=\"get\">"
 217                      "Word: <input type=\"type\" name=\"word\" />"
 218                      "<input type=\"submit\" value=\"Submit\" />"
 219                      "</form>")})
 220      ;; dump value into "input" cell
 221      (when (re-matches #"/add" (:uri req))
 222        (set-cell input (second (re-matches #".+=(.+)" (:query-string req))))
 223        {:status 303 :headers {"Location" "../list"}})
 224      ;; render the value of the "list" cell
 225      (when-let [matched (re-matches #"/list" (:uri req))]
 226        {:status  200
 227         :headers {"Content-Type" "text/html"}
 228         :body    (apply str (flatten (list "<ul>"
 229                                            (map #(str "<li>"%"</li>") @names)
 230                                            "</ul>"
 231                                            "<p><a href=\"/\">another word</a></p>")))})))
 232
 233   (run-jetty #'app {:port 3000})
 234 #+end_src
 235
 236 * notes
 237 ** look at mutable data stores
 238 - http://clojure.org/agents
 239 - http://clojure.org/atoms
 240 - http://clojure.org/refs
 241
 242 most definitely will use agents, functions to set their values are
 243 applied to them with send (or send-off if potentially I/O bound), they
 244 support validators, and they can be set to run actions (i.e. alert
 245 propagators) as part of their update cycle (with add-watcher).
 246
 247 ** design to permit distribution across multiple machines
 248 it should be possible to wrap these mutable items including
 249 - network connections from other machines
 250 - hardware (timers, I/O devices, etc...)
 251
 252 in cells, so that the propagator system remains "pure"
 253
 254 * licence
 255
 256 Copyright (C) 2010 Eric Schulte
 257
 258 This program is free software: you can redistribute it and/or modify
 259 it under the terms of the GNU General Public License as published by
 260 the Free Software Foundation, either version 3 of the License, or
 261 (at your option) any later version.
 262
 263 This program is distributed in the hope that it will be useful,
 264 but WITHOUT ANY WARRANTY; without even the implied warranty of
 265 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 266 GNU General Public License for more details.
 267
 268 You should have received a [[file:COPYING][copy of the GNU General Public License]]
 269 along with this program.  If not, see <http://www.gnu.org/licenses/>.