Lisp Programming (1111)

textbook (html, MIT press)
How to run your programs?
exercise 1: summary the Foreward written by Alan Perlis.
- Read the Foreward , and write a summary at least 100 words in a file.
- Put your file in ~/scheme-1111/exer1
- Deadline: 2022/Sep/20 00:05 AM.
exercise 2: figure out the sum of squares of the smaller two arguments
- Write a procedure named 'sum-of-square-smaller-two' which accepts three arguments and figures out the sum of squares of the smaller two of the arguments.
```
      $ scheme48
      > ,load ex2-sum-square-smaller-two.scm
      > 
      > (sum-of-square-smaller-two 1 2 3)
      5
      > (sum-of-square-smaller-two 1 2 -3)
      10
      > (sum-of-square-smaller-two 2 2 2)
      8
      > ,exit
      $ 
      
```
- Put your code in ~/scheme-1111/exer2
- Deadline: 2022/Sep/27 00:05 AM.
exercise 3: Calculate the cube-root
- Write a procedure, named (cube-root x), which will return y such that y^3 = x.
- For improving a guess, check exercise 1.8.
- For estimating if a guess is good enough, please use the idea discussed in exercise 1.7.
- For example:
```
      $ scheme48
      > ,load ex3-cube-root.scm
      > (cube-root 1331)
      11.0
      > (cube-root 512)
      8.0
      > ,exit
      $  
      
```
- Put your code in ~/scheme-1111/exer3
- Deadline: 2022/Oct/04 00:05 AM.
exercise 4: recursive and linear iterative
- Refer to exercise 1.11 but the formula is changed to
  f(0) = 7
  f(1) = 3
  f(2) = 5
  f(n) = -f(n-1) + f(n-2) + f(n-3) if n ≥ 3 and n %3 == 0
  f(n) = f(n-1) - f(n-2) + f(n-3) if n ≥ 3 and n %3 == 1
  f(n) = -f(n-1) + f(n-2) - f(n-3) if n ≥ 3 and n %3 == 2
- Note that you have to write two procedures. One is written in recursive way and another in linear iterative way.
- You can use (remainder n m) to compute the remainder of n divided by m.
- For example:
```
      $ scheme48
      > ,load ex4.scm
      > (fun-rec 0)
      7
      > (fun-rec 5)
      -3
      > (fun-rec 10)
      51
      > (fun-ite 10)
      51
      > (fun-ite 100)
      84553538310603107
      > (fun-rec 100)     <------------- take too much time to run
      ^C
      interrupt: keyboard interrupt [command-level-event-handler]
                 keyboard
      1> ,exit
      $ 
      
```
- Your program should be put under ~/scheme-1111/exer4.
- Deadline: 2022/Oct/11 00:05 AM.

exercise 5: linear-iterative expmod

Write a linear-iteraitve expmod.
Check exercise 1.16 for how to convert 'recursive' to 'iterative'.
The name of your function should be named ``expmod''.
You should define two internal procedures named, *mod, square.

For example:

      $
      $ cat ex5.scm 
      (define (expmod b n m)
        (define (*mod a b)  . . . . )
        (define (square x)  . . . . )
        (define (iter res b n)  . . . )
        (iter 1 b n))
      $ 
      $ scheme48
      > ,load ex5.scm
      > 
      > (expmod 3 1000 123)
      42
      > (expmod 3 0 123)
      1
      > (expmod 3 101 10)
      3
      > (expmod 123232 11123232322 1123)
      256
      > ,exit
      $

Your program should be put under ~/scheme-1111/exer5
Deadline: 2022/Oct/18 00:05 AM.

exercise 6: filtered accumulate

Refer to exercise 1.33.
Write a linear-iterative filtered-accumulate.
Using the above filtered-accumulate, write a procedure, named (sum-divisors n), which calculates the sum of divisors of n.

