SICP Chapter #04 Examples in Erlang

-module(sicp04).
-import(scheme).
%-export([start/0]).
-compile(export_all).

print(X) ->
   io:write(X),
   io:format("~n").

start() ->
   section_4_1_4(),
   section_4_1_5(),
   section_4_1_6().


% 4.1.1 - The Metacircular Evaluator -  The Core of the Evaluator
section_4_1_1() ->
   print ("").

eval({tm_unit}, Env)                 -> {val_unit};
eval({tm_bool, Exp}, Env)            -> {val_bool, Exp};
eval({tm_int, Exp}, Env)             -> {val_int, Exp};
eval({tm_real, Exp}, Env)            -> {val_real, Exp};
eval({tm_string, Exp}, Env)          -> {val_string, Exp};
eval({tm_quoted, Exp}, Env)          -> {val_quoted, Exp};
eval({tm_if, Exp, E1, E2}, Env)      -> case eval(Exp, Env) =:= {val_bool, true} of true -> eval(E1, Env); false -> eval(E2, Env) end;
eval({tm_cond, Exp}, Env)            -> eval(cond2if(Exp), Env);
eval({tm_begin, Exp}, Env)           -> lists:foldl(fun (X, _) -> eval(X, Env) end, {val_unit}, Exp);
eval({tm_symbol, Exp}, Env)          -> lookup_variable_value(Exp, Env);
eval({tm_definition, E1, E2}, Env)   -> define_variable(E1, eval(E2, Env), Env);
eval({tm_assignment, E1, E2}, Env)   -> set_variable_value(E1, eval(E2, Env), Env);
eval({tm_lambda, Parms, Body}, Env)  -> {val_closure, Parms, Body, Env};
eval({tm_application, F, Args}, Env) -> apply_(eval(F, Env), lists:map(fun (X) -> eval(X, Env) end, Args)).

apply_({val_primitive, Sym, F}, Args) -> F(Args);
apply_({val_closure, Parameters, Body, Env}, Args) ->
   case length(Parameters) =/= length(Args) of
      true ->
         case length(Parameters) < length(Args) of
            true  -> throw({evaluator, "Too many arguments supplied"});
            false -> throw({evaluator, "Too few arguments supplied"})
         end;
      false ->
         % create the closure environment
         NewEnv = [new_dictionary()|Env],
         % pair up the parameters and arguments into a list
         Pairs = list_pair_zip(Parameters, Args),
         % push the parameters/arguments into the closure environment
         lists:map(fun ({X, Y}) -> define_variable(X, Y, NewEnv) end, Pairs),
         % evaluate the body of the closure
         X = eval(Body, NewEnv),
         % garbage collect the dictionary (note: this will kill tail-recursion)
         ets:delete(hd(NewEnv)),
         X
   end;
apply_(F, Args) -> print(F), print(Args), throw ({evaluator, "Unknown procedure type -- APPLY"}).


% 4.1.3 - The Metacircular Evaluator - Evaluator Data Structures
new_dictionary() -> ets:new(frame, [ordered_set]).

lookup_variable_value(Var, [Frame|EnclosingEnvironment]) ->
   case ets:member(Frame, Var) of
      true  ->
         L = ets:lookup(Frame, Var),
         case L of
            [{Key, Val}] -> Val
         end;
      false -> lookup_variable_value(Var, EnclosingEnvironment)
   end;
lookup_variable_value(Var, []) ->
   print (Var),
   throw ({evaluator, "Unbound variable ", Var}).

set_variable_value(Var, Val, [Frame|EnclosingEnvironment]) ->
   case ets:contains(Frame, Var) of
      true  -> ets:insert(Frame, {Var, Val}), Val;
      false -> set_variable_value(Var, Val, EnclosingEnvironment)
   end;
set_variable_value(Var, Val, []) ->
   throw ({evaluator, "Unbound variable -- SET! ", Var}).

