Topics:SICP in other languages:JavaScript:Chapter 1

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/

[edit]

SICP Chapter #01 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; }

[edit]

// 1.1.1 The Elements of Programming - Expressions

print (486);
print (137 + 349);
print (1000 - 334);
print (5 * 99);
print (10 / 5);
print (2.7 + 10.0);
print (21 + 35 + 12 + 7);
print (25 * 4 * 12);
print (3 * 5 + 10 - 6);
print (3 * (2 * 4 + 3 + 5) + 10 - 7 + 6);

[edit]

// 1.1.2 The Elements of Programming - Naming and the Environment

var size = 2;
print (size);
print (5 * size);
var pi = 3.14159;
var radius = 10.0;
print (pi * radius * radius);
var circumference = 2.0 * pi * radius;
print (circumference);

[edit]

// 1.1.3 The Elements of Programming - Evaluating Combinations

print ((2 + (4 * 6)) * (3 + 5 + 7));

[edit]

// 1.1.4 The Elements of Programming - Compound Procedures

function square(x) { return x * x; }
print (square(21));
print (square(2 + 5));
print (square(square(3)));
function sum_of_squares(x, y) { return square(x) + square(y); }
print (sum_of_squares(3, 4));
function f(a) { return sum_of_squares(a + 1, a * 2); }
print (f(5));

[edit]

// 1.1.5 The Elements of Programming - The Substitution Model for Procedure Application

print (f(5));
print (sum_of_squares(5 + 1, 5 * 2));
print (square(6) + square(10));
print ((6 * 6) + (10 * 10));
print (36 + 100);
print (f(5));
print (sum_of_squares(5 + 1, 5 * 2));
print (square(5 + 1) + square(5 * 2));

print (((5 + 1) * (5 + 1)) + ((5 * 2) * (5 * 2)));
print ((6 * 6) + (10 * 10));
print (36 + 100);
print (136);

[edit]

// 1.1.6 The Elements of Programming - Conditional Expressions and Predicates

function abs(x) {
   if (x > 0)
      return x;
   else if (x == 0)
      return 0;
   else
      return -x;
}
function abs_1(x) {
   if (x < 0)
      return -x;
   else
      return x;
}
var x = 6;
print ((x > 5) && (x < 10));
function ge(x, y) {
   return (x > y) || (x == y)
}
function ge_1(x, y) {
   return !(x < y)
}

// Exercise 1.1
print (10);
print (5 + 3 + 4);
print (9 - 1);
print (6 / 2);
print (2 * 4 + 4 - 6);
var a = 3;
var b = a + 1;
print (a + b + a * b);
print (a == b);
print ((b > a && b < a * b) ? b : a);
print ((a == 4) ? 6 : (b == 4) ? (6 + 7 + a) : 25);
print (2 + ((b > a) ? b : a));
print (((a > b) ? a : (a < b) ? b : -1) * (a + 1));

// Exercise 1.2
print (((5.0 + 4.0 + (2.0 - (3.0 - (6.0 + (4.0 / 5.0))))) /
         (3.0 * (6.0 - 2.0) * (2.0 - 7.0))));

// Exercise 1.3
function three_n(n1, n2, n3) {
   if (n1 > n2)
      if (n1 > n3)
         if (n2 > n3)
            return n1*n1 + n2*n2;
         else
            return n1*n1 + n3*n3;
      else
         return n1*n1 + n3*n3;
   else
      if (n2 > n3)
         if (n1 > n3)
            return n2*n2 + n1*n1;
         else
            return n2*n2 + n3*n3;
      else
         return n2*n2 + n3*n3;
}

// Exercise 1.4
function a_plus_abs_b(a, b) {
   if (b > 0)
      return a + b;
   else
      return a - b;
}

// Exercise 1.5
function p() { return p(); }
function test(x, y) {
   if (x == 0)
      return 0;
   else
      return y;
}
// commented out as this is in infinite loop
// test(0, p())

[edit]

