Lisp Programming (1102)

text (html, MIT press)
How to run your programs?
exercise 1: summary the Forward written by Alan Perlis.
- Read the Forward , and write a summary at least 100 words in a file.
- Put your file in ~/scheme-1102/exer1
- Deadline: 2022/Feb/22 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,
```
      $ scheme48
      > ,load ex2.scm
      > 
      > (square-mid 1 1 1)
      1
      > (square-mid 0 1 2)
      1
      > (square-mid 1 -1 -3)
      1
      > (square-mid 3 -9 -9)
      81
      > ,exit
      $ 
      
```
- Put your file in ~/scheme-1102/exer2
- Deadline: 2022/Mar/01 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-1102/exer3
- Deadline: 2022/Mar/08 00:05 AM.
exercise 4: recursive and linear iterative
- Refer to exercise 1.11 but the formula is changed to
  f(n) = n if n < 3
  f(n) = f(n-1) - f(n-2) + 2*f(n-3) if n ≥ 3 and n is even
  f(n) = 2*f(n-1) + f(n-2) - f(n-3) if n ≥ 3 and n is odd
- 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 test if a number is even.
- For example:
```
      $ scheme48
      > ,load ex4-fun.scm
      > (fun-rec 12)
      504
      > (fun-ite 12)
      504
      > (fun-ite 101)
      4298817677507282099568640
      > (fun-rec 101)
      ^C                     <----------- take too much time, so abort
      interrupt: keyboard interrupt [command-level-event-handler]
                 keyboard
      1> ,exit
      $ 
      
```
- Your program should be put under ~/scheme-1102/exer4.
- Deadline: 2022/March/15 00:05 AM.
exercise 5: linear-iterative expmod
- Write a linear-iteraitve expmod.
- Check exercise 1.16 for how to convert 'recursive' to 'iterative'.
- Your program should be put under ~/scheme-1102/exer5
- The name of your function should be named ``expmod''.
- Deadline: 2022/Mar/22 00:05 AM.
exercise 6: filtered accumulate
- Refer to exercise 1.33.
- Write a linear iterative filtered-accumulate and with this procedure write two procedures,
  - prod-prime which calculate the product of all positive integers less than n that are relative prime to n
  - prod-prime-mod which calculate the remainder of the previous product with n
  - You should define certain auxiliary functions and with them invoke your filtered-accumulate to complete the two previous procedures. For prod-prime-mod, you can not just calculate the product and then do remainder. You should define an operator which will do multiplication and remainder together.
- Summary: filtered-accumulate, prod-prime, prod-prime-mod, and other small functions.
```
       --prompt--> scheme48
       > ,load ex6-filtered-accu.scm
       > 
       > (filtered-accumulate * 1 identity 1 inc 10 odd?)
       945
       > (filtered-accumulate * 1 identity 1 inc 10 even?)
       3840
       > (prod-prime 5)       ;; 1 * 2 * 3 * 4
       24
       > (prod-prime 6)       ;; 1 * 5
       5
       > (prod-prime-mod 5)   ;; 1 * 2 * 3 * 4 mod 5
       4
       > (prod-prime-mod 6)   ;; 1 * 5 mod 6
       5
       > (prod-prime-mod 29)  ;; 1 * 2 * 3 * 4 .... 28 mod 29
       28
       > (prod-prime-mod 31)  ;; if p is prime then (prod-prime-mod p) = p-1
       30
       > ,exit
       --prompt--> 
      
```
- Put your file(s) under ~/scheme-1102/exer6
- Deadline 2022/Mar/29, 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 (sqrt x).
The "cont-frac" can be implemented in linear iterative way or linear recursive way..
Use your "cont-frac" to rewrite sqrt.
That is, you have to invoke "cont-frac" with appropriate procedures to get the result.

For example,

      $ scheme48
      > ,load ex7-cont-frac-sqrt.scm
      > (+ 1 (cont-frac (lambda (i) i) (lambda (i) i) 200))
      1.5819767068693262
      > 
      > (sqrt 100)
      9.999999999999996
      > (+ 1 (cont-frac (lambda (i) 99) (lambda (i) 2) 200))
      9.999999999999996
      >
      > (sqrt 0.0001)
      0.010365573432748798
      > (- 1 (cont-frac (lambda (i) -0.9999) (lambda (i) -2) 200))
      0.010365573432748798
      > ,exit
      $

