Skip to content

Instantly share code, notes, and snippets.

@bmjames
Created December 17, 2010 17:11
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmjames/745291 to your computer and use it in GitHub Desktop.
Save bmjames/745291 to your computer and use it in GitHub Desktop.
Evaluator for SKI combinator calculus trees
-module(skicalc).
-author("Ben James <benj@lshift.net>").
-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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment