Evaluator with Trace

For this example we want to give our evaluator the power to create a trace of its execution. We add a function line/2 that takes a term and a value and creates a string that describes the term and shows that this evaluates to the value.

For example given the term {con, 42} and the value 42 it returns the string "eval({con,42}) <== 42" or similar.

Obviously this makes sense only if the value we pass is actually the value returned by the evaluation of the term we pass.  I mean, we won't call line({con, 42}), 99).

Then when the evaluator evaluates a term it also calls this function line/2 with the term and with the resulting value, thus showing the trace of that step, and returns this in a tuple with the actual return value.

Also I needed an extra function write_term/1 in there to turn a term into a string, for example to turn {con, 42} into the string "{con, 42}".

These extra functions are not exported from the module because we won't need to call them from the shell. Well, yes we would for testing, so you might opt to export them at first and then remove the export later.

So now each time I evaluate a term I include a trace of the evaluation in a tuple with the result, and I add to the trace each time it passes through.

Anyway here is the code now:

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

% evaluator with trace

eval({con, A}) ->
    {line({con, A}, A), A};
eval({dv, T, U}) ->
    {X, A} = eval(T),
    {Y, B} = eval(U),
    {X ++ Y ++ line({dv, T, U}, (A div B)), A div B}.

write_term({con, A}) ->
    "{con, " ++ io_lib:print(A) ++ "}";
write_term({dv, T, U}) ->
    "{dv, " ++ write_term(T) ++ ", " ++ write_term(U) ++ "}".

line(Term, A) ->
    "eval (" ++ write_term(Term) ++ ") <==" ++ io_lib:print(A) ++ io_lib:nl().

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

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

So now when I evaluate the Answer I get back the value 42 tucked into a tuple with the string that constitutes the accumulated trace of the eval operations:

1> l(eval_t).
{module,eval_t}
2> eval_t:eval(eval_t:answer()).
{"eval ({con, 1972}) <==1972\neval ({con, 2}) <==2\neval ({dv, {con, 1972}, {con
, 2}}) <==986\neval ({con, 23}) <==23\neval ({dv, {dv, {con, 1972}, {con, 2}}, {
con, 23}}) <==42\n",
 42}

I need to spread that trace string out - split that string at each "\n" character:

eval ({con, 1972}) <==1972
eval ({con, 2}) <==2
eval ({dv, {con, 1972}, {con, 2}}) <==986
eval ({con, 23}) <==23
eval ({dv, {dv, {con, 1972}, {con, 2}}, {con, 23}}) <==42

Why does the arrow point from the result to the parameter and not the other way?  Don't know.  Hmm.

Evaluator with State.

Leaving the error processing aside the next example incorporates an updateable state into our evaluator.  As an example we say that we wish to count how often the division operation has been called.  We could do this by creating a global variable that we increment in the division code.  In our functional version we do this by tagging our values with a state, our counter, by including it in a tuple. So instead of our evaluator returning an integer A it will return return {A, N} where A is the integer result and N is is the count of division operations that we have done.

So we adapt the evaluator to set and maintain this counter, as so:

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

% evaluator with state

eval({{con, A}, X}) ->
    {A, X};
eval({{dv, T, U}, X}) ->
    {A, Y} = eval({T, X}),
    {B, Z} = eval({U, Y}),
    {A div B, Z + 1}.

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

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

The counter is passed through each evaluation and on the line where we do the division we add one to it.

Then when we evaluate Answer we also pass a starting value zero for the counter:  the result contains the answer 42 and the final value of the counter, 2.

1> l(eval_s).
{module,eval_s}
2> eval_s:eval({eval_s:answer(), 0}).
{42,2}
3> eval_s:eval({eval_s:error(), 0}).
** exception error: an error occurred when evaluating an arithmetic expression
     in function  eval_s:eval/1 (c:/Users/polly/Erlang/eval_s.erl, line 12)

Evaluating Error still gives you an exception of course.

Evaluator with error handling

The next version allows for the fact that the core division operation can fail. The natural way to deal with this is to throw an exception and get out of the module up to a higher level. However this means that your function has not properly returned.  The other approach is to plough on to the end, taking care to avoid using anything that depends on a value you couldn't get because of the error.  Everyone has written code like this. Your execution code forks and forks again.  Or rather, everyone has a favourite strategy for avoiding writing code like this.  Subject for a later blog post I think.  Anyway, this is how we can handle the error state in our evaluator.  Intead of just returning a value A we return either the tuple {ok, A}, where A is some integer, representing a successful evaluation, or else the tuple {error, Reason} where Reason is some string explaining what the error is.

Then in the evaluator when we are passed a parameter which evaluates to an error we just pass that error back.  If we are asked to divide by zero we create the error expression.  Otherwise it is calculated as normal.  we just have to add the forks to the code to make this work, like so:

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

% evaluator with error handling

eval({con, A}) ->
    {ok, A};
