CodeDump : StructureAndImplementationOfComputerPrograms

CodeDump :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register

Structure And Interpretation Of Computer Programs


up

I encountered this slashdot post. Where a students asks all the big names (mainly Linus and Stroustrup caught my eye) some basic questions about life as a programmer. One of the questions was 'what is your favorite book related to computer programming'. Some mentioned GEB, some K&R but there was one book I hadn't heard about before. Well it turned out this book was available for free online. And I know, the mind is strong, the body is weak, I started reading it and I'm using this page to dump some stuff.

So the book handles a Lisp dialect called scheme. I'll be using emacs and guile to do the examples (guile even has some C bindings ;-) ). I also made use of plt-scheme which has a bit better indentation but seems to have fewer primitives (like random and runtime).

Exercise 1.2

Translate the following expression into prefix form: (5+4+(2-(3-(6+4/5))))/(3*(6-2)*(2-7)):

( / (5
    4
    ( - 2
         (- 3
        (+ 6
           (/ 4.0 5.0)))))
    ( * 3
    ( - 6 2 )
    ( - 2 7 )))


Exercise 1.3

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

First the <= operator will be the defined, followed by the sumMaxSquares function which takes three operators. First the sum of all squares will be made, followed with subtracting the smallest square.
(define (<= x y)
  (or (< x y) (= x y)))

(define (sumMaxSquares a b c)
  (- (+ (* a a)
    (* b b)
    (* c c))
    (cond ((and (<= a b) (<= a c)) (* a a))
       ((and (<= b a) (<= b c)) (* b b))
       ((and (<= c a) (<= c b)) (* c c)))))


This can easily be tested with all possible combinations:

(sumMaxSquares 1 1 1)
(sumMaxSquares 2 1 1)
(sumMaxSquares 1 2 1)
(sumMaxSquares 1 1 2)
(sumMaxSquares 1 2 3)
(sumMaxSquares 1 3 2)
(sumMaxSquares 2 1 3)
(sumMaxSquares 2 3 1)
(sumMaxSquares 3 1 2)
(sumMaxSquares 3 2 1)


(Which should give the results 1, 5, 5, 5,13,13,13,13,13,13).

Exercise 1.4

Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))


As the procedure names says the condition results in the operator. When b is positive it will execute (+ a b) when b is negative (- a b) will be executed. So the condition returns an operator.

Newtons method for finding the square root

The following code uses Newtons method to find the square root. Newtons method says that a value is closer to the square root of a number x if we average a guess y with x/y.

In Scheme this looks like:

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (square x)
  (* x x))

(define (sqrt x)
  (sqrt-iter 1.0 x))


A C++ version looks like:

#include <iostream>
#include <cmath>
using namespace std;

double newton(double val){
        double guess = 1;
        while (fabs(guess * guess - val)  > 0.001){
                guess = (guess + (val / guess))/2.0;
        }
}

int main(int argc, char **argv){
        cout << newton(9) << endl;
}


Exercise 1.6

Explain the outcome when the following changes get applied to the previous procedure ?

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))


The result guile gives is:
standard input:28:1: In expression (sqrt 9 ()):
standard input:28:1: Stack overflow
ABORT: (stack-overflow)


The explanation is simple. The interpreter tries to infinitely expand the else clause (which is sqrt-iter, which contains the new-if which contains sqrt-iter, which contains new-if which contains sqrt-iter ....).

Exercise 1.7

Alter good-enough? in Newtons method to check if the delta between two consecutive iterations becomes small enough.

(define (sqrt-iter oldguess  guess x)
  (if (good-enough? oldguess guess )
          guess
          (sqrt-iter guess
                     (improve guess x)
                     x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2.0))

(define (good-enough? oldguess guess )
  (< (abs (- oldguess guess)) 0.001))

(define (sqrt x)
  (define oldguess 1)
  (sqrt-iter oldguess  (improve oldguess x)  x))


Exercise 1.7

Use the formula (x/(y^2)+2y)/3 to get an approximation to find the cube root within Newtons method.

(define (cubrt-iter oldguess  guess x)
  (if (good-enough? oldguess guess )
          guess
          (cubrt-iter guess
                     (improve guess x)
                     x)))

(define (improve y x)
  (/ (+ (/ x
       (* y y))
    (+ y y))
      3.0))


(define (average x y)
  (/ (+ x y) 2.0))

(define (good-enough? oldguess guess )
  (< (abs (- oldguess guess)) 0.001))

(define (cubrt x)
  (define oldguess 1)
  (cubrt-iter oldguess  (improve oldguess x)  x))


Which produces the following output:
guile> (cubrt 9)
2.08008382323852
guile> (* (cubrt 9) (cubrt 9) (cubrt 9))
9.00000000242235


Factorial

The following scheme code calculates the factorial, which is the de facto standard for introducing recursion:

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))


which looks a lot like it's C/C++ brother (except the prefix notation that is):

int factorial(int n){
    if(n == 1){
        return 1;   
    }else{
        return n*factorial(n-1);
    }
}


Exercise 1.9

Given the following functions are test1 and test2 recursive or iterative ?
(define (inc a)
    (+ a 1))
(define (dec a)
    (- a 1))

(define (test1 a b)
  (if (= a 0)
      b
      (inc  (+ (dec a)  b))))
 
 (define (test2 a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))


test1 is recursive, recursion depth is equal to a, while test2 is iterative with a n iterations.

Exercise 1.10

This book uses Ackermann's function, this function is defined here . However the code in the book doesn't seem to give the same results as wikipedia. The original code is:
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))


While I would write it as:

(define (A m n)
  (cond ((= m 0) (+ n 1))
        ((= n 0) (A (- m 1) 1))
        (else (A (- m 1)
              (A m ( - n 1))))))


A recursive version that calculates a Fibonacci number:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Offcourse this does way too much redundant steps, that's why an iterative function would be much more useful:

(define (fib-iter res prev count)
  (if (= count 0)
      prev
      (fib-iter (+ res prev) res (- count 1))))

Here the current, the previous and the counter are passed to the next call. Initial call should have res set to 1 and prev to 0.

Exercise 1.11

Given a function f(n) which returns n if n < 3 or f(n-1)+2*f(n-2)+3*f(n-3) otherwise, write both a recursive and an iterative procedure to compute n

The recursive version looks like:
(define (f_rec n)
  (if (< n 3)
       n
       (+ (f_rec (- n 1)) (* 2 (f_rec (- n 2))) (* 3 (f_rec (- n 3))))))

While the iterative version looks like:
(define (run_f_it n)
  (cond ((= n 0)  0)
        ((= n 1)  1)
        ((= n 2)  2)
        (else (f_it 2 1 0 (- n 3)))))

(define (f_it n1 n2 n3 count)
  (cond ((< count 0) n1)
        (else (f_it (+ n1 (* 2 n2) (* 3 n3)) n1 n2 (- count 1)))))

Mental note: you will want to avoid recursion in scheme ;).

Exercise 1.12

Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

(define (pascal x y)
  (cond ((> x y) 0)
        ((= x y) 1)
        ((= x 1) 1)
        (else (+ (pascal (- x 1) (- y 1)) (pascal x (- y 1))))))


Note that a extra condition has been added that returns zero when the boundaries of the triangle are exceeded.

Exercise 1.16

Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps. Use the observation that (b^{n/2})^2= (b^2)^{n/2}

(define (even? n)
  (= (remainder n 2) 0))

(define (fast-exp b n)
  (fast-exp-iter 1 b n))

(define (fast-exp-iter a b n)
  (cond ((= n 0) a)
        ((even? n) (fast-exp-iter a (* b b) (/ n 2) ))
        (else (fast-exp-iter (* a b) b (- n 1)))))


Note that remainder is a primitive function.

Exercise 1.17

Given the following piece of code:

(define (* a b)
  (if (= b a)
      0
      (+ a (* a (- b 1)))))


this code performs multiplication in a linear number of steps. Now suppose we include, together with addition, operations doubles, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-exp that uses a logarithmic number of steps:

(define (double a)
  (+ a a))

(define (halve a)
  (/ a 2))

(define (even? n)
  (= (remainder n 2) 0))

(define (* a b)
  (cond ((= b 0) 0)
        ((even? b) (double (* a (halve b))))
        (else (+ a (* a (- b 1))))))


Exercise 1.18

Using the results of 1.16 and 1.17 devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.

(define (double a)
  (+ a a))

(define (halve a)
  (/ a 2))

(define (even? n)
  (= (remainder n 2) 0))

(define (* a b)
  (iter* 0 a b)
)

(define (iter* res a b)
  (cond ((= b 0) res)
        ((even? b) (iter* res (double a) (halve b)))
        (else (iter* (+ res a) a (- b 1)))))



Euclids algorithm

Euclids algorithm is an algorithm for finding the greatest common divisor and it works by the observation that GCD(a,b)=GCD(b,a mod b). In scheme this looks like
(define (gcd a b)
  (if (= b 0)
       a
       (gcd b (remainder a b))))


In C one would be happy with
int gcd(int a, int b){
  if(b==0){
    return a;
  }else{
    return gcd(b,a%b);
  }
}


or the iterative version:
int ggd(int a, int b){
  int remain;
  while(b!=0){
    remain=a%b;
    a=b;
    b=remain;
  }
  return a;
}


Finding primes

The following codes determines if a number is a prime number:

(define (smallest-divisor n)
  (find-divisor n 2))

(define (square a)
  (* a a))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= (smallest-divisor n) n))


While a C version looks like:
bool isPrime(int n){
  int cur=2;
  while(cur*cur < n && n%cur!=0){
    cur++;
  }
  return n%cur!=0;
}


All of these have a complexity of sqrt(n). A second method for finding primes is based on Fermat's little theorem. Which states that if n is a prime (a^n)%n=a%n. So given a number n pick several random a values, if all modulos are equal to zero the chances are very high that n is a prime indeed. An implementation of a probabilistic test for primality using Fermat's little theorem looks like:

