Skip to content

Instantly share code, notes, and snippets.

@amtal
Created September 25, 2011 04:10
Show Gist options
  • Save amtal/1240218 to your computer and use it in GitHub Desktop.
Save amtal/1240218 to your computer and use it in GitHub Desktop.
Simple interpreter using a monad for a "mutable" environment.
-module(rpn).
-export([eval/1, hypotenuse/2]).
-compile({parse_transform,do}).
-spec eval([Op]) -> stack_m(ok).
%% Interpreter for a simple stack-based language.
%%
%% Uses a custom stack_m monad, which is a trivial wrapper around state_m[1].
%% It exports:
%% -spec pop() -> stack_m(A).
%% -spec push(A) -> stack_m(ok).
%% -spec run(stack_m(A), [B]) -> {A, [B]}.
%%
%% Note how the stack looks like a mutable data structure - but actually isn't.
%%
%% Its representation is also completely opaque. We know that stack_m:run/2
%% takes a list to initialize it, and returns a list once the program's been
%% run, but those are just views. The internal representation is hidden from us.
%%
%% This opaqueness makes it trivial to extend. If we wanted to add {load,Key}
%% and {store,Key} instructions, turning stack_m into an interpreter environment
%% monad, all we'd have to do is add a dictionary to the hidden state and define:
%% -spec load(Key) -> env_m(Val).
%% -spec store(Key,Val) -> env_m(ok).
%%
%% [1] In Erlando there's no state_m, there's a state_t(identify_m()). Monad
%% transformers are a way to compose different monads to get a monad that has
%% all their properties... But that's a whole new topic.
eval([]) -> stack_m:return(ok).
eval([Op|Rest]) -> do([stack_m||
op(Op),
eval(Rest)]).
% where
op({push,X}) when is_number(X) ->
stack_m:push(X);
op(pop) ->
stack_m:pop();
op(dup) -> do([stack_m||
X <- pop(),
push(X),
push(X)]);
op(swap) -> do([stack_m||
A <- pop(),
B <- pop(),
push(A),
push(B)]);
op(sqrt) -> do([stack_m||
A <- pop(),
B <- pop(),
push(math:sqrt(A,B))]);
op(Op) when Op==add; Op==mul -> do([stack_m||
A <- pop(),
B <- pop(),
begin
C = case Op of % replacement of haskell's let
add -> A+B;
mul -> A*B
end,
push(C)
end]);
op(sqr) -> do([stack_m||
eval(dup),
eval(mul)]);
op(Op) -> error({bad_op,Op}).
hypotenuse(A,B) ->
Program = [{push,A},{push,B}|hyp()],
{ok,[C]} = stack_m:run(eval(Program),[]),
C.
% where
hyp() -> [sqr, swap, sqr, add, sqrt].
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment