Skip to content

Modeling Access to Global State

blancas edited this page Feb 5, 2013 · 20 revisions

An alternative to accessing local state is to pass data around as arguments to functions. This helps to keep functions free of side-effects but involves more work, it can make the code more complex, and it doesn't scale well as the data increases. The Reader monad offers the ability to access data, supplied by its caller, at any point within the flow of control, while hiding away the boilerplate of passing things around. In exchange for boxing values inside the Reader data type, we get the simplicity of global data from pure functions.

We first load the Morph core and monads namespaces.

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

reader is a constructor of Reader instances. It takes any kind of Clojure value.

(reader "foo")
;; Reader@87

The actual value of a Reader depends on the data provided during evaluation (see run-reader below). Thus unevaluated Reader values print as just a numeric id.

The following code illustrates the mechanics of the Reader facility and its use. There are two functions that trivially supply text for printing. A third one collects the text and prints it with a given margin, whose value is to be read as if it were global, though all these functions are pure. The code that runs the reader monad provides the value of the margin.

(defn text1 [] (reader "The quick fox"))
(defn text2 [] (reader "jumped over the lazy dog"))

(defn line []
  "makes a line with two parts and a margin"
  (monad [part1 (text1)
          part2 (text2)
          margin ask]
    (let [sp (clojure.string/join (repeat margin \space))]
      (reader (str sp part1 part2)))))

The monad macro provides the sequencing of Reader values and their bindings to the local variables. In this case, the variable part1 gets the string boxed in the Reader by function text1, and part2 gets the text from function text2. The variable margin gets the result of ask which is a predefined function that reads the Reader's environment value, in this case 8. Function line, in turn, makes a reader off the margin and the two lines of text. That is the Reader to be run by run-reader.

run-reader takes a Reader instance and the initial value for its environment. Callers can only supply a single value, but this may be any Clojure data structure. To complete the above example, here we call run-reader passing the Reader value return by line and the value 8 as the environment, which is meant to provide the line's margin. The result is the string created by str and returned as a Reader value.

(println (run-reader (line) 8))
;;        The quick foxjumped over the lazy dog

The monad macro will always return values of the same kind it works with. In the above example in function line, it uses Reader values (containing strings) and the environment value. Then it uses the reader constructor to return the result. Note that run-reader uses the result of line called with no arguments. Thus it is not apparent how ask is able to provide the value 8 to the variable margin. The answer is that the reader constructor makes high-order functions, so the one returned by line is the one that gets the environment value.

Organizing Code with a Reader Monad

To illustrate how to take advantage of the Reader plumbing, consider a simple expression evaluator for S-expressions in infix notation. It supports the use of Math constants from a global table. (We could, of course, write the evaluator as single function, but this way helps with the motivation for using Reader.)

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

(declare run)
(defn add [x y] (+ (run x) (run y)))
(defn sub [x y] (- (run x) (run y)))
(defn mul [x y] (* (run x) (run y)))
(defn div [x y] (/ (run x) (run y)))
(defn const [x] (if (symbol? x) (table x) x))

(defn run [op]
  (if (list? op)
    (case (second op)
      + (add (first op) (last op))
      - (sub (first op) (last op))
      * (mul (first op) (last op))
      / (div (first op) (last op)))
    (const op)))