// 1.1.7 The Elements of Programming - Example: Square Roots by Newton's Method

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

function good_enough(guess, x) {
   return abs(square(guess) - x) < 0.001;
}

function average(x, y) {
   return (x + y) / 2.0;
}

function improve(guess, x) {
   return average(guess, parseFloat(x) / guess);
}

function sqrt_iter(guess, x) {
   if (good_enough(guess, x))
      return guess;
   else
      return sqrt_iter(improve(guess, x), x);
}

function sqrt_0(x) {
   return sqrt_iter(1.0, parseFloat(x));
}

print (sqrt_0(9));
print (sqrt_0(100 + 37));
print (sqrt_0(sqrt_0(2)+sqrt_0(3)));
print (square(sqrt_0(1000)));

// Exercise 1.6
function new_if(predicate, then_clause, else_clause) {
   if (predicate)
      return then_clause;
   else
      return else_clause;
}
print (new_if((2==3), 0, 5));
print (new_if((1==1), 0, 5));
function sqrt_iter_0(guess, x) {
   return new_if(
      good_enough(guess, x),
      guess,
      sqrt_iter_0(improve(guess, x), x));
}

// Exercse 1.7
function good_enough_gp(guess, prev) {
   return abs(guess - prev) / guess < 0.001;
}
function sqrt_iter_gp(guess, prev, x) {
   if (good_enough_gp(guess, prev))
      return guess;
   else
      return sqrt_iter_gp(improve(guess, x), guess, x);
}
function sqrt_gp(x) {
   return sqrt_iter_gp(4.0, 1.0, x);
}

// Exercise 1.8
function improve_cube(guess, x) {
   return (2.0*guess + x/(guess * guess)) / 3.0;
}
function cube_iter(guess, prev, x) {
   if (good_enough_gp(guess, prev))
      return guess;
   else
      return cube_iter(improve_cube(guess, x), guess, x);
}
function cube_root_0(x) {
   return cube_iter(27.0, 1.0, x);
}

[edit]

// 1.1.8 The Elements of Programming - Procedures as Black-Box Abstractions

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

function double(x) { return x + x; }

function square_real(x) { return Math.exp(double(Math.log(x))); }

function good_enough_1(guess, x) {
   return abs(square(guess) - x) < 0.001;
}

function improve_1(guess, x) {
   return average(guess, parseFloat(x) / guess);
}

function sqrt_iter_1(guess, x) {
   if (good_enough_1(guess, x))
      return guess;
   else
      return sqrt_iter_1(improve_1(guess, x), x);
}

function sqrt_1(x) {
   return sqrt_iter_1(1.0, x);
}

print (square(5));

// Block-structured
function sqrt_2(x) {
   function good_enough(guess, x) {
      return abs(square(guess) - x) < 0.001;
   }

   function improve(guess, x) {
      return average(guess, float(x) / guess);
   }

   function sqrt_iter(guess, x) {
      if (good_enough(guess, x))
         return guess;
      else
         return sqrt_iter(improve(guess, x), x);
   }

   return sqrt_iter(1.0, x);
}

// Taking advantage of lexical scoping
function sqrt_3(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);
}

[edit]

// 1.2.1 Procedures and the Processes They Generate - Linear Recursion and Iteration


// Recursive
function factorial(n) {
   if (n == 1)
      return 1;
   else
      return n * factorial(n - 1);
}

print (factorial(6));

// Iterative
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_1(n) {
   return fact_iter(1, 1, n);
}

// Iterative, block-structured (from footnote)
function factorial_2(n) {
   function iter(product, counter) {
      if (counter > n)
         return product;
      else
         return iter(counter * product, counter + 1);
   }
   return iter(1, 1);
}

// Exercise 1.9
function inc(a) { return a + 1; }
function dec(a) { return a - 1; }
function plus(a, b) {
   if (a == 0)
      return b;
   else
      return inc(plus(dec(a), b));
}
function plus_1(a, b) {
   if (a == 0)
      return b;
   else
      return plus_1(dec(a), inc(b));
}