eval({dv, T, U}) ->
    case eval(T) of
        {error, E} -> {error, E};
        {ok, A} ->
            case eval(U) of
                {error, E} -> {error, E};
                {ok, B} ->
                    if
                        B == 0 -> {error, "divide by zero"};
                        true -> {ok, A div B}
                    end
            end
    end.

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

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

Applying the new evaluator to Answer returns the tuple {ok, 42} indicating a successfully completed computation and showing the result:  applying it to Error returns {error, "divide by zero"}.  These are both legitimate return values for the function.

1> l(eval_e).
{module,eval_e}
2> eval_e:eval(eval_e:answer()).
{ok,42}
3> eval_e:eval(eval_e:error()).
{error,"divide by zero"}

The Streets of Software City are littered with cases where the return values from a function can include values that are not just quantitively different but qualitatively different.  For example a function that is supposed to return the next character from a stream can also return an integer that is not a character because it needs to indicate the end of file somehow.  Or a function that finds the index of a character inside a string can return -1 to indicate that there is no character to find.  End-of-file is not a type of character: -1 is not an index: your return data is polluted with meta-data.  Being able to tag values and then pattern match against the tags is one way to tackle this.  In Haskell you can create types that have alternative qualitatively different values and bolt them into your type system so the code won't even compile if you haven't handled all the cases correctly.  That has to be the right way, surely?

Anyway this handles the error but has the bad effect that your code keeps forking every time you hit a function that can return the two different types of value.

The basic evaluator

OK so I've taken down Philip Wadler's paper "Monads for functional programming" from its place on my One Day I'll Get My Head Round This pile because I ask myself, how would this work in Erlang?  Here goes.

Basic evaluator

The paper illustrates application of monads to functional programming by means of a series of variations on a tiny example program, a module for evaluating simple expressions.

The evaluator works on two types of term:

• A term is either a constant, denoted by the tuple {con, A} where A is some integer, 
• Or it is a quotient, denoted {dv, T, U} where T and U are other terms.

The basic evaluator looks like this. To evaluate a Constant {con, A} we return the integer A.  To evaluate the quotient {dv, T, U} we evaluate T and U and then divide the value from T by the value from U.
There are also two example expressions to test, called Answer and Error:

• Answer represents the calculations (1972/2)/23 = 42 (I get the allusion) and 
• Error represents 1/0 so it is there to cause an error.  

I've added these to the module as functions to save typing them out.  Here is the code.
-module(eval0).
-export([eval/1]).
-export([answer/0, error/0]).

% Basic evaluator

eval({con, A}) ->
    A;
eval({dv, T, U}) ->
    eval(T) div eval(U).

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

error() ->
    {dv, {con, 1}, {con, 0}}.
So I can load this code into the Erlang shell and evaluate the two expressions answer and error:

C:\Users\polly\Erlang>erl
Eshell V5.10.2  (abort with ^G)
1> l(eval0).
{module,eval0}
2> eval0:eval(eval0:answer()).
42
3> eval0:eval(eval0:error()).
** exception error: an error occurred when evaluating an arithmetic expression
     in function  eval0:eval/1 (c:/Users/polly/Erlang/eval0.erl, line 10)
4> q().
ok
5>
C:\Users\polly\Erlang>

So answer brings back the answer 42, and error leads to an exception in the shell.

Running in the Shell

Ok so now to amend that hello script so that I can run it in the shell in a more mainstream fashion.  We need two additional lines at the start of the file, so:

-module(hello).
-export([main/1]).

The first line declares that this file constitutes a module called "hello".  The second line declares that this module exports a function called "main" which takes one parameter. The rest of the file is the same except I've added some line feeds to tidy up the output:

main([]) ->
    io:format("Hello World~n");
main([Arg]) ->
    io:format("Hello ~s~n", [Arg]);
main([Arg|More]) ->
    io:format("Hello ~s and~n", [Arg]),
    main(More).

Now on the command line we compile this so:

C:\Users\polly\Erlang>dir hello.*
12/12/2013  10:15               227 hello.erl
07/11/2013  13:32               186 hello.erl~
C:\Users\polly\Erlang>erlc hello.erl
C:\Users\polly\Erlang>dir hello.*
12/12/2013  10:21               688 hello.beam
12/12/2013  10:15               227 hello.erl
07/11/2013  13:32               186 hello.erl~

Ok the beam file is the compiled code.

Now to run the shell from the command line with the command erl:

C:\Users\polly\Erlang>erl
Eshell V5.10.2  (abort with ^G)
1> l(hello).
{module,hello}
2> hello:main(["Curly","Larry","Moe"]).
Hello Curly and
Hello Larry and
Hello Moe
ok
3> q().
ok
4>
C:\Users\polly\Erlang>

The numbered prompt 1> 2> etc are prompts in the shell.  The command l(hello) loads a module called "hello" from the appropriate beam file.  We then call the functions with the module - colon - function name format, as hello:main(...)

The command q(). returns the atom ok and then exits from the shell.

ok.

Refactoring

