propagator.org

   1 #+TITLE: Concurrent Propagator in Clojure
   2 #+OPTIONS: toc:nil num:nil
   3 #+LaTeX_CLASS: normal
   4 #+begin_html
   5   <style type="text/css">
   6     <!--/*--><![CDATA[/*><!--*/
   7     pre { background-color: #232323; color: #E6E1DC;}
   8     /*]]>*/-->
   9   </style>
  10 #+end_html
  11
  12 A concurrent propagator system implemented in [[http://clojure.org][Clojure]].  This simple
  13 project builds on the scheme propagator system from Gerald Sussman's
  14 [[http://dspace.mit.edu/handle/1721.1/44215][The art of the Propagator]].
  15
  16 #+begin_quote
  17   We develop a programming model built on the idea that the basic
  18   computational elements are autonomous machines interconnected by
  19   shared cells through which they communicate. Each machine
  20   continuously examines the cells it is interested in, and adds
  21   information to some based on deductions it can make from information
  22   from the others. This model makes it easy to smoothly combine
  23   expression-oriented and constraint-based programming; it also easily
  24   accommodates implicit incremental distributed search in ordinary
  25   programs. This work builds on the original research of Guy Lewis
  26   Steele Jr. and was developed more recently with the help of Chris
  27   Hanson.
  28 #+end_quote
  29
  30 Major differences between this system and the one implemented in /The
  31 art of the Propagator/ are that,
  32 1) this implementation admits parallel execution through the use of
  33    Clojure's [[http://clojure.org/agents][agents]].
  34 2) this version does not implement the backtracking system which
  35    breaks the locality of the propagator system
  36
  37 (note: this is an exploratory, educational implementation and isn't
  38 suitable for any sort of /production/ application.)
  39
  40 #+source: code-counter
  41 #+begin_src sh :var file="src/propagator.clj" :exports none
  42   cat $file|sed '/^[ \t]*$/d'|grep -v "^[ \t];"|wc -l
  43 #+end_src
  44
  45 This system is implemented in src_emacs-lisp[:var d=code-counter]{d}
  46 lines of Clojure code in [[http://repo.or.cz/w/propagator.git/blob_plain/HEAD:/src/propagator.clj][src/propagator.clj]].
  47
  48 ** Usage Examples
  49 - square roots calculation using Heron's method
  50   #+begin_src clojure :tangle src/heron.clj
  51     (in-ns 'propagator)
  52     (defcell guess 1)
  53     (defcell x 9)
  54     (defcell done false)
  55     (defcell margin 0.1)
  56
  57     ;; check if we're close enough to a solution to cease improving
  58     (defpropagator enough [x guess] [done]
  59       (Thread/sleep 1000) ; sleep to allow observation of incremental calculation
  60       (if (< (abs (- (* guess guess) x)) @margin) true false))
  61
  62     ;; incrementally improve our guess
  63     (defpropagator heron [x done guess] [guess]
  64       (Thread/sleep 1000)
  65       (if done
  66         guess
  67         (/ (+ guess (/ x guess)) 2.0)))
  68
  69     (comment           ; after building the system
  70       (set-cell x 89)  ; update the value of x
  71       (deref guess)    ; immediately begin observing improvements in guess
  72       (deref guess))
  73   #+end_src
  74
  75 - parallel spread sheet using Clojure formulas is implemented in
  76   src_emacs-lisp[:var d=code-counter(file="src/spreadsheet.clj")]{(- d 5)}
  77   in [[http://repo.or.cz/w/propagator.git/blob_plain/HEAD:/src/spreadsheet.clj][src/spreadsheet.clj]].
  78
  79 ** License
  80 Copyright (C) 2010 Eric Schulte
  81
  82 This program is free software: you can redistribute it and/or modify
  83 it under the terms of the GNU General Public License as published by
  84 the Free Software Foundation, either version 3 of the License, or
  85 (at your option) any later version.
  86
  87 This program is distributed in the hope that it will be useful,
  88 but WITHOUT ANY WARRANTY; without even the implied warranty of
  89 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  90 GNU General Public License for more details.
  91
  92 You should have received a copy of the GNU General Public License
  93 along with this program.  If not, see <http://www.gnu.org/licenses/>.