// Exercise 1.10
function ax(x, y) {
   if (y == 0)
      return 0;
   else if (x == 0)
      return 2 * y;
   else if (y == 1)
      return 2;
   else
      return ax(x - 1, ax(x, y - 1));
}
print (ax(1, 10));
print (ax(2, 4));
print (ax(3, 3));
function fx(n) { return ax(0, n); }
function g(n) { return ax(1, n); }
function h(n) { return ax(2, n); }
function k(n) { return 5 * n * n; }

[edit]

// 1.2.2 Procedures and the Processes They Generate - Tree Recursion


// Recursive
function fib(n) {
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return fib(n - 1) + fib(n - 2);
}

// Iterative
function fib_iter(a, b, count) {
   if (count == 0)
      return b;
   else
      return fib_iter(a + b, a, count - 1);
}
function fib_1(n) {
   return fib_iter(1, 0, n);
}

// Counting change
function first_denomination(x) {
   if (x == 1) return 1;
   else if (x == 2) return 5;
   else if (x == 3) return 10;
   else if (x == 4) return 25;
   else if (x == 5) return 50;
}

function cc(amount, kinds_of_coins) {
   if (amount == 0)
      return 1;
   else if (amount < 0)
      return 0;
   else if (kinds_of_coins == 0)
      return 0;
   else
      return cc(amount, kinds_of_coins - 1) +
             cc(amount - first_denomination(kinds_of_coins), kinds_of_coins);
}

function count_change(amount) {
   return cc(amount, 5);
}

print (count_change(100));

// Exercise 1.11
function fi(n) {
   if (n < 3)
      return n;
   else
      return fi(n - 1) + 2*fi(n - 2) + 3*fi(n - 3);
}

function fi_iter(a, b, c, count) {
   if (count == 0)
      return c;
   else
      return fi_iter(a + 2*b + 3*c, a, b, count - 1);
}

function fi_1(n) { return fi_iter(2, 1, 0, n); }

// Exercise 1.12
function pascals_triangle(n, k) {
   if (n == 0 || k == 0 || n == k)
      return 1;
   else
      return pascals_triangle(n - 1, k - 1) + pascals_triangle(n - 1, k);
}

[edit]

// 1.2.3 Procedures and the Processes They Generate - Orders of Growth


// Exercise 1.15
function cube(x) { return x * x * x; }
function p(x) { return 3.0*x - 4.0*cube(x); }
function sine(angle) {
   if (!(abs(angle) > 0.1))
      return angle;
   else
      return p(sine(angle / 3.0));
}

[edit]

// 1.2.4 Procedures and the Processes They Generate - Exponentiation


// Linear recursion
function expt(b, n) {
   if (n == 0)
      return 1;
   else
      return b * expt(b, (n - 1));
}

// Linear iteration
function expt_iter(b, counter, product) {
   if (counter == 0)
      return product;
   else
      return expt_iter(b, counter - 1, b * product);
}
function expt_1(b, n) {
   return expt_iter(b, n, 1);
}

// Logarithmic iteration
function even(n) { return (n % 2) == 0; }

function fast_expt(b, n) {
   if (n == 0)
      return 1;
   else
      if (even(n))
         return square(fast_expt(b, n / 2));
      else
         return b * fast_expt(b, n - 1);
}

// Exercise 1.17
function multiply(a, b) {
   if (b == 0)
      return 0;
   else
      return plus(a, multiply(a, dec(b)));
}

// Exercise 1.19
// exercise left to reader to solve for p' and q'
// function fib_iter(a, b, p, q, count) {
//    if (count == 0)
//       return b;
//    else
//       if (even(count))
//          return fib_iter(a, b, p', q', count / 2);
//       else
//          return fib_iter((b * q) + (a * q) + (a * p), (b * p) + (a * q), p, q, count - 1);
// }
// function fib(n) {
//    return fib_iter(1, 0, 0, 1, n);
// }

[edit]

