Main Page | Recent changes | Edit this page | Page history Printable version | Disclaimers

Not logged in Log in | Help

Topics:SICP in other languages:JavaScript:Chapter 3

From CTMWiki

Table of contents

1 About SICP 2 SICP Chapter #03 Examples in JavaScript 3 // 3.1.1 - Assignment and var State - var State Variables 4 // 3.1.2 - Assignment and var State - The Benefits of Introducing Assignment 5 // 3.1.3 - Assignment and var State - The Cost of Introducing Assignment 6 // 3.2.1 - The Environment Model of Evaluation - The Rules for Evaluation 7 // 3.2.2 - The Environment Model of Evaluation - Applying Simple Procedures 8 // 3.2.3 - The Environment Model of Evaluation - Frames as Repository of var State 9 // 3.2.4 - The Environment Model of Evaluation - Internal Definitions

About SICP

The following JavaScript code is derived from the examples provided in the book:
      "Structure and Interpretation of Computer Programs, Second Edition" by Harold Abelson and Gerald Jay Sussman with Julie Sussman.
      http://mitpress.mit.edu/sicp/

SICP Chapter #03 Examples in JavaScript

// Utility functions

// Use this print function for javascript embedded in html page
// function print(s) { document.writeln(s + "<br>"); }

// Reference Implementation of ES4 does not have parseFloat function yet
function parseFloat(x) { return x / 1.0; }

// Functions defined in previous chapters
function gcd(a, b) {
   if (b == 0)
      return a;
   else
      return gcd(b, a % b);
}

function square(x) { return x * x; }
function average(x, y) {
   return (x + y) / 2.0;
}
function has_no_divisors(n, c) {
   if (c == 1)
      return true;
   else if (n % c == 0)
      return false;
   else
      return has_no_divisors(n, c-1);
}
function is_prime(n) {
   return has_no_divisors(n, n-1);
}
function enumerate_interval(low, high) {
   var rt = [];
   for (var i = low; i <= high; i++) {
      rt.push(i);
   }
   return rt;
}
function is_odd(n) { return n % 2 == 1; }
function is_even(n) { return !is_odd(n); }

// 3.1.1 - Assignment and var State - var State Variables

var balance = 100;

function withdraw(amount) {
   if (balance >= amount) {
      balance = balance - amount;
      return balance;
   } else {
      print('InsufficientFunds: ' + balance);
      return null;
   }
}

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

function new_withdraw() {
   var balance = 100
   return function(amount) {
      if (balance >= amount) {
         balance = balance - amount;
         return balance;
      } else {
         print('InsufficientFunds: ' + balance);
         return null;
      }
   }
}

function make_withdraw(init_balance) {
   var balance = init_balance
   return function(amount) {
      if (balance >= amount) {
         balance = balance - amount;
         return balance;
      } else {
         print('InsufficientFunds: ' + balance);
         return null;
      }
   }
}

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

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

function Account(init_balance) {
   this.balance = init_balance
   this.withdraw = function(amount) {
      if (this.balance >= amount) {
         this.balance = this.balance - amount;
         return this.balance;
      } else {
         print('InsufficientFunds: ' + this.balance);
         return null;
      }
   }
   this.deposit = function(amount) {
      this.balance = this.balance + amount;
      return this.balance;
   }
   this.getbalance = function() {
      return this.balance;
   }
}

acc = new Account(100);
acc.withdraw(50);
acc.withdraw(60);
acc.deposit(40);
acc.withdraw(60);
print (acc.getbalance());

new Account(100);

// Exercise 3.1
// exercise left to reader to define appropriate functions
// a = new Accumulator(5);
// a.f(10);
// a.f(10);

// Exercise 3.2
// exercise left to reader to define appropriate functions
// s = Monitored(sqrt);
// s.f(100);
// s.how_many_calls();

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

// 3.1.2 - Assignment and var State - The Benefits of Introducing Assignment

var random_init = 7;

function rand_update(x) {
   var a = 27;
   var b = 26;
   var m = 127;
   return (a*x + b) % m;
}

function rand() {
   x = random_init;
   random_init = rand_update(random_init);
   return x;
}

function cesaro_test() {
   return gcd(rand(), rand()) == 1;
}

function monte_carlo(trials, experiment) {
   function iter (trials_remaining, trials_passed) {
      if (trials_remaining == 0)
         return trials_passed / trials;
      else if (experiment())
         return iter(trials_remaining - 1, trials_passed + 1);
      else
         return iter(trials_remaining - 1, trials_passed);
   }
   return iter(trials, 0);
}

function estimate_pi(trials) {
   return Math.sqrt(6.0 / monte_carlo(trials, cesaro_test));
}

print (estimate_pi(10));