define_variable(Var, Val, [Frame|_]) -> ets:insert(Frame, {Var, Val}), Val;
define_variable(Var, Val, []) -> throw ({evaluator, "Empty Environment ", Var}).

cond2if([{Pred, Exp}|Xs]) -> {tm_if, Pred, Exp, cond2if(Xs)};
cond2if([]) -> {tm_unit}.

list_pair_zip([H1|T1], [H2|T2]) -> [{H1, H2}|list_pair_zip(T1, T2)];
list_pair_zip([], []) -> [].


% 4.1.4 - The Metacircular Evaluator -  Running the Evaluator as a Program
eval_print(TheGlobalEnvironment, Code) ->
   Val = eval(Code, TheGlobalEnvironment),
   print (Val),
   Val.

section_4_1_4() ->
   TheGlobalEnvironment = scheme:make_global_environment(),

   eval_print(TheGlobalEnvironment, {tm_int, 123}),

   % 1 + 6.
   eval_print(TheGlobalEnvironment, {tm_application, {tm_symbol, '+'}, [{tm_int, 1}, {tm_int, 6}]}),

   % 1 + (2 * 3).
   eval_print(TheGlobalEnvironment,
      {tm_application,
         {tm_symbol, '+'},
         [
            {tm_int, 1},
            {tm_application,{tm_symbol, '*'}, [{tm_int, 2}, {tm_int, 3}]}
         ]}),

   % X = 6.
   eval_print(TheGlobalEnvironment, {tm_definition, 'X', {tm_int, 6}}),

   % (1 + X).
   eval_print(TheGlobalEnvironment,
      {tm_application,
         {tm_symbol, '+'},
         [
            {tm_int, 1},
            {tm_symbol, 'X'}
         ]}),

   % Pi = 3.14.
   eval_print(TheGlobalEnvironment, {tm_definition, 'Pi', {tm_real, 3.14}}),

   % 27.0 / (13.0 - Pi).
   eval_print(TheGlobalEnvironment,
      {tm_application,
         {tm_symbol, '/'},
         [
            {tm_real, 27.0},
            {tm_application,
               {tm_symbol, '-'},
               [
                  {tm_real, 13.0},
                  {tm_symbol, 'Pi'}
               ]}
         ]}),

   % square() -> fun (X) -> X * X end.
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'square',
         {tm_lambda,
            ['X'],
            {tm_application,
               {tm_symbol, '*'},
               [
                  {tm_symbol, 'X'},
                  {tm_symbol, 'X'}
               ]}}}),

   % Z = square(5.0).
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'Z',
         {tm_application,
            {tm_symbol, 'square'},
            [
               {tm_real, 5.0}
            ]}}),

   % append(Xs, Ys) ->
   %    case Xs =:= [] of
   %       true -> Ys;
   %       false -> [hd(Xs) | append(tl(Xs), Ys)
   %    end.
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'append',
         {tm_lambda,
            ['Xs', 'Ys'],
            {tm_if,
               {tm_application, {tm_symbol, '='}, [{tm_symbol, 'Xs'}, {tm_unit}]},
               {tm_symbol, 'Ys'},
               {tm_application,
                  {tm_symbol, 'cons'},
                  [
                     {tm_application, {tm_symbol, 'car'}, [{tm_symbol, 'Xs'}]},
                     {tm_application,
                        {tm_symbol, 'append'},
                        [
                           {tm_application, {tm_symbol, 'cdr'}, [{tm_symbol, 'Xs'}]},
                           {tm_symbol, 'Ys'}
                        ]}
                  ]}}}}),

   % Xs = [a, b, c].
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'Xs',
         {tm_application,
            {tm_symbol, 'cons'},
            [
               {tm_string, a},
               {tm_application,
                  {tm_symbol, 'cons'},
                  [
                     {tm_string, b},
                     {tm_application, {tm_symbol, 'cons'}, [{tm_string, c}, {tm_unit}]}
                  ]}
            ]}}),

   % Ys = [d, e, f].
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'Ys',
         {tm_application,
            {tm_symbol, 'cons'},
            [
               {tm_string, d},
               {tm_application,
                  {tm_symbol, 'cons'},
                  [
                     {tm_string, e},
                     {tm_application, {tm_symbol, 'cons'}, [{tm_string, f}, {tm_unit}]}
                  ]}
            ]}}),

   % Zs = append(Xs, Ys).
   eval_print(TheGlobalEnvironment, {tm_application, {tm_symbol, 'append'}, [{tm_symbol, 'Xs'}, {tm_symbol, 'Ys'}]}),

   % if
   %    X > 0 -> X;
   %    X == 0 -> print('zero'), 0;
   %    true -> -X
   % end.
   eval_print(TheGlobalEnvironment,
      {tm_cond,
         [
            {{tm_application, {tm_symbol, '>'}, [{tm_symbol, 'X'}, {tm_int, 0}]}, {tm_symbol, 'X'}},
            {
               {tm_application, {tm_symbol, '='}, [{tm_symbol, 'X'}, {tm_int, 0}]},
               {tm_begin,
                  [
                     {tm_application, {tm_symbol, 'display'}, [{tm_string, "zero"}]},
                     {tm_int, 0}
                  ]
               }
            },
            {{tm_bool, true}, {tm_application, {tm_symbol, '-'}, [{tm_symbol, 'X'}]}}
         ]}),

   % case X > 0 of
   %    true  -> X;
   %    false ->
   %       case X =:= 0 of
   %          true  -> print("zero"), 0;
   %          false -> -X
   %       end
   % end.
   eval_print(TheGlobalEnvironment,
      {tm_if,
         {tm_application, {tm_symbol, '>'}, [{tm_symbol, 'X'}, {tm_int, 0}]},
         {tm_symbol, 'X'},
         {tm_if,
            {tm_application, {tm_symbol, '='}, [{tm_symbol, 'X'}, {tm_int, 0}]},
            {tm_begin,
               [
                  {tm_application, {tm_symbol, 'display'}, [{tm_string, "zero"}]},
                  {tm_int, 0}
               ]},
            {tm_application, {tm_symbol, '-'}, [{tm_symbol, 'X'}]}}}),

   % begin
   %    X = 3,
   %    Y = X + 2,
   %    Z = X + Y + 5,
   %    x * z
   % end.
   eval_print(TheGlobalEnvironment,
      {tm_application,
         {tm_lambda,
            [],
            {tm_begin,
               [
                  {tm_definition, 'X', {tm_int, 3}},
                  {tm_definition, 'Y', {tm_application, {tm_symbol, '+'}, [{tm_symbol, 'X'}, {tm_int, 2}]}},
                  {tm_definition,
                     'Z',
                     {tm_application,
                        {tm_symbol, '+'},
                        [
                           {tm_symbol, 'X'},
                           {tm_application, {tm_symbol, '+'}, [{tm_symbol, 'Y'}, {tm_int, 5}]}
                        ]}},
                  {tm_application, {tm_symbol, '*'}, [{tm_symbol, 'X'}, {tm_symbol, 'Z'}]}
               ]}},
         []}),

   % The "and" is not working properly for val.
   % The answer given is 5, but it should be 3.
   % X = 1.
   % begin
   %    X = 3
   %    Y = X + 2
   %    Y
   % end.
   eval_print(TheGlobalEnvironment, {tm_definition, 'X', {tm_int, 1}}),
   eval_print(TheGlobalEnvironment,
      {tm_application,
         {tm_lambda,
            [],
            {tm_begin,
               [
                  {tm_definition, 'X', {tm_int, 3}},
                  {tm_definition, 'Y', {tm_application, {tm_symbol, '+'}, [{tm_symbol, 'X'}, {tm_int, 2}]}},
                  {tm_symbol, 'Y'}
               ]}},
         []}),

   % An extension to the eval function should address this problem:
   %  ((let? exp) (m-eval (let->combination exp) env))
   %  (define (let->combination let-exp)
   %    (let ((names (let-bound-variables let-exp))
   %          (values (let-values let-exp))
   %          (body (let-body let-exp)))
   %      (cons (list 'lambda names body) values)))

   % fib(N) ->
   %    FibIter =
   %       fun (Self, A, B, Count) ->
   %          case Count of
   %             0 -> B;
   %             true -> Self(Self, A+B, A, Count-1)
   %          end,
   %    FibIter(FibIter, 1, 0, N).
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'fib',
         {tm_lambda,
            ['N'],
            {tm_begin,
               [
                  {tm_definition,
                     'FibIter',
                     {tm_lambda,
                        ['A', 'B', 'Count'],
                        {tm_if,
                           {tm_application, {tm_symbol, '='}, [{tm_symbol, 'Count'}, {tm_int, 0}]},
                           {tm_symbol, 'B'},
                           {tm_application,
                              {tm_symbol, 'FibIter'},
                              [
                                 {tm_application, {tm_symbol, '+'}, [{tm_symbol, 'A'}, {tm_symbol, 'B'}]},
                                 {tm_symbol, 'A'},
                                 {tm_application, {tm_symbol, '-'}, [{tm_symbol, 'Count'}, {tm_int, 1}]}
                              ]}}}},
                  {tm_application, {tm_symbol, 'FibIter'}, [{tm_int, 1}, {tm_int, 0}, {tm_symbol, 'N'}]}
               ]}}}),

   % fib(10).
   eval_print(TheGlobalEnvironment, {tm_application, {tm_symbol, 'fib'}, [{tm_int, 10}]}).


% 4.1.5 - The Metacircular Evaluator - Data as Programs
section_4_1_5() ->
   TheGlobalEnvironment = scheme:make_global_environment(),

   % factorial(N) ->
   %    case N =:= 1 of
   %       true  -> 1;
   %       false -> N * factorial(N-1)
   %    end.
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'factorial',
         {tm_lambda,
            ['N'],
            {tm_if,
               {tm_application, {tm_symbol, '='}, [{tm_symbol, 'N'}, {tm_int, 1}]},
               {tm_int, 1},
               {tm_application,
                  {tm_symbol, '*'},
                  [
                     {tm_symbol, 'N'},
                     {tm_application,
                        {tm_symbol, 'factorial'},
                        [
                           {tm_application, {tm_symbol, '-'}, [{tm_symbol, 'N'}, {tm_int, 1}]}
                        ]}
                  ]}}}}),

   % factorial(5}
   eval_print(TheGlobalEnvironment, {tm_application, {tm_symbol, 'factorial'}, [{tm_int, 5}]}).

   % Exercise 4.15
