Modeling Access to Global State

Read/Write access to global state makes a function impure. On the other hand, passing around multiple or complex, compound arguments is tedious and makes functions less reusable. The State monad is a facility that provides the ability to read and modify all or part of a data structure as simply as if it were global, but from pure functions. This (seemingly) global data, or environment, may be any Clojure value.

First we load the Morph core and monads namespaces.

(use 'blancas.morph.core
     'blancas.morph.monads)

state is a constructor for values that participate in a computation that provides a global environment. Since its result may depend on the environment provided during evaluation, a State instance just prints with a numeric id (its hash code).

(state 737)
;; State@10

eval-state evaluates a sequence of State values and produces a result. It takes a State instance and the initial state of the data environment.

(eval-state (state 747) 0)
;; 747

exec-state evaluates a sequence of State values and produces a result; returns the final state of the data environment. It takes a State instance and the initial state of the data environment.

(exec-state (state "foo") 747)
;; 747

The following example illustrates the mechanics of creating and evaluating a sequence of State instances.

(def s1 (state 3))
(def s2 (state 4))
(def calc (monad [x s1          ;; first operand
                  y s2          ;; second one
                  f get-state]  ;; operator from the supplied data
            (state (f x y))))   ;; return result as a State instance

(eval-state calc *)
;; 12

Organizing Code with a State Monad

To illustrate how to take advantage of the State monad plumbing, consider a simple expression evaluator for S-expressions in infix notation. It supports the use of Math constants from a global table.

(def table {'DEG 57.295779 'E 2.718281 'PI 3.141592})

(declare run)

(defn calc [op x y]
  (op (run x) (run y)))

(defn const [x]
  (if (symbol? x) (table x) x))

(defn run [op]
  (if (list? op)
    (case (second op)
      + (calc + (first op) (last op))
      - (calc - (first op) (last op))
      * (calc * (first op) (last op))
      / (calc / (first op) (last op)))
    (const op)))

(run '(3 + (2 * PI)))
;; 9.283184

Access to the symbol table can happen in nested, recursive calls to run. What we want is to read values of variables but also add new variables to the table. Also, we want to avoid using the table as a global declaration. Furthermore, we don't want to pass the table around from run to const or calc and back to run again. We solve this problem by making all function return State instances. Now, since run will return a State, function calc must unbox the values with the monad macro.

(defn calc [op x y]
  (monad [a (run x) b (run y)]
    (state (op a b))))

Function const should also return a State instance. By doing so it participates in the State monad sequence and therefore it can access the State's data environment. It does so using gets.

gets is a function of the State monad that works on the data environment. It takes a function, which is applied on the environment and the result is returned as a State instance (just like the Reader's asks function.)

(defn const [x]
  (if (symbol? x) (gets x) (state x)))

Note that the symbol argument is given to gets as the function argument. This works because a symbol can take a map as an argument, in which case it looks itself up as a key and returns the value or nil. Here is the new version of the evaluator.

(def table {'DEG 57.295779 'E 2.718281 'PI 3.141592})

(declare run)

(defn calc [op x y]
  (monad [a (run x) b (run y)]
    (state (op a b))))

(defn const [x]
  (if (symbol? x) (gets x) (state x)))

(defn run [op]
  (if (list? op)
    (case (second op)
      + (calc + (first op) (last op))
      - (calc - (first op) (last op))
      * (calc * (first op) (last op))
      / (calc / (first op) (last op)))
    (const op)))

Now we can evaluate expressions for the computed value or for the final state of the environment. Note that we provide the table as the data environment in the calls below.

(eval-state (run '(3 + (2 * PI))) table)
;; 9.283184
(exec-state (run '(3 + (2 * PI))) table)
;; {PI 3.141592, E 2.718281, DEG 57.295779}

State can be Changed or Replaced

We'll now add two more functions to our evaluator. The first one is for adding a new variable; for this we'll add the following syntax: (var = value) and will resolve to value at the place of usage. We use the function modify-state for adding a new key-value pair to the table.

modify-state takes a function and optional, additional arguments, which are applied to the current data environment to produce a new result. In the following code we need to use assoc to add the variable declaration:

(defn decl [x y]
  (>> (modify-state assoc x y) (state y)))

This function creates a State instance but its value is not used for the greater computation, so a short way to chain two State instances is with >> so that the first value is ignored; we need to return (state y) because the value of the declared variable is used in the place of declaration.

The second function to add is a command to clear the symbol table. It usage is: (value %) and evaluates to value at the place where it appears. To replace the data environment we use put-state.

put-state takes a value to serve as the new data environment. Fo the new command, use supply an empty map.

(defn clear [x]
  (>> (put-state {}) (state x)))

We're also not interested in the return value of put-state so we chain it with >> but make sure to return the value as a state, since is needed at the place of usage. We now have the final version of our evaluator.

(def table {'DEG 57.295779 'E 2.718281 'PI 3.141592})

(declare run)

(defn calc [op x y]
  (monad [a (run x) b (run y)]
    (state (op a b))))

(defn const [x]
  (if (symbol? x) (gets x) (state x)))

(defn decl [x y]
  (>> (modify-state assoc x y) (state y)))

(defn clear [x]
  (>> (put-state {}) (state x)))

(defn run [op]
  (if (list? op)
    (case (second op)
      + (calc + (first op) (last op))
      - (calc - (first op) (last op))
      * (calc * (first op) (last op))
      / (calc / (first op) (last op))
      = (decl   (first op) (last op))
      % (clear  (first op)))
    (const op)))

We can now evaluate expressions that declare new variables and clear the symbol table.

(eval-state (run '(((k = 5) * 2) + k)) table)
;; 15
(exec-state (run '(((k = 5) * 2) + k)) table)
;; {PI 3.141592, E 2.718281, DEG 57.295779, k 5}
(eval-state (run '(((k = 5) * 2) + (8 %))) table)
;; 18
(exec-state (run '(((k = 5) * 2) + (8 %))) table)
;; {}

Functions calc, const, decl, and clear have read and write access a collection provided by the evaluator function, with the same ease as if it were a global definition, but remaining pure functions.