Lisp Programming (1131)

textbook (html, MIT press)
How to run your programs?
exercise 1: summary the preface of "Thinking Forth."
- Read the the first two paragraphs of preface of Thinking Forth , and write a summary at least 50 words in a file.
- Put your file in ~/scheme-1131/exer1
- Deadline: 2024/Sep/17 00:05 AM.
exercise 2: calculate the difference of the larger two of three numbers
- Write a procedure which accepts three arguments and returns the difference of the larger two of them.
- For example,
```
      $ scheme48
      > ,load ex2-diff-of-larger-two.scm
      > (diff-of-larger-two -1 -2 10)
      11
      > (diff-of-larger-two 100 3 9)
      91
      > (diff-of-larger-two -1 -2 -100)
      1
      > ,exit
      $ 
      
```
- Put your file in ~/scheme-1131/exer2
- Deadline: 2024/Oct/01 00:05 AM.
exercise 3: Calculate the root of a polynomial
- Write a procedure, named (root-of-poly Z), which will return x such that
  x³ + x² - Z = 0
- For improving a guess, check newton method. The first guess should be 1.0.
- For estimating if a guess is good enough, please use the idea discussed in exercise 1.7.
- For example:
```
      $ scheme48
      > ,load ex3-root-of-poly.scm
      > (root-of-poly 2)
      1.0
      > (root-of-poly 0.375)
      0.5
      > (root-of-poly 1.0)
      0.7548776662466928
      > (root-of-poly -2.0)
      -1.695620769559862
      > (root-of-poly -4)
      -2.0
      > ,exit 
      $ 
      
```
- Put your code in ~/scheme-1131/exer3
- Deadline: 2024/Oct/08 00:05 AM.

exercise 4: recursive and linear iterative

Refer to exercise 1.11 but the formula is changed.
See pseudo code in following example.
Note that you have to write two procedures. One is written in recursive way and another in linear iterative way.
You can use (even? n) to check if n is even.

For example:

      $ cat ex4-func.scm 
      ;
      ;  f(n) = 0   if n < 0
      ;       = 9   if n = 0
      ;       = 2   if n = 1
      ;       = f(n-1) + f(n-2) - n/2,   n > 1 and n is even
      ;       = f(n-1) - f(n-2) + 1      n > 1 and n is odd
      ;
      
      (define (recur n)
        ........)
      (define (iter n)
        ........)
      $ 
      $
      $ scheme48
      > ,load ex4-func.scm
      > (recur 0)
      9
      > (iter 0)
      9
      > (recur 1)
      2
      > (iter 1)
      2
      > (recur -10)
      0
      > (iter -100)
      0
      > (recur 29)
      1669
      > (iter 29)
      1669
      > (iter 100)
      89238786449
      > (recur 100)  <------- take too much time, just break 
      ^C
      interrupt: keyboard interrupt [command-level-event-handler]
                 keyboard
      1> ,exit
      $

You should put your program under ~/scheme-1131/exer4.
Deadline: 2024/Oct/15 00:05 AM.

exercise 5: fast matrix exponentiation

Write a procedure to calculate the second component of Mⁿ * v,
where M is a 2x2 matrix and v is a 2x1 vector.