// 1.2.5 Procedures and the Processes They Generate - Greatest Common Divisors

function gcd(a, b) {
   if (b == 0)
      return a;
   else
      return gcd(b, a % b);
}
print (gcd(40, 6));

// Exercise 1.20
print (gcd(206, 40));

[edit]

// 1.2.6 Procedures and the Processes They Generate - Example: Testing for Primality


// prime
function divides(a, b) { return (b % a) == 0; }

function find_divisor(n, test_divisor) {
   if (square(test_divisor) > n)
      return n;
   else if (divides(test_divisor, n))
      return test_divisor;
   else
      return find_divisor(n, test_divisor + 1);
}

function smallest_divisor(n) { return find_divisor(n, 2); }

function prime(n) { return n == smallest_divisor(n); }

// fast_prime
function expmod(nbase, nexp, m) {
   if (nexp == 0)
      return 1;
   else
      if (even(nexp))
         return square(expmod(nbase, nexp / 2, m)) % m;
      else
         return (nbase * (expmod(nbase, (nexp - 1), m))) % m;
}

function fermat_test(n) {
   function try_it(a) { return expmod(a, n, n) == a; }
   return try_it(1 + Math.round((Math.random()*n)-1));
}

function fast_prime(n, ntimes) {
   if (ntimes == 0) return true;
   else
      if (fermat_test(n)) return fast_prime(n, ntimes - 1);
      else return false;
}

// Exercise 1.21
print (smallest_divisor(199));
print (smallest_divisor(1999));
print (smallest_divisor(19999));

// Exercise 1.22
function report_prime(elapsed_time) {
   print (" *** " + elapsed_time);
}
function start_prime_test(n, start_time) {
   if (prime(n)) {
      report_prime((new Date()).getTime() - start_time);
   }
}
function timed_prime_test(n) {
   print ("\n" + n);
   start_prime_test(n, (new Date()).getTime());
}

// Exercise 1.25
function expmod_1(nbase, nexp, m) {
   return fast_expt(nbase, nexp) % m;
}

// Exercise 1.26
function expmod_2(nbase, nexp, m) {
   if (nexp == 0)
      return 1;
   else
      if (even(nexp))
         return (expmod_2(nbase, (nexp / 2), m) *
                 expmod_2(nbase, (nexp / 2), m)) % m;
      else
         return (nbase * expmod_2(nbase, nexp - 1, m)) % m;
}

// Exercise 1.27
function carmichael(n) {
   return fast_prime(n, 100) && !prime(n);
}

print (carmichael(561));
print (carmichael(1105));
print (carmichael(1729));
print (carmichael(2465));
print (carmichael(2821));
print (carmichael(6601));

[edit]

// 1.3 Formulating Abstractions with Higher-Order Procedures

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

[edit]

// 1.3.1 Formulating Abstractions with Higher-Order Procedures - Procedures as Arguments

function sum_integers(a, b) {
   if (a > b)
      return 0;
   else
      return a + sum_integers(a + 1, b);
}

function sum_cubes(a, b) {
   if (a > b)
      return 0;
   else
      return cube(a) + sum_cubes(a + 1, b);
}

function pi_sum(a, b) {
   if (a > b)
      return 0.0;
   else
      return (1.0 / (a * (a + 2.0))) + pi_sum(a + 4.0, b);
}

function sum(term, a, next, b) {
   if (a > b)
      return 0;
   else
      return term(a) + sum(term, next(a), next, b);
}

// Using sum
function inc_1(n) { return n + 1; }

function sum_cubes_1(a, b) {
   return sum(cube, a, inc, b);
}

print (sum_cubes_1(1, 10));

function identity(x) { return x; }

function sum_integers_1(a, b) {
   return sum(identity, a, inc_1, b);
}

print (sum_integers_1(1, 10));

function pi_sum_1(a, b) {
   function pi_term(x) { return 1.0 / (x * (x + 2.0)); }
   function pi_next(x) { return x + 4.0; }
   return sum(pi_term, a, pi_next, b);
}

