About SICP The following Python 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 #01 Examples in Python #!/usr/local/bin/python # -*- coding: UTF-8 -*- import math import random import time # 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) print (21 + 35 + 12 + 7) print (25 * 4 * 12) print (3 * 5 + 10 - 6) print (3 * (2 * 4 + 3 + 5) + 10 - 7 + 6) # 1.1.2 The Elements of Programming - Naming and the Environment size = 2 print (size) print (5 * size) pi = 3.14159 radius = 10 print (pi * radius * radius) circumference = 2 * pi * radius print (circumference) # 1.1.3 The Elements of Programming - Evaluating Combinations print ((2 + (4 * 6)) * (3 + 5 + 7)) # 1.1.4 The Elements of Programming - Compound Procedures def square(x): return x * x print (square(21)) print (square(2 + 5)) print (square(square(3))) def sum_of_squares(x, y): return square(x) + square(y) print (sum_of_squares(3, 4)) def f(a): return sum_of_squares(a + 1, a * 2) print (f(5)) # 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) # 1.1.6 The Elements of Programming - Conditional Expressions and Predicates def abs(x): if x > 0: return x elif x == 0: return 0 else: return -x def abs(x): if x < 0: return -x else: return x x = 6 print (x > 5 and x < 10) def ge(x, y): return x > y or x == y def ge(x, y): return not(x < y) # Exercise 1.1 print (10) print (5 + 3 + 4) print (9 - 1) print (6 / 2) print (2 * 4 + 4 - 6) a = 3 b = a + 1 print (a + b + a * b) print (a == b) print (b if b > a and b < a * b else a) print (6 if a == 4 else 6 + 7 + a if b == 4 else 25) print (2 + (b if b > a else a)) print ((a if a > b else b if a < b else -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 def 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 def a_plus_abs_b(a, b): if b > 0: return a + b else: return a - b # Exercise 1.5 def p(): return p() def test(x, y): if x == 0: return 0 else: return y # commented out as this is in infinite loop # test(0, p()) # 1.1.7 The Elements of Programming - Example: Square Roots by Newton's Method def square(x): return x * x def good_enough(guess, x): return abs(square(guess) - x) < 0.001 def average(x, y): return (x + y) / 2.0 def improve(guess, x): return average(guess, float(x) / guess) def sqrt_iter(guess, x): if good_enough(guess, x): return guess else: return sqrt_iter(improve(guess, x), x) def sqrt(x): return sqrt_iter(1.0, float(x)) print (sqrt(9)) print (sqrt(100 + 37)) print (sqrt(sqrt(2)+sqrt(3))) print (square(sqrt(1000))) # Exercise 1.6 def 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)) def sqrt_iter(guess, x): return new_if( good_enough(guess, x), guess, sqrt_iter(improve(guess, x), x)) # Exercse 1.7 def good_enough_gp(guess, prev): return abs(guess - prev) / guess < 0.001 def sqrt_iter_gp(guess, prev, x): if good_enough_gp(guess, prev): return guess else: return sqrt_iter_gp(improve(guess, x), guess, x) def sqrt_gp(x): return sqrt_iter_gp(4.0, 1.0, float(x)) # Exercise 1.8 def improve_cube(guess, x): return (2.0*guess + float(x)/(guess * guess)) / 3.0 def cube_iter(guess, prev, x): if good_enough_gp(guess, prev): return guess else: return cube_iter(improve_cube(guess, x), guess, x) def cube_root_0(x): return cube_iter(27.0, 1.0, x) # 1.1.8 The Elements of Programming - Procedures as Black-Box Abstractions def square(x): return x * x def double(x): return x + x def square_real(x): return math.exp(double(math.log(x))) def good_enough(guess, x): return abs(square(guess) - x) < 0.001 def improve(guess, x): return average(guess, float(x) / guess) def sqrt_iter(guess, x): if good_enough(guess, x): return guess else: return sqrt_iter(improve(guess, x), x) def sqrt(x): return sqrt_iter(1.0, x) print (square(5)) # Block-structured def sqrt(x): def good_enough(guess, x): return abs(square(guess) - x) < 0.001 def improve(guess, x): return average(guess, float(x) / guess) def 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 def sqrt(x): def good_enough(guess): return abs(square(guess) - x) < 0.001 def improve(guess): return average(guess, float(x) / guess) def sqrt_iter(guess): if good_enough(guess): return guess else: return sqrt_iter(improve(guess)) return sqrt_iter(1.0) # 1.2.1 Procedures and the Processes They Generate - Linear Recursion and Iteration # Recursive def factorial(n): if n == 1: return 1 else: return n * factorial(n - 1) print (factorial(6)) # Iterative def fact_iter(product, counter, max_count): if counter > max_count: return product else: return fact_iter(counter * product, counter + 1, max_count) def factorial(n): return fact_iter(1, 1, n) # Iterative, block-structured (from footnote) def factorial(n): def iter(product, counter): if counter > n: return product else: return iter(counter * product, counter + 1) return iter(1, 1) # Exercise 1.9 def inc(a): return a + 1 def dec(a): return a - 1 def plus(a, b): if a == 0: return b else: return inc(plus(dec(a), b)) def plus(a, b): if a == 0: return b else: return plus(dec(a), inc(b)) # Exercise 1.10 def a(x, y): if y == 0: return 0 elif x == 0: return 2 * y elif y == 1: return 2 else: return a(x - 1, a(x, y - 1)) print (a(1, 10)) print (a(2, 4)) print (a(3, 3)) def f(n): return a(0, n) def g(n): return a(1, n) def h(n): return a(2, n) def k(n): return 5 * n * n # 1.2.2 Procedures and the Processes They Generate - Tree Recursion # Recursive def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n - 1) + fib(n - 2) # Iterative def fib_iter(a, b, count): if count == 0: return b else: return fib_iter(a + b, a, count - 1) def fib(n): return fib_iter(1, 0, n) # Counting change def first_denomination(x): if x == 1: return 1 elif x == 2: return 5 elif x == 3: return 10 elif x == 4: return 25 elif x == 5: return 50 def cc(amount, kinds_of_coins): if amount == 0: return 1 elif amount < 0: return 0 elif kinds_of_coins == 0: return 0 else: return (cc(amount, kinds_of_coins - 1) + cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)) def count_change(amount): return cc(amount, 5) print (count_change(100)) # Exercise 1.11 def f(n): if n < 3: return n else: return f(n-1) + 2*f(n-2) + 3*f(n-3) def f_iter(a, b, c, count): if count == 0: return c else: return f_iter(a + 2*b + 3*c, a, b, count-1) def f(n): return f_iter(2, 1, 0, n) # Exercise 1.12 def pascals_triangle(n, k): if n == 0: return 1 elif n == k: return 1 else: return pascals_triangle(n-1, k-1) + pascals_triangle(n-1, k) # 1.2.3 Procedures and the Processes They Generate - Orders of Growth # Exercise 1.15 def cube(x): return x * x * x def p(x): return 3.0 * x - 4.0 * cube(x) def sine(angle): if not(abs(angle) > 0.1): return angle else: return p(sine(angle / 3.0)) # 1.2.4 Procedures and the Processes They Generate - Exponentiation # Linear recursion def expt(b, n): if n == 0: return 1 else: return b * expt(b, n - 1) # Linear iteration def expt_iter(b, counter, product): if counter == 0: return product else: return expt_iter(b, counter - 1, b * product) def expt(b, n): return expt_iter(b, n, 1) # Logarithmic iteration def even(n): return (n % 2) == 0 def 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 def 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' #def 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) #def fib(n): # return fib_iter(1, 0, 0, 1, n) # 1.2.5 Procedures and the Processes They Generate - Greatest Common Divisors def 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)) # 1.2.6 Procedures and the Processes They Generate - Example: Testing for Primality # prime def divides(a, b): return (b % a) == 0 def find_divisor(n, test_divisor): if square(test_divisor) > n: return n elif divides(test_divisor, n): return test_divisor else: return find_divisor(n, test_divisor + 1) def smallest_divisor(n): return find_divisor(n, 2) def prime(n): return n == smallest_divisor(n) # fast_prime def 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 def fermat_test(n): def try_it(a): return expmod(a, n, n) == a return try_it(random.randint(0, n-1)) def 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 def report_prime(elapsed_time): print (" *** " + str(elapsed_time)) def start_prime_test(n, start_time): if prime(n): report_prime(time.time() - start_time) def timed_prime_test(n): print ("\n" + str(n)) start_prime_test(n, time.time()) # Exercise 1.25 def expmod(nbase, nexp, m): return fast_expt(nbase, nexp) % m # Exercise 1.26 def expmod(nbase, nexp, m): if nexp == 0: return 1 else: if even(nexp): return (expmod(nbase, (nexp / 2), m) * expmod(nbase, (nexp / 2), m)) % m else: return (nbase * expmod(nbase, nexp - 1, m)) % m # Exercise 1.27 def carmichael(n): return fast_prime(n, 100) and not(prime(n)) print (carmichael(561)) print (carmichael(1105)) print (carmichael(1729)) print (carmichael(2465)) print (carmichael(2821)) print (carmichael(6601)) # 1.3 Formulating Abstractions with Higher-Order Procedures def cube(x): return x * x * x # 1.3.1 Formulating Abstractions with Higher-Order Procedures - Procedures as Arguments def sum_integers(a, b): if a > b: return 0 else: return a + sum_integers(a + 1, b) def sum_cubes(a, b): if a > b: return 0 else: return cube(a) + sum_cubes(a + 1, b) def pi_sum(a, b): if a > b: return 0.0 else: return (1.0 / (a * (a + 2.0))) + pi_sum(a + 4.0, b) def sum(term, a, next, b): if a > b: return 0 else: return term(a) + sum(term, next(a), next, b) # Using sum def inc(n): return n + 1 def sum_cubes(a, b): return sum(cube, a, inc, b) print (sum_cubes(1, 10)) def identity(x): return x def sum_integers(a, b): return sum(identity, a, inc, b) print (sum_integers(1, 10)) def pi_sum(a, b): def pi_term(x): return 1.0 / (x * (x + 2.0)) def pi_next(x): return x + 4.0 return sum(pi_term, a, pi_next, b) print (8.0 * pi_sum(1, 1000)) def integral(f, a, b, dx): def add_dx(x): return x + dx return sum(f, a + (dx / 2.0), add_dx, b) * dx def cube(x): return x * x * x print (integral(cube, 0.0, 1.0, 0.01)) # exceeds maximum recursion depth # print (integral(cube, 0.0, 1.0, 0.001)) # Exercise 1.29 def simpson(f, a, b, n): h = float(abs(b-a)) / n def 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) print (simpson(cube, 0, 1, 100)) # Exercise 1.30 def sum_iter(term, a, next, b, acc): if a > b: return acc else: return sum_iter(term, next(a), next, b, acc + term(a)) def sum_cubes(a, b): return sum_iter(cube, a, inc, b, 0) print (sum_cubes(1, 10)) # Exercise 1.31 def product(term, a, next, b): if a > b: return 1 else: return term(a) * product(term, next(a), next, b) def factorial(n): return product(identity, 1, inc, n) def product_iter(term, a, next, b, acc): if a > b: return acc else: return product_iter(term, next(a), next, b, acc * term(a)) # Exercise 1.32 def accumulate(combiner, null_value, term, a, next, b): if a > b: return null_value else: return combiner(term(a), accumulate(combiner, null_value, term, next(a), next, b)) def sum(a, b): return accumulate(lambda x,y: x+y, 0, identity, a, inc, b) def product(a, b): return accumulate(lambda x,y: x*y, 1, identity, a, inc, b) def 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))) def sum(a, b): return accumulate_iter(lambda x,y: x+y, identity, a, inc, b, 0) def product(a, b): return accumulate_iter(lambda x,y: x*y, identity, a, inc, b, 1) # Exercise 1.33 def filtered_accumulate(combiner, null_value, term, a, next, b, pred): if a > b: return null_value else: if pred(a): return combiner(term(a), filtered_accumulate(combiner, null_value, term, next(a), next, b, pred)) else: return filtered_accumulate(combiner, null_value, term, next(a), next, b, pred) print (filtered_accumulate(lambda x,y: x+y, 0, square, 1, inc, 5, prime)) # 1.3.2 Formulating Abstractions with Higher-Order Procedures - Constructing Procedures Using Lambda def pi_sum(a, b): return sum(lambda x: 1.0 / (x * (x + 2.0)), a, lambda x: x + 4.0, b) def integral(f, a, b, dx): return sum(f, a + (dx / 2.0), lambda x: x + dx, b) * dx def plus4(x): return x + 4 plus4 = lambda x: x + 4 print ((lambda x, y, z: x + y + square(z)) (1, 2, 3)) # Using let def f(x, y): def f_helper(a, b): return x*square(a) + y*b + a*b return f_helper(1 + x*y, 1 - y) def f(x, y): return (lambda a, b: x*square(a) + y*b + a*b) (1 + x*y, 1 - y) def f(x, y): a = 1 + x*y b = 1 - y return x*square(a) + y*b + a*b # python does not have let binding and lambdas are limited to an expression # so we'll use default parameters to emulate (courtesy of Randy Hudson) x = 5 print ((lambda x=3: x + x*10)() + x) x = 2 print ((lambda x=3,y=x+2: x*y)()) def f(x, y): a = 1 + x*y b = 1 - y return x*square(a) + y*b + a*b # Exercise 1.34 def f(g): return g(2) print (f(square)) print (f(lambda z: z * (z + 1))) # 1.3.3 Formulating Abstractions with Higher-Order Procedures - Procedures as General Methods # Half-interval method def close_enough(x, y): return abs(x - y) < 0.001 def positive(x): return x >= 0.0 def negative(x): return not(positive(x)) def 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) elif negative(test_value): return search(f, midpoint, pos_point) else: return midpoint def half_interval_method(f, a, b): a_value = f(a) b_value = f(b) if negative(a_value) and positive(b_value): return search(f, a, b) elif negative(b_value) and positive(a_value): return search(f, b, a) else: raise Exception("Values are not of opposite sign " + str(a) + " " + str(b)) print (half_interval_method(math.sin, 2.0, 4.0)) print (half_interval_method(lambda x: x*x*x - 2.0*x - 3.0, 1.0, 2.0)) # Fixed points tolerance = 0.00001 def fixed_point(f, first_guess): def close_enough(v1, v2): return abs(v1 - v2) < tolerance def 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(lambda y: math.sin(y) + math.cos(y), 1.0)) # note: this function does not converge def sqrt(x): return fixed_point(lambda y: float(x) / y, 1.0) def sqrt(x): return fixed_point(lambda y: average(y, float(x) / y), 1.0) # Exercise 1.35 def golden_ratio(): return fixed_point(lambda x: 1.0 + 1.0/x, 1.0) # Exercise 1.36 # 35 guesses before convergence print (fixed_point(lambda x: math.log(1000.0) / math.log(x), 1.5)) # 11 guesses before convergence (average_damp defined below) # print (fixed_point(average_damp(lambda x: math.log(1000.0) / math.log(x)), 1.5)) # Exercise 1.37 # exercise left to reader to define cont_frac # cont_frac(lambda i: return 1.0, lambda i: return 1.0, k) # 1.3.4 Formulating Abstractions with Higher-Order Procedures - Procedures as Returned Values def average_damp(f): return lambda x: average(float(x), f(x)) print ((average_damp(square)) (10.0)) def sqrt(x): return fixed_point(average_damp(lambda y: float(x) / y), 1.0) def cube_root(x): return fixed_point(average_damp(lambda y: float(x) / square(y)), 1.0) print (cube_root(8)) # Newton's method dx = 0.00001 def deriv(g): return lambda x: float(g(x + dx) - g(x)) / dx def cube(x): return x * x * x print (deriv(cube) (5.0)) def newton_transform(g): return lambda x: x - float(g(x)) / (deriv(g) (x)) def newtons_method(g, guess): return fixed_point(newton_transform(g), guess) def sqrt(x): return newtons_method(lambda y: square(y) - x, 1.0) # Fixed point of transformed function def fixed_point_of_transform(g, transform, guess): return fixed_point(transform(g), guess) def sqrt(x): return fixed_point_of_transform(lambda y: x / y, average_damp, 1.0) def sqrt(x): return fixed_point_of_transform(lambda y: square(y) - x, newton_transform, 1.0) # Exercise 1.40 def cubic(a, b, c): return lambda x: cube(x) + a*x*x + b*x + c print (newtons_method(cubic(5.0, 3.0, 2.5), 1.0)) # Exercise 1.41 def double(f): return lambda x: f(f(x)) print (double(inc)(5)) print (double(double)(inc)(5)) print (double(double)(double)(inc)(5)) # Exercise 1.42 def compose(f, g): return lambda x: f(g(x)) print (compose(square, inc)(6)) #Exercise 1.43 def repeated(f, n): def iterate(arg, i): if i > n: return arg else: return iterate(f(arg), i+1) return lambda x: iterate(x, 1) print (repeated(square, 2)(5)) # Exercise 1.44 def smooth(f, dx): return lambda x: average(x, (f(x-dx) + f(x) + f(x+dx)) / 3.0) print (fixed_point(smooth(lambda x: math.log(1000.0) / math.log(x), 0.05), 1.5)) #Exercise 1.46 def iterative_improve(good_enough, improve): def iterate(guess): next = improve(guess) if good_enough(guess, next): return next else: return iterate(next) return lambda x: iterate(x) def fixed_point(f, first_guess): tolerance = 0.00001 def good_enough(v1, v2): return abs(v1-v2) < tolerance return iterative_improve(good_enough, f)(first_guess) print (fixed_point(average_damp(lambda x: math.log(1000.0) / math.log(x)), 1.5)) ```

Chris Rathman / Chris.Rathman@tx.rr.com