Evaluator for SKI combinator calculus trees

skicalc.erl

-module(skicalc).
-export([eval/1, conv/1]).

% Valid terms to be eval1uated here are binary trees represented as
% two-element tuples. Leaves can be anything, and the atoms s, k and i
% represent the symbols S, K and I in the calculus' alphabet.

% For example, an operator to reverse two elements can be defined as:
% 
%     1> R = {{s,{k,{s,i}}},k}.    
%     {{s,{k,{s,i}}},k}
%     2> skicalc:eval({{R,x},y}).
%     {y,x}

eval(X) when is_list(X) ->
    eval(conv(X));
eval(X) ->
    case eval1(X) of
        X -> X;
        Y -> eval(Y)
    end.

eval1({i, X}) -> X;
eval1({{k, X}, _Y}) -> X;
eval1({{{s, X}, Y}, Z}) -> {{X, Z}, {Y, Z}};
eval1({X, Y}) -> {eval1(X), eval1(Y)};
eval1(X) -> X.

%% Convert list-based terms to the tuples used by eval/1.
%% The lists can be written more alike the usual written
%% syntax, where left associativity is the default unless
%% parentheses indicate otherwise. For example: 
%% 
%%   41>skicalc:conv([a,b,[c,d]]).
%%   {{a,b},{c,d}}

conv([H|T]) when is_list(H) -> conv(H++T);
conv(L) ->
    conv1(lists:reverse(L)).

conv1([X]) -> X;
conv1([H|T]) when is_list(H) -> {conv1(T), conv(H)};
conv1([H|T]) -> {conv1(T), H};
conv1(X) -> X.