print (8.0 * pi_sum_1(1, 1000));

function integral(f, a, b, dx) {
   function add_dx(x) { return x + dx; }
   return sum(f, a + (dx / 2.0), add_dx, b) * dx;
}

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

print (integral(cube, 0.0, 1.0, 0.01));
// exceeds maximum recursion depth in JS2.0.  Works in ES4 which has TCO.
print (integral(cube, 0.0, 1.0, 0.001));

// Exercise 1.29
function simpson(f, a, b, n) {
   var h = abs(b - a) / n;
   function sum_iter(term, start, next, stop, acc) {
      if (start > stop)
         return acc;
      else
         return sum_iter(term, next(start), next, stop, acc + term(a + start * h));
   }
   return h * sum_iter(f, 1, inc, n, 0.0);
}
simpson(cube, 0.0, 1.0, 100);

// Exercise 1.30
function sum_iter(term, a, next, b, acc) {
   if (a > b)
      return acc;
   else
      return sum_iter(term, next(a), next, b, acc + term(a));
}
// 'sum_cubes_2' reimplements 'sum_cubes_' but uses 'sum_iter' in place of 'sum'
function sum_cubes_2(a, b) { return sum_iter(cube, a, inc, b, 0); }
sum_cubes_2(1, 10);

// Exercise 1.31
// a.
function product(term, a, next, b) {
   if (a > b)
      return 1;
   else
      return term(a) * product(term, next(a), next, b);
}
function factorial_2(n) { return product(identity, 1, inc, n); }

// b.
function product_iter(term, a, next, b, acc) {
   if (a > b)
      return acc;
   else
      return product_iter(term, next(a), next, b, acc * term(a));
}
function factorial_3(n) { return product_iter(identity, 1, inc, n, 1); }

// Exercise 1.32
// a.
function accumulate(combiner, nullValue, term, a, next, b) {
   if (a > b)
      return nullValue;
   else
      return combiner(term(a), accumulate(combiner, nullValue, term, next(a), next, b));
}

// sum:     accumulate(plus, 0, identity, a, inc, b);
function sum_1(a, b) {
   return accumulate(plus, 0, identity, a, inc, b)
}
function product_1(a, b) { return a * b; }
// product: accumulate(multiply, 1, identity, a, inc, b);

// b.
// NOTE: starting value of 'acc' is 'nullValue'
function accumulate_iter(combiner, term, a, next, b, acc) {
   if (a > b)
      return acc;
   else
      return accumulate_iter(combiner, term, next(a), next, b, combiner(acc, term(a)));
}

// sum:     accumulate_iter(plus, identity, a, inc, b, 0);
function sum_2(a, b) {
    return accumulate_iter(function(x,y) { return x+y }, identity, a, inc, b, 0)
}
// function times(a, b) { return a * b; }
// product: accumulate_iter(times, identity, a, inc, b, 1);
function product_2(a, b) {
   return accumulate_iter(multiply, identity, a, inc, b, 1)
}

// Exercise 1.33
function filtered_accumulate(combiner, nullValue, term, a, next, b, pred) {
   if (a > b)
      return nullValue;
   else if (pred(a))
      return combiner(term(a), filtered_accumulate(combiner, nullValue, term, next(a), next, b, pred));
   else
      return filtered_accumulate(combiner, nullValue, term, next(a), next, b, pred);
}

// a.
filtered_accumulate(plus, 0, square, 1, inc, 5, prime);  // 39

// b. Not sure how to implement this without modifying 'filtered_accumulate' to have 'pred'
//    accept two arguments

[edit]

// 1.3.2 Formulating Abstractions with Higher-Order Procedures - Constructing Procedures Using Lambda

function pi_sum_2(a, b) {
   return sum(
      function(x) { return 1.0 / (x * (x + 2.0)); },
      a,
      function(x) { return x + 4.0 },
      b);
}

function integral_1(f, a, b, dx) {
   return sum(f, a + (dx / 2.0), function(x) { return x + dx; }, b) * dx;
}