run_forever() -> run_forever().

halts(P, Q) -> true.

try_(P) ->
   case halts(P, P) of
      true  -> run_forever();
      false -> throw({halted})
   end.


% 4.1.6 - The Metacircular Evaluator - Internal Definitions
section_4_1_6() ->
   TheGlobalEnvironment = scheme:make_global_environment(),

   % f(X) ->
   %    IsEven =
   %       fun (Self, IsOdd, 0) -> true;
   %           (Self, IsOdd, N) -> IsOdd(IsOdd, Self, N-1)
   %       end,
   %    IsOdd =
   %       fun (Self, IsEven, 0) -> false;
   %           (Self, IsEven, N) -> IsEven(IsEven, Self, N-1)
   %       end,
   %    ... rest of body of f ...,
   %    IsEven(IsEven, IsOdd, X).
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'f',
         {tm_lambda,
            ['X'],
            {tm_begin,
               [
                  {tm_definition,
                     'IsEven',
                     {tm_lambda,
                        ['N'],
                        {tm_if,
                           {tm_application, {tm_symbol, '='}, [{tm_symbol, 'N'}, {tm_int, 0}]},
                           {tm_bool, true},
                           {tm_application,
                              {tm_symbol, 'IsOdd'},
                              [{tm_application, {tm_symbol, '-'}, [{tm_symbol, 'N'}, {tm_int, 1}]}]
                           }
                        }
                     }
                  },
                  {tm_definition,
                     'IsOdd',
                     {tm_lambda,
                        ['N'],
                        {tm_if,
                           {tm_application, {tm_symbol, '='}, [{tm_symbol, 'N'}, {tm_int, 0}]},
                           {tm_bool, false},
                           {tm_application,
                              {tm_symbol, 'IsEven'},
                              [{tm_application, {tm_symbol, '-'}, [{tm_symbol, 'N'}, {tm_int, 1}]}]
                           }
                        }
                     }
                  },
                  {tm_application, {tm_symbol, 'IsEven'}, [{tm_symbol, 'X'}]}
               ]
            }
         }
      }),

   % f(3).
   eval_print(TheGlobalEnvironment, {tm_application, {tm_symbol, 'f'}, [{tm_int, 3}]}),

   % Exercise 4.19
   % begin
   %    A = 1,
   %    F =
   %       fun (X) ->
   %          B = A + X,
   %          A = 5,
   %          A + B
   %       end,
   %    F(10)
   % end.
   eval_print(TheGlobalEnvironment,
      {tm_begin,
         [
            {tm_definition, 'A', {tm_int, 1}},
            {tm_definition,
               'F',
               {tm_lambda,
                  ['X'],
                  {tm_begin,
                     [
                        {tm_definition, 'B', {tm_application, {tm_symbol, '+'}, [{tm_symbol, 'A'}, {tm_symbol, 'X'}]}},
                        {tm_definition, 'A', {tm_int, 5}},
                        {tm_application, {tm_symbol, '+'}, [{tm_symbol, 'A'}, {tm_symbol, 'B'}]}
                     ]
                  }
               }
            },
            {tm_application, {tm_symbol, 'F'}, [{tm_int, 10}]}
         ]
      }),

   % factorial(N) ->
   %    case N =:= 1 of
   %       true  -> 1;
   %       false -> N * factorial(N-1)
   %    end.
   eval_print(TheGlobalEnvironment,
      {tm_definition,
         'factorial',
         {tm_lambda,
            ['N'],
            {tm_if,
               {tm_application, {tm_symbol, '='}, [{tm_symbol, 'N'}, {tm_int, 1}]},
               {tm_int, 1},
               {tm_application,
                  {tm_symbol, '*'},
                  [
                     {tm_symbol, 'N'},
                     {tm_application,
                        {tm_symbol, 'factorial'},
                        [
                           {tm_application, {tm_symbol, '-'}, [{tm_symbol, 'N'}, {tm_int, 1}]}
                        ]}
                  ]}}}}),

