Lisp Programming (1092)

text (html, MIT press)
How to run your programs?
exercise 1: summary first three sections of an article written by Alan Perlis.
- Read first three sections of an article , extract a most important sentence for each section, and write sentences in a file.
- Put your file in ~/scheme-1092/exer1
- Deadline: 2021/Mar/02 00:05 AM.
exercise 2: calculate the difference of max and min of three numbers
- Write a procedure which accepts three arguments and returns the difference of the maximum and the minimum of them.
- For example,
```
      $ scheme48
      > ,load ex2-diff.scm
      > (diff 2 5 8)
      6
      > (diff 2 5 -8)
      13
      > (diff 2 2 8)
      6
      > ,exit
      $ 
      
```
- Put your file in ~/scheme-1092/exer2
- Deadline: 2021/Mar/09 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-1092/exer3
- Deadline: 2021/Mar/16 00:05 AM.
exercise 4: linear 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) if n ≥ 3 and n % 3 == 0
  f(n) = f(n-1) - f(n-2) if n ≥ 3 and n % 3 != 0
- Note that you have to write two procedures. One is written in recursive way and another in linear iterative way.
- You can use (remainder p q) to get the remainder of p divided by q.
- For example:
```
      $ scheme48
      > ,load ex4-ite-rec.scm
      > (rec 4)
      1
      > (ite 4)
      1
      > (ite 1000)
      1
      > (rec 1000)
      ^C                    <------------------ take too much time, so abort
      interrupt: keyboard interrupt [command-level-event-handler]
                 keyboard
      1> ,exit
      $ 
      
```
- Your program should be put under ~/scheme-1092/exer4.
- Deadline: 2021/March/23 00:05 AM.

exercise 5: complex fast-expt

Refer to exercise 1.16.
Write a procedure, named (comp-fast-expt a b n), which calculates (a + bi)^n in linear iterative way with O(log n) time.
You can use (list a b) to combine two numbers in a list.

For example:

      $ cat ex5-comp-expt.scm 
      (define (comp-fast-expt a b n)
        (define (iter a b c d n)
           (cond ((= n 0) (list a b))    <---- Use (list a b)!
         .......
      $ 
      $ scheme48
      > ,load ex5-comp-expt.scm
      > (comp-fast-expt 0 1 100)
      (1 0)
      > (comp-fast-expt 0 1 10)
      (-1 0)
      > (comp-fast-expt 0 1 15)
      (0 -1)
      > (comp-fast-expt .70710678118654 .70710678118654 10000)
      (0.9999999998939737 0.0)
      > ,exit
      $

Your program should be put under ~/scheme-1092/exer5.
Deadline: 2021/March/30 00:05 AM.

exercise 6: fast-fib mod m
- Refer to exercise 1.19.
- Write a procedure, named (fib-mod n m), which calculates f_n mod m in O(log n) time.
- Use the idea of exercise 1.19 to figure out the answer quickly. O(log n) is a must.
- The mod operation should be done after each multiplication or addition. Not just be done only once at the end.
- For example:
```
      $ scheme48
      > ,load ex6-fast-fib-m.scm
      > (fib-mod 1234567890 12119)
      10091
      > ,exit
      $ 
      
```
- Your program should be put under ~/scheme-1092/exer6.
- Deadline: 2021/April/06 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: 2021 Apr 13 00:05 am
Put your file(s) under ~/scheme-1092/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: 2021/May/04 00:05
- Put your file(s) under ~/scheme-1092/exer8
exercise 9: finding the second smallest of arguments
- Refer to exercise 2.20 for variable number of arguments.
- Write a procedure, (second a b ....), which accepts at least two arguments, and returns the second smallest of them.
- For example:
```
      $ scheme48
      > ,load ex9-second.scm
      > (second 1 2 9 43 32  -1)
      1
      > (second 1 2 9 32 32 0 99 33 4 4 4)
      1
      > (second 10 9 8 7 6 4 4 4 4 4)
      4
      > ,exit
      $ 
      
```
- Deadline: 2021/May/11 00:05
- Put your file(s) under ~/scheme-1092/exer9

exercise 10: iterative fringe

Refer to exercise 2.28.
You should implement it in linear-iterative way.
The list can be used like a stack in the way that
you can push the temporary result by ``cons''
and pop the data out by ``car'' and ``cdr''.

The following shows an example and gives the explanation.

      $ scheme48
      > ,load ex10-iter-fringe.scm
      > (fringe '(4 (7 8) ((9) 11) 3))
      (4 7 8 9 11 3) 
      > ,exit
      $ 
      
      The result for each iteration is shown below for explanation.
      Note the temporary result is stored reversed. 
      So it has to be reversed before return. 
      Note (reverse L) is provided by system. You do not need to write it again.
      
      (4 (7 8) ((9) 11) 3)    ()    <-- '4' is not a pair, so move to result 
      ((7 8) ((9) 11) 3)     (4)    <-- (7 8) is a pair, so transform and store
      (7 (8) ((9) 11) 3)     (4)        back to list
      ((8) ((9) 11) 3)     (7 4)        
      (8 () ((9) 11) 3)    (7 4)  
      (() ((9) 11) 3)    (8 7 4)    <-- () is discarded
      (((9) 11) 3)       (8 7 4)    
      ((9) (11) 3)       (8 7 4)    
      (9 () (11) 3)      (8 7 4)    
      (() (11) 3)      (9 8 7 4)
      ((11) 3)         (9 8 7 4)
      (11 () 3)        (9 8 7 4)
      (() 3)        (11 9 8 7 4)
      (3)           (11 9 8 7 4)
      ()          (3 11 9 8 7 4)    <-- reversed result

Deadline: 2021/May/18 00:05
Put your file(s) under ~/scheme-1092/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 '(a b c))
      ((a) (b) (c))
      >
      > (enum-tuples '(10 19 21) '(klim oak))
      ((10 klim) (19 klim) (21 klim) (10 oak) (19 oak) (21 oak))
      >
      > (enum-tuples '(a b) '(x y z) '(osaka rei))
      ((a x osaka) (b x osaka) (a y osaka) (b y osaka) (a z osaka) (b z osaka) (a x rei) (b x rei) (a y rei) (b y rei) (a z rei) (b z rei))
      > ,exit
      $

exercise 12: extending the deriving procedure
- Refer to exercise 2.56.
- Deadline: 2021/June/01 00:05
- Put your file(s) under ~/scheme-1092/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: 2021/June/8 00:05 am
Put your file(s) under ~/scheme-1092/exer13