We saw how the
Either monad captures a computational feature that captures threading messages through an expression evaluation. The
Reader monad similarly captures a feature that threads a read-only environment through a computation. Recall the signature of the current
eval function for
where an environment is explicitly passed as an argument. While this works fine, we typically don’t pass environments to interpreters to pragmatic evaluation functions. The environment exists as an ephemeral data structure the interpreter is aware of implicitly. The
Reader gives us exactly this capability for maintaining an environment during evaluation.
Reader is a datatype with a single constructor whose argument is a function from environment to value.
runR pulls the function out of the monad encapsulation and executes it on a specific environment:
runR :: Reader e a -> e -> a runR (Reader f) e = f e
R of type
runR e extracts the function and applies it to a specific environment,
e. We’ll construct the
Reader instance that encapsulates a function, then extract and execute the function.
So far, this looks nothing like
Either in form or function. Let’s look at the
Monad instance for
Reader and see how
bind are implemented. Following is the
Monad instance for
return function takes a value, creates a function from an environment, and wraps it up in the
Reader constructor. The function returns the argument to
return regardless of the input environment. In effect,
return creates a constant function from environment to value. Let’s see it at work with
return 5 creates the
(Reader \e -> 5).
\e -> 5 and applies it to the second argument,
, resulting in
5. A second example shows the same result with an alternative environment:
return encapsulates a the simplest computation - returning a constant value.
>>= passed through a
Left value and performed a specified operation on a
Right value. In
>>= will perform a computation and pass the result to a subsequent computation. It is, in effect, a sequence operator. For reference, the type from the
Monad class and the
bind instance for
Before diving into
bind in depth, look carefully at executing the function it creates from the inside out. If we think of
eval, we first evaluate
g with the result used as input to
f. At its essence,
Reader sequences the execution of
f. The role of
e is as an environment for both. We can define arbitrary numbers of functions, sequence them, and provide an environment.
Let’s look at a simple example of adding 1 to an input value:
return 5, the
Reader that simple returns
f is the function that takes a value and produces a
Reader that returns the result of adding
1 to the input. Looking at executing
(return 5) resulting in
5. It then applies
5 resulting in a
Reader that simply returns
(return 6) resulting in
Because the result of
runR is a number, we can add other operations to the sequence:
Now we can sequence operations. But given nothing else, the environment is constant across all the
runR executions. Worse yet, there’s no way to use or modify it. Let’s look at how to look at and change the environment locally.
ask simply returns the environment:
It’s important to realize that
ask is not a function, but a
Reader instance. Let’s run it and see what it does:
ask returns the environment. If the result of
ask is the environment value, then
ask >>= f should use the environment as the input to
That’s exactly what happens here. The environment is used in subsequent calculations following
asks will apply a function to the environment and return the result:
asks is not a
Reader, but instead a function from environment to value to
Reader. It builds a
bind. For example,
asks (\x -> head x) is an operation that takes the first element of an environment an returns it. Assuming of course, the environment is a list. Let’s try it out:
asks runs and pulls the first element off the environment list. The result is passed to a simple function that returns its input.
asks applies a function to the environment and
return produces it as output. We can now ignore the environment, return the environment, and apply a function to the environment.
local makes things interesting and starts showing off the
Reader at work by making changes to the local environment. Like
asks, local is a function that creates a
Reader that can be used in a
local’s two arguments are a function on the environment and a
Reader. The function is applied to the environment in a similar manner as
Reader is a monad that will be run with the modified environment.
r is a
Reader that will be run in the environment created by
f e. How does
local do this?
local first executes
ask to get the environment. The result is then passed as input to the second
bind argument as
e. Remember, the second argument to
bind is a function from an environment to a
Reader. Look carefully at the returned
return of course returns a value. That value is obtained by running the
Reader passed to
f e as the environment. The
Reader passed to local as
t is run inside another
Reader with a new environment. Thus the name
local. When the nested
Reader runs, the created environment is lost and the original environment restored. This is key as it is exactly the behavior our environment exhibits.
Take a step back and think about what we’ve done in a different way. All
Reader instances are encapsulated computations wrapped up in a datatype.
runR executes those computations.
return encapsulates single, atomic computations.
bind sequences computations allowing results from prior computations to flow to later computations.
Reader adds and environment, but all instances of
Monad do roughly the same thing. Encapsulate and sequence computations.
How can we use the
Reader to implement an interpreter? In earlier versions of interpreters with an environment, we passed the environment as an argument to
eval. Each expression is evaluated by recursive calls to
eval on subterms. This is long established. Evaluating some subterms cause changes to the environment, an issue not explored thoroughly.
Let’s start through the definition of
evalM, a monadic evaluator for FBAE. The signature is:
The return result is a
Reader. Remember that to get a value from the
Reader we must run
runR on the result. We’ll define an
eval function later that does just this.
Thinking about expressions in
FBAE, we can divide them up into two groups based on how they use the environment. Specifically, there are three sets:
The first set includes returning constants and evaluating mathematical expressions. None of them require accessing the environment directly:
A couple of utility functions are useful for lifting addition and subtraction into the
Id requires accessing the environment to find the value of an identifier. This is easily done using
ask to get the environment and using a lookup function to find the needed environment record.
lookupVar returns a
Maybe, thus we use a case statement to extract the return value or throw an error message. For completeness,
lookupVar is simply a call to
lookup that treats its argument as a list of pairs:
The last two expressions require adding information to the environment.
local does exactly what we need. Evaluating both
App requires adding a variable binding to the environment:
local exactly the same way. The value associated with the added identifier is calculated first and use with the identifier to partially instantiate
addVar. When supplied with an environment,
addVar will result in a new environment with the addition.
evalM b evaluates
b in the context of the environment created by
Again for completeness, the definition of
Does this monadic interpreter implement static or dynamic scoping? How can you tell? I’ll give you a hint and say we’ll look at a statically scoped interpreter next and forever leave dynamically scoped languages.
To implement static scoping we add closures that record the environment where a function is defined. We’ve done this once already and will simply repeat the process hear using the
Reader. First, the abstract syntax:
Nothing changed other than adding the argument type to
Lambda. We’ll see if we need this for evaluation, but we will certainly need it for type checking. Still the same language, just with that small addition.
With types references from the abstract syntax, we need to include the datatype for
For completeness again we include the type for values introduced earlier for static scoping. The important bit is the inclusion of closures for recording the static environment:
Finally, the environment type:
Now we can define
evalM, the monadic evaluator using the
evalM accepts an abstract syntax value and returns a
Reader that we’ll evaluate with
runR. The only change here is the
Reader encapsulates a function of type
Env -> FBAEVal rather than
Env -> FBAE used previously:
Now the interpreter. Same song, second verse. Everything is identical until we get to the
Lambda we need to grave the environment when it is defined. When
env was a parameter, this was easy. Using
ask it still is. We simply execute
ask to return a copy of the environment and bind the result to
env. Then creating the closure is exactly as it was in the non-monadic statically scoped interpreter.
The returned closure contains the environment obtained with
ask when the
lambda is evaluated. Note that we are evaluating a
lambda, not an application. That comes next.
App is where the environment from the closure is actually used. In effect, when we evaluate the app we need to start with the environment from the closure rather than the enviornment maintained by the
Reader to that point. We don’t want to add to the enviroment. Instead we want to replace it.
When evaluating the
App we first evaluate
a to get the closure and argument value. For dynamic scoping we added a pair to the result of
ask and replaced the environment with
local. We need to do the same thing again, but using the closure environment rather than the
Reader environment. We’ll accomplish this by passing a new function to
Look below how
useClosure is used. The first three arguments are instantiated with the identifier name, value and the environment from the closure. The result is a function of type
Env -> Env, exactly what
local needs. This particular function ignores that argument and produces a new environment using
e from the closure:
useClosure creates a new environment by adding the new binding needed for evaluating
App to the environment from the closure.
local plugs that in and we’re now good go go.
Now that we know how to build an environment from
bind, it’s time to evaluate identifiers by looking them up.
ask returns the environment that is in turn bound to
lookup is performed to find
env. If it’s there, return it. If it’s not, throw an error.
It’s useful to redefine
evalM so the interpreter operates in the same way as previous interpreters:
Now we have a statically scoped interpreter for
FBAE using a
As you might have guessed, the
Reader is also quite effective at type checking. What is particularly interesting is the similarly between the type checker and evaluator.
For completeness, the context type is defined as a list of string/type pairs:
The signature for our new type inference function is roughly the same as the evaluator, except that we return a
Reader that encapsulates types. We will still need to use
runR to evaluate the result of called
The type of number constants is simply
TNum. Just return it:
The binary operations on numbers are identical modulo error messages. Both find the types of their arguments and make sure both are numbers. If they are, return
TNum as the type of the operation. If not, throw an error:
bind adds bindings to the context when type checking.
typeofM uses the
Reader to pass along the context rather than the environment, but the operations are almost identical.
bind first uses
ask to get the current context. It calculates the type of the identifier being added, and then uses
local in the same way as
evalM to add the binding to the local context:
To perform static type checking, we need to use the
lambda variant that carries a type for its argument.
(i,t) is added to the context and
typeofM b used to get
r', the range type, that is the typeof the function body. The type of the
(TFun t r'):
App case uses
typeofM to get the type of the function and its argument. The function type provides the domain and range of the associated function. If the type of the argument is the domain type, then the
app is the range type. If they do not match, then
typeofM throws an error. The
if expression is where all the work for this function is performed:
Finally finding the type of an identifier is simply looking it up on the context.
ask returns the context, a lookup is performed, and either a type is returned or an error message is thrown:
Like other functions, we can made the monadic version look like a traditional version with a quick definition:
Reader is an exceptionally powerful and useful programming pattern. Utility functions like
local are just few samples of what kinds of operations can be defined on the environment. Even the function
useClosure could be rewritten as a custom operation rather than using
In our work thus far we have used our own
Reader. The standard Haskell libraries contain a
Reader implementation. However, when learning how to use the
Reader it is far better to have visibility into the implementation than simply try to use the
Reader interface. Monad type signatures are not enough to understand their utility.
It is worth spending time with a good Haskell tutorial and learning the