For example:

      $ cat ex5-mat-exp.scm 
      ;
      ;  (mat-exp-iter a b c d n x y)
      ;    where a, b, c, and d denote a matrix M
      ;       M = (a b
      ;            c d)
      ;    and x, y denote a vectorv v
      ;       v = (x
      ;            y)
      ;  when n = 0 return y
      ;  otherwise, return y of M^n * v 
      ;
      (define (mat-exp-iter a b c d n x y)
        .....
      $ scheme48
      > ,load ex5-mat-exp.scm
      > (mat-exp-iter 1 1 1 0 0 1 0)
      0
      > (mat-exp-iter 1 1 1 0 10 1 0)
      55
      > (mat-exp-iter 1 0 0 1 15000 1 4)
      4
      > (mat-exp-iter 1 0 0 2 34 1 1)
      17179869184
      > ,exit
      $

You should put your program under ~/scheme-1131/exer5.
Deadline: 2024/Oct/22 00:05 AM.

exercise 6: generalized accumulator

You have to write two procedures.

First is (accu op init term a end? next)
which will accumulate the values according to the rule:

        if (end? a) then 
          return init
        else 
          collect (term a) with op, and a is changed to (next a)

The second is (hail n)
which counts how many conversion are done in the hailstone sequence started with n.
If n==1, the sequence is over and there is no conversion.
Otherwise if n is even, n is converted to n/2
Otherwise if n is odd, n is converted to 3*n + 1
The (hail n) must be implemented with just one invocation of (accu ....) . Of course, you can define internal help functions.

For example:

      $ scheme48
      > ,load ex6-accu.scm
      > 
      > (accu + 0 
          (lambda (x) x)
          1
          (lambda (x) (> x 100))
          (lambda (x) (+ x 1)))
      5050
      > 
      > (accu + 0
          (lambda (x) x)
          100
          (lambda (x) (< x 0))
          (lambda (x) (- x 2)))
      2550
      >
      > (hail 1)    ; 1, done
      0
      > (hail 2)    ; 2 --> 1
      1
      > (hail 1024) ; 1024 --> 512 .... --> 1
      10
      > (hail 11)   ; 11 --> 34 --> 17 --> 52 ...
      14
      > (hail 34)
      13
      > (hail 10)   ; 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1
      6
      > ,exit
      $

You should put your program under ~/scheme-1131/exer6.
Deadline: 2024/Oct/29 00:05 AM.

exercise 7: generalized fibonacci sequence generator

You have to write two procedures, (make-fib a b F G P) and (fibonacci n) .
Your (fibonacci n) must be made by just one invocation of (make-fib ...) .

For example:

      $ cat ex7-make-fib.scm
      ; (make-fib a b F G P) will return a procedure f,
      ; where f(n) = a,                  if n=0
      ;            = b,                  if n=1
      ;            = F(f(n-1), f(n-2)),  if n>1 and P(n)
      ;            = G(f(n-1), f(n-2)),  otherwise
      ;
      (define (make-fib a b F G P) ...)
      
      (define fibonacci (make-fib ...))
      $
      $ scheme48
      > ,load ex7-make-fib.scm
      >
      > (define f (make-fib 1 -1 + - even?))
      ; no values returned
      > (f 0)
      1
      > (f 1)
      -1
      > (f 2)
      0
      > (f 3)
      1
      > (f 10)
      3
      > (f 101)
      4807526976
      >
      > (fibonacci 0)
      0 
      > (fibonacci 10)
      55
      >
      > ,exit
      $

You should put your program under ~/scheme-1131/exer7.
Deadline: 2024/Nov/05 00:05 AM.

exercise 8: representing a triple with a number

Refer to exercise 2.5.
Note the requirement of nonnegative is removed. Your method should accept three integers.
Rational operation should not be used in your program.

You have to write 6 procedures as shown below.

      $ 
      $ cat ex8-triple.scm 
      (define (fast-expt b n) ....)
      (define (extract-exp n b) ....) 
      
      (define (make-triple a b c)  ....)
      (define (first  x) ...)
      (define (second x) ...)
      (define (third  x) ...)
      $  
      $ scheme48
      > ,load ex8-triple.scm
      >
      > (fast-expt 2 10)
      1024
      > (extract-exp 72 2)
      3
      > (extract-exp 72 9)
      1
      > (extract-exp 72 3)
      2
      > (extract-exp 72 11)
      0
      >
      > (define x (make-triple 3 -9 0))
      ; no values returned
      > (first x)
      3
      > (second x)
      -9
      > (third x)
      0
      > ,exit
      $

You should put your program under ~/scheme-1131/exer8.
Deadline: 2024/Nov/19 00:05 AM.

exercise 9: handling variable number of arguments

Refer to exercise 2.20.
Write a generalized `same-parity'. The procedure is
(select p x₀ x₁ x₂ x₃ ..... x_n),
where p is mandatory, and x₀, x₁ ...x_n are optional.
p is a predicate which is called like (p k x_k). and will return a boolean value.
The `select' will return a list consisted of x_i where (p i x_i) return true.
Write same-parity with the previous select.
You will need apply and its usage is shown below.

For example:

      $ 
      $ cat ex9-select.scm 
      (define (select f . items)   ....)
      
      (define (same-parity a . items)
        (apply select ....))
      ;
      ; (apply f L), apply f with argument list L, 
      ;   for example: (apply + (list 7 9 11)) ==>  (+ 7 9 11)
      ; If `f' can accept variable number of arguments, `apply' is a must
      ; since it is impossible to invoke f like (f 1 2) and (f a b c d)
      ; simultaneously in a program. 
      ;
      $ 
      $ 
      $ scheme48
      > ,load ex9-select.scm
      > 
      > (select (lambda (n x) (even? n)) 0 1 2 3 4 5 6 7 11)
      (0 2 4 6 11)
      >
      > (select (lambda (n x) (odd? x)) 0 1 2 3 4 5 6 7 11)
      (1 3 5 7 11)
      >
      > (same-parity 1 2 3 4 5 6 7 8 9 11 13 14)
      (1 3 5 7 9 11 13)
      >
      > (same-parity 0 1 2 3 4 5 6 7 8 9 11 13 14)
      (0 2 4 6 8 14)
      >
      > ,exit
      $

Deadline: 2024/Nov/26 00:05
Put your file(s) under ~/scheme-1131/exer9

exercise 10: quick sort

Consult your book of algorithm for explanation of quick sort.
Write two procedures, (partition a L) and (qsort L) .
Your partition should be implemented with filter.
The (partition a L) will partition L into two lists, left and right,
where ``left'' consists of elements in L which are less than a,
and ``right'' consists of elements in L which are equal to or greater than a.
The procedure will return (left right).

For example:

      $
      $ cat ex10-qsort.scm
      ;
      ; the definition of filter
      ; you can copy it from textboot.
      (define (filter p L) ...)
      
      ; 
      ; the partition implemented with filter
      (define (partition a L) ...)
      
      (define (qsort L) ...)
      $  
      $
      $ scheme48 
      > ,load ex10-qsort.scm
      >                    
      > (partition 7 '(1 2 3 4 5 77 -9 10)) 
      ((1 2 3 4 5 -9) (77 10))
      >
      > (partition 7 '(7 7 7 7 7))
      (() (7 7 7 7 7))
      >
      > (partition 7 '(1 2 7 7 1 100))
      ((1 2 1) (7 7 100))
      >
      > (qsort '())
      ()
      >
      > (qsort '(34))
      (34)
      >
      > (qsort '(12 10)) 
      (10 12)
      >
      > (qsort '(1 2 3 4 5 77 -9 10))
      (-9 1 2 3 4 5 10 77)
      >
      $

Deadline: 2024/Dec/03 00:05
Put your file(s) under ~/scheme-1131/exer10

exercise 11: generating a random sequence

Write (make-rnd a b m s) which will create a pseudo random sequence by linear congruential method.
Note you can reset the random sequence started with another seed by passing the resultant procedure a number. See examples below.

For example:

      $ 
      $ cat ex11-rnd.scm 
      ;
      ; s = (a*s + b) mod m
      ;
      (define (make-rnd a b m s) ...)
      $  
      $ scheme48
      > ,load ex11-rnd.scm
      > (define r (make-rnd 7 11 119 0))
      ; no values returned
      > (r)
      11     <------  (7*0 + 11) % 119 = 11
      > (r)
      88     <------  (7*11 + 11) % 119 = 88
      > (r 1002)
      50     <------  s reset to 50 = 1002 % 119
      > (r)
      4      <------  (7*50 + 11) % 119 = 4
      > (r)
      39     <------  (7*4 + 11) % 119 = 39
      > (r)
      46     <------  (7*39 + 11) % 119 = 46
      > ,exit
      $

Deadline: 2024/Dec/10 00:05
Put your file(s) under ~/scheme-1131/exer11

exercise 12: Draw environment figures
- Refer to exercise 3.11. You have to draw two figures like Figure 3.11.
- Draw the figure when (make-account ..) is defined.
- Draw the figure when ((acc 'deposit) 40) is invoked.
  Since (acc..) may call another procedures, draw the figure when there are most number of frames.
- The second figure just add something on the first figure, so the two figured can be combined with
  drawing the first figure with one color and
  drawing the addition with another color.