Deadline: 2022 Apr 05 00:05 am
Put your file(s) under ~/scheme-1102/exer7

exercise 8: iterative improve
- Refer to exercise 1.46.
- First you have to write a procedure, (iterative-improve ok? improve), which accepts two arguments.
  First argument is a procedure which is used to test if the current guess is good enough.
  Second argument is also a procedure which is used to improve the current guess.
  That is, both arguments are like (lambda (x) .....).
- The return value of "iterative-improve" is a procedure which, when invoked with an initial guess, will return the approximated answer. That is, the usage is like:
  ((iterative-improve your-ok? your-improve) guess).
- (your-ok? g0) will determine if g0 is good enough. (That is, it will return a boolean value.)
- (your-improve g0) will, based on g0, return the next improved guess.
- After "iterative-improve" is written, you have to use it to rewrite "sqrt". That is, your new sqrt must invoke iterative-improve with appropriate arguments.
  And to avoid redefine system sqrt, the new sqrt is named ``mysqrt'.
- For example,
```
      $ scheme48
      > ,load ex8-iter-improve.scm
      > 
      > (mysqrt 144)
      12.000000012408687
      > (mysqrt 0.0001)
      0.010000714038711746
      > ((iterative-improve (lambda (x) (> x 100)) (lambda (x) (+ x 0.3))) 0.7)
      100.29999999999941
      > ,exit
      $ 
     
```
- Deadline: 2022/Apr/26 00:05 am
- Put your file(s) under ~/scheme-1102/exer8
exercise 9: 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 ex9-pair-int.scm
      > (define x (my-cons 2 -5))
      ; no values returned
      > (my-car x)
      2
      > (my-cdr x)
      -5
      > ,exit
      $ 
      
```
- Deadline: 2022/May/03 00:05
- Put your file(s) under ~/scheme-1102/exer9
exercise 10: finding the second max of arguments
- Refer to exercise 2.20 for variable number of arguments.
- Write a procedure, (second-max a b ....), which accepts at least two arguments, and returns the second max of them.
- For example:
```
      $ scheme48
      > ,load ex10-second-max.scm
      > (second-max 1 2 3 4 5 6 9 9 10 8)
      9
      > (second-max 2 2)
      2
      > (seoncd-max 3 2)
      > ,exit
      $  
      
```
- Deadline: 2022/May/10 00:05
- Put your file(s) under ~/scheme-1102/exer10

exercise 11: generate and filter triples

Generate all triples and filter them so that in each triple one element is equal to the sum of the other two.
Use `filter' and `flatmap'.

For example:

      $ scheme48
      > ,load ex11-triples.scm
      > (sum-triples '(1 2 3) '(3 4 5) '(4 5 6))
      ((1 3 4) (1 4 5) (1 5 4) (1 5 6) (2 3 5) (2 4 6) (3 3 6))
      > (sum-triples '(1 2) '(9) '(8 7))
      ((1 9 8) (2 9 7))
      > (sum-triples '(1 1 1) '(2) '(3 3))
      ((1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3))
      > ,exit
      $

Deadline: 2022/May/17 00:05
Put your file(s) under ~/scheme-1102/exer11

exercise 12: extending the deriving procedure
- Refer to exercise 2.56.
- Deadline: 2022/May/24 00:05
- Put your file(s) under ~/scheme-1102/exer12

exercise 13: monitor a function

Refer to exercise 3.2.

The ``f'' may take more than one arguments. See the examples below.
You may have to use ``apply''.

      $ scheme48
      > ,load ex13-monitor.scm
      > 
      > (define add (make-monitored +))
      ; no values returned
      > (add 'how-many-calls)
      0
      > (add 2 4 5)
      11
      > (add 'how-many-calls)
      1
      > (define (accumulate op e L)
          (if (null? L) e
              (op (car L) 
                  (accumulate op e (cdr L)))))
      ; no values returned
      > 
      > (accumulate + 0 '(1 2 3 4 5 6))
      21
      > (accumulate add 0 '(1 2 3 4 5 6))
      21
      > (add 'how-many-calls)
      7
      > ,exit
      $

Deadline: 2022/May/31 00:05 am
Put your file(s) under ~/scheme-1102/exer13