Saturday 8 February 2014

Evaluator with State, Monad version

This is a bit more subtle.  In the evaluator with error, the additional information in the monadic value was a product of the parameter of the function.  That is to say, whether the result of applying function F to value X was an {ok...} or an {error...} depended on F(X).  However for the case of an evaluator with state the state is maintained in parallel with the values we are evaluating but it does not depend on the values.  So how is this handled?  In the evaluator with state our monadic value is not a tuple, it is a function that returns a tuple.

I'm going to start with a version that does not change the state.  Here is  the first version of the code.

-module(state_monad).
-export([unit/1, bind/2]).

unit(A) ->
    fun(X) ->
   {A, X}
    end.

bind(M, K) ->
    fun(X) ->
   {A, Y} = M(X),
   {B, Z} = (K(A))(Y),
   {B, Z}
    end.

Right, unit/1 now takes an un-monadic value A and returns a function that takes a state X and returns the value in a tuple with the state X.

And now bind/2 takes a monadic value M - which will be a function - plus a function K that is going to be applied to the value inside the monadic value.  What does bind/2 return? It returns a function that takes a state X and returns a tuple {B, Z} where B is a new value and Z is a new state.

So first this function that we are going to return has to open up the monadic value M - and how to do this? M is a function that takes a state, so we execute the function M(X) with the state X and we get out the value, A, and the state Y that has been packed inside:

   {A, Y} = M(X)

So now we have to apply our function F to the value A because that is what bind is for: and this gives us a monadic value, ie a function that takes a state as argument  - that is we execute K(A) to get the function then apply it to Y, which looks like this - (K(A))(Y).

   {B, Z} = (K(A))(Y):

This now returns the new tuple {B, Z} as required.

Now to try this here is the evaluator code that uses the state monad, without doing anything with the state:

-module(eval_sm).
-export([eval/1]).
-export([answer/0, error/0]).

-import(state_monad, [unit/1, bind/2]).

% Evaluator with state monad

eval({con, A}) ->
    unit(A);
eval({dv, T, U}) ->
    bind(eval(T), fun(A) ->
        bind(eval(U), fun(B) -> 
            unit(A div B)
        end)
    end).

answer() ->
    {dv, {dv, {con, 1972}, {con, 2}}, {con, 23}}.

error() ->
    {dv, {con, 1}, {con, 0}}.

If I now compile these and load them up and blithely eval(answer) I get this:

Eshell V5.10.2  (abort with ^G)
1> l(eval_sm).
{module,eval_sm}
2> eval_sm:eval(eval_sm:answer()).
#Fun<state_monad.1.81552699>
3>

Evaluating returns a function not a value.  To make this work fully I need to call this function, passing some state:-

3> (eval_sm:eval(eval_sm:answer()))("some state").
{42,"some state"}

That's it, I get the actual answer 42 in wraps with the state that I passed in at the top.

To make this actually do something we now need to add a function that will change the state.  We add a function tick/0 which returns a function that takes a state (we are now assuming this is going to be a number) and returns a tuple containing a dummy value and the state now incremented:

tick() ->
    fun(X) ->
   {ok, X+1}
    end.

This goes in the state monad code so we will need to export it.

The objective is to count how many times we execute a division. So in the evaluator, when we perform a division operation instead of just calling this:

        unit(A div B)

we do this:

        bind(tick(), fun(E)-> unit(A div B) end)

That is we bind the tick() function onto a function we invent on the spot to do the division.  We need a dummy parameter E in there - well I think we do, I'm not an Erlang lawyer - which just gives us a warning from the compiler.

It does however give the right answer - now I pass 0 as my initial state and it gets incremented:

1> l(eval_sm).
{module,eval_sm}
2> (eval_sm:eval(eval_sm:answer()))(0).
{42,2}
3>

42 is the answer to the evaluation and 2 is the final value of the state.

This is the final code:

-module(state_monad).
-export([unit/1, bind/2]).
-export([tick/0]).

unit(A) ->
    fun(X) ->
   {A, X}
    end.

bind(M, K) ->
    fun(X) ->
   {A, Y} = M(X),
   {B, Z} = (K(A))(Y),
   {B, Z}
    end.

tick() ->
    fun(X) ->
   {ok, X+1}
    end.


-module(eval_sm).
-export([eval/1]).
-export([answer/0, error/0]).

-import(state_monad, [unit/1, bind/2, tick/0]).

% Evaluator with state monad

eval({con, A}) ->
    unit(A);
eval({dv, T, U}) ->
    bind(eval(T), fun(A) ->
        bind(eval(U), fun(B) -> 
            bind(tick(), fun(E)-> unit(A div B) end)
        end)
    end).

answer() ->
    {dv, {dv, {con, 1972}, {con, 2}}, {con, 23}}.

error() ->
    {dv, {con, 1}, {con, 0}}.

Some doodling with pencil and paper will be required before I'm sure I see why that works. I take my hat off to the people who thought of this stuff.