function plus4(x) { return x + 4; }

plus4_1 = function(x) { return x + 4; }

print ((function(x, y, z) { return x + y + square(z) }) (1, 2, 3));

// Using let
function f_1(x, y) {
   function f_helper(a, b) {
      return x*square(a) + y*b + a*b;
   }
   return f_helper(1 + x*y, 1 - y)
}

function f_2(x, y) {
   return (function(a, b) { return x*square(a) + y*b + a*b; }) (1 + x*y, 1 - y);
}

function f_3(x, y) {
   a = 1 + x*y;
   b = 1 - y;
   return x*square(a) + y*b + a*b;
}

// javascript does not have let binding - used lambda to emulate
var x = 5;
print (function() {
         var x = 3;
         return x + (x * 10);
       }() + x);

var x = 2;
print (function(x) {
         var y = x + 2;
         var x = 3;
         return x * y;
       }(x));

function f_4(x, y) {
   a = 1 + x*y;
   b = 1 - y;
   return x*square(a) + y*b + a*b;
}

// Exercise 1.34
function f_5(g) { return g(2); }
print (f_5(square));
print (f_5(function(z) { return z * (z + 1) } ));

[edit]

// 1.3.3 Formulating Abstractions with Higher-Order Procedures - Procedures as General Methods


// Half-interval method
function close_enough(x, y) {
   return abs(x - y) < 0.001;
}

function positive(x) { return x >= 0.0; }
function negative(x) { return !(positive(x)); }

function search(f, neg_point, pos_point) {
   midpoint = average(neg_point, pos_point);
   if (close_enough(neg_point, pos_point))
      return midpoint;
   else
      test_value = f(midpoint);
      if (positive(test_value))
         return search(f, neg_point, midpoint);
      else if (negative(test_value))
         return search(f, midpoint, pos_point);
      else
         return midpoint;
}

function half_interval_method(f, a, b) {
   a_value = f(a);
   b_value = f(b);
   if (negative(a_value) && positive(b_value))
      return search(f, a, b);
   else if (negative(b_value) && positive(a_value))
      return search(f, b, a);
   else
      throw ("Exception: Values are not of opposite sign " + a + " " + b);
}

print (half_interval_method(Math.sin, 2.0, 4.0));

print (half_interval_method(function(x) { return x*x*x - 2.0*x - 3.0; }, 1.0, 2.0));

// Fixed points
tolerance = 0.00001

function fixed_point(f, first_guess) {
   function close_enough(v1, v2) {
      return abs(v1 - v2) < tolerance;
   }
   function tryit(guess) {
      next = f(guess);
      if (close_enough(guess, next))
         return next;
      else
         return tryit(next);
   }
   return tryit(first_guess);
}

print (fixed_point(Math.cos, 1.0));

print (fixed_point(function(y) { return Math.sin(y) + Math.cos(y); }, 1.0));

// note: this function does not converge
function sqrt_4(x) {
   return fixed_point(function(y) { return parseFloat(x) / y; }, 1.0)
}

function sqrt_5(x) {
   return fixed_point(function(y) { return average(y, parseFloat(x) / y); }, 1.0)
}

// Exercise 1.35
function golden_ratio() {
   return fixed_point(function(x) { return 1.0 + 1.0 / x; }, 1.0);
}

// Exercise 1.36
// Add the following line to function, 'fixed_point':
//  ... var next = f(guess);
//  print(next);
//  ... if (close_enough(guess, next))
// -- 35 guesses before convergence
print(fixed_point(function(x) { return Math.log(1000.0) / Math.log(x); }, 1.5));
// -- 11 guesses before convergence (average_damp defined below)
print(fixed_point(average_damp(function(x) { return Math.log(1000.0) / Math.log(x); }), 1.5));

// Exercise 1.37
// exercise left to reader to define cont_frac
// cont_frac(function(i) { return 1.0; }, function(i) { return 1.0; }, k)