% Exercise 4.21
% Y Combinator
Y =
   (fun (N) ->
       fun (Fact) -> Fact(Fact(N)) end,
       fun (Ft, 1) -> 1;
           (Ft, K) -> K * Ft(Ft(K-1))
       end
    end)(10),
    print (Y),
%   _ = {EvalPrint
%      tm_application(
%         tm_application(
%            tm_lambda(['Fact'] tm_application(tm_symbol('Fact') [tm_symbol('Fact')]))
%            [
%               tm_lambda(
%                  ['Ft']
%                  tm_lambda(
%                     ['K']
%                     tm_if(
%                        tm_application(tm_symbol('=') [tm_symbol('K') tm_int(1)])
%                        tm_int(1)
%                        tm_application(
%                           tm_symbol('*')
%                           [
%                              tm_symbol('K')
%                              tm_application(
%                                 tm_application(tm_symbol('Ft') [tm_symbol('Ft')])
%                                 [tm_application(tm_symbol('-') [tm_symbol('K') tm_int(1)])])
%                           ]))))
%            ])
%         [tm_int(10)])}
   print ("").

y = fun (N) ->
       fun (Fact) -> Fact(Fact(N)) end,
       fun (Ft, 1) -> 1;
           (Ft, K) -> K * Ft(Ft(K-1))
       end
    end,