For example:

      $ scheme48
      > ,load ex6.scm
      > 
      > (define (ok k) #t)       ;; always true
      ; no values returned
      > (define (inc x) (+ x 1))
      ; no values returned
      > (define (id x) x)
      ; no values returned
      > (filtered-accumulate ok + 0 id 1 inc 10)
      55
      > (filtered-accumulate ok * 1 id 1 inc 10)
      3628800
      > (filtered-accumulate even? + 0 id 1 inc 10)
      30
      > (sum-divisors 10)
      18
      > (sum-divisors 1)
      1
      > (sum-divisors 120)
      360
      > ,exit
      $

Your program should be put under ~/scheme-1111/exer6
Deadline: 2022/Oct/25 00:05 AM.

exercise 7: calculating continued-fraction
- Refer to exercise 1.37.
- You have to write two procedures. One is (cont-frac n d k) and another is (root x).
- The "cont-frac" can be implemented in linear iterative way or linear recursive way..
- Use your "cont-frac" to write (root x).
  The (root x) computes the root of f(y)=y^2-y-x.
  Assume x >= 0.
- For example,
```
      $ scheme48
      > ,load ex7.scm
      > (+ 1.0 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 1000))
      1.618033988749895
      > 
      > (root 5)
      2.7912878474779195
      > (root 0)
      1.0
      > (root 1)  
      1.618033988749895
      > ,exit
      $ 
      
```
- Deadline: 2022 Nov 01:05 am
- Put your file(s) under ~/scheme-1111/exer7
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.
- For example:
```
      $ scheme48
      > ,load ex8-pair-int.scm
      > (define x (my-cons 2 -5))
      ; no values returned
      > (my-car x)
      2
      > (my-cdr x)
      -5
      > ,exit
      $ 
      
```
- Deadline: 2022/Nov/22 00:05
- Put your file(s) under ~/scheme-1111/exer8

exercise 9: handling variable number of arguments

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

For example:

      $ scheme48
      > ,load ex9-select.scm
      > (select (lambda (x y) (= x y)) 10 1 2 3 10 20 10)
      (10 10)
      > (select (lambda (x y) (even? y)) 10 1 2 3 4 5 6 7 8)
      (2 4 6 8)
      > (select (lambda (x y) (even? (+ x y))) 4 1 2 3 4 5 6 7 8 9 10 11)
      (2 4 6 8 10)
      > (same-parity 4 1 2 3 4 5 6 7 8 9 10 11)
      (4 2 4 6 8 10)
      > (select (lambda (x y) (even? (+ x y))) 3 1 2 3 4 5 6 7 8 9 10 11)
      (1 3 5 7 9 11)
      > (same-parity 3 1 2 3 4 5 6 7 8 9 10 11)
      (3 1 3 5 7 9 11)
      > (same-parity 1)
      (1)
      >
      ; 
      ; (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                            ; the same as the first example
             (cons (lambda (x y) (= x y)) 
                   (cons 10       
                         (list 1 2 3 10 20 10))))
      (10 10)
      > ,exit

Deadline: 2022/Nov/29 00:05
Put your file(s) under ~/scheme-1111/exer9

exercise 10: converting a tree to a list in preorder

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-preorder.scm
      >
      > (preorder '(a  (b (c))  (e (f) (g))))
      (a b c e f g)
      >
      > (preorder '(a (b) (c) (f (g) (h))))
      (a b c f g h)
      >
      > (preorder '((hello) (b) ((baga me) (ok))))
      ((hello) b (baga me) ok)
      > ,exit
      $

Deadline: 2022/Dec/06 00:05
Put your file(s) under ~/scheme-1111/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.
The tuples are listed in row-major order.

      $ scheme48
      > ,load ex11-enum-tuples-row-major.scm
      > (enum-tuples) 
      ()
      > (enum-tuples '(a b c))
      ((a) (b) (c))
      > (enum-tuples '(a b c) '(11 22))
      ((a 11) (a 22) (b 11) (b 22) (c 11) (c 22))
      > (enum-tuples '(a b) '(1 2) '(ok no))
      ((a 1 ok) (a 1 no) (a 2 ok) (a 2 no) (b 1 ok) (b 1 no) (b 2 ok) (b 2 no))
      > (enum-tuples '(a b) '(yes) '(ok no) '(aloha hi))
      ((a yes ok aloha) (a yes ok hi) (a yes no aloha) (a yes no hi) (b yes ok aloha) (b yes ok hi) (b yes no aloha) (b yes no hi))
      > ,exit
      $

Deadline: 2022/Dec/13 00:05
Put your file(s) under ~/scheme-1111/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: 2022/Dec/20 00:05
Put your file(s) under ~/scheme-1111/exer12

exercise 13: monitor a function

Refer to exercise 3.2.

The ``f'' may take any number of arguments. See the examples below.
You may have to use ``apply''.

      $ scheme48
      > ,open random
      > (define a (make-random 1024))
      ; no values returned
      > (a)
      150946159
      > (a)
      44350967
      > ,load ex13-monitor.scm
      > (define f (make-monitored a))
      ; no values returned
      > (f)
      88941411
      > (f)
      154130900
      > (f 'how-many-calls?)
      2
      > (f) 
      1024
      > (f)
      159857230
      > (f)
      53732961
      > (f 'how-many-calls?)
      5
      > (f 'reset-count)
      0
      > (f)
      10059006
      > (f 'how-many-calls?)
      1
      > (define plus (make-monitored +))
      ; no values returned
      > (plus)
      0
      > (plus 1 2 3 4 5)
      15
      > (plus 'how-many-calls?)
      2
      > (plus 'reset-count)
      0
      > (plus 1 2)
      3
      > (plus 'how-many-calls?)
      1
      > ,exit
      $

Deadline: 2022/Dec/27 00:05
Put your file(s) under ~/scheme-1111/exer13