A quick and dirty lambda calculus to combinatory logic transformer

ski.erl

-module (ski).

% http://en.wikipedia.org/wiki/Combinatory_logic

-export ([apply/2, lambda/2, transform/1, to_binary/1, to_iolist/1]).

-record (apply, {function, input}).
-record (lambda, {name, expression}).

-define (APPLY (Function, Input), #apply{function=Function, input=Input}).
-define (LAMBDA (Name, Expression), #lambda{name=Name, expression=Expression}).

apply (Function, Input) ->
  ?APPLY (Function, Input).

lambda (Name, Expression) when is_atom (Name) ->
  ?LAMBDA (Name, Expression).

transform (X) when is_atom (X) ->
  X;

transform (?APPLY (E0, E1)) ->
  ?APPLY (transform (E0), transform (E1));

transform (?LAMBDA (X, X)) ->
  'I';

% Special case for an expanded K being there.
transform (?LAMBDA (X, ?LAMBDA (_, X))) ->
  'K';

% Special case for an expanded S being there.
transform (?LAMBDA (X, ?LAMBDA (Y, ?LAMBDA (Z,
             ?APPLY (?APPLY (X, Z), ?APPLY (Y, Z)))))) ->
  'S';

transform (?LAMBDA (X, ?LAMBDA (Y, E))) ->
  transform (?LAMBDA (X, transform (?LAMBDA (Y, E))));

transform (?LAMBDA (X, ?APPLY (E0, E1))) ->
  case E1 of
    X ->
      % eta reduction
      transform (E0);
    _ ->
      E0_ = transform (?LAMBDA (X, E0)),
      E1_ = transform (?LAMBDA (X, E1)),
      ?APPLY (?APPLY ('S', E0_), E1_) end;

transform (?LAMBDA (X, Y)) when X =/= Y ->
  ?APPLY ('K', Y).

to_binary (E) ->
  iolist_to_binary (to_iolist (E)).

to_iolist (X) when is_atom (X) ->
  io_lib:format ("~s", [X]);

to_iolist (?APPLY (E0, E1)) ->
  [<<"(">>, to_iolist (E0), <<" ">>, to_iolist (E1), <<")">>];

to_iolist (?LAMBDA (X, E)) ->
  [<<"(\\">>, to_iolist (X), <<" -> ">>, to_iolist (E), <<")">>].

% vi:set et sw=2 sts=2: