Lisp Programming (1121)

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-1121/exer1
- Deadline: 2023/Sep/19 00:05 AM.

exercise 2: calculate the square of the middle of three numbers

Write a procedure which accepts three arguments and returns the square of the middle of them.

For example,

      $
      $ cat ex2.scm 
      
      .... some auxiliary procedures
      
      (define (square-of-mid a b c)
        ..... the code ...
      
      $  
      $ scheme48
      > ,load ex2.scm
      > (square-of-mid 1 2 3)
      4
      > (square-of-mid 3 2 1) 
      4
      > (square-of-mid -1 -9 4)
      1
      > (square-of-mid -1 -1 3)
      1
      > (square-of-mid -9 -100 -9)
      81
      > ,exit
      $

Put your file in ~/scheme-1121/exer2
Deadline: 2023/Sep/28 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^3 - 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.scm
      > (root-of-poly 0)
      1.0
      > (root-of-poly -6)
      2.0
      > (root-of-poly 1200)
      -10.65795346861856
      > ,exit
      $ 
      
```
- Put your code in ~/scheme-1121/exer3
- Deadline: 2023/Oct/03 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
      ;       = 3   if n = 0
      ;       = 1   if n = 1
      ;       = f(n-1) + (n/2) * f(n-2),   n > 1 and n is even
      ;       = f(n-1) - f(n-2)            n > 1 and n is odd
      ;
      (define (recur n)
         .......
      (define (iter n)
         .......
      
      $ scheme48
      > ,load ex4-func.scm
      > 
      > (recur -9)
      0
      > (recur 6)
      41
      > (iter 6)
      41
      > (recur 19)
      4963761
      > (iter 19)
      4963761
      > (recur 20)
      59565131
      > (iter 20)
      59565131
      > (recur 30)
      30408595023479
      > (iter 30)
      30408595023479
      > ,exit
      $

Your program should be put under ~/scheme-1121/exer4.
Deadline: 2022/Oct/17 00:05 AM.

exercise 5: fast matrix exponentiation

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

For example:

      $ cat ex5-mat-exp.scm 
      ;
      ;  (mat-exp-iter M n v)
      ;    where M = (a b
      ;               c d)
      ;    and   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
      $

exercise 6: generalizing fast-expt

      $ cat ex6-fast.scm 
      ;
      ; The fast should be run in O(log n) time.
      ;
      ; (fast op unit a n) 
      ;   = unit                     if n = 0
      ;   = a 'op' a 'op' .... a,    if n > 0
      ;     (n occurrences of a)
      ; The unit should satisfy the following property.
      ;   a 'op' unit = unit 'op' a = a  for all valid a
      ;
      ; For example,
      ; (fast * 1 2 10) ---> 1024
      ; (fast + 0 2 10) ---> 20
      ;
      ; Note:
      ;  You can only assume n is a non-negative integer.
      ;  The 'a' can be something like a matric, a function, ... etc.
      ;
      
      (define (fast op unit a n)  .... )
      $ 
      $
      $ scheme48
      > ,load ex6-fast.scm
      >
      > (fast * 1 2 10)    ;;;;; 2 * 2 * 2 .... = 2 ^ 10
      1024
      > (fast + 0 2 10)    ;;;;; 2 + 2 + 2 .... = 2 * 10
      20
      > (fast (lambda (x y) (remainder (* x y) 97)) 1 
              3 100)       ;;;;;  3^100 mod 97
      81
      > ,exit
      $

Your program should be put under ~/scheme-1121/exer6
Deadline: 2023/Oct/31 00:05 AM.

exercise 7: fibonacci-like sequence generator

      $ cat ex7-make-fib.scm
      ;
      ; (make-fib a b F G P) will return a function, f, 
      ;                      which does something like
      ; 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)
        ........)
      $
      $ scheme48
      > ,load ex7-make-fib.scm
      >
      > (define fib (make-fib 0 1 + * (lambda (x) #t)))
      ; no values returned
      > (fib 0)
      0
      > (fib 10)
      55
      > (define iter (make-fib 7 2 + - 
                         (lambda (n) (= (remainder n 3) 1))))
      ; no values returned
      > (iter 0)
      7
      > (iter 1)
      2
      > (iter 10)
      -12
      > ,exit
      $

Your program should be put under ~/scheme-1121/exer7
Deadline: 2023/Nov/14 00:05 AM.

exercise 8: representing a pair with a number

Refer to exercise 2.5.
Note the requirement of nonnegative is removed. Your method should accept two integers.
You should use postive integer to represent the pair, not with a fraction number.

For example:

      $ scheme48
      $ scheme48
      > ,load ex8-pair-int.scm
      > (define a (my-cons -3 12))
      ; no values returned
      > (my-car a)
      -3
      > (my-cdr a)
      12
      > (define b (my-cons 3 -2))
      ; no values returned
      > (my-car b)
      3
      > (my-cdr b)
      -2
      > (define z (my-cons 3 4))
      ; no values returned
      > (my-car z)
      3
      > (my-cdr z)
      4
      > ,exit
      $

Deadline: 2023/Nov/21 00:05
Put your file(s) under ~/scheme-1121/exer8

exercise 9: handling variable number of arguments

Refer to exercise 2.20.
Write a generalized `same-parity'. The procedure is
(select-combine p op a x1 x2 x3 ..... xn),
where p, op, and a are mandatory, x1...xn are optional.
'p' is a predicate which is called like (p x_i). and will return a boolean value.
The `select-combine' will return a list consisted of (op a x_i) where (p x_i) return true.
Write `same-parity' with the previous `select-combine'.
You will need `apply' and its usage is shown below.

For example:

      $ scheme48
      > ,load ex9-select.scm
      > (select-combine even? + 1 2 3 4 5 6)
      (3 5 7)
      > (select-combine odd? * 1 2 3 4 5 6 7)
      (3 5 7)
      > (select-combine odd? * 2 2 3 4 5 6 7)
      (6 10 14)
      > (select-combine odd? * 2 2 4 6)
      ()
      > (same-parity 1 2 3 4 5 6 7 8 9 10)
      (1 3 5 7 9)
      > (same-parity 10 9 8 7 6 5 4 3 2 1)
      (10 8 6 4 2)
      > (same-parity 11)
      (11)
      ; 
      ; (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. 
      ;
      > (apply + (list 1 2 3))                   ;  the same as (+ 1 2 3)
      6
      > (apply + (cons 1 (cons 2 (list 7 9))))   ; the same as (+ 1 2 7 9)
      19
      > (apply select-combine                    ; the same as the first example
           (cons even?   
              (cons +
                 (cons 1
                    (list 2 3 4 5 6)))))
      (3 5 7)
      > ,exit 
      $

Deadline: 2023/Nov/28 00:05
Put your file(s) under ~/scheme-1121/exer9

exercise 10: converting a tree to a list in postorder

A tree with a single node is like: '(a).
A tree with root 'a' and two children 'b' 'c' is like: '(a (b) (c)). And more examples:

            a
          / | \      ==> (a (b) (c) (d))
         b  c  d

            a
          / | \      ==> (a (b) (c (e)) (d (f) (g))) 
         b  c  d
            |  |\
            e  f g

For example:
Note the values stored in nodes may be another list.

      $ scheme48
      > ,load ex10-postorder.scm
      > (postorder '())
      ()                          <---- empty tree
      > (postorder '(a))
      (a)                         <---- single node
      > (postorder '(a (b) (c (e) (f))))     <----------------- a
      (b e f c a)                                              / \
      >                                                       b   c
      >                                                          / \
      >                                                         e   f
      >
      > (postorder '(a ((aloha)) (c (e) ((oak milk)))))  <----  a
      ((aloha) e (oak milk) c a)                               / \
      >                                                   (aloha) c
      >                                                          / \
      >                                                         e   (oak milk)
      >
      > ,exit
      $

Deadline: 2023/Dec/05 00:05
Put your file(s) under ~/scheme-1121/exer10

exercise 11: enumerating tuples

Define a procedure, (enum-tuples list-1 list-2 .... list-k) which will generate a list of k-tuples. The tuples contains all combinations of elements from each list.

      $ scheme48
      > ,load ex11-enum-tuples.scm
      > (enum-tuples)
      ()
      > (enum-tuples '())
      ()
      > (enum-tuples '(a b c))
      ((a) (b) (c))
      > (enum-tuples '(a b c) '())
      ()
      > (enum-tuples '(a b c) '(1 2) '(x y z))
      ((a 1 x) (a 1 y) (a 1 z) (a 2 x) (a 2 y) (a 2 z) (b 1 x) 
       (b 1 y) (b 1 z) (b 2 x) (b 2 y) (b 2 z) (c 1 x) (c 1 y)
       (c 1 z) (c 2 x) (c 2 y) (c 2 z))
      > ,exit

Deadline: 2023/Dec/12 00:05
Put your file(s) under ~/scheme-1121/exer11

exercise 12: extending the deriving procedure

Refer to exercise 2.56.

For example,

      $ scheme48
      > ,load ex12-deriv.scm
      > (deriv '(+ x y) 'y)
      1
      > (deriv '(* x y) 'x)
      y
      > (deriv '(** (+ x y) 9) 'x)
      (* 9 (** (+ x y) 8))
      > (deriv '(** (+ x y) 1) 'y)
      1
      > (deriv '(** (+ x y) 2) 'y)
      (* 2 (+ x y))
      > (deriv '(** (* x y) 3) 'x)
      (* (* y 3) (** (* x y) 2))
      > ,exit
      $

Deadline: 2023/Dec/19 00:05
Put your file(s) under ~/scheme-1121/exer12

exercise 13: monitor a function

Refer to exercise 3.2.

This exercise generalizes the make-monitored in exercise 3.2:

the f may take any number of arguments
the monitored function when called with 'reset-count will reset the internal count

See the examples below.
You may have to use apply.

      $ scheme48
      > ,load ex13-monitor.scm
      > (define plus (make-monitored +))
      ; no values returned
      > (plus 1 2 3)
      6
      > (plus 9)
      9
      > (plus 9 -1 2 3 4)
      17
      > (plus 'how-many-calls?)
      3
      > (plus 'reset-count)
      0
      > (plus 1 2 3 4 5)
      15
      > (plus 'how-many-calls?)
      1
      > ,exit
      $

Deadline: 2023/Dec/26 00:05
Put your file(s) under ~/scheme-1121/exer13