// second version (no assignment)
function random_gcd_test(trials, initial_x) {
   function iter(trials_remaining, trials_passed, x) {
      var x1 = rand_update(x);
      var x2 = rand_update(x1);
      if (trials_remaining == 0)
         return parseFloat(trials_passed) / trials;
      else if (gcd(x1, x2) == 1)
         return iter(trials_remaining - 1, trials_passed + 1, x2);
      else
         return iter(trials_remaining - 1, trials_passed, x2);
   }
   return iter(trials, 0, initial_x);
}

function estimate_pi_2(trials) {
   return Math.sqrt(6.0 / random_gcd_test(trials, random_init));
}

random_init = 7;
print (estimate_pi_2(10));

// Exercise 3.6
// exercise left to reader to define appropriate functions
// function random_in_range(low, high) {
//    var range = high - low;
//    return low + random(range);
// }

// 3.1.3 - Assignment and var State - The Cost of Introducing Assignment

function make_simplified_withdraw(init_balance) {
   var balance = init_balance;
   return function(amount) {
      balance = balance - amount;
      return balance;
   }
}

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

function make_decrementer(balance) {
   return function(amount) { return balance - amount; };
}

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

make_decrementer(25)(20);
(function(amount) { return 25 - amount; })(20);
25 - 20;

make_simplified_withdraw(25)(20);

// Sameness and change
var d1 = make_decrementer(25);
var d2 = make_decrementer(25);

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

var peter_acc = new Account(100);
var paul_acc = new Account(100);

peter_acc = new Account(100);
paul_acc = peter_acc;

// Pitfalls of imperative programming
function factorial(n) {
   function iter(product, counter) {
      if (counter > n)
         return product;
      else
         return iter(counter * product, counter + 1);
   }
   return iter(1, 1);
}

function factorial_1(n) {
   var product = 1;
   var counter = 1;
   function iter() {
      if (counter > n) {
         return product;
      } else {
         product = counter * product;
         counter = counter + 1;
         return iter();
      }
   }
   return iter();
}

// Exercise 3.7
// exercise left to reader to define appropriate functions
// paul_acc = new JointAccount(peter_acc, "open_sesame", "rosebud");

// 3.2.1 - The Environment Model of Evaluation - The Rules for Evaluation

function square(x) { return x * x; }

square = function(x) { return x * x; }

// 3.2.2 - The Environment Model of Evaluation - Applying Simple Procedures

function square(x) { return x * x; }

function sum_of_squares(x, y) {
   return square(x) + square(y);
}

function f(a) {
   return sum_of_squares(a + 1, a * 2);
}

// Exercise 3.9
function factorial_3(n) {
   if (n == 1)
      return 1;
   else
      return n * factorial_3(n - 1);
}

function fact_iter(product, counter, max_count) {
   if (counter > max_count)
      return product;
   else
      return fact_iter(counter * product, counter + 1, max_count);
}

function factorial_4(n) {
   return fact_iter(1, 1, n);
}

// 3.2.3 - The Environment Model of Evaluation - Frames as Repository of var State

function make_withdraw_2(init_balance) {
   var balance = init_balance
   return function(amount) {
      if (balance >= amount) {
         balance = balance - amount;
         return balance;
      } else {
         print('InsufficientFunds: ' + balance);
         return null;
      }
   }
}

w1 = make_withdraw_2(100);
print (w1(50));
w2 = make_withdraw_2(100);

// Exercise 3.10
function make_withdraw_3(initial_amount) {
   var balance = initial_amount;
   return function(amount) {
      if (balance >= amount) {
         balance = balance - amount;
         return balance;
      } else {
         print('InsufficientFunds: ' + balance);
         return null;
      }
   }
}
w1 = make_withdraw_3(100);
print (w1(50));
w2 = make_withdraw_3(100);

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

// same as in section 1.1.8
function sqrt(x) {
   function good_enough(guess) {
      return abs(square(guess) - x) < 0.001;
   }
   function improve(guess) {
      return average(guess, parseFloat(x) / guess);
   }
   function sqrt_iter(guess) {
      if (good_enough(guess))
         return guess;
      else
         return sqrt_iter(improve(guess));
   }
   return sqrt_iter(1.0);
}

// Exercise 3.11
function Account2(init_balance) {
   this.balance = init_balance
   this.withdraw = function(amount) {
      if (this.balance >= amount) {
         this.balance = this.balance - amount;
         return this.balance;
      } else {
         print('InsufficientFunds: ' + this.balance);
         return null;
      }
   }
   this.deposit = function(amount) {
      this.balance = this.balance + amount;
      return this.balance;
   }
   this.getbalance = function() {
      return this.balance;
   }
}

acc = new Account2(50)
acc.deposit(40)
acc.withdraw(60)
print (acc.getbalance())
acc2 = new Account2(100)

Edit this page | Discuss this page | Page history | What links here | Related changes Main Page | About CTMWiki | Recent changes |   This page has been accessed 953 times. This page was last modified 16:26, 30 Nov 2007.