Clearly the business of opening a text file, reading through it line by line, and returning some result is going to be a general process.  Therefore let us factor out the general process from the specific application.  How about this:

The top function to process the file takes a file name, and some function to be applied to each line of the file, and a starting value to be threaded through the various lines of the file. We open the file and then call the sub-function that executes the loop, passing across the stream, and the function, and the starting value.  After this returns we get back the final value, so we can close the file and return our final value, so:

process_file(Filename, Fun, StartValue) ->
    {ok, Stream} = file:open(Filename, [read]),
    FinalValue = process_file_loop(Stream, Fun, StartValue),
    file:close(Stream),
    FinalValue.
 
Our function that executes the loop will require the stream and the function and an initial value.  It attempts to read a line but if no more is available it returns the value it was given, nothing more to be said.  However if it gets a line it can call the supplied function with the line and with the starting value, and it will get back some new value.  It can then call itself with this new value to continue the loop, like this:

process_file_loop(Stream, Fun, Value) ->
    case io:get_line(Stream, "") of
        eof ->
            Value;
        Line ->
            NewValue = Fun(Line, Value),
            process_file_loop(Stream, Fun, NewValue)
    end.

Right, that's the general case code.  In our specific application the function we want to apply is that bit of code that writes the line to the terminal with the line number and then increments the line number. We don't do anything with the line number in the end but it has to be threaded through.  We don't have to define this as a named function - with the syntax fun(...)->... we can create it as an anonymous function just when we need it.  So we set the process in motion by calling the process_file function passing the file name, the function we want to apply, and the starting value which is the line number 1.  So our main() function is this:


main([Filename]) ->
    process_file(Filename, 
         fun(Line, LineNumber)->
             io:format("~4.10.0B ~s", [LineNumber, Line]),
             LineNumber+1
         end,
         1).

Still works?

C:\Users\polly\Erlang>escript listout.erl hello.erl
0001
0002 main([]) ->
0003     io:format("Hello World");
0004 main([Arg]) ->
0005     io:format("Hello ~s", [Arg]).
C:\Users\polly\Erlang>

Yep.  Hey, I just did a lambda.  Thank you madam, your G&T is on its way.

Retaining a Value

Ok that's fine but now I want to print out a line number against those output lines.  Therefore the line number is an additional argument to the looper function:  set it to 1 on the first call from the main function, and then add one to it each time it is re-called from inside the looper.  Basic.  Like this:


main([Filename]) ->
    {ok, Stream} = file:open(Filename, [read]),
    listout_loop(Stream, 1),
    file:close(Stream).

listout_loop(Stream, LineNumber) ->
    case io:get_line(Stream, "") of
        eof ->
            ok;
        Line ->
            io:format("~b ~s", [LineNumber, Line]),
            listout_loop(Stream, LineNumber+1)
    end.

Speaking in rodent terms, then, in a procedural language you might keep the line number in a variable that you increment each time through the loop, squirrel-like, burying your treasure in the ground for easy access later: whereas in a functional language you keep your variable quantity balanced on your call parameters, hamster-like, running with your essentials stuffed in your cheeks.

So, just for the exercise, how would I return a result from the process?  Say I wanted to see the number of lines?  Well, when I hit eof I can return the LineNumber value - actually no, I will want LineNumber-1 because if I got eof then there was no line number LineNumber.  Then write this out at the end, no reason to except to prove I can do it.

Note incidentally that we don't close the file in the loop function when it gets the eof flag:  i.e. we don't say

    eof ->
        file:close(Stream).

By the Toybox Rule (If You Get It Out You Put It Away) it's the function that opens the file that should close it.


main([Filename]) ->
    {ok, Stream} = file:open(Filename, [read]),
    LineCount = listout_loop(Stream, 1),
    file:close(Stream),
    io:format("(~b lines)", [LineCount]).

listout_loop(Stream, LineNumber) ->
    case io:get_line(Stream, "") of
        eof ->
            LineNumber-1;
        Line ->
            io:format("~4.10.0B ~s", [LineNumber, Line]),
            listout_loop(Stream, LineNumber+1)
    end.

The mysterious format definition "~4.10.0B" requests a field four digits long in base 10 with 0 as the fill-up character showing the value of some Binary ie integer quantity.

So it looks like this:

C:\Users\polly\Erlang>escript listout.erl hello.erl
0001
0002 main([]) ->
0003     io:format("Hello World");
0004 main([Arg]) ->
0005     io:format("Hello ~s", [Arg]).
(5 lines)
C:\Users\polly\Erlang>

I admit I'm getting to like the idea that starting-lower-case identifiers are just atoms that mean themselves and can go enywhere with impunity.  Something has always told me that Nothing Of Importance Should Depend On The Case Of An Identifier but maybe the advantages justify breaking the rule.  These atoms do what symbols do in Lisp but in Lisp I have sometimes been caught out by forgetting whether I have quoted something or by quoting a quote.  Anyway.

Exercise: make the size of the line number field a parameter that can be passed in on the command line:-)