// Exercise 1.38 - unfinished

// Exercise 1.39 - unfinished

[edit]

// 1.3.4 Formulating Abstractions with Higher-Order Procedures - Procedures as Returned Values

function average_damp(f) {
   return function(x) { return average(parseFloat(x), f(x)); }
}

print ((average_damp(square)) (10.0));

function sqrt_6(x) {
   return fixed_point(average_damp(function(y) { return parseFloat(x) / y; }), 1.0);
}

function cube_root(x) {
   return fixed_point(average_damp(function(y) { return parseFloat(x) / square(y); }), 1.0)
}

print (cube_root(8));

// Newton's method
dx = 0.00001
function deriv(g) {
   return function(x){ return parseFloat(g(x + dx) - g(x)) / dx; };
}

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

print (deriv(cube_2) (5.0));

function newton_transform(g) {
   return function(x) { return x - (parseFloat(g(x)) / (deriv(g) (x))); };
}

function newtons_method(g, guess) {
   return fixed_point(newton_transform(g), guess);
}

function sqrt_7(x) {
   return newtons_method(function(y) { return square(y) - x; } , 1.0);
}

// Fixed point of transformed function
function fixed_point_of_transform(g, transform, guess) {
   return fixed_point(transform(g), guess);
}

function sqrt_8(x) {
   return fixed_point_of_transform(function(y) { return x / y; }, average_damp, 1.0);
}

function sqrt_9(x) {
   return fixed_point_of_transform(function(y) { return square(y) - x; }, newton_transform, 1.0)
}

// Exercise 1.40
function cubic(a, b, c) {
   return function(x) { return x*x*x + a*x*x + b*x + c; };
}

print(newtons_method(cubic(5.0, 3.0, 2.5), 1.0)); // -4.452...

// Exercise 1.41
function double_(f) {
   return function(x) { return f(f(x)); };
}
print((double_(inc))(5));                         //  7
print((double_(double_(inc)))(5));                //  9
print((double_(double_(double_(inc))))(5));       // 13

// Exercise 1.42
function compose_(f, g) {
   return function(x) { return f(g(x)); };
}
print((compose_(square, inc))(6));                // 49

// Exercise 1.43
function repeated(f, n) {
   function iterate(arg, i) {
      if (i > n)
         return arg;
      else
         return iterate(f(arg), i + 1);
   }

   return function(x) { return iterate(x, 1); };
}
print((repeated(square, 2))(5));                  // 625

// Exercise 1.44 ('n-fold-smooth' not implemented)
function smooth(f, dx) {
   return function(x) { return average(x, (f(x-dx) + f(x) + f(x+dx)) / 3.0); };
}
print(fixed_point(smooth(function(x) { return Math.log(1000.0) / Math.log(x); }, 0.05), 1.5));

// Exercise 1.45 - unfinished

// Exercise 1.46 ('sqrt' not implemented)
function iterative_improve(good_enough, improve) {
   function iterate_(guess) {
      var next = improve(guess);
      if (good_enough(guess, next))
         return next;
      else
         return iterate_(next);
   }
   return function(x) { return iterate_(x); };
}
function fixed_point_(f, first_guess) {
   var tolerance = 0.00001;
   function good_enough(v1, v2) {
      return Math.abs(v1 - v2) < tolerance;
   }
   return (iterative_improve(good_enough, f))(first_guess);
}
print(fixed_point_(average_damp(function(x) { return Math.log(1000.0) / Math.log(x); }), 1.5));

// Note:  Must be careful using lexical scoping in JavaScript.
// The following will print "after"
var vx = "before";
function fv() { return vx; }
var vx = "after";
print (fv());

// The following will print "second" two times
function fg() { return "first"; }
print(fg());
function fg() { return "second"; }
print(fg());

Retrieved from "http://www.codepoetics.com/wiki/index.php?title=Topics:SICP_in_other_languages:JavaScript:Chapter_1"

This page has been accessed 2019 times. This page was last modified 03:01, 7 Nov 2007.