Skip to content

Instantly share code, notes, and snippets.

Created December 17, 2010 17:11
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
Evaluator for SKI combinator calculus trees
-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(X) ->
case eval1(X) of
X -> X;
Y -> eval(Y)
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([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