SICP Chapter #03 Examples in Lua

-- Utility functions
function table_to_string(T)
   if type(T) ~= 'table' then return tostring(T) end
   local rt = "{"
   local first = true
   for key,value in pairs(T) do
      if (not first) then rt = rt .. ',' end
      first = false
      if type(value) == 'table' and type(key) == 'number' then
         rt = rt ..  table_to_string(value)
      elseif type(value) == 'table' then
         rt = rt .. key .. "=" ..  table_to_string(value)
      elseif type(key) == 'number' then
         rt = rt .. value
      else
         rt = rt .. key .. "=" .. value
      end
   end
   rt = rt .. "}"
   return rt
end

function printx(T)
   if type(T) == 'table' then
      print (table_to_string(T))
   else
      print (T)
   end
end

function table_copy(T)
   local rt = {}
   for key,value in pairs(T) do
      rt[key] = value
   end
   return rt
end

function table_slice(T, first, last)
   local rt = {}
   if last == nil then last = #T end
   for i = first, last, 1 do
      rt[#rt+1] = T[i]
   end
   return rt
end

-- Functions defined in previous chapters
function gcd(a, b)
   if (b == 0) then
      return a
   else
      return gcd(b, math.mod(a, b))
   end
end

function square(x) return x * x end
function average(x, y)
   return (x + y) / 2
end
function has_no_divisors(n, c)
   if (c == 1) then
      return true
   elseif (math.mod(n, c) == 0) then
      return false
   else
      return has_no_divisors(n, c-1)
   end
end
function is_prime(n)
   return has_no_divisors(n, n-1)
end
function enumerate_interval(low, high)
   local rt = {}
   for i = low, high, 1 do
      rt[#rt+1] = i
   end
   return rt
end
function is_odd(n) return math.mod(n, 2) == 1 end
function is_even(n) return not(is_odd(n)) end

-- 3.1.1 - Assignment and Local State - Local State Variables
balance = 100

function withdraw(amount)
   if balance >= amount then
      balance = balance - amount
      return balance
   else
      print('InsufficientFunds: ' .. tostring(balance))
      return nil
   end
end

print (withdraw(25))
print (withdraw(25))
print (withdraw(60))
print (withdraw(15))

function new_withdraw()
   local balance = 100
   return function(amount)
      if balance >= amount then
         balance = balance - amount
         return balance
      else
         print('InsufficientFunds: ' .. tostring(balance))
         return nil
      end
   end
end

function make_withdraw(init_balance)
   local balance = init_balance
   return function(amount)
      if balance >= amount then
         balance = balance - amount
         return balance
      else
         print('InsufficientFunds: ' .. tostring(balance))
         return nil
      end
   end
end

w1 = make_withdraw(100)
w2 = make_withdraw(100)

print (w1(50))
print (w2(70))
print (w2(40))
print (w1(40))

function make_account(init_balance)
   local balance = init_balance
   local function withdraw(amount)
      if balance >= amount then
         balance = balance - amount
         return balance
      else
         print('InsufficientFunds: ' .. tostring(balance))
         return nil
      end
   end
   local function deposit(amount)
      balance = balance + amount
      return balance
   end
   local function getbalance()
      return balance
   end
   return { withdraw=withdraw, deposit=deposit, balance=getbalance }
end

acc = make_account(100)
acc.withdraw(50)
acc.withdraw(60)
acc.deposit(40)
acc.withdraw(60)
print (acc.balance())

_ = make_account(100)

-- Exercise 3.1
-- exercise left to reader to define appropriate functions
-- a = make_accumulator(5)
-- a.f(10)
-- a.f(10)

-- Exercise 3.2
-- exercise left to reader to define appropriate functions
-- s = make_monitored(sqrt)
-- s.f(100)
-- s.how_many_calls()

-- Exercise 3.3
-- exercise left to reader to define appropriate functions
-- acc make_account(100, "secret-password")
-- acc.withdraw(40, "secret-password")
-- acc.withdraw(50, "some-other-password")

-- 3.1.2 - Assignment and Local State - The Benefits of Introducing Assignment
random_init = 7

function rand_update(x)
   local a = 27
   local b = 26
   local m = 127
   return math.mod(a*x + b, m)
end

function rand()
   local x = random_init
   random_init = rand_update(random_init)
   return x
end

function cesaro_test()
   return gcd(rand(), rand()) == 1
end

function monte_carlo(trials, experiment)
   local function iter (trials_remaining, trials_passed)
      if trials_remaining == 0 then
         return trials_passed / trials
      elseif experiment() then
         return iter(trials_remaining - 1, trials_passed + 1)
      else
         return iter(trials_remaining - 1, trials_passed)
      end
   end
   return iter(trials, 0)
end

function estimate_pi(trials)
   return math.sqrt(6.0 / monte_carlo(trials, cesaro_test))
end

print (estimate_pi(10))

-- second version (no assignment)
function random_gcd_test(trials, initial_x)
   local function iter(trials_remaining, trials_passed, x)
      local x1 = rand_update(x)
      local x2 = rand_update(x1)
      if trials_remaining == 0 then
         return trials_passed / trials
      elseif gcd(x1, x2) == 1 then
         return iter(trials_remaining - 1, trials_passed + 1, x2)
      else
         return iter(trials_remaining - 1, trials_passed, x2)
      end
   end
   return iter(trials, 0, initial_x)
end

function estimate_pi(trials)
   return math.sqrt(6.0 / random_gcd_test(trials, random_init))
end

random_init = 7
print (estimate_pi(10))

-- Exercise 3.6
-- exercise left to reader to define appropriate functions
-- function random_in_range(low, high)
--    local range = high - low
--    return low + random(range)
-- end

-- 3.1.3 - Assignment and Local State - The Cost of Introducing Assignment
function make_simplified_withdraw(init_balance)
   local balance = init_balance
   return function(amount)
      balance = balance - amount
      return balance
   end
end

w = make_simplified_withdraw(25)
print (w(20))
print (w(10))

function make_decrementer(balance)
   return function(amount) return balance - amount end
end

d = make_decrementer(25)
print (d(20))
print (d(10))

_ = make_decrementer(25)(20)
_ = (function(amount) return 25 - amount end)(20)
_ = 25 - 20

_ = make_simplified_withdraw(25)(20)

-- Sameness and change
d1 = make_decrementer(25)
d2 = make_decrementer(25)

w1 = make_simplified_withdraw(25)
w2 = make_simplified_withdraw(25)
print (w1(20))
print (w1(20))
print (w2(20))

peter_acc = make_account(100)
paul_acc = make_account(100)

peter_acc = make_account(100)
paul_acc = peter_acc

-- Pitfalls of imperative programming
function factorial(n)
   local function iter(product, counter)
      if counter > n then
         return product
      else
         return iter(counter * product, counter + 1)
      end
   end
   return iter(1, 1)
end

function factorial(n)
   local product = 1
   local counter = 1
   local function iter()
      if counter > n then
         return product
      else
         product = counter * product;
         counter = counter + 1;
         return iter()
      end
   end
   return iter()
end

-- Exercise 3.7
-- exercise left to reader to define appropriate functions
-- paul_acc = make_joint(peter_acc, "open_sesame", "rosebud")

-- 3.2.1 - The Environment Model of Evaluation - The Rules for Evaluation
function square(x) return x * x end

square = function(x) return x * x end

-- 3.2.2 - The Environment Model of Evaluation - Applying Simple Procedures
function square(x) return x * x end

function sum_of_squares(x, y)
   return square(x) + square(y)
end

function f(a)
   return sum_of_squares(a + 1, a * 2)
end

-- Exercise 3.9
function factorial(n)
   if n == 1 then
      return 1
   else
      return n * factorial(n - 1)
   end
end

function fact_iter(product, counter, max_count)
   if counter > max_count then
      return product
   else
      return fact_iter(counter * product, counter + 1, max_count)
   end
end

function factorial(n)
   return fact_iter(1, 1, n)
end

-- 3.2.3 - The Environment Model of Evaluation - Frames as Repository of Local State
function make_withdraw(init_balance)
   local balance = init_balance
   return function(amount)
      if balance >= amount then
         balance = balance - amount
         return balance
      else
         print('InsufficientFunds: ' .. tostring(balance))
         return nil
      end
   end
end

w1 = make_withdraw(100)
print (w1(50))
w2 = make_withdraw(100)

-- Exercise 3.10
function make_withdraw(initial_amount)
   local balance = initial_amount
   return function(amount)
      if balance >= amount then
         balance = balance - amount
         return balance
      else
         print('InsufficientFunds: ' .. tostring(balance))
         return nil
      end
   end
end
w1 = make_withdraw(100)
print (w1(50))
w2 = make_withdraw(100)

-- 3.2.4 - The Environment Model of Evaluation - Internal Definitions

-- same as in section 1.1.8
function sqrt(x)
   local function good_enough(guess)
      return abs(square(guess) - x) < 0.001
   end

   local function improve(guess)
      return average(guess, x / guess)
   end

   local function sqrt_iter(guess)
      if good_enough(guess) then
         return guess
      else
         return sqrt_iter(improve(guess))
      end
   end

   return sqrt_iter(1.0)
end

-- Exercise 3.11
function make_account(init_balance)
   local balance = init_balance
   local function withdraw(amount)
      if balance >= amount then
         balance = balance - amount
         return balance
      else
         print('InsufficientFunds: ' .. tostring(balance))
         return nil
      end
   end
   local function deposit(amount)
      balance = balance + amount
      return balance
   end
   local function getbalance()
      return balance
   end
   return { withdraw=withdraw, deposit=deposit, balance=getbalance }
end

acc = make_account(50)
acc.deposit(40)
acc.withdraw(60)
print (acc.balance())
acc2 = make_account(100)