Topics:SICP in other languages:JavaScript:Chapter 2
From CTMWiki
| Table of contents |
[edit]
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/
[edit]
SICP Chapter #02 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; }
function insert(x, xs) {
var rt = xs.slice(0)
rt.unshift(x);
return rt;
}
function isArray(x) {
if (x == null) return false;
if (typeof(x) != 'object') return false;
if (typeof(x.length) != 'number') return false;
if (typeof(x.join) != 'function') return false;
if (typeof(x.sort) != 'function') return false;
if (typeof(x.reverse) != 'function') return false;
if (typeof(x.concat) != 'function') return false;
if (typeof(x.pop) != 'function') return false;
if (typeof(x.push) != 'function') return false;
if (typeof(x.shift) != 'function') return false;
if (typeof(x.slice) != 'function') return false;
if (typeof(x.splice) != 'function') return false;
if (typeof(x.unshift) != 'function') return false;
return true;
}
// Functions defined in previous chapters
function gcd(a, b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
function fib(n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
function identity(x) { return x; }
[edit]
// 2 Building Abstractions with Data
function linear_combination(a, b, x, y) {
return a*x + b*y;
}
function mul(a, b) { return a * b }
function linear_combination1(a, b, x, y) {
return mul(a, x) + mul(b, y)
}
[edit]
// 2.1.1 Introduction to Data Abstraction - Example: Arithmetic Operations for Rational Numbers
// Literal Translation //
function make_rat(n, d) { return [n, d]; }
function numer(items) { return items[0]; }
function denom(items) { return items[1]; }
function add_rat(x, y) {
return make_rat(numer(x)*denom(y) + numer(y)*denom(x), denom(x)*denom(y));
}
function sub_rat(x, y) {
return make_rat(numer(x)*denom(y) - numer(y)*denom(x), denom(x)*denom(y));
}
function mul_rat(x, y) {
return make_rat(numer(x)*numer(y), denom(x)*denom(y));
}
function div_rat(x, y) {
return make_rat(numer(x)*denom(y), denom(x)*numer(y));
}
function equal_rat(x, y) {
return numer(x)*denom(y) == numer(y)*denom(x);
}
function cons(x, y) { return [x, y]; }
function car(items) { return items[0] }
function cdr(items) { return items[1] }
x = cons(1, 2);
print (car(x));
print (cdr(x));
x = cons(1, 2);
y = cons(3, 4);
z = cons(x, y);
print (car(car(z)));
print (car(cdr(z)));
print (z);
//footnote // alternative definitions
make_rat1 = cons;
numer1 = car;
denom1 = cdr;
x = [1, 2];
y = [3, 4];
print (numer(x));
print (denom(x));
function compose(f, g) { return function(x) { return f(g(x)); }; }
function print_rat(x) {
print (numer(x) + "/" + denom(x));
}
one_half = make_rat(1,2);
print_rat(one_half);
one_third = make_rat(1, 3);
print_rat(add_rat(one_half, one_third));
print_rat(mul_rat(one_half, one_third));
print_rat(add_rat(one_third, one_third));
// reducing to lowest terms in constructor
function make_rat2(n, d) {
var g = gcd(n, d);
return [n / g, d / g];
}
function add_rat2(x, y) {
return make_rat2(numer(x)*denom(y) + numer(y)*denom(x), denom(x)*denom(y));
}
print_rat(add_rat2(one_third, one_third));
// end Literal Translation //
// Record Translation //
function make_rat_rec(n, d) {
return new function() { this.numer = n; this.denom = d; };
}
function add_rat_rec(x, y) {
return make_rat_rec(x.numer*y.denom + y.numer*x.denom, x.denom*y.denom);
}
function sub_rat_rec(x, y) {
return make_rat_rec(x.numer*y.denom - y.numer*x.denom, x.denom*y.denom);
}
function mul_rat_rec(x, y) {
return make_rat_rec(x.numer*y.numer, x.denom*y.denom);
}
function div_rat_rec(x, y) {
return make_rat_rec(x.numer*y.denom, x.denom*y.numer);
}
function equal_rat_rec(x, y) {
return x.numer*y.denom == y.numer*x.denom;
}
function print_rat_rec(x) {
print (x.numer + "/" + x.denom);
}
one_half = make_rat_rec(1,2);
print_rat_rec(one_half);
one_third = make_rat_rec(1, 3);
print_rat_rec(add_rat_rec(one_half, one_third));
print_rat_rec(mul_rat_rec(one_half, one_third));
print_rat_rec(add_rat_rec(one_third, one_third));
// reducing to lowest terms in constructor
function make_rat_rec2(n, d) {
var g = gcd(n, d);
return new function() { this.numer = n / g; this.denom = d / g; };
}
function add_rat_rec2(x, y) {
return make_rat_rec2((x.numer * y.denom) + (y.numer * x.denom), x.denom * y.denom);
}
print_rat_rec(add_rat_rec2(one_third, one_third));
// end Record Translation //
// Object Translation //
function Rational(n, d) {
this.numer = n;
this.denom = d;
this.add_rat = function(y) {
return new Rational(this.numer*y.denom + y.numer*this.denom, this.denom*y.denom);
};
this.sub_rat = function(y) {
return new Rational(this.numer*y.denom - y.numer*this.denom, this.denom*y.denom);
};
this.mul_rat = function(y) {
return new Rational(this.numer*y.numer, this.denom*y.denom);
};
this.div_rat = function(y) {
return new Rational(this.numer*y.denom, this.denom*y.numer);
};
this.equal_rat = function(y) {
return this.numer*y.denom == y.numer * this.denom;
};
this.print_rat = function() {
print (this.numer + "/" + this.denom);
};
}
one_half = new Rational(1, 2);
one_half.print_rat();
one_third = new Rational(1, 3);
one_half.add_rat(one_third).print_rat();
one_half.mul_rat(one_third).print_rat();
one_third.add_rat(one_third).print_rat();
// reducing to lowest terms in constructor
function Rational2(n, d) {
var g = gcd(n, d);
this.numer = n / g;
this.denom = d / g;
this.add_rat = function(y) {
return new Rational2(this.numer*y.denom + y.numer*this.denom, this.denom*y.denom);
};
this.sub_rat = function(y) {
return new Rational2(this.numer*y.denom - y.numer*this.denom, this.denom*y.denom);
};
this.mul_rat = function(y) {
return new Rational2(this.numer*y.numer, this.denom*y.denom);
};
this.div_rat = function(y) {
return new Rational2(this.numer*y.denom, this.denom*y.numer);
};
this.equal_rat = function(y) {
return this.numer*y.denom == y.numer * this.denom;
};
this.print_rat = function() {
print (this.numer + "/" + this.denom);
}
}
one_third = new Rational2(1, 3);
one_third.print_rat();
one_third.add_rat(one_third).print_rat();
// end Object Translation //
// Class Translation - ES4 //
class Rational3 {
var numer;
var denom;
function Rational3(n, d) {
numer = n;
denom = d;
}
function add_rat(y) {
return new Rational3(numer*y.denom + y.numer*denom, denom*y.denom);
}
function sub_rat(y) {
return new Rational3(numer*y.denom - y.numer*denom, denom*y.denom);
}
function mul_rat(y) {
return new Rational3(numer*y.numer, denom*y.denom);
}
function div_rat(y) {
return new Rational3(numer*y.denom, denom*y.numer);
}
function equal_rat(y) {
return this.numer*y.denom == y.numer * denom;
}
function print_rat() {
print (numer + "/" + denom);
}
}
one_half = new Rational3(1, 2);
one_half.print_rat();
one_third = new Rational3(1, 3);
one_half.add_rat(one_third).print_rat();
one_half.mul_rat(one_third).print_rat();
one_third.add_rat(one_third).print_rat();
// reducing to lowest terms in constructor
class Rational4 {
var numer;
var denom;
function Rational4(n, d) {
var g = gcd(n, d);
numer = n / g;
denom = d / g;
}
function add_rat(y) {
return new Rational4(numer*y.denom + y.numer*denom, denom*y.denom);
}
function sub_rat(y) {
return new Rational4(numer*y.denom - y.numer*denom, denom*y.denom);
}
function mul_rat(y) {
return new Rational4(numer*y.numer, denom*y.denom);
}
function div_rat(y) {
return new Rational4(numer*y.denom, denom*y.numer);
}
function equal_rat(y) {
return this.numer*y.denom == y.numer * denom;
}
function print_rat() {
print (numer + "/" + denom);
}
}
one_third = new Rational4(1, 3);
one_third.print_rat();
one_third.add_rat(one_third).print_rat();
// end Class Translation //
// Exercise 2.1
function make_rat3(n, d) {
if ((d < 0 && n < 0) || n < 0)
return new function() { this.numer = d * -1; this.denom = n * -1; };
else
return new function() { this.numer = d; this.denom = n; };
}
[edit]
// 2.1.2 Introduction to Data Abstraction - Abstraction barriers
// Record Translation //
// reducing to lowest terms in selectors
function make_rat4(n, d) {
return new function() { this.numer = d; this.denom = n; };
}
function numer4(x) {
var g = gcd(x.numer, x.denom)
return x.numer / g
}
function denom4(x) {
var g = gcd(x.numer, x.denom)
return x.denom / g
}
// end Record Translation //
// Object Translation //
// reducing to lowest terms in selectors
function Rational5(n, d) {
this.n = n;
this.d = d;
this.numer = function() {
var g = gcd(this.n, this.d);
return this.n / g;
}
this.denom = function() {
var g = gcd(this.n, this.d);
return this.d / g;
}
this.add_rat = function(y) {
return new Rational5(this.numer()*y.denom() + y.numer()*this.denom(), this.denom()*y.denom());
};
this.sub_rat = function(y) {
return new Rational5(this.numer()*y.denom() - y.numer()*this.denom(), this.denom()*y.denom());
};
this.mul_rat = function(y) {
return new Rational5(this.numer()*y.numer(), this.denom()*y.denom());
};
this.div_rat = function(y) {
return new Rational5(this.numer()*y.denom(), this.denom()*y.numer());
};
this.equal_rat = function(y) {
return this.numer()*y.denom() == y.numer() * this.denom();
};
this.print_rat = function() {
print (this.numer() + "/" + this.denom());
}
}
one_third = new Rational5(1, 3);
one_third.print_rat();
one_third.add_rat(one_third).print_rat();
// end Object Translation //
// Class Translation - ES4 //
// reducing to lowest terms in selectors
class Rational6 {
var n;
var d;
function numer() {
var g = gcd(n, d);
return n / g;
}
function denom() {
var g = gcd(n, d);
return d / g;
}
function Rational6(n, d) {
this.n = n;
this.d = d;
}
function add_rat(y) {
return new Rational6(numer()*y.denom() + y.numer()*denom(), denom()*y.denom());
}
function sub_rat(y) {
return new Rational6(numer()*y.denom() - y.numer()*denom(), denom()*y.denom());
}
function mul_rat(y) {
return new Rational6(numer()*y.numer(), denom()*y.denom());
}
function div_rat(y) {
return new Rational6(numer()*y.denom(), denom()*y.numer());
}
function equal_rat(y) {
return this.numer()*y.denom() == y.numer() * denom();
}
function print_rat() {
print (numer() + "/" + denom());
}
}
one_third = new Rational6(1, 3);
one_third.print_rat();
one_third.add_rat(one_third).print_rat();
// end Class Translation //
// Exercise 2.2
function make_point(x, y) {
return new function() { this.x = x; this.y = y; };
}
function make_segment(start_segment, end_segment) {
return new function() { this.start_segment = start_segment; this.end_segment = end_segment; };
}
function midpoint_segment(segment) {
var s = segment.start_segment;
var e = segment.end_segment;
return make_point((s.x + e.x) / 2, (s.y + e.y) / 2);
}
function print_point(p) {
print ("(" + p.x + ", " + p.y + ")");
}
// Exercise 2.3
function square(x) { return x * x; }
function length_segment(segment) {
var s = segment.start_segment;
var e = segment.end_segment;
return Math.sqrt(square(e.x - s.x) + square(e.y - s.y));
}
// Constructors create type tagged using <pair>
function make_rectangle_axy(anchor, xlen, ylen) {
return new function() { this.anchor = anchor; this.xlen = xlen; this.ylen = ylen; };
}
function make_rectangle_seg(start_segment, end_segment) {
return new function() { this.start_segment = start_segment; this.end_segment = end_segment; };
}
x = make_rectangle_axy(10,20);
// 'length_rectangle' and 'width_rectangle' act as an abstraction barrier for higher-level
// procedures because 'rectangle' implementation details are buried here, and should the
// implementation change, only these procedures will need to be altered to support the change
function length_rectangle(rect) {
if (x.anchor != undefined)
return 0; // Compute length ...
else if (x.start_segment != undefined)
return 0; // Compute length ...
}
function width_rectangle(rect) {
// As per 'length_rectangle' except that rectangle width is returned ...
return 0
}
// High-level procedures are quarantined from representation / implementation details
function area_rectangle(rect) {
return length_rectangle(rect) * width_rectangle(rect);
}
function perimeter_rectangle(rect) {
return length_rectangle(rect) * 2 + width_rectangle(rect) * 2;
}
[edit]
// 2.1.3 Introduction to Data Abstraction - What is meant by data?
function cons2(x, y) {
function dispatch(m) {
if (m == 0)
return x
else if (m == 1)
return y
else
throw ("Argument not 1 or 2 // CONS " + m);
}
return dispatch;
}
function car2(z) { return z(0); }
function cdr2(z) { return z(1) }
// Exercise 2.4
function cons3(x, y) {
return function(m) { return m(x, y); }
}
function car3(z) {
return z(function(p, q) { return p; })
}
function cdr3(z) {
return z(function(p, q) {return q; })
}
// Exercise 2.5
function cons4(x, y) {
return Math.pow(2, x * Math.pow(3, y))
}
function car4(z) {
if (z % 2 == 0)
return car4((z / 2) + 1);
else
return 0;
}
function cdr4(z) {
if (z % 3 == 0)
return cdr4((z / 3) + 1);
else
return 0;
}
// Exercise 2.6
zero = function(f) { return function(x) { return x; }; };
function add1(n) {
return function(f) {
return function(x) {
return f(n(f)(x));
};
};
}
[edit]
// 2.1.4 Introduction to Data Abstraction - Extended Exercise: Interval Arithmetic
// Record Translation //
function make_interval(a, b) {
return new function() { this.lower_bound = a; this.upper_bound = b; };
}
function add_interval(x, y) {
return make_interval(x.lower_bound + y.lower_bound, x.upper_bound + y.upper_bound);
}
function mul_interval(x, y) {
var p1 = x.lower_bound * y.lower_bound;
var p2 = x.lower_bound * y.upper_bound;
var p3 = x.upper_bound * y.lower_bound;
var p4 = x.upper_bound * y.upper_bound;
return make_interval(
Math.min(Math.min(p1, p2), Math.min(p3, p4)),
Math.max(Math.max(p1, p2), Math.max(p3, p4)));
}
function div_interval(x, y) {
var z = make_interval(1 / y.upper_bound, 1 / y.lower_bound);
return mul_interval(x, z);
}
function make_center_width(c, w) {
return make_interval(c-w, c+w);
}
function center(interval) {
return (interval.lower_bound + interval.upper_bound) / 2;
}
function width(interval) {
return (interval.upper_bound - interval.lower_bound) / 2;
}
// parallel resistors
function par1(r1, r2) {
return div_interval(mul_interval(r1, r2), add_interval(r1, r2));
}
function par2(r1, r2) {
var one = make_interval(1, 1);
return div_interval(one,
add_interval(div_interval(one, r1),
div_interval(one, r2)));
}
// end Record Translation //
// Object Translation //
function Interval(a, b) {
this.lower_bound = a;
this.upper_bound = b;
this.add_interval = function(y) {
return new Interval(this.lower_bound + y.lower_bound, this.upper_bound + y.upper_bound);
};
this.mul_interval = function(y) {
var p1 = this.lower_bound * y.lower_bound;
var p2 = this.lower_bound * y.upper_bound;
var p3 = this.upper_bound * y.lower_bound;
var p4 = this.upper_bound * y.upper_bound;
return new Interval(
Math.min(Math.min(p1, p2), Math.min(p3, p4)),
Math.max(Math.max(p1, p2), Math.max(p3, p4)));
};
this.div_interval = function(y) {
var z = new Interval(1 / y.upper_bound, 1 / y.lower_bound);
return this.mul_interval(x, z);
};
this.make_center_width = function(c, w) {
return new Interval(c-w, c+w);
};
this.center = function() {
return (this.lower_bound + this.upper_bound) / 2;
};
this.width = function() {
return (this.upper_bound - this.lower_bound) / 2;
}
}
// parallel resistors
function par3(r1, r2) {
return r1.mul_interval(r2).div_interval(r1.add_interval(r2));
}
function par4(r1, r2) {
var one = new Interval(1, 1);
return one.div_interval(one.div_interval(r1).add_interval(one.div_interval(r2)));
}
// end Object Translation //
// Class Translation - ES4 //
class Interval2 {
var lower_bound;
var upper_bound;
function Interval2(a, b) {
lower_bound = a;
upper_bound = b;
}
function add_rat(y) {
return new Rational3(numer*y.denom + y.numer*denom, denom*y.denom);
}
function add_interval(y) {
return new Interval(lower_bound + y.lower_bound, upper_bound + y.upper_bound);
}
function mul_interval(y) {
var p1 = lower_bound * y.lower_bound;
var p2 = lower_bound * y.upper_bound;
var p3 = upper_bound * y.lower_bound;
var p4 = upper_bound * y.upper_bound;
return new Interval(
Math.min(Math.min(p1, p2), Math.min(p3, p4)),
Math.max(Math.max(p1, p2), Math.max(p3, p4)));
}
function div_interval(y) {
var z = new Interval(1 / y.upper_bound, 1 / y.lower_bound);
return mul_interval(x, z);
}
function make_center_width(c, w) {
return new Interval(c-w, c+w);
}
function center() {
return (lower_bound + upper_bound) / 2;
}
function width() {
return (upper_bound - lower_bound) / 2;
}
}
// parallel resistors
function par5(r1, r2) {
return r1.mul_interval(r2).div_interval(r1.add_interval(r2));
}
function par6(r1, r2) {
var one = new Interval(1, 1);
return one.div_interval(one.div_interval(r1).add_interval(one.div_interval(r2)));
}
// end Class Translation //
// Exercise 2.8
function sub_interval(x, y) {
return make_interval(x.lower_bound - y.lower_bound, x.upper_bound - y.upper_bound);
}
// Exercise 2.9
i = make_interval(5, 10);
j = make_interval(15, 25);
// width of the sum (or difference) of two intervals *is* a function only of the widths of
// the intervals being added (or subtracted)
print (width(add_interval(i, j)) + " " + width(i) + " " + width(j));
print (width(sub_interval(i, j)) + " " + width(i) + " " + width(j));
// width of the product (or quotient) of two intervals *is not* a function only of the widths
// of the intervals being multiplied (or divided)
print (width(mul_interval(i, j)) + " " + width(i) + " " + width(j));
print (width(div_interval(i, j)) + " " + width(i) + " " + width(j));
// Exercise 2.10
function is_zero_interval(i) {
return i.lower_bound == 0 || i.upper_bound == 0;
}
function div_interval_zero_check(x, y) {
if (is_zero_interval(y))
throw("Zero interval divisor");
else
return div_interval(x, y);
}
// Exercise 2.12
function make_center_percent(c, p) {
return make_center_width(c, p * c / 100);
}
function percent(i) {
return width(i) / center(i) * 100;
}
[edit]
// 2.2.1 Hierarchical Data and the Closure Property - Representing Sequences
one_through_four = [1, 2, 3, 4];
print (one_through_four);
print (one_through_four[0]);
print (one_through_four.slice(1));
print (one_through_four[1]);
print (insert(10, one_through_four));
function list_ref(items, n) {
return items[n];
}
squares = [1, 4, 9, 16, 25];
print (list_ref(squares, 3));
function length(items) {
return items.length;
}
odds = [1, 3, 5, 7];
print (length(odds));
function append(xs, ys) {
var rt = xs.slice(0);
for (key in ys) {
rt.push(ys[key]);
}
return rt;
}
print (append(squares, odds));
print (append(odds, squares));
// throws exception in ES4 reference implementation
//print (squares.concat(odds));
//print (odds.concat(squares));
// Mapping over lists
function scale_list(factor, items) {
var rt = [];
for (key in items) {
rt.push(items[key] * factor);
}
return rt;
}
print (scale_list(10, [1, 2, 3, 4, 5]));
// uncurried version of map
function map(proc, items) {
var rt = [];
for (key in items) {
rt.push(proc(items[key]));
}
return rt;
}
print (map(Math.abs, [-10, 2.5, -11.6, 17]));
print (map(function(x) { return x * x; }, [1, 2, 3, 4]));
function scale_list2(factor, items) {
return map(function(x) { return x * factor; }, items);
}
// curried version map
function mapc(proc) {
function map_lambda(items) {
var rt = [];
for (key in items) {
rt.push(proc(items[key]));
}
return rt;
}
return map_lambda;
}
print (mapc (Math.abs) ([-10, 2.5, -11.6, 17]));
print (mapc (function(x) { return x * x; }) ([1, 2, 3, 4]));
function scale_list(factor, items) {
return mapc (function(x) { return x * factor; }) (items);
}
// Exercise 2.17
function last_pair(items) {
return items[items.length-1];
}
print (last_pair([23, 72, 149, 34]));
// Exercise 2.18
function reverse(items) {
var rt = [];
for (var i = items.length-1; i >= 0; i--) {
rt.push(items[i]);
}
return rt;
}
print (reverse([1, 4, 9, 16, 25]));
function reverse2(items) {
var rt = items.slice(0);
rt.reverse();
return rt;
}
print (reverse2([1, 4, 9, 16, 25]));
// Exercise 2.19
function no_more(items) {
return items.length == 0;
}
function except_first_denomination(coin_values) {
var tail = coin_values.slice(1);
return tail;
}
function first_denomination(coin_values) {
var head = coin_values[0];
return head;
}
function cc(amount, coin_values) {
if (amount == 0)
return 1;
else if (amount < 0 || no_more(coin_values))
return 0;
else
return cc(amount, except_first_denomination(coin_values)) +
cc(amount - first_denomination(coin_values), coin_values);
}
us_coins = [50, 25, 10, 5, 1];
uk_coins = [100, 50, 20, 10, 5, 2, 1, 0.5];
// works but takes a long time based on inefficiency above (slice)
// print (cc(100, us_coins));
// print (cc(100, uk_coins));
// Exercise 2.20
function filter1(predicate, items) {
var rt = [];
for (key in items) {
if (predicate(items[key])) {
rt.push(items[key]);
}
}
return rt;
}
function is_odd(n) { return n % 2 == 1; }
function is_even(n) { return !is_odd(n); }
function same_parity(items) {
var head = items[0];
var tail = items.slice(1);
var predicate = is_odd(head) ? is_odd : is_even;
return filter1(predicate, tail);
}
print (same_parity([1, 2, 3, 4, 5, 6, 7]));
print (same_parity([2, 3, 4, 5, 6, 7]));
// Exercise 2.21
function square_list(items) {
rt = [];
for (key in items) {
rt.push(items[key] * items[key]);
}
return rt;
}
print (square_list([1, 2, 3, 4]));
function square_list(items) {
return mapc (function(x) { return x * x; }) (items);
}
print (square_list([1, 2, 3, 4]));
// Exercise 2.23
function for_each(f, items) {
for (key in items) {
f(items[key]);
}
}
[edit]
// 2.2.2 Hierarchical Data and the Closure Property - Hierarchical Structures
function count_leaves(items) {
var n = 0;
for (key in items) {
if (isArray(items[key]))
n += count_leaves(items[key]);
else
n += 1;
}
return n;
}
x = [[1, 2], [3, 4]];
print (x.length);
print (count_leaves(x));
print ([x, x]);
print ([x, x].length);
print (count_leaves([x, x]));
// Mapping over trees
function scale_tree(factor, items) {
var rt = [];
for (key in items) {
if (isArray(items[key]))
rt.push(scale_tree(factor, items[key]));
else
rt.push(factor * items[key]);
}
return rt;
}
print (scale_tree(10, [1, [2, [3, 4], 5], [6, 7]]));
function scale_tree(factor, items) {
return mapc(
function(sub_tree) {
if (isArray(sub_tree))
return scale_tree(factor, sub_tree);
else
return sub_tree * factor;
}
) (items);
}
print (scale_tree(10, [1, [2, [3, 4], 5], [6, 7]]));
// Exercise 2.24
print ([1, [2, [3, 4]]]);
// Exercise 2.25
print ([1, 3, [5, 7], 9]);
print ([[7]]);
print ([1, [2, [3, [4, [5, [6, 7]]]]]]);
// Exercise 2.26
x = [1, 2, 3];
y = [4, 5, 6];
print (append(x, y));
print ([x, y]);
// Exercise 2.27
function deep_reverse(items) {
var rt = []
for (var i = items.length-1; i >= 0; i--) {
if (isArray(items[key]))
rt.push(deep_reverse(items[i]));
else
rt.push(items[i]);
}
return rt;
}
x = [[1, 2], [3, 4]];
print (x);
print (reverse(x));
print (deep_reverse(x));
// Exercise 2.28
function fringe(items) {
var rt = [];
for (key in items) {
if (isArray(items[key])) {
var xs = fringe(items[key]);
for (key2 in xs) {
rt.push(xs[key2]);
}
} else {
rt.push(items[key]);
}
}
return rt;
}
x = [[1, 2], [3, 4]]
print (fringe(x))
print (fringe([x, x]))
// Exercise 2.29
// List-based representation
// a.
function make_mobile(left, right) {
return new function() { this.left = left; this.right = right; };
}
function make_branch(length, struc) {
return new function() { this.length = length; this.struc = struc; };
}
// Helpers for b. and c.
function branch_weight(branch) {
if (branch.length == 0)
return 0;
else if (isArray(branch))
return branch_weight(branch.struct);
else
return branch.struc;
}
function total_branch_length(branch) {
if (branch.length == 0)
return 0;
else if (isArray(branch))
return branch.length + total_branch_length(branch.struc);
else
return branch.length;
}
// b.
function total_weight(mobile) {
return branch_weight(mobile.left) + branch_weight(mobile.right);
}
// c. [Not as per specification]
function is_mobile_balanced(mobile) {
var lmwl = total_branch_length(mobile.left) * branch_weight(mobile.left);
var rmwl = total_branch_length(mobile.right) * branch_weight(mobile.right);
return lmwl == rmwl;
}
// Exercise 2.30
function square_tree(items) {
var rt = [];
for (key in items) {
if (isArray(items[key]))
rt.push(square_tree(items[key]));
else
rt.push(items[key]*items[key]);
}
return rt;
}
print (square_tree([1, [2, [3, 4], 5], [6, 7]]));
// Exercise 2.31
function tree_map(items, proc) {
var rt = [];
for (key in items) {
if (isArray(items[key]))
rt.push(tree_map(items[key], proc))
else
rt.push(proc(items[key]));
}
return rt;
}
function square_tree(items) {
return tree_map(items, function(x) { return x * x; });
}
print (square_tree([1, [2, [3, 4], 5], [6, 7]]));
// Exercise 2.32
function subsets(items) {
if (items.length == 0) {
return [[]];
} else {
var head = items[0];
var tail = items.slice(1);
var rest = subsets(tail);
return append(rest, mapc (function(x) { return append([head], x); }) (rest));
}
}
print (subsets([1, 2, 3]));
[edit]
// 2.2.3 Hierarchical Data and the Closure Property - Sequences as Conventional Interfaces
function is_odd(n) { return n % 2 == 1; }
function is_even(n) { return !is_odd(n); }
function square(x) { return x * x; }
function sum_odd_squares(items) {
var sum = 0;
for (key in items) {
if (isArray(items[key]))
sum += sum_odd_squares(items[key]);
else if (is_odd(items[key]))
sum = sum + square(items[key]);
}
return sum;
}
function even_fibs(n) {
var rt = [];
for (var i = 0; i < n; i++) {
var f = fib(i);
if (is_even(f))
rt.push(f);
}
return rt;
}
print (even_fibs(10));
// Sequence operations
print (mapc (square) ([1,2,3,4,5]));
// non-curried version of filter
function filter(predicate, items) {
var rt = [];
for (key in items) {
if (predicate(items[key]))
rt.push(items[key]);
}
return rt;
}
print (filter(is_odd, [1,2,3,4,5]));
// curried version of filter
function filterc(predicate) {
function filter_lambda(items) {
var rt = [];
for (key in items) {
if (predicate(items[key]))
rt.push(items[key]);
}
return rt;
}
return filter_lambda;
}
print (filterc (is_odd) ([1,2,3,4,5]))
// non-curried version of accumulate (aka foldl)
function accumulate(oper, initial, items) {
var rt = initial;
for (key in items) {
rt = oper(items[key], rt);
}
return rt;
}
function construct(x, items) {
rt = items.slice(0);
rt.push(x);
return rt;
}
print (accumulate(function(x,y) { return x+y; }, 0, [1,2,3,4,5]));
print (accumulate(function(x,y) { return x*y; }, 1, [1,2,3,4,5]));
print (accumulate(construct, [], [1,2,3,4,5]));
// curried version of accumulate (aka foldl)
function accumulatec(oper) {
function initial_lambda(initial) {
function sequence_lambda(items) {
var rt = initial
for (key in items) {
rt = oper(items[key], rt);
}
return rt;
}
return sequence_lambda;
}
return initial_lambda;
}
print (accumulatec (function(x,y) { return x+y }) (0) ([1,2,3,4,5]));
print (accumulatec (function(x,y) { return x*y }) (1.0) ([1,2,3,4,5]));
print (accumulatec (construct) ([]) ([1,2,3,4,5]));
function enumerate_interval(low, high) {
var rt = [];
for (var i = low; i <= high; i++) {
rt.push(i);
}
return rt;
}
print (enumerate_interval(2,7));
function enumerate_tree(items) {
var rt = [];
for (key in items) {
if (isArray(items[key])) {
var xs = fringe(items[key]);
for (key2 in xs) {
rt.push(xs[key2]);
}
} else {
rt.push(items[key]);
}
}
return rt;
}
print (enumerate_tree([1, [2, [3, 4], 5]]));
function sum_odd_squares2(tree) {
return (
accumulatec (
function(x,y) { return x+y; })
(0)
(mapc (square) (filterc (is_odd) (enumerate_tree(tree)))));
}
function even_fibs2(n) {
return accumulatec (construct) ([]) (filterc (is_even) (mapc (fib) (enumerate_interval(0, n))));
}
function list_fib_squares(n) {
return accumulatec (construct) ([]) (mapc (square) (mapc (fib) (enumerate_interval(0, n))));
}
print (list_fib_squares(10));
function product_of_squares_of_odd_elements(sequence) {
return accumulatec (function(x,y) { return x*y }) (1) (mapc (square) (filterc (is_odd) (sequence)));
}
print (product_of_squares_of_odd_elements([1,2,3,4,5]));
function Employee(init_empname, init_jobtitle, init_salary) {
this.empname = init_empname;
this.jobtitle = init_jobtitle;
this.salary = init_salary;
}
function isProgrammer(emp) {
return emp.jobtitle == "Programmer";
}
function getSalary(emp) {
return emp.salary;
}
function salary_of_highest_paid_programmer(records) {
return accumulatec (Math.max) (0) (mapc (getSalary) (filterc (isProgrammer) (records)));
}
recs = [new Employee("Fred", "Programmer", 180),
new Employee("Hank", "Programmer", 150)]
print (salary_of_highest_paid_programmer(recs));
// Nested mappings
n = 5 // book doesn't define n
print (accumulatec
(append)
([])
(mapc
(function(i) {
return mapc (function(j) { return [i,j]; }) (enumerate_interval(1, i-1))
})
(enumerate_interval(1, n))));
function flatmap(proc) {
return (
function(seq) {
return accumulatec (append) ([]) (mapc (proc) (seq));
})
}
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 prime_sum(pair) {
return is_prime(pair[0] + pair[1]);
}
function make_pair_sum(pair) {
return [pair[0], pair[1], pair[0] + pair[1]];
}
function prime_sum_pairs(n) {
return (
mapc (make_pair_sum)
(filterc
(prime_sum)
(flatmap
(function(i) { return mapc (function(j) { return [i,j]; }) (enumerate_interval(1, i-1)) })
(enumerate_interval(1, n)))));
}
print (prime_sum_pairs(10));
function remove(item, sequence) {
return filterc (function(x) { return x != item; }) (sequence);
}
function permutations(items) {
if (items.length == 0)
return [[]];
else
return (
flatmap
(function(x) {
return mapc (function(a) { return append(a, [x]); }) (permutations(remove(x, items)));
})
(items));
}
print (permutations([1,2,3]));
// Exercise 2.34
// exercise left to reader to define appropriate functions
// function horner_eval(x, coefficient_sequence) {
// return accumulatec (function(this_coeff, higher_terms) { return ??FILL_THIS_IN??; }) (0) (coefficient_sequence);
// }
// horner_eval(2, [1,3,0,5,0,1]));
// Exercise 2.36
// exercise left to reader to define appropriate functions
// function accumulate_n(oper) {
// function initial_lambda(initial) {
// function sequence_lambda(sequence) {
// if (sequence.length == 0)
// return initial;
// else
// return [accumulatec (oper) (init) (??FILL_THIS_IN??),
// accumulate_n (oper) (init) (??FILL_THIS_IN??)];
// }
// return sequence_lambda;
// }
// return initial_lambda;
// }
// accumulate_n (function(x,y) { return x + y; }) (0) (s)
// Exercise 2.38
foldc_right = accumulatec
function foldc_left(oper) {
function initial_lambda(initial) {
function sequence_lambda(items) {
var rt = initial
for (var i = items.length-1; i >= 0; i--) {
rt = oper(rt, items[i]);
}
return rt;
}
return sequence_lambda;
}
return initial_lambda;
}
print (foldc_right (function(x,y) { return x/y; }) (1.0) ([1,2,3]));
print (foldc_left (function(x,y) { return x/y; }) (1.0) ([1,2,3]));
print (foldc_right (construct) ([]) ([1,2,3]));
print (foldc_left (function(x,y) { return construct(y,x); }) ([]) ([1,2,3]));
// Exercise 2.42
// exercise left to reader to define appropriate functions
// function queens(board_size) {
// function queen_cols(k) {
// if (k == 0)
// return [empty_board];
// else
// return (
// filterc
// (function(positions) { return isSafe(k, positions); })
// (flatmap
// (function(rest_of_queens) {
// return (
// mapc
// (function(new_row) { return adjoin_position(new_row, k, rest_of_queens); })
// (enumerate_interval(1, board_size)));
// })
// (queen_cols(k-1))));
// }
// return queen_cols(board_size);
// }
// Exercise 2.43
// exercise left to reader to define appropriate functions
// function queens(board_size) {
// function queen_cols(k) {
// if (k == 0)
// return [empty_board];
// else
// return (
// filterc
// (function(positions) { return isSafe(k, positions); })
// (flatmap
// (function(new_row) {
// return (
// mapc
// (function(rest_of_queens) { return adjoin_position(new_row, k, rest_of_queens); })
// (queen_cols(k-1)));
// }) (
// enumerate_interval(1, board_size))))
// }
// return queen_cols(board_size);
// }
[edit]
// 2.2.4 Hierarchical Data and the Closure Property - Example: a picture language
// these two routines are to be written
function draw_line(x, y) { }
function wave(xframe) { return xframe; }
function Vect(x, y) {
return new function() { this.x = x; this.y = y; };
}
function make_vect(x, y) { return new Vect(x, y); }
function xcor_vect(v) { return v.x; }
function ycor_vect(v) { return v.y; }
function add_vect(v1, v2) {
return make_vect(xcor_vect(v1) + xcor_vect(v2), ycor_vect(v1) + ycor_vect(v2));
}
function sub_vect(v1, v2) {
return make_vect(xcor_vect(v1) - xcor_vect(v2), ycor_vect(v1) - ycor_vect(v2));
}
function scale_vect(s, v) {
return make_vect(s * xcor_vect(v), s * ycor_vect(v));
}
function Frame(orig, edge1, edge2) {
return new function() { this.orig = orig; this.edge1 = edge1; this.edge2 = edge2; };
}
function make_frame(origin, edge1, edge2) {
return new Frame(origin, edge1, edge2);
}
function origin_frame(f) { return f.orig; }
function edge1_frame(f) { return f.edge1; }
function edge2_frame(f) { return f.edge2; }
a_frame = make_frame(make_vect(0, 0), make_vect(1, 0), make_vect(0, 1));
function Segment(x, y) {
return new function() { this.x = x; this.y = y; };
}
function start_segment(seg) { return seg.x; }
function end_segment(seg) { return seg.y; }
// Frames
function frame_coord_map(xframe, v) {
return add_vect(
origin_frame(xframe),
add_vect(scale_vect(xcor_vect(v), edge1_frame(xframe)),
scale_vect(ycor_vect(v), edge2_frame(xframe))));
}
frame_coord_map(a_frame, make_vect(0, 0));
origin_frame(a_frame);
// Painters
function foreach(f) {
function foreach_lambda(items) {
for (key in items) {
f(items[key]);
}
}
return foreach_lambda;
}
function segments_painter(segment_list, xframe) {
foreach (
function(segment) {
draw_line(
frame_coord_map (xframe) (start_segment, segment),
frame_coord_map (xframe) (end_segment, segment));
}) (
segment_list);
}
function transform_painter(painter, origin, corner1, corner2) {
function transform_painter_lambda(xframe) {
var m = frame_coord_map(xframe);
var new_origin = m(origin);
return painter(
make_frame(
new_origin,
sub_vect(m(corner1), new_origin),
sub_vect(m(corner2), new_origin)));
}
return transform_painter_lambda;
}
function flip_vert(painter) {
return transform_painter(
painter,
make_vect(0, 1),
make_vect(1, 1),
make_vect(0, 0));
}
function flip_horiz(painter) {
return transform_painter(
painter,
make_vect(1, 0),
make_vect(0, 0),
make_vect(1, 1));
}
function shrink_to_upper_right(painter) {
return transform_painter(
painter,
make_vect(0.5, 0.5),
make_vect(1, 0.5),
make_vect(0.5, 1));
}
function rotate90(painter) {
return transform_painter(
painter,
make_vect(1, 0),
make_vect(1, 1),
make_vect(0, 0));
}
function rotate180(painter) {
return transform_painter(
painter,
make_vect(1, 1),
make_vect(0, 1),
make_vect(1, 0));
}
function squash_inwards(painter) {
return transform_painter(
painter,
make_vect(0, 0),
make_vect(0.65, 0.35),
make_vect(0.35, 0.65));
}
function beside(painter1, painter2) {
function beside_lambda(xframe) {
var split_point = make_vect(0.5, 0);
var paint_left = (
transform_painter(
painter1,
make_vect(0, 0),
split_point,
make_vect(0, 1)));
var paint_right = (
transform_painter(
painter2,
split_point,
make_vect(1, 0),
make_vect(0.5, 1)));
paint_left(xframe);
paint_right(xframe);
}
return beside_lambda;
}
function below(painter1, painter2) {
function below_lambda(xframe) {
var split_point = make_vect(0, 0.5);
var paint_below = (
transform_painter(
painter1,
make_vect(0, 0),
make_vect(1, 0),
split_point));
var paint_above = (
transform_painter(
painter2,
split_point,
make_vect(1, 0.5),
make_vect(0, 1)));
paint_below(xframe);
paint_above(xframe);
}
return below_lambda;
}
function up_split(painter, n) {
if (n == 0) {
return painter;
} else {
var smaller = up_split(painter, n-1);
return below(painter, beside(smaller, smaller));
}
}
wave2 = beside(wave, flip_vert(wave));
wave4 = below(wave2, wave);
function flipped_pairs(painter) {
var painter2 = beside(painter, flip_vert(painter));
return below(painter2, painter2);
}
wave4 = flipped_pairs(wave);
function right_split(painter, n) {
if (n == 0) {
return painter;
} else {
var smaller = right_split(painter, n-1);
return beside(painter, below(smaller, smaller));
}
}
function corner_split(painter, n) {
if (n == 0) {
return painter;
} else {
var up = up_split(painter, n-1);
var right = right_split(painter, n-1);
var top_left = beside(up, up);
var bottom_right = below(right, right);
var corner = corner_split(painter, n-1);
return beside(below(painter, top_left), below(bottom_right, corner));
}
}
function square_limit(painter, n) {
var quarter = corner_split(painter, n);
var half = beside(flip_horiz(quarter), quarter);
return below(flip_vert(half), half);
}
// Higher_order operations
function square_of_four(tleft, tright, bleft, bright) {
function square_of_four_lambda(painter) {
var top = beside(tleft(painter), tright(painter));
var bottom = beside(bright(painter), bright(painter));
return below(bottom, top);
}
return square_of_four_lambda;
}
function flipped_pairs(painter) {
var combine4 = square_of_four(identity, flip_vert, identity, flip_vert);
return combine4(painter);
}
// footnote
flipped_pairs = square_of_four(identity, flip_vert, identity, flip_vert);
function square_limit(painter, n) {
var combine4 = square_of_four(flip_horiz, identity, rotate180, flip_vert);
return combine4(corner_split(painter, n));
}
// Exercise 2.45
// exercise left to reader to define appropriate functions
// right_split = split(beside, below)
// up_split = split(below, beside)
// Exercise 2.47
function make_frame2(origin, edge1, edge2) {
return [origin, edge1, edge2];
}
function make_frame3(origin, edge1, edge2) {
return [origin, [edge1, edge2]];
}
[edit]
// 2.3.1 Symbolic Data - Quotation
// To Be Done.
[edit]
// 2.3.2 Symbolic Data - Example: Symbolic Differentiation
function is_same_number(x, y) {
return typeof(x) == 'number' && typeof(y) == 'number' && x == y;
}
function is_variable(x) {
return typeof(x) == 'string';
}
function is_same_variable(x, y) {
return is_variable(x) && is_variable(y) && x == y;
}
function is_sum(items) {
return items[0] == 'sum';
}
function is_product(items) {
return items[0] == 'product';
}
function make_sum(x, y) {
if (typeof(x) == 'number' && typeof(y) == 'number')
return x + y;
else
return ['sum', x, y];
}
function make_product(x, y) {
if (typeof(x) == 'number' && typeof(y) == 'number')
return x * y;
else
return ['product', x, y];
}
function add_end(items) {
if (is_sum(items))
return items[1];
else
throw("Invalid pattern match " + items);
}
function aug_end(items) {
if (is_sum(items))
return items[2];
else
throw("Invalid pattern match " + items);
}
function multiplier(items) {
if (is_product(items))
return items[1];
else
throw("Invalid pattern match " + items);
}
function multiplicand(items) {
if (is_product(items))
return items[2];
else
throw("Invalid pattern match " + items);
}
function deriv(exp, varx) {
if (typeof(exp) == 'number')
return 0;
else if (is_variable(exp))
if (is_same_variable(exp, varx))
return 1;
else
return 0;
else if (is_sum(exp))
return make_sum(deriv(add_end(exp), varx),
deriv(aug_end(exp), varx));
else if (is_product(exp))
return make_sum(make_product(multiplier(exp), deriv(multiplicand(exp), varx)),
make_product(deriv(multiplier(exp), varx), multiplicand(exp)));
else
throw("Invalid expression " + exp);
}
// dx(x + 3) = 1
print (deriv(['sum','x', 3], 'x'));
// // dx(x*y) = y
print (deriv(['product', 'x', 'y'], 'x'));
// dx(x*y + x + 3) = y + 1
print (deriv(['sum', ['sum', ['product', 'x', 'y'], 'x'], 3], 'x'));
// With simplification
function make_sum2(x, y) {
if (typeof(x) == 'number' && x == 0)
return y;
else if (typeof(y) == 'number' && y == 0)
return x;
else if (typeof(x) == 'number' && typeof(y) == 'number')
return x + y;
else
return ['sum', x, y];
}
function make_product2(x, y) {
if (typeof(x) == 'number' && x == 0)
return 0;
else if (typeof(y) == 'number' && y == 0)
return 0;
else if (typeof(x) == 'number' && x == 1)
return y;
else if (typeof(y) == 'number' && y == 1)
return x;
else if (typeof(x) == 'number' && typeof(y) == 'number')
return x * y;
else
return ['product', x, y];
}
function deriv2(exp, varx) {
if (typeof(exp) == 'number')
return 0;
else if (is_variable(exp))
if (is_same_variable(exp, varx))
return 1;
else
return 0;
else if (is_sum(exp))
return make_sum2(deriv2(add_end(exp), varx),
deriv2(aug_end(exp), varx));
else if (is_product(exp))
return make_sum2(make_product2(multiplier(exp), deriv2(multiplicand(exp), varx)),
make_product2(deriv2(multiplier(exp), varx), multiplicand(exp)));
else
throw("Invalid expression " + exp);
}
// dx(x + 3) = 1
print (deriv2(['sum','x', 3], 'x'));
// // dx(x*y) = y
print (deriv2(['product', 'x', 'y'], 'x'));
// dx(x*y + x + 3) = y + 1
print (deriv2(['sum', ['sum', ['product', 'x', 'y'], 'x'], 3], 'x'));
[edit]
// 2.3.3 Symbolic Data - Example: Representing Sets
// unordered
function is_element_of_set(x, items) {
for (key in items) {
if (x == items[key])
return true;
}
return false;
}
function adjoin_set(x, items) {
if (is_element_of_set(x, items))
return items;
else
return append([X], items);
}
function intersection_set(xs, ys) {
var rt = [];
for (key in xs) {
if (is_element_of_set(value, ys))
rt.push(items[key]);
}
return rt;
}
// ordered
function is_element_of_set(x, items) {
for (key in items) {
if (x == items[key])
return true;
else if (x < items[key])
return false;
}
return false;
}
function intersection_set(xs, ys) {
var rt = [];
var i = 1;
var j = 1;
while (i <= xs.length && j <= ys.length) {
if (xs[i] == ys[j]) {
rt.push(xs[i]);
i += 1;
j += 1;
} else if (xs[i] < ys[j]) {
i += 1;
} else {
j += 1;
}
}
return rt;
}
Nil = undefined;
function Node(value, left, right) {
return new function() { this.value = value; this.left = left; this.right = right; };
}
function is_element_of_set2(x, node) {
if (node == Nil)
return false;
else
if (x == node.value)
return true;
else if (x < node.value)
return is_element_of_set2(x, node.left);
else
return is_element_of_set2(x, node.right);
}
print (is_element_of_set2(3,
Node(2,
Node(1, Nil, Nil),
Node(3, Nil, Nil))));
function adjoin_set2(x, node) {
if (node == Nil)
return Node(x, Nil, Nil);
else
if (x == node.value)
return node;
else if (x < node.value)
return Node(node.value, adjoin_set2(x, node.left), node.right);
else
return Node(node.value, node.left, adjoin_set2(x, node.right));
}
function node_to_string(node) {
if (node == Nil)
return 'Nil';
else
return 'Node(' + node.value + ', ' + node_to_string(node.left) + ', ' + node_to_string(node.right) + ')';
}
print (
node_to_string(
adjoin_set2(
3,
Node(4,
Node(2, Nil, Nil),
Node(6, Nil, Nil)))));
// Exercise 2.63
function tree_to_list(node) {
if (node == Nil)
return [];
else
return append(tree_to_list(node.left),
append(
[node.value],
tree_to_list(node.right)));
}
print (
tree_to_list(
Node(4,
Node(2, Nil, Nil),
Node(6, Nil, Nil))));
function tree_to_list2(node) {
function copy_to_list(node, xs) {
if (node == Nil)
return xs;
else
return copy_to_list(node.left, append([node.value], copy_to_list(node.right, xs)));
}
return copy_to_list(node, []);
}
print (
tree_to_list2(
Node(4,
Node(2, Nil, Nil),
Node(6, Nil, Nil))));
// Exercise 2.64
function partial_tree(elts, n) {
if (n == 0) {
return [Nil, elts];
} else {
var left_size = Math.floor((n-1) / 2);
var right_size = n - (left_size + 1);
var left_result = partial_tree(elts, left_size);
var left_tree = left_result[0];
var non_left_elts = left_result[1];
var this_entry = non_left_elts[0]
var right_result = partial_tree(non_left_elts.slice(1), right_size);
var right_tree = right_result[0];
var remaining_elts = right_result[1];
return [Node(this_entry, left_tree, right_tree), remaining_elts];
}
}
function list_to_tree(elements) {
result = partial_tree(elements, elements.length);
return result[0];
}
print (node_to_string(list_to_tree([2, 4, 6])));
// information retrieval
function lookup(given_key, items) {
for (key in items) {
if (given_key == items[key][0])
return items[key][1];
}
return Nil;
}
print (lookup(2, [[1, 'a'], [2, 'b'], [3, 'c']]));
[edit]
// 2.3.4 Symbolic Data - Example: Huffman Encoding Trees
function make_leaf(symbol, weight) {
return new function() { this.tag='leaf'; this.symbol=symbol; this.weight=weight; };
}
function is_leaf(node) {
return node.tag == 'leaf';
}
function symbol_leaf(node) {
if (is_leaf(node))
return node.symbol;
else
throw("Invalid pattern match " + node);
}
function weight_leaf(node) {
if (is_leaf(node))
return node.weight;
else
throw("Invalid pattern match " + node);
}
function symbols(node) {
if (is_leaf(node))
return [node.symbol];
else
return node.subsymbols;
}
function weight(node) {
return node.weight;
}
function make_code_tree(left, right) {
return new function () {
this.tag='tree';
this.subsymbols=append(symbols(left), symbols(right));
this.weight=weight(left) + weight(right);
this.left=left;
this.right=right;
}
}
function left_node(node) {
if (!is_leaf(node))
return node.left;
else
throw("Invalid pattern match " + node);
}
function right_node(node) {
if (!is_leaf(node))
return node.right;
else
throw("Invalid pattern match " + node);
}
function choose_node(n, node) {
if (n == 0)
return left_node(node);
else if (n == 1)
return right_node(node);
else
throw("Invalid pattern match " + node);
}
// decoding
function decode(bits, tree) {
function decode_1(bits, current_node) {
if (bits.length == 0) {
return [];
} else {
var head = bits[0];
var tail = bits.slice(1);
var next_node = choose_node(head, current_node);
if (is_leaf(next_node))
return append([symbol_leaf(next_node)], decode_1(tail, tree));
else
return decode_1(tail, next_node);
}
}
return decode_1(bits, tree);
}
// sets
function adjoin_set3(x, items) {
if (node == Nil) {
return [x];
} else {
var head = items[0];
if (weight(x) < weight(head)) {
return append([x], items);
} else {
var tail = items.slice(1);
return append(head, adjoin_set3(x, tail));
}
}
}
function make_leaf_set(node) {
var head = node[0];
var tail = node.slice(1);
if (is_leaf(head))
return adjoin_set3(make_leaf(symbol_leaf(head), symbol_weight(head)), make_leaf_set(tail));
else
throw("Invalid pattern match " + node);
}
// Exercise 2.67
sample_tree = make_code_tree(
make_leaf('A', 4),
make_code_tree(
make_leaf('B', 2),
make_code_tree(
make_leaf('D', 1),
make_leaf('C', 1))));
sample_message = [0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0];
print (decode(sample_message, sample_tree));
// Exercise 2.68
// exercise left to reader to define appropriate functions
// function encode(message, tree) {
// if (message.length == 0) {
// return [];
// } else {
// var head = message[1];
// var tail = message.slice(2);
// return append(encode_symbol(head, tree), encode(tail, tree));
// }
// }
[edit]
// 2.4.1 Multiple Representations for Abstract Data - Representations for Complex Numbers
// Same as above
function square(x) { return x * x; }
// Rectangular
function real_part_r(z) { return z[0]; }
function imag_part_r(z) { return z[1]; }
function magnitude_r(z) {
return Math.sqrt(square(real_part_r(z)) + square(imag_part_r(z)));
}
function angle_r(z) {
return Math.atan2(imag_part_r(z), real_part_r(z));
}
function make_from_real_imag_r(x, y) {
return [x, y];
}
function make_from_mag_ang_r(r, a) {
return [r*Math.cos(a), r*Math.sin(a)];
}
// polar
function magnitude_p(z) { return z.magnitude; }
function angle_p(z) { return z.angle; }
function real_part_p(z) {
return magnitude_p(z) * Math.cos(angle_p(z));
}
function imag_part_p(z) {
return magnitude_p(z) * Math.sin(angle_p(z));
}
function make_from_real_imag_p(x, y) {
return new function() {
this.magnitude = Math.sqrt(square(x) + square(y));
this.angle = Math.atan2(y, x);
};
}
function make_from_mag_ang_p(r, a) {
return new function() {
this.magnitude = r;
this.angle = a;
};
}
// using the abstract type
magnitude = magnitude_r;
angle = angle_r;
real_part = real_part_r;
imag_part = imag_part_r;
make_from_real_imag = make_from_real_imag_r;
make_from_mag_ang = make_from_mag_ang_r;
z = make_from_real_imag_r(1, 2);
print (make_from_real_imag(real_part(z), imag_part(z)));
print (make_from_mag_ang(magnitude(z), angle(z)));
function add_complex(z1, z2) {
return make_from_real_imag(
real_part(z1) + real_part(z2),
imag_part(z1) + imag_part(z2));
}
function sub_complex(z1, z2) {
return make_from_real_imag(
real_part(z1) - real_part(z2),
imag_part(z1) - imag_part(z2));
}
function mul_complex(z1, z2) {
return make_from_mag_ang(
magnitude(z1) * magnitude(z2),
angle(z1) + angle(z2));
}
function div_complex(z1, z2) {
return make_from_mag_ang(
magnitude(z1) / magnitude(z2),
angle(z1) - angle(z2));
}
[edit]
// 2.4.2 Multiple Representations for Abstract Data - Tagged Data
function attach_tag(type_tag, contents) {
return [type_tag, contents];
}
function type_tag(a) {
if (a[0] == 'rectangular')
return 'rectangular';
else if (a[0] == 'polar')
return 'polar';
else
throw("Invalid pattern match " + a);
}
function contents(a) {
if (a[0] == 'rectangular')
return a[1];
else if (a[0] == 'polar')
return a[1];
else
throw("Invalid pattern match " + a);
}
function is_rectangular(a) {
return type_tag(a) == 'rectangular';
}
function is_polar(a) {
return type_tag(a) == 'polar';
}
// Rectangular
function make_from_real_imag_rectangular(x, y) {
return attach_tag('rectangular', [x, y]);
}
function make_from_mag_ang_rectangular(r, a) {
return attach_tag('rectangular', [r*Math.cos(a), r*Math.sin(a)])
}
function real_part_rectangular(z) {
return z[0];
}
function imag_part_rectangular(z) {
return z[1];
}
function magnitude_rectangular(z) {
return Math.sqrt(square(real_part_rectangular(z)) + square(imag_part_rectangular(z)));
}
function angle_rectangular(z) {
Math.atan2(imag_part_rectangular(z), real_part_rectangular(z));
}
// Polar
function make_from_real_imag_polar(x, y) {
return attach_tag('polar', [Math.sqrt(square(x) + square(y)), Math.atan2(y, x)]);
}
function make_from_mag_ang_polar(r, a) {
return attach_tag('polar', [r, a]);
}
function magnitude_polar(z) {
return z[0];
}
function angle_polar(z) {
return z[1];
}
function real_part_polar(z) {
return magnitude_polar(z) * Math.cos(angle_polar(z));
}
function imag_part_polar(z) {
return magnitude_polar(z) * Math.sin(angle_polar(z));
}
// Generic selectors
function real_part_g(a) {
if (type_tag(a) == 'rectangular')
return real_part_rectangular(contents(a));
else if (type_tag(a) == 'polar')
return real_part_polar(contents(a));
else
throw("Invalid pattern match " + a);
}
function imag_part_g(a) {
if (type_tag(a) == 'rectangular')
return imag_part_rectangular(contents(a));
else if (type_tag(a) == 'polar')
return imag_part_polar(contents(a));
else
throw("Invalid pattern match " + a);
}
function magnitude_g(a) {
if (type_tag(a) == 'rectangular')
return magnitude_rectangular(contents(a));
else if (type_tag(a) == 'polar')
return magnitude_polar(contents(a));
else
throw("Invalid pattern match " + a);
}
function angle_g(a) {
if (type_tag(a) == 'rectangular')
return angle_rectangular(contents(a));
else if (type_tag(a) == 'polar')
return angle_polar(contents(a));
else
throw("Invalid pattern match " + a);
}
// Constructors for complex numbers
function make_from_real_imag_g(x, y) {
return make_from_real_imag_rectangular(x, y);
}
function make_from_mag_ang_g(r, a) {
return make_from_mag_ang_polar(r, a);
}
// same as before
function add_complex_g(z1, z2) {
return make_from_real_imag_g(
real_part_g(z1) + real_part_g(z2),
imag_part_g(z1) + imag_part_g(z2));
}
function sub_complex_g(z1, z2) {
return make_from_real_imag_g(
real_part_g(z1) - real_part_g(z2),
imag_part_g(z1) - imag_part_g(z2));
}
function mul_complex_g(z1, z2) {
return make_from_mag_ang_g(
magnitude_g(z1) * magnitude_g(z2),
angle_g(z1) + angle_g(z2));
}
function div_complex_g(z1, z2) {
return make_from_mag_ang_g(
magnitude_g(z1) / magnitude_g(z2),
angle_g(z1) - angle_g(z2));
}
print (add_complex_g(make_from_real_imag_g(3, 4), make_from_real_imag_g(3, 4)))
[edit]
// 2.4.3 Multiple Representations for Abstract Data - Data-Directed Programming and Additivity
// To Be Done.
[edit]
// 2.5.1 Systems with Generic Operations - Generic Arithmetic Operations
// To Be Done.
![[Main Page]](/wiki/stylesheets/images/wiki.png)