(define (square a)
  (* a a)) 

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m ) )))
                     
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
            (else false)))


And the same implemented in C++ looks like this:

int square(int a){
  return a*a;
}

int expmod(int base, int exp, int m){
  if(exp==0){
    return 1;       
  }else if(exp%2==0){
    return square(expmod(base,exp/2,m))%m;
  }else{
    return (base*expmod(base,exp-1,m))%m;
  }
}

bool fermattest(int n){
  int a = 1+(rand()%(n-1));
  return (expmod(a,n,n)==a);
}

bool fastprime(int n, int times){
  if(times==0){
    return true;
  }else{
    if(fermattest(n)){
      return fastprime(n,times-1);
    }else{
      return false;
    }
  }
}


Exercise 1.23
The smallest-divisor procedure shown at the start of this section does lots of needless testing: After it checks to see if the number is divisible by 2 there is no point in checking to see if it is divisible by any larger even numbers. This suggests that the values used for test-divisor should not be 2,3,4,5,6,... but rather 2,3,5,7,9,.. To implement this change, define a procedure next that returns three if its input is equal to 2 and otherwise retruns its input plus 2.

(define (smallest-divisor n)
  (find-divisor n 2))

(define (square a)
  (* a a))

(define (next n)
  (cond ((= test-divisor 2) 3)
        (else (+ test-divisor 2))))
 
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= (smallest-divisor n) n))


Exercise 1.27

Demonstrate that the Carmichael numbers really do fool the Fermat test. That is, write a procedure that takes an integer n and tests whether a^n is congruent to a modulo n for every a < n, and try your procedure on the given Carmichael numbers

(define (square a)
  (* a a))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m ) )))

(define (doTheMagic number counter)
  (cond ((= counter number) 1)
        ((= (expmod counter number number) counter) (doTheMagic number (+ counter 1)))
        (else 0)))

(define (verifyCarmichael n)
  (doTheMagic n 1))

(verifyCarmichael 561)
(verifyCarmichael 1105)
(verifyCarmichael 1729)
(verifyCarmichael 2465)
(verifyCarmichael 2821)
(verifyCarmichael 6601)


Exercise 1.29

Simpson's Rule is a more accurate method of numerical integration. More information on Simpson's rule can be found on wikipedia. Define a procedure that takes the arguments f,a,b and n and returns the value of the integral, computer using Simpson's Rule. Use your procedure to integrate cube between 0 and 1.

In the code below coef is used to get a coefficient, getH calculates h and simpson-iter is an iterative function which calculates the actual result.
(define (coef n max)
  (cond ((= n 0) 1 )
        ((= n max) 1)
        ((= (remainder n 2) 0) 2)
        (else 4)))

(define (simpson-iter f a b n h cur res)
  (if (> cur n)
      res
      ( simpson-iter f a b n h (+ cur 1) (+
                                        res
                                        (* (coef cur n)
                                           (f (+ a (* cur h))))))))

(define (getH a b n)
   (/ (- b a ) n))
   
(define (simpson f a b n)
  (* (/ (getH a b n) 3)
    (simpson-iter f a b n (getH a b n) 0 0)))
 
(define (cube x) (* x x x ))

(simpson cube 0 1 1000)


Exercise 1.31

The sum procedure is only the simplest of a vast number of similar abstraction that can be captured as higher-order procedures. Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. If your product procedure generates a recursive process, write on that generates an iterative process.

Below the code is given for a recursive function product and an iterative function productIter. The lowest two lines illustrate how to use those two procedures to calculate factorials.
(define (next a)
  (+ a 1))

(define (identity a) a)

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

(define (productIter term a next b res)
  (if (> a b)
      res
      (productIter term (next a) next b (* res (term a)))))

(product identity 1 next 3)
(productIter identity 1 next 3 1)


Exercise 1.32

Show that sum and product are both special cases of a still more general notion called accumulate that combines a collection of term. Accumulate takes as argumetns the same term and range specifications as sum and product, together with a combiner procedure that specifies how the current term is to be combined with the accumulation of the preceding terms. Create both a recursive and an iteratieve procedure

(define (next a) (+ a 1))
(define (identity a) a)
(define (sum a b) (+ a b))
(define (product a b) (* a b))

(define (accumulate accumFun term a next b)
  (if (> a b)
      1
      (accumFun (term a)         
                (accumulate product term (next a) next b))))

(define (accumIter accumFun term a next b res)
  (if (> a b)
      res
      (accumIter accumFun term (next a) next b (accumFun res (term a)))))

(accumulate product identity 1 next 3)
(accumIter product identity 1 next 3 1)


Exercise 1.35

Show that the golden ratio is a fixed point of the transformation x -> 1 + 1/x, and use this fact to compute by means of the fixed-point procedure.

(define tolerance 0.000001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)


up
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.0
Page was generated in 0.5785 seconds