Lisp 程式設計 (1032)

課本全文
How to run your programs?
exercise 1: exercising the scheme48 interpreter
- Practice the code examples in 1.1.
- Write your comment about this course in a file.
- The file should be put under ~/scheme-1032/exer1
- Deadline 2015/Mar/03 00:05 AM.
exercise 2: calculate the area of a right triangle
- Write a function which is called with three numbers.
  The function first determines if the three numbers can form a right triangle.
  If possible, the function returns the area or return 0.
- Keep your functions small and simple. Instead of writing a big function, try to break it into smaller ones.
- Put your file(s) under ~/scheme-1032/exer2
- Deadline: 2015/Mar/10 00:05 am
exercise 3: improving the good-enough? and calculating the cube-root
- Write a function which figures out the cube root of the input number (exercise 1.8) with improved good-enough? (exercise 1.7).
- You should just write a function which combines exercise 1.7 and 1.8,
- Refer to exercise 1.7 and exercise 1.8.
- Put your program under ~/scheme-1032/exer3
- Deadline 2015/Mar/17, 00:05 am
exercise 4: linear recursive and linear iterative
- Refer to exercise 1.11 but the function is changed as follows.
```
        f(n) = n                   if n < 3 
             = f(n-1) - 2*f(n-3)   otherwise
      
```
- Both linear recursive and linear iterative verions are required.
- Put your file(s) under ~/scheme-1032/exer4
- Deadline 2015/Mar/24, 00:05 am
exercise 5: linear iterative exponentiation
- Refer to exercise 1.16.
- To practice local definition, put your iterative function inside the definition of (fast-expt b n).
- Put your file(s) under ~/scheme-1032/exer5
- Deadline 2015/Mar/31, 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 reminader 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)
       24
       > (prod-prime 6)
       5
       > (prod-prime-mod 5)
       4
       > (prod-prime-mod 6)
       5
       > (prod-prime-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-1032/exer6
- Deadline 2015/Apr/07, 00:05 am
exercise 7: n-th root
- Refer to exercise 1.42, 1,43, and 1.45.
- First you have to write `compose' (exercise 1.42) and use it to write "repeated" (exercise 1.43).
- Then with compose and repeated, write "nth-root" (exercise 1.45).
  You should also use average-damp and fixed-point.
- You have to determine how many times average-damp is called such that the converted function when passed to fixed-point will converge. You have to do some experiments. Just using n is no good.
- Use the number of invocation of average-damp to write your nth-root.
- Summary: compose, repeated, number of invocation of average-damp, nth-root
```
       --prompt--> scheme48
       > ,load ex7-nth-root.scm
       > (nth-root (fast-expt 2 16) 8)
       4.0
       > (nth-root (fast-expt 2 32) 16)
       4.0
       > (nth-root (fast-expt 2 100) 50)
       3.9999999986136436
       > (nth-root (fast-expt 5 10) 10)
       4.9999999992832524
       > ,exit
       --prompt--> 
      
```
- Put your file(s) under ~/scheme-1032/exer7
- Deadline 2015/Apr/21, 00:05 am
exercise 8: Combining numbers with exponentiation and multiplication
- Refer to exercise 2.5.
- Deadline: 2015 May 5 00:05 am
- Put your file(s) under ~/scheme-1032/exer8
exercise 9: same-parity
- Refer to exercise 2.20.
- Use ``filter'' to implement. ``filter'' is defined in section 2.2.3.
- Deadline: 2015 May 12 00:05 am
- Put your file(s) under ~/scheme-1032/exer9

exercise 10: extracting the exponent quickly

Write a function, (power-of n a), which will extract the exponent of a in n. For example, if n = 2^11 * 3^9, (power-of n 2) = 11.

Please use the method as mentioned in class. Following shows the values of variables in each steps. These messages are for your reference. You do not need to output them.

       $ scheme48
       > ,load ex10-power-of.scm
       >     
       > (define a (* (expt 2 14) (expt 3 6)))
       ; no values returned
       > a
       11943936
       > 
       > (power-of a 2)
       2  --  1  --  ()
       4  --  2  --  ((2 1))
       16  --  4  --  ((4 2) (2 1))
       256  --  8  --  ((16 4) (4 2) (2 1))
       65536  --  16  --  ((256 8) (16 4) (4 2) (2 1))
       11943936  --  ((256 8) (16 4) (4 2) (2 1))  --  0
       46656  --  ((16 4) (4 2) (2 1))  --  8
       2916  --  ((4 2) (2 1))  --  12
       729  --  ((2 1))  --  14
       729  --  ()  --  14
       14
       > 
       > (power-of a 3)
       3  --  1  --  ()
       9  --  2  --  ((3 1))
       81  --  4  --  ((9 2) (3 1))
       6561  --  8  --  ((81 4) (9 2) (3 1))
       11943936  --  ((81 4) (9 2) (3 1))  --  0
       147456  --  ((9 2) (3 1))  --  4
       16384  --  ((3 1))  --  6
       16384  --  ()  --  6
       6
       > 
       > (power-of a 7)
       7  --  1  --  ()
       11943936  --  ()  --  0
       0
       > ,exit
       $

Deadline: 2015 May 19 00:05 am
Put your file(s) under ~/scheme-1032/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 '(x y z))
      '((x) (y) (z))
      > (enum-tuples '(a b c) '(hello world))
      '((a hello) (b hello) (c hello) (a world) (b world) (c world))
      > (enum-tuples '(1 2) '(h i j k))
      '((1 h) (2 h) (1 i) (2 i) (1 j) (2 j) (1 k) (2 k))
      > ,exit
      $

Deadline: 2015 May 26 00:05 am
Put your file(s) under ~/scheme-1032/exer11

exercise 12: extending the deriving procedure
- Refer to exercise 2.56.
- Deadline: 2015 June 02 00:05am
- Put your file(s) under ~/scheme-1032/exer12
exercise 13: monitoring a function
- Refer to exercise 3.2.
- Deadline: 2015 June 09 00:05am
- Put your file(s) under ~/scheme-1032/exer13

exercise 14: translating a tree to a stream

Define a procedure, (stream-enum-leaves T), which will convert a tree T to a stream.

       $ scheme48
       > ,load ex14-stream.scm
       > (define x (stream-enum-leaves '((1 2) (a (b)) (p (q (r))))))
       ; no values returned
       > x
       '(1 . #{Procedure 1168 (unnamed in make-promise in scheme-level-1)})
       > (stream-car x)
       1
       > (stream-ref x 2)
       'a
       > (display-stream x)
           
       1
       2
       a
       b
       p
       q
       r'done
       > ,exit
       $
       $ cat ex14-stream.scm
       (define-syntax cons-stream
         (syntax-rules ()
           ((cons-stream a b)
            (cons a (delay b)))))
       (define (stream-car s) (car s))
       (define (stream-cdr s) (force (cdr s)))
       (define the-empty-stream 'empty-stream)
       (define (stream-null? s) (eq? s the-empty-stream))
           
       (define (stream-ref s n)  .....
       (define (stream-enumerate-interval low high)  ....
       (define (stream-for-each proc s)   ....
       (define (display-stream s)   .....
       (define (stream-filter pred stream)   ....
       (define (stream-enum-leaves T)   ......
           
       $

Deadline: 2015 June 16 00:05 am
Put your file(s) under ~/scheme-1032/exer14