expr.erl

-module(expr).
-export([test/0]).

-type expr() :: {num, integer()}
             |  {val, atom()}
             |  {add, expr(), expr()}
             |  {mul, expr(), expr()}.

-type inst() :: {push, integer()}
             |  {fetch, atom()}
             |  {add}
             |  {mul}.

-type env() :: [{atom(), integer()}].

-type program() :: [inst()].

-type stack() :: [integer()].

-spec print(expr()) -> string().
print({num,N}) ->
    integer_to_list(N);
print({val,A}) ->
    atom_to_list(A);
print({add,E1,E2}) ->
    "(" ++ print(E1) ++ "+" ++ print(E2) ++ ")";
print({mul,E1,E2}) ->
    "(" ++ print(E1) ++ "*" ++ print(E2) ++ ")".

-spec lookup(env(),atom()) -> integer().
lookup([{A,V}|_], A) ->
    V;
lookup([_|Rest], A) ->
    lookup(Rest, A).

-spec eval(env(),expr()) -> integer().
eval(_Env,{num,N}) ->
    N;
eval(Env,{val,A}) ->
   lookup(Env,A);
eval(Env,{add,E1,E2}) ->
    eval(Env,E1) + eval(Env,E2);
eval(Env,{mul,E1,E2}) ->
    eval(Env,E1) * eval(Env,E2).

-spec compile(expr()) -> program().
compile({num,N}) ->
    [{push,N}];
compile({val,A}) ->
    [{fetch,A}];
compile({add,E1,E2}) ->
    compile(E1) ++ compile(E2) ++ [{add}];
compile({mul,E1,E2}) ->
    compile(E1) ++ compile(E2) ++ [{mul}].

-spec run(env(),program(),stack()) -> integer().
run(Env,[{push,N}|Continue],Stack) ->
    run(Env,Continue,[N|Stack]);
run(Env,[{fetch,A}|Continue],Stack) ->
    run(Env,Continue,[lookup(Env,A)|Stack]);
run(Env,[{add}|Continue],[N1,N2|Stack]) ->
    run(Env,Continue,[(N1+N2)|Stack]);
run(Env,[{mul}|Continue],[N1,N2|Stack]) ->
    run(Env,Continue,[(N1*N2)|Stack]);
run(_Env,[],[N]) ->
    N.

test() ->
    Env = [{x,42}],
    Expression = {add,{add,{num,2},{mul,{num,3},{num,4}}},{val,x}},

    "((2+(3*4))+x)" = print(Expression),
    56 = eval(Env,Expression),

    Program = [{push,2},{push,3},{push,4},{mul},{add},{fetch,x},{add}],
    Program = compile(Expression),

    56 = run(Env,Program,[]),

    0.