(run '((5 * 2) - ((6 / 2) + 4)))
;; 3
(run '(10 * PI))
;; 31.41592

The processing of numbers and constants occurs at deep in the parsing process. What we want is to avoid access to the global data table from inside the function const; and we don't want to pass the table to run and then to the support functions and from there back to run. That's the job of the Reader monad. To refactor our code we stipulate the following: all evaluator functions shall return a Reader value. Note that the input data for all functions remains the same: a symbol, a number, or a list.

Considering that all functions now return a Reader, let's see how the function add should change. Here is the current code:

(defn add [x y] (+ (run x) (run y)))

We can see that it calls run which itself returns a Reader, so we need to extract the operands from them before we can call the addition operator. For that we use the monad macro:

(defn add [x y]
  (monad [a (run x) b (run y)] (reader (+ a b))))

The number boxed in the return value from (run x) is bound to a and the one from (run y) to b. Then function add just makes a new Reader with their sum. The key part is in function const; that's where we get access to the table. Here is the current code:

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

We won't use a global anymore' instead, we use the function asks.

asks gets the value from the Reader environment, applies on it a function we supply, and returns the result as a Reader value. Use this function when the environment (the Reader's data) is a compound value or a collection and you need only a specific value. In this case we just want to lookup a constant in the table, so we use the symbol as a function:

(defn const [x]
  (if (symbol? x) (asks x) (reader x)))

;; (asks x) works because this works:
('PI table)
;; 3.141592

Note that this function neither takes the table as an argument nor uses the global declaration. The Reader's plumbing takes care of providing the data where is needed. With this changes, here we have the whole evaluator.

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

(defn add [x y]
  (monad [a (run x) b (run y)] (reader (+ a b))))

(defn sub [x y]
  (monad [a (run x) b (run y)] (reader (- a b))))

(defn mul [x y]
  (monad [a (run x) b (run y)] (reader (* a b))))

(defn div [x y]
  (monad [a (run x) b (run y)] (reader (/ a b))))

(defn const [x]
  (if (symbol? x) (asks x) (reader x)))

(defn run [op]
  (if (list? op)
    (case (second op)
      + (add (first op) (last op))
      - (sub (first op) (last op))
      * (mul (first op) (last op))
      / (div (first op) (last op)))
    (const op)))

To execute our new monadic evaluator we use the function run-reader.

run-reader takes a Reader expression and a Clojure value of any kind, which forms the Reader's data environment. It returns the value inside the Reader value produced. Here we pass the table map as the data to be used in function const.

(run-reader (run '((5 * 2) - ((6 / 2) + 4))) table)
;; 3
(run-reader (run '(10 * PI)) table)
;; 31.41592

Simplifying the Evaluator

The above code satisfied our requirement of using pure functions with the ease of direct global data. Now we can simplify the evaluator. Recall that the job of our arithmetic functions is just to extract values, apply an operator, and put the result back in a Reader. That's because an operator like + cannot work on numbers boxed in a Reader. What we would want is to apply a function on values inside Readers. It turns out we can do just that because every Reader is something called an applicative functor.

Applicative functors support the <*> (apply) operator. This operator works like apply but all the arguments are inside instances of the Applicative protocol, such as Reader. Thus, if in our first evaluator we have this code:

(defn add [x y] (+ (run x) (run y)))

Now, using the <*> operator on Readers we could write the following, where both the operator and operands are all Reader values:

(defn add [x y] (<*> (reader +) x y))

;; to see that this would work, evaluate the above definition and then this:
(run-reader (add (reader 3) (reader 4)) table)
;; 7

In fact, the code has been so simplified that we can actually write the whole evaluator as a single function, as we hinted at the start.

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

(defn run [op]
  (if (list? op)
    (case (second op)
      + (<*> (reader +) (run (first op)) (run (last op)))
      - (<*> (reader -) (run (first op)) (run (last op)))
      * (<*> (reader *) (run (first op)) (run (last op)))
      / (<*> (reader /) (run (first op)) (run (last op))))
    (if (symbol? op) (asks op) (reader op))))

(run-reader (run '((5 * 2) - ((6 / 2) + 4))) table)
;; 3
(run-reader (run '(10 * PI)) table)
;; 31.41592

Changes in the Data

The data carried by the Reader (its environment) may be changed for subordinate expressions, without changing the data for the rest of the code. For example, say we want to support negative constants with a new operator. We could just negate a call to const but to illustrate a change in the data we will evaluate const under a changed constants table where all the values of the map are negated in advance.

local takes a function and a Reader value. It applies the function to the Reader environment and then evaluates the reader value using the modified environment. For our evaluator we want to change the # the map values, so we use another Morph feature. A monad is also a Functor that supports fmap which is a generalized version of map that can work on any type that implements the Functor protocol. Here is how fmap works on the constants table:

(fmap - table)
;; {PI -3.141592, E -2.718281, DEG -57.295779}

Since local takes a function, we'll pass (fmap -) taking advantage that Morph defines fmap curried, so there's no need to use partial. Using the local evaluation of negative constants we have the final version of our evaluator:

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

(defn run [op]
  (if (list? op)
    (case (second op)
      + (<*> (reader +) (run (first op)) (run (last op)))
      - (<*> (reader -) (run (first op)) (run (last op)))
      * (<*> (reader *) (run (first op)) (run (last op)))
      / (<*> (reader /) (run (first op)) (run (last op)))
      n (local (fmap -) (run (first op))))
    (if (symbol? op) (asks op) (reader op))))

;; (E n) means -E:
(run-reader (run '(2 * (E n))) table)
;; -5.436562