Lambda calculus interpreter. Slow realisation.

lc.erl

-module(evaluate).

-compile(export_all).

test_program() ->
    [[l, l, l, [var, 2], [var, 0], [var, 1]],
      1,
      2,
     [l, l, [var, 1]]].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

eval([l | Body]) ->
     [l | Body];

eval(List) when is_list(List) ->
    foldl1(
        fun (X, F) ->
            [l | Body] = eval(F),
            eval(substitute(Body, X))
        end,
        List);

eval(Other) -> Other.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

sink([l | Body]) -> Body;

sink(Other) -> Other.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

substitute([l | Body], X) -> [l | substitute(Body, push(X))];

substitute([var, 0], X) -> X;

substitute([var, N], _) -> [var, N - 1];

substitute(List, X) when is_list(List) ->
    lists:map(
        fun (Item) ->
            substitute(Item, X)
        end,
        List);

substitute(Other, _) -> Other.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

push([l | Body]) ->
     [l | push(Body)];

push([var, N]) -> [var, N + 1];

push(List) when is_list(List) ->
    lists:map(fun push/1, List);

push(Other) -> Other.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

foldl1(Fun, List) -> lists:foldl(Fun, hd(List), tl(List)).

log(Msg, Array) -> io:format(Msg ++ "\n", Array).

trace(Msg, Value) -> log(Msg, [Value]),
                     Value.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

print(Program) -> lists:flatten(print(0, Program)).

print(Name, [l | Body]) ->
    case is_lambda(Body) of
        true  -> [[$a + Name], " ", print(Name + 1, Body)];
        false -> [[$a + Name], " -> ", print(Name + 1, Body)]
    end;

print(_,    [var, N]) -> [$a + N];

print(Name,  List) when is_list(List) ->
    Result =
        lists:map(
            fun (X) ->
                Z = print(Name, X),

                case is_term(X) of
                     true  -> Z;
                     false -> ["(", Z, ")"]
                end
            end,
            List),
    foldl1(
        fun (X, Acc) ->
            [Acc, " ", X]
        end,
        Result);

print(_,     Other) -> io_lib:format("~p", [Other]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

is_term([var, _]) -> true;

is_term(T) -> not is_list(T).

is_lambda([l | _]) -> true;

is_lambda(_) -> false.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

selftest() ->
    eval(test_program()).