SICP Chapter #03 Examples in Erlang
-module(sicp03).
%-export([start/0]).
-compile(export_all).
print(X) ->
io:write(X),
io:format("~n").
start() ->
section_3_1_1(),
section_3_1_2(),
section_3_1_3(),
section_3_2_1(),
section_3_2_2(),
section_3_2_3(),
section_3_2_4(),
section_3_3_1(),
section_3_3_2(),
section_3_3_3(),
section_3_3_4(),
section_3_3_5(),
section_3_4_1(),
section_3_4_2(),
section_3_5_1().
% Functions used to mimic mutable cells
new_cell(X) -> spawn(fun() -> cell(X) end).
cell(Value) ->
receive
{set, NewValue} -> cell(NewValue);
{get, Pid} -> Pid!{return, Value}, cell(Value);
{dispose} -> {}
end.
set_cell(Cell, NewValue) -> Cell!{set, NewValue}.
get_cell(Cell) ->
Cell!{get, self()},
receive
{return, Value} -> Value
end.
dispose_cell(Cell) -> Cell!{dispose}.
% Functions defined in previous chapters
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).
square(X) -> X * X.
average(X, Y) -> (X + Y) / 2.
has_no_divisors(_, 1) -> true;
has_no_divisors(N, C) ->
case N rem C =:= 0 of
true -> false;
false -> has_no_divisors(N, C-1)
end.
is_prime(N) -> has_no_divisors(N, N-1).
enumerate_interval(Low, High) when Low > High -> [];
enumerate_interval(Low, High) -> [Low|enumerate_interval(Low+1, High)].
% 3.1.1 - Assignment and Local State - Local State Variables
-record(account_record, {withdraw, deposit, balance}).
section_3_1_1() ->
Balance = new_cell(100),
withdraw(Balance, 25),
withdraw(Balance, 25),
try withdraw(Balance, 60) catch {insufficientFunds, _} -> skip end,
withdraw(Balance, 15),
print (get_cell(Balance)),
W1 = make_withdraw(100),
W2 = make_withdraw(100),
W1(50),
W2(70),
try W2(40) catch {insufficientFunds, _} -> skip end,
W1(40),
Acc = make_account(100),
(Acc#account_record.withdraw)(50),
try (Acc#account_record.withdraw)(60) catch {insufficientFunds, _} -> skip end,
(Acc#account_record.deposit)(40),
(Acc#account_record.withdraw)(60),
print ((Acc#account_record.balance)()),
Acc2 = make_account(100).
withdraw(Balance, Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end.
new_withdraw() ->
Balance = new_cell(100),
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end.
make_withdraw(Initial_Balance) ->
Balance = new_cell(Initial_Balance),
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end.
make_account(Initial_Balance) ->
Balance = new_cell(Initial_Balance),
Withdraw =
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end,
Deposit =
fun (Amount) ->
set_cell(Balance, get_cell(Balance) + Amount)
end,
GetBalance =
fun () ->
get_cell(Balance)
end,
#account_record{withdraw = Withdraw, deposit = Deposit, balance = GetBalance}.
% 3.1.2 - Assignment and Local State - The Benefits of Introducing Assignment
section_3_1_2() ->
print (estimate_pi(10)).
rand_update(X) ->
A = 27,
B = 26,
M = 127,
(A*X + B) rem M.
rand(Random) ->
X = get_cell(Random),
set_cell(Random, rand_update(X)),
X.
cesaro_test() ->
Random = new_cell(7),
fun () ->
gcd(rand(Random), rand(Random)) == 1
end.
monte_carlo(Trials, Experiment) ->
Iter =
fun (Self, 0, TrialsPassed) -> TrialsPassed / Trials;
(Self, TrialsRemaining, TrialsPassed) ->
case (Experiment()) of
true -> Self(Self, TrialsRemaining-1, TrialsPassed+1);
false -> Self(Self, TrialsRemaining-1, TrialsPassed)
end
end,
Iter(Iter, Trials, 0).
estimate_pi(Trials) ->
math:sqrt(6.0 / monte_carlo(Trials, cesaro_test())).
% second version (no assignment)
random_gcd_test(Trials, InitialX) ->
Iter =
fun (Self, 0, TrialsPassed, _) -> TrialsPassed / Trials;
(Self, TrialsRemaining, TrialsPassed, X) ->
X1 = rand_update(X),
X2 = rand_update(X1),
case gcd(X1, X2) == 1 of
true -> Self(Self, TrialsRemaining-1, TrialsPassed+1, X2);
false -> Self(Self, TrialsRemaining-1, TrialsPassed, X2)
end
end,
Iter(Iter, Trials, 0, InitialX).
% Exercise 3.6
% exercise left to reader to define appropriate functions
% random_in_range(Low High) ->
% Range = High - Low,
% Low + randomx(Range).
% 3.1.3 - Assignment and Local State - The Cost of Introducing Assignment
section_3_1_3() ->
W = make_simplified_withdraw(new_cell(25)),
W(20),
W(10),
D = make_decrementer(new_cell(25)),
print (D(20)),
print (D(10)),
print ((make_decrementer(new_cell(25)))(20)),
print ((fun (Amount) -> 25 - Amount end)(20)),
print (25 - 20),
print ((make_simplified_withdraw(new_cell(25)))(20)),
% Sameness and change
D1 = make_decrementer(new_cell(25)),
D2 = make_decrementer(new_cell(25)),
W3 = make_simplified_withdraw(new_cell(25)),
W4 = make_simplified_withdraw(new_cell(25)),
print (W3(20)),
print (W3(20)),
print (W4(20)),
PeterAcc = make_account(100),
PaulAcc = make_account(100),
PeterAcc1 = make_account(100),
PaulAcc1 = PeterAcc1,
print (factorial1(5)).
make_simplified_withdraw(Balance) ->
fun (Amount) ->
set_cell(Balance, get_cell(Balance) - Amount),
get_cell(Balance)
end.
make_decrementer(Balance) ->
fun (Amount) ->
set_cell(Balance, get_cell(Balance) - Amount),
get_cell(Balance)
end.
% Pitfalls of imperative programming
factorial(N) ->
Iter =
fun (Self, Product, Counter) ->
case Counter > N of
true -> Product;
false -> Self(Self, Counter*Product, Counter+1)
end
end,
Iter(Iter, 1, 1).
factorial1(N) ->
Product = new_cell(1),
Counter = new_cell(1),
Iter =
fun (Self) ->
case get_cell(Counter) > N of
true -> get_cell(Product);
false ->
set_cell(Product, get_cell(Counter) * get_cell(Product)),
set_cell(Counter, get_cell(Counter) + 1),
Self(Self)
end
end,
Iter(Iter).
% 3.2.1 - The Environment Model of Evaluation - The Rules for Evaluation
section_3_2_1() ->
Square = fun (X) -> X * X end.
% Same as above
% square(X) -> X * X.
% 3.2.2 - The Environment Model of Evaluation - Applying Simple Procedures
section_3_2_2() ->
print (sum_of_squares(5, 6)),
% Exercise 3.9
print (factorial2(5)),
print (factorial3(5)).
% square(X) -> X * X.
sum_of_squares(X, Y) ->
square(X) + square(Y).
f (A) ->
sum_of_squares(A+1, A*2).
% Exercise 3.9
factorial2(1) -> 1;
factorial2(N) -> N * factorial2(N-1).
fact_iter(Product, Counter, MaxCount) ->
case Counter > MaxCount of
true -> Product;
false -> fact_iter(Counter*Product, Counter+1, MaxCount)
end.
factorial3(N) -> fact_iter(1, 1, N).
% 3.2.3 - The Environment Model of Evaluation - Frames as Repository of Local State
section_3_2_3() ->
W5 = make_withdraw1(new_cell(100)),
W5(50),
W6 = make_withdraw1(new_cell(100)),
% Exercise 3.10
W7 = make_withdraw2(100),
W7(50),
W8 = make_withdraw2(100).
make_withdraw1(Balance) ->
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end.
% Exercise 3.10
make_withdraw2(InitialAmount) ->
Balance = new_cell(InitialAmount),
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end.
% 3.2.4 - The Environment Model of Evaluation - Internal Definitions
section_3_2_4() ->
% Exercise 3.11
Acc3 = make_account1(50),
(Acc3#account_record.deposit)(40),
(Acc3#account_record.withdraw)(60),
Acc4 = make_account1(100).
% same as in section 1.1.8
sqrt_3(X) ->
Good_Enough =
fun (Guess) ->
abs(square(Guess) - X) < 0.001
end,
Improve =
fun (Guess) ->
average(Guess, X / Guess)
end,
Sqrt_Iter =
fun (Self, Guess) ->
case (Good_Enough(Guess)) of
true -> Guess;
false -> Self(Self, Improve(Guess))
end
end,
Sqrt_Iter(Sqrt_Iter, 1.0).
% Exercise 3.11
make_account1(InitBalance) ->
Balance = new_cell(InitBalance),
Withdraw =
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end,
Deposit =
fun (Amount) ->
set_cell(Balance, get_cell(Balance) + Amount)
end,
GetBalance =
fun () ->
get_cell(Balance)
end,
#account_record{withdraw = Withdraw, deposit = Deposit, balance = GetBalance}.
% 3.3.1 - Modeling with Mutable Data - Mutable List Structure
section_3_3_1() ->
% Exercise 3.12
X = mlist([a, b]),
Y = mlist([c, d]),
Z = mappend1(X, Y),
W = mappend1(X, Y),
print (listm(W)),
print (listm(X)),
% Exercise 3.13
Zm = make_cycle(mlist([a, b])),
print (listm(Zm)),
% Exercise 3.14
Vm = mlist([a, b, c, d]),
Wm = mystery(Vm),
% Sharing and identity
% X = mlist([a, b]),
Z1 = mlist([X, X]),
Z2 = mcons(mlist([a, b]), mlist([a, b])),
print (listm(Z1)),
set_to_wow(Z1),
print (listm(Z2)),
set_to_wow(Z2),
% Exercise 3.20
X3 = mcons2(1, 2),
Z3 = mcons2(X3, X3),
set_mcar2(mcdr2(Z3), 17),
print (mcar2(X3)).
mcons(X, Y) -> {new_cell(X), new_cell(Y)}.
mcar({H, _}) -> get_cell(H).
mcdr({_, T}) -> get_cell(T).
set_mcar({H, _}, X) -> set_cell(H, X).
set_mcdr({_, T}, Y) -> set_cell(T, Y).
% Exercise 3.12
mappend([], Ys) -> Ys;
mappend({H, T}, Ys) -> mcons(get_cell(H), mappend(get_cell(T), Ys)).
last_pair(Xs) ->
case mcdr(Xs) of
[] -> Xs;
T -> last_pair(T)
end.
mappend1(Xs, Ys) ->
set_mcdr(last_pair(Xs), Ys),
Xs.
mlist(Xs) ->
lists:foldr(fun (V, B) -> mcons(V, B) end, [], Xs).
listm(_, 0) -> ['...'];
listm([], _) -> [];
listm({H, T}, N) ->
X = get_cell(H),
case X of
{A, B} -> [listm(X)|listm(get_cell(T), N-1)];
_ -> [X|listm(get_cell(T), N-1)]
end.
listm(Xs) -> listm(Xs, 25).
% Exercise 3.13
make_cycle(Xs) ->
set_mcdr(last_pair(Xs), Xs),
Xs.
% Exercise 3.14
mystery(X) ->
Loop =
fun(Self, [], Y) -> Y;
(Self, X, Y) ->
Temp = mcdr(X),
set_mcdr(X, Y),
Self(Self, Temp, X)
end,
Loop(Loop, X, new_cell([])).
set_to_wow(X) ->
set_mcar(mcar(X), "Wow").
% Exercise 3.16
is_pair({_, _}) -> true;
is_pair(_) -> false.
count_pairs(X) ->
case not(is_pair(X)) of
true -> 0;
false -> count_pairs(mcar(X)) + count_pairs(mcdr(X)) + 1
end.
% Mutation as assignment
mcons1(H, T) ->
fun (mcar) -> H;
(mcdr) -> T
end.
mcar1(Z) -> Z(mcar).
mcdr1(Z) -> Z(mcdr).
mcons2(H, T) ->
X = new_cell(H),
Y = new_cell(T),
fun (mcar) -> get_cell(X);
(mcdr) -> get_cell(Y);
(set_mcar) -> fun (V) -> set_cell(X, V) end;
(set_mcdr) -> fun (V) -> set_cell(Y, V) end
end.
mcar2(Z) -> Z(mcar).
mcdr2(Z) -> Z(mcdr).
set_mcar2(Z, V) -> (Z(set_mcar))(V).
set_mcdr2(Z, V) -> (Z(set_mcdr))(V).
% 3.3.2 - Modeling with Mutable Data - Local State Variables
section_3_3_2() ->
% Exercise 3.21
Q1 = make_queue(),
insert_queue(Q1, a),
insert_queue(Q1, b),
print (delete_queue(Q1)),
print (delete_queue(Q1)).
front_ptr({H, T}) -> H.
rear_ptr({H, T}) -> T.
set_mcar3({H, T}, Item) -> set_cell(H, Item).
set_mcdr3({H, T}, Item) -> set_cell(T, Item).
set_front_ptr(Q, Item) -> set_mcar3(Q, Item).
set_rear_ptr(Q, Item) -> set_mcdr3(Q, Item).
is_empty_queue(Q) ->
case get_cell(front_ptr(Q)) =:= [] of
true -> true;
false -> false
end.
make_queue() ->
N = [],
{new_cell(N), new_cell(N)}.
front_queue(Q) ->
case get_cell(front_ptr(Q)) of
{A, _} -> A
end.
insert_queue(Q, Item) ->
N = {Item, new_cell([])},
case get_cell(front_ptr(Q)) of
[] ->
set_front_ptr(Q, N),
set_rear_ptr(Q, N);
_ ->
case get_cell(rear_ptr(Q)) of
{_, Nxt} ->
set_cell(Nxt, N),
set_rear_ptr(Q, N)
end
end.
delete_queue(Q) ->
case get_cell(front_ptr(Q)) of
{_, Nxt} ->
Item = front_queue(Q),
set_front_ptr(Q, get_cell(Nxt)),
Item
end.
% 3.3.3 - Modeling with Mutable Data - Representing Tables
section_3_3_3() ->
D3 = make_table(),
insert(abc, 123, D3),
print (lookup(abc, D3)),
D4 = make_table(),
insert2(abc, 123, 12.3, D4),
print (lookup2(abc, 123, D4)),
Dictionary2 = make_dictionary2(),
put_dictionary2(Dictionary2, abc, 123, 12.3),
print (get_dictionary2(Dictionary2, abc, 123)),
Fib_Table = make_table(),
print (memo_fib(Fib_Table, 10)).
assoc(Key, Rec) ->
case Rec of
{tab, Xs} -> assoc(Key, get_cell(Xs));
{leaf} -> {leaf};
{tree, K, V, Xs} when Key =:= K -> Rec;
{tree, K, V, Xs} -> assoc(Key, get_cell(Xs))
end.
lookup(Key, Table) ->
Record = assoc(Key, Table),
case Record of
{tree, K, V, _} -> {some, get_cell(V)};
_ -> {none}
end.
insert(Key, Value, Table) ->
Record = assoc(Key, Table),
case Record of
{tree, K, V, _} -> set_cell(V, Value);
_ ->
case Table of
{tab, Xs} -> set_cell(Xs, {tree, Key, new_cell(Value), new_cell(get_cell(Xs))})
end
end.
make_table() -> {tab, new_cell({leaf})}.
% two-dimensional
lookup2(Key1, Key2, Table) ->
Record = assoc(Key1, Table),
case Record of
{tree, K1, V, _} -> lookup(Key2, get_cell(V));
_ -> {none}
end.
insert2(Key1, Key2, Value, Table) ->
Record = assoc(Key1, Table),
case Record of
{tree, K, V, _} -> insert(Key2, Value, get_cell(V));
_ ->
case Table of
{tab, Xs} ->
NewTab = make_table(),
insert(Key2, Value, NewTab),
set_cell(Xs, {tree, Key1, new_cell(NewTab), new_cell(get_cell(Xs))})
end
end.
% local tables
make_dictionary2() -> spawn(fun() -> dictionary2(make_table()) end).
dictionary2(Table) ->
receive
{get, Pid, Key1, Key2} ->
Record = assoc(Key1, Table),
case Record of
{tree, K1, V, _} -> Pid!{return, lookup(Key2, get_cell(V))};
_ -> Pid!{return, none}
end,
dictionary2(Table);
{put, Key1, Key2, Value} ->
Record = assoc(Key1, Table),
case Record of
{tree, K, V, _} -> insert(Key2, Value, get_cell(V));
_ ->
case Table of
{tab, Xs} ->
NewTab = make_table(),
insert(Key2, Value, NewTab),
set_cell(Xs, {tree, Key1, new_cell(NewTab), new_cell(get_cell(Xs))})
end
end,
dictionary2(Table);
{dispose} -> {}
end.
put_dictionary2(Dictionary2, Key1, Key2, Value) -> Dictionary2!{put, Key1, Key2, Value}.
get_dictionary2(Dictionary2, Key1, Key2) ->
Dictionary2!{get, self(), Key1, Key2},
receive
{return, Value} -> Value
end.
dispose_dictionary2(Dictionary2) -> Dictionary2!{dispose}.
% Exercise 3.27
fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
memoize(Table, F, X) ->
PreviouslyComputedResult = lookup(X, Table),
case PreviouslyComputedResult of
{some, Item} -> Item;
{none} ->
Result = F(X),
insert(X, Result, Table),
Result
end.
memo_fib(Table, N) ->
Fib =
fun (0) -> 0;
(1) -> 1;
(N) -> memo_fib(Table, N-1) + memo_fib(Table, N-2)
end,
memoize(Table, Fib, N).
% 3.3.4 - Modeling with Mutable Data - A Simulator for Digital Circuits
-record(wire_record, {get_signal, set_signal, add_action}).
section_3_3_4() ->
Aw = make_wire(),
Bw = make_wire(),
Cw = make_wire(),
Dw = make_wire(),
Ew = make_wire(),
Sw = make_wire(),
or_gate_1(Aw, Bw, Dw),
and_gate(Aw, Bw, Cw),
inverter(Cw, Ew),
and_gate(Dw, Ew, Sw),
% Sample simulation
Input1 = make_wire(),
Input2 = make_wire(),
Sum = make_wire(),
Carry = make_wire(),
probe(sum, Sum),
probe(carry, Carry),
half_adder(Input1, Input2, Sum, Carry),
set_signal(Input1, hi),
propagate(),
set_signal(Input2, hi),
propagate().
call_each([]) -> {};
call_each([H|T]) ->
H(),
call_each(T).
get_signal(Wire) -> (Wire#wire_record.get_signal)().
set_signal(Wire, NewValue) -> (Wire#wire_record.set_signal)(NewValue).
add_action(Wire, ActionProcedure) -> (Wire#wire_record.add_action)(ActionProcedure).
make_wire() ->
SignalValue = new_cell(lo),
ActionProcedures = new_cell([]),
SetMySignal =
fun (NewValue) ->
case not(get_cell(SignalValue) =:= NewValue) of
true ->
set_cell(SignalValue, NewValue),
call_each(get_cell(ActionProcedures));
false -> {}
end
end,
AcceptActionProcedure =
fun (Proc) ->
set_cell(ActionProcedures, [Proc | get_cell(ActionProcedures)])
end,
GetSignal =
fun () ->
get_cell(SignalValue)
end,
#wire_record{get_signal = GetSignal, set_signal = SetMySignal, add_action = AcceptActionProcedure}.
logical_not(lo) -> hi;
logical_not(hi) -> lo.
logical_and(hi, hi) -> hi;
logical_and(_, _) -> lo.
logical_or(lo, lo) -> lo;
logical_or(_, _) -> hi.
make_time_segment(Time, Queue) ->
{time_segment, new_cell(Time), Queue}.
segment_time({time_segment, Time, Queue}) -> Time.
segment_queue({time_segment, Time, Queue}) -> Queue.
% agenda is a list of time segments
make_agenda() -> mcons(make_time_segment(0, make_queue()), []).
current_time(Agenda) -> get_cell(segment_time(mcar(Agenda))).
current_time_ref(Agenda) -> segment_time(mcar(Agenda)).
set_current_time(Agenda, Time) -> set_cell(current_time_ref(Agenda), Time).
segments(Agenda) -> mcdr(Agenda).
set_segments(Agenda, Segments) -> set_mcdr(Agenda, Segments).
first_segment(Agenda) -> mcar(segments(Agenda)).
rest_segments(Agenda) -> mcdr(segments(Agenda)).
empty_agenda(Agenda) -> segments(Agenda) =:= [].
first_agenda_item(Agenda) ->
case empty_agenda(Agenda) of
true -> throw({agenda, "Agenda is empty -- FIRST-AGENDA-ITEM"});
false ->
FirstSeg = first_segment(Agenda),
set_current_time(Agenda, get_cell(segment_time(FirstSeg))),
front_queue(segment_queue(FirstSeg))
end.
remove_first_agendaitem(Agenda) ->
Q = segment_queue(first_segment(Agenda)),
delete_queue(Q),
case is_empty_queue(Q) of
true -> set_segments(Agenda, rest_segments(Agenda));
false -> {}
end.
add_to_agenda(Time, Action, Agenda) ->
BelongsBefore =
fun (Segments) ->
case Segments =:= [] of
true -> true;
false -> Time < get_cell(segment_time(mcar(Segments)))
end
end,
MakeNewTimeSegment =
fun (Time, Action) ->
Q = make_queue(),
insert_queue(Q, Action),
make_time_segment(Time, Q)
end,
AddToSegments =
fun (Self, Segments) ->
case get_cell(segment_time(mcar(Segments))) =:= Time of
true -> insert_queue(segment_queue(mcar(Segments)), Action);
false ->
Rest = mcdr(Segments),
case BelongsBefore(Rest) of
true -> set_mcdr(Segments, mcons(MakeNewTimeSegment(Time, Action), mcdr(Segments)));
false -> Self(Self, Rest)
end
end
end,
SegmentsX = segments(Agenda),
case BelongsBefore(SegmentsX) of
true -> set_segments(Agenda, mcons(MakeNewTimeSegment(Time, Action), SegmentsX));
false -> AddToSegments(AddToSegments, SegmentsX)
end.
% Note: erlang discourages use of process dictionary. But it'll do for now.
the_agenda() ->
case get(the_agenda) =:= undefined of
true ->
put(the_agenda, make_agenda()),
get(the_agenda);
false -> get(the_agenda)
end.
after_delay(Delay, Action) ->
add_to_agenda(Delay + current_time(the_agenda()), Action, the_agenda()).
inverter_delay() -> 2.
and_gate_delay() -> 3.
or_gate_delay() -> 5.
inverter(Input, Output) ->
NewValue = logical_not(get_signal(Input)),
InvertInput =
fun () ->
after_delay(inverter_delay(), fun () -> set_signal(Output, NewValue) end)
end,
add_action(Input, InvertInput).
and_gate(A1, A2, Output) ->
NewValue = logical_and(get_signal(A1), get_signal(A2)),
AndActionProcedure =
fun () ->
after_delay(and_gate_delay(), fun () -> set_signal(Output, NewValue) end)
end,
add_action(A1, AndActionProcedure),
add_action(A2, AndActionProcedure).
or_gate(A1, A2, Output) ->
NewValue = logical_or(get_signal(A1), get_signal(A2)),
OrActionProcedure =
fun () ->
after_delay(or_gate_delay(), fun () -> set_signal(Output, NewValue) end)
end,
add_action(A1, OrActionProcedure),
add_action(A2, OrActionProcedure).
half_adder(A, B, S, C) ->
D = make_wire(),
E = make_wire(),
or_gate(A, B, D),
and_gate(A, B, C),
inverter(C, E),
and_gate(D, E, S).
or_gate_1(A1, A2, Output) ->
B = make_wire(),
C = make_wire(),
D = make_wire(),
inverter(A1, B),
inverter(A2, C),
and_gate(B, C, D),
inverter(D, Output).
full_adder(A, B, Cin, Sum, Cout) ->
S = make_wire(),
C1 = make_wire(),
C2 = make_wire(),
half_adder(B, Cin, S, C1),
half_adder(A, S, Sum, C2),
or_gate(C1, C2, Cout).
propagate() ->
case empty_agenda(the_agenda()) of
true -> {};
false ->
FirstItem = first_agenda_item(the_agenda()),
FirstItem(),
remove_first_agendaitem(the_agenda()),
propagate()
end.
probe(Name, Wire) ->
add_action(
Wire,
fun () ->
io:write(Name),
io:format(" "),
io:write(current_time(the_agenda)),
io:format(" NewValue = "),
io:write(get_signal(Wire)),
io:format("~n")
end).
% Exercise 3.31
% accept_action_procedure_1(Proc) ->
% set_cell(ActionProcedures, [Proc|ActionProcedures]).
% 3.3.5 - Modeling with Mutable Data - Propagation of Constraints
-record(propagator_record, {process_new_value, process_forget_value}).
-record(connector_record, {has_value, get_value, set_value, forget_value, connect}).
section_3_3_5() ->
User = #propagator_record{process_new_value = fun () -> {} end,
process_forget_value = fun () -> {} end},
Cx = make_connector(),
Fx = make_connector(),
celsius_fahrenheit_converter(Cx, Fx),
probe_connector('Celsius temp', Cx),
probe_connector('Fahrenheit temp', Fx),
set_value(Cx, 100.0, User),
forget_value(Cx, User),
set_value(Fx, 32.0, User),
% Exercise 3.36
Ay = make_connector(),
By = make_connector(),
set_value(Ay, 10, User).
inform_about_value(Propagator) ->
(Propagator#propagator_record.process_new_value)().
inform_about_no_value(Propagator) ->
(Propagator#propagator_record.process_forget_value)().
has_value(Connector) ->
(Connector#connector_record.has_value)().
get_value(Connector) ->
(Connector#connector_record.get_value)().
set_value(Connector, NewValue, Informant) ->
(Connector#connector_record.set_value)(NewValue, Informant).
forget_value(Connector, Retractor) ->
(Connector#connector_record.forget_value)(Retractor).
connect(Connector, NewConstraint) ->
(Connector#connector_record.connect)(NewConstraint).
for_each_except(Except, Procedure, List) ->
Loop =
fun (Self, []) -> {};
(Self, [H|T]) when H =:= Except -> Self(Self, T);
(Self, [H|T]) -> Procedure(H), Self(Self, T)
end,
Loop(Loop, List).
make_connector() ->
ValueList = new_cell([]),
InformantList = new_cell([]),
Constraints = new_cell([]),
HasValue =
fun () ->
not(get_cell(ValueList) =:= [])
end,
GetValue =
fun () ->
hd(get_cell(ValueList))
end,
Informant =
fun () ->
hd(get_cell(InformantList))
end,
SetValue =
fun (NewVal, Setter) ->
case not(HasValue()) of
true ->
set_cell(ValueList, [NewVal]),
set_cell(InformantList, [Setter]),
for_each_except(Setter, fun inform_about_value/1, get_cell(Constraints));
false ->
case not(GetValue()) =:= NewVal of
true -> throw ({constraint, "Contradiction"});
false -> {}
end
end
end,
ForgetValue =
fun(Retractor) ->
case not(get_cell(InformantList) =:= []) andalso Retractor =:= Informant() of
true ->
set_cell(InformantList, []),
set_cell(ValueList, []),
for_each_except(Retractor, fun inform_about_no_value/1, get_cell(Constraints));
false -> {}
end
end,
Connect =
fun (NewConstraint) ->
case not(lists:member(NewConstraint, get_cell(Constraints))) of
true -> set_cell(Constraints, [NewConstraint | get_cell(Constraints)]);
false -> {}
end,
case HasValue() of
true -> inform_about_value(NewConstraint);
false -> {}
end
end,
#connector_record{has_value = HasValue,
get_value = GetValue,
set_value = SetValue,
forget_value = ForgetValue,
connect = Connect}.
adder(A1, A2, Sum) ->
Me = new_cell({}),
ProcessNewValue =
fun () ->
case has_value(A1) andalso has_value(A2) of
true -> set_value(Sum, get_value(A1) + get_value(A2), get_cell(Me));
false ->
case has_value(A1) andalso has_value(Sum) of
true -> set_value(A2, get_value(Sum) - get_value(A1), get_cell(Me));
false ->
case has_value(A2) andalso has_value(Sum) of
true -> set_value(A1, get_value(Sum) - get_value(A2), get_cell(Me));
false -> {}
end
end
end
end,
ProcessForgetValue =
fun () ->
forget_value(Sum, get_cell(Me)),
forget_value(A1, get_cell(Me)),
forget_value(A2, get_cell(Me)),
ProcessNewValue()
end,
set_cell(Me, #propagator_record{process_new_value = ProcessNewValue,
process_forget_value = ProcessForgetValue}),
connect(A1, get_cell(Me)),
connect(A2, get_cell(Me)),
connect(Sum, get_cell(Me)).
multiplier(M1, M2, Product) ->
Me = new_cell({}),
ProcessNewValue =
fun () ->
case (has_value(M1) andalso get_value(M1) == 0.0) orelse
(has_value(M2) andalso get_value(M2) == 0.0) of
true -> set_value(Product, 0.0, get_cell(Me));
false ->
case has_value(M1) andalso has_value(M2) of
true -> set_value(Product, get_value(M1) * get_value(M2), get_cell(Me));
false ->
case has_value(Product) andalso has_value(M1) of
true -> set_value(M2, get_value(Product) / get_value(M1), get_cell(Me));
false ->
case has_value(Product) andalso has_value(M2) of
true -> set_value(M1, get_value(Product) / get_value(M2), get_cell(Me));
false -> {}
end
end
end
end
end,
ProcessForgetValue =
fun () ->
forget_value(Product, get_cell(Me)),
forget_value(M1, get_cell(Me)),
forget_value(M2, get_cell(Me)),
ProcessNewValue()
end,
set_cell(Me, #propagator_record{process_new_value = ProcessNewValue,
process_forget_value = ProcessForgetValue}),
connect(M1, get_cell(Me)),
connect(M2, get_cell(Me)),
connect(Product, get_cell(Me)).
constant(Value, Connector) ->
Me = new_cell({}),
ProcessNewValue =
fun () ->
throw ({constraint, "Unknown request -- CONSTANT -- process_new_value"})
end,
ProcessForgetValue =
fun () ->
throw ({constraint, "Unknown request -- CONSTANT -- process_forget_value"})
end,
set_cell(Me, #propagator_record{process_new_value = ProcessNewValue,
process_forget_value = ProcessForgetValue}),
connect(Connector, get_cell(Me)),
set_value(Connector, Value, get_cell(Me)).
probe_connector(Name, Connector) ->
Me = new_cell({}),
PrintProbe =
fun (Value) ->
io:format("Probe: "),
io:write(Name),
io:format(" = "),
io:write(Value),
io:format("~n")
end,
ProcessNewValue =
fun () ->
PrintProbe(get_value(Connector))
end,
ProcessForgetValue =
fun () ->
io:format("Probe: "),
io:write(Name),
io:format(" = ?"),
io:format("~n")
end,
set_cell(Me, #propagator_record{process_new_value = ProcessNewValue,
process_forget_value = ProcessForgetValue}),
connect(Connector, get_cell(Me)).
celsius_fahrenheit_converter(C, F) ->
U = make_connector(),
V = make_connector(),
W = make_connector(),
X = make_connector(),
Y = make_connector(),
multiplier(C, W, U),
multiplier(V, X, U),
adder(V, Y, F),
constant(9.0, W),
constant(5.0, X),
constant(32.0, Y).
% Exercise 3.34
squarer(A, B) ->
multiplier(A, A, B).
% 3.4.1 - Concurrency: Time Is of the Essence - The Nature of Time in Concurrent Systems
section_3_4_1() ->
Balance1 = new_cell(100),
% Exercise 3.38
set_cell(Balance1, get_cell(Balance1) + 10),
set_cell(Balance1, get_cell(Balance1) - 20),
set_cell(Balance1, get_cell(Balance1) - (get_cell(Balance1) div 2)),
print(get_cell(Balance1)).
withdraw1(Balance, Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end.
% 3.4.2 - Concurrency: Time Is of the Essence - Mechanisms for Controlling Concurrency
section_3_4_2() ->
X = new_cell(10),
parallel_execute(fun () -> set_cell(X, get_cell(X) * get_cell(X)) end,
fun () -> set_cell(X, get_cell(X) + 1) end),
receive after 100 -> {} end,
print(get_cell(X)),
set_cell(X, 10),
S = make_serializer(),
parallel_execute(fun () -> S(fun () -> set_cell(X, get_cell(X) * get_cell(X)) end) end,
fun () -> S(fun () -> set_cell(X, get_cell(X) + 1) end) end),
receive after 100 -> {} end,
print(get_cell(X)),
% Exercise 3.39
set_cell(X, 10),
parallel_execute(fun () -> set_cell(X, S(fun () -> get_cell(X) * get_cell(X) end)) end,
fun () -> S(fun () -> set_cell(X, get_cell(X) + 1) end) end),
receive after 100 -> {} end,
print(get_cell(X)),
% Exercise 3.40
set_cell(X, 10),
parallel_execute(fun () -> set_cell(X, get_cell(X) * get_cell(X)) end,
fun () -> set_cell(X, get_cell(X) * get_cell(X) * get_cell(X)) end),
receive after 100 -> {} end,
print(get_cell(X)),
set_cell(X, 10),
parallel_execute(fun () -> S(fun () -> set_cell(X, get_cell(X) * get_cell(X)) end) end,
fun () -> S(fun () -> set_cell(X, get_cell(X) * get_cell(X) * get_cell(X)) end) end),
receive after 100 -> {} end,
print(get_cell(X)).
parallel_execute(F1, F2) ->
spawn(F1),
spawn(F2).
% Implementing serializers
make_mutex() -> spawn(fun() -> mutex() end).
mutex() ->
receive
{lock, Pid} ->
Pid!{lock},
receive
{unlock} -> {}
end,
mutex();
{dispose} -> {}
end.
lock_mutex(Mutex) ->
Mutex!{lock, self()},
receive
{lock} -> {lock}
end.
unlock_mutex(Mutex) -> Mutex!{unlock}.
dispose_mutex(Mutex) -> Mutex!{dispose}.
make_serializer() ->
Mutex = make_mutex(),
fun (P) ->
lock_mutex(Mutex),
X = P(),
unlock_mutex(Mutex),
X
end.
make_account_2(InitBalance) ->
Balance = new_cell(InitBalance),
Withdraw =
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end,
Deposit =
fun (Amount) ->
set_cell(Balance, get_cell(Balance) + Amount)
end,
GetBalance =
fun () ->
get_cell(Balance)
end,
Mutex = make_mutex(),
Lock =
fun (P) ->
lock_mutex(Mutex),
X = P(),
unlock_mutex(Mutex),
X
end,
#account_record{withdraw = fun (Amount) -> Lock(fun () -> Withdraw(Amount) end) end,
deposit = fun (Amount) -> Lock(fun () -> Deposit(Amount) end) end,
balance = GetBalance}.
% Exercise 3.41
make_account_3(InitBalance) ->
Balance = new_cell(InitBalance),
Withdraw =
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end,
Deposit =
fun (Amount) ->
set_cell(Balance, get_cell(Balance) + Amount)
end,
Mutex = make_mutex(),
Lock =
fun (P) ->
lock_mutex(Mutex),
X = P(),
unlock_mutex(Mutex),
X
end,
#account_record{withdraw = fun (Amount) -> Lock(fun () -> Withdraw(Amount) end) end,
deposit = fun (Amount) -> Lock(fun () -> Deposit(Amount) end) end,
balance = fun () -> Lock(fun () -> get_cell(Balance) end) end}.
% Exercise 3.42
make_account_4(InitBalance) ->
Balance = new_cell(InitBalance),
Withdraw =
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end,
Deposit =
fun (Amount) ->
set_cell(Balance, get_cell(Balance) + Amount)
end,
GetBalance =
fun () ->
get_cell(Balance)
end,
Mutex = make_mutex(),
Lock =
fun (P) ->
lock_mutex(Mutex),
X = P(),
unlock_mutex(Mutex),
X
end,
ProtectedWithdraw = fun (Amount) -> Lock(fun () -> Withdraw(Amount) end) end,
ProtectedDeposit = fun (Amount) -> Lock(fun () -> Deposit(Amount) end) end,
#account_record{withdraw = ProtectedWithdraw,
deposit = ProtectedDeposit,
balance = GetBalance}.
% Multiple shared resources
-record(account_serialize_record, {withdraw, deposit, balance, serializer}).
make_account_5(InitBalance) ->
Balance = new_cell(InitBalance),
Withdraw =
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end,
Deposit =
fun (Amount) ->
set_cell(Balance, get_cell(Balance) + Amount)
end,
GetBalance =
fun () ->
get_cell(Balance)
end,
Mutex = make_mutex(),
Lock =
fun (P) ->
lock_mutex(Mutex),
X = P(),
unlock_mutex(Mutex),
X
end,
#account_serialize_record{withdraw = Withdraw,
deposit = Deposit,
balance = GetBalance,
serializer = Lock}.
exchange(Account1, Account2) ->
Difference = (Account1#account_serialize_record.balance)() - (Account2#account_serialize_record.balance)(),
(Account1#account_serialize_record.withdraw)(Difference),
(Account2#account_serialize_record.deposit)(Difference),
Difference.
deposit(Account, Amount) ->
S = Account#account_serialize_record.serializer,
D = Account#account_serialize_record.deposit,
S(fun () -> D(Amount) end).
serialized_exchange(Account1, Account2) ->
Serializer1 = Account1#account_serialize_record.serializer,
Serializer2 = Account2#account_serialize_record.serializer,
Serializer1(
fun () ->
Serializer2(fun () -> exchange(Account1, Account2) end)
end).
% Exercise 3.44
transfer(FromAccount, ToAccount, Amount) ->
(FromAccount#account_serialize_record.withdraw)(Amount),
(ToAccount#account_serialize_record.deposit)(Amount).
% Exercise 3.45
make_account_6(InitBalance) ->
Balance = new_cell(InitBalance),
Withdraw =
fun (Amount) ->
case get_cell(Balance) >= Amount of
true -> set_cell(Balance, get_cell(Balance) - Amount);
false -> throw ({insufficientFunds, get_cell(Balance)})
end
end,
Deposit =
fun (Amount) ->
set_cell(Balance, get_cell(Balance) + Amount)
end,
GetBalance =
fun () ->
get_cell(Balance)
end,
Mutex = make_mutex(),
Lock =
fun (P) ->
lock_mutex(Mutex),
X = P(),
unlock_mutex(Mutex),
X
end,
#account_serialize_record{withdraw = fun (Amount) -> Lock(fun () -> Withdraw(Amount) end) end,
deposit = fun (Amount) -> Lock(fun () -> Deposit(Amount) end) end,
balance = GetBalance,
serializer = Lock}.
deposit1(Account, Amount) ->
(Account#account_serialize_record.deposit)(Amount).
% 3.5.1 - Streams - Streams Are Delayed Lists
section_3_5_1() ->
% print (hd(tl(lists:filter(fun is_prime/1, enumerate_interval(10000, 1000000))))),
print ("").
sum_primes(A, B) ->
Iter =
fun (Self, Count, Accum) when Count > B -> Accum;
(Self, Count, Accum) ->
case is_prime(Count) of
true -> Self(Self, Count+1, Count+Accum);
false -> Self(Self, Count+1, Accum)
end
end,
Iter(Iter, A, 0).
sum_primes_1(A, B) ->
lists:foldr(fun erlang:'+'/2, 0, lists:filter(fun is_prime/1, enumerate_interval(A, B))).
|