Evaluator for SKI combinator calculus trees

skicalc.erl

-module(skicalc).
-author("Ben James <[email protected]>").

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

% Valid terms to be evaluated 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: 
% 
%     1> skicalc:conv([a,b,[c,d]]).
%     {{a,b},{c,d}}
%     2> R = [s,[k,[s,i]],k].
%     [s,[k,[s,i]],k]
%     3> skicalc:eval([R, x, y]).
%     {y, x}

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.