Lisp Programming (1082)

text (html, MIT press)
How to run your programs?
exercise 1: Write an excerpt of an article written by Alan Perlis.
- Read the article and write an excerpt (in English) in a file.
- Your file should not be too long. About 100 words are enough.
- Put your file in ~/scheme-1082/exer1
- Deadline: 2020/Mar/03 00:05 AM.
exercise 2: figure out the sum of squares of the biggest and the smallest
- Write a procedure named 'sum-of-square-extremes' which accepts three arguments and will figure out the sum of squares of the biggest and smallest.
```
      $ scheme48
      > ,load ex2-sum-square-extremes.scm
      > (sum-of-square-extremes -1 -2 9)
      85
      > (sum-of-square-extremes 9 2 1)
      82
      > (sum-of-square-extremes 9 -1 -1)      
      82
      > ,exit
      $ 
      
```
- Put your code in ~/scheme-1082/exer2
- Deadline: 2020/Mar/10 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-1082/exer3
- Deadline: 2020/Mar/17 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) - 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 p q) to get the remainder of p divided by q.
- For example:
```
      $ scheme48
      > ,load ex4-rec-iter.scm
      > (f-rec 23)
      171
      > (f-iter 23)
      171
      > (f-iter 78)
      543339722
      > (f-rec 78)
      ^C                 <-------------  take too much time, so abort
      interrupt: keyboard interrupt [command-level-event-handler]
                 keyboard
      1> ,exit
      $ 
      
```
- Your program should be put under ~/scheme-1082/exer4.
- Deadline: 2020/March/24 00:05 AM.
exercise 5: fast-expt based on cube
- Rewrite fast-expt but use cube instead of square.
  (fast-expt b n) = 1 if n = 0
  (fast-expt b n) = (cube (fast-expt b (/ n 3))) if n % 3 == 0
  (fast-expt b n) = (* b (fast-expt b (- n 1))) if n % 3 == 1
  (fast-expt b n) = (* b b (fast-expt b (- n 2))) if n % 3 == 2
- Note that you have to write two procedures. One is written in recursive way and another in linear iterative way.
- For example:
```
          
      $ scheme48
      > ,load ex5-fast-expt-cube.scm
      > (fast-expt-rec 2 10)
      1024
      > (fast-expt-iter 2 10)
      1024
      > (fast-expt-rec 1.2 100)
      82817974.52201441
      > (fast-expt-iter 1.2 100)
      82817974.52201444
      > (fast-expt-rec 0.8 100)
      2.0370359763345032e-10
      > (fast-expt-iter 0.8 100)
      2.0370359763345022e-10
      > ,exit
      $ 
      
```
- Your program should be put under ~/scheme-1082/exer5.
- Deadline: 2020/March/31 00:05 AM.

exercise 6: generalizing fast-expt

      $ scheme48
      > ,load ex6-fast.scm
      > (fast * 1 2 10)
      1024
      > (fast + 0 2 10)
      20
      > (define (*mod x y)
          (remainder (* x y) 7))
      ; no values returned
      > (fast *mod 1 2 10)
      2
      > ,exit
      $

Deadline: 2020 Apr 7 00:05 am
Put your file(s) under ~/scheme-1082/exer6

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 (pi epsilon).
The "cont-frac" should be implemented in linear iterative way.
To approximate pi, invoke (pi epsilon). It will calculate (cont-frac n d 1), (cont-fract n d 2), ... until two consecutive values are close enough, that is, the distance between them is less than epsilon.

To calculate pi, the sequence N_i is: 4, 1^2, 2^2, 3^2, ...
and the sequence D_i is: 1, 3, 5, 7, .... For example,

      $ scheme48
      > ,load ex7-cont-frac-pi.scm
      > (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 10)
      0.6179775280898876                <------ (1 + sqrt(5))/2 - 1
      > (cont-frac (lambda (i) 1.0) (lambda (i) 2.0) 10)
      0.41421355164605467               <------ sqrt(2) - 1
      > (+ 1 (cont-frac (lambda (i) 1.0) (lambda (i) 2.0) 30))
      1.4142135623730951                <------ sqrt(2)
      > (+ 1 (cont-frac (lambda (i) 2.0) (lambda (i) 2.0) 30))
      1.7320508075688772                <------ sqrt(3)
      > 
      > (pi 0.001)
      3.141463414634146
      > (pi 0.0000000001)
      3.141592653586889
      > ,exit
      $

Deadline: 2020 Apr 14 00:05 am
Put your file(s) under ~/scheme-1082/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: 2020/May/05 00:05
- Put your file(s) under ~/scheme-1082/exer8

exercise 9: extracting a sub-list

Write a function, (sublist L start-index sublen), which returns a sublist from L, starting from start-index and with length=sublen.

For example:

      $ scheme48
      > (sublist '(0 1 2 3 4) 1 3)
      '(1 2 3)
      > (sublist '(0 1 2 3 4) 0 2)
      '(0 1)
      > (sublist '(0 1 2 3 4) 1 0)
      '()
      > (sublist '(0 1 2 3 4) 4 2)
      '(4)
      > (sublist '(0 1 2 3 4) 4 1)
      '(4)
      > (sublist '(0 1 2 3 4) 5 2)
      '()
      > (sublist '(0 1 2 3 4) 2 5)
      '(2 3 4)
      > ,exit
      $

Deadline: 2020/May/12 00:05
Put your file(s) under ~/scheme-1082/exer9

exercise 10: iterative count-leaves
- Refer to count-leaves in the text.
- You should re-implement it in linear-iterative way.
- The list can be used like a stack, so that you can push (cons) the temporary result and pop (car and cdr) the data out.
```
       $ scheme48
       > ,load ex10-iter-count-leaves.scm
       > (count-leaves '(1 2 3 4 5))
       5
       > (count-leaves '(1 2 (((3))) 4 (5 6)))
       6
       > (count-leaves '((1 2) 3 (((((5)))))))
       4
       > ,exit
       $ 
       
```
- Deadline: 2020/May/19 00:05 am
- Put your file(s) under ~/scheme-1082/exer10
exercise 11: practicing sequence interface
- Write a procedure (sum-relative-prime n) which will compute the sum of numbers which are less than n and relative prime to n.
```
 
      $ scheme48
      > ,load ex11-sum-rel-prime.scm
      > (sum-relative-prime 7)
      21
      > (sum-relative-prime 12)
      24
      > (sum-relative-prime 97)  
      4656
      > ,exit
      $ 
      
```
- You should write your program with "enumerate-interval", "accumulate", and "filter".
- Deadline: 2020/May/26 00:05 am
- Put your file(s) under ~/scheme-1082/exer11

exercise 12: 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 ex12-enum-tuples.scm
      > (enum-tuples)
      ()
      > (enum-tuples '(a b c))
      ((a) (b) (c))
      > (enum-tuples '(1 2) '(hello ohio aloha))
      ((1 hello) (2 hello) (1 ohio) (2 ohio) (1 aloha) (2 aloha))
      > (enum-tuples '(1 2) '(11 22) '(999))
      ((1 11 999) (2 11 999) (1 22 999) (2 22 999))
      > ,exit
      $

Deadline: 2020/June/02 00:05 am
Put your file(s) under ~/scheme-1082/exer12

exercise 13: making a linear congruential generator

Define a procedure, (make-lcg a c m seed) which will generate a linear congruential generator where seed is the X_0 and a,c,m form the recurrence relation
X_{n+1} = (a X_{n} + c) mod m.

      $ scheme48
      > ,load ex13-make-lcg.scm
      > (define r1 (make-lcg 7 12 179 3))
      ; no values returned
      > (define r2 (make-lcg 33 55 1221 22))
      ; no values returned
      > (r1)
      3
      > (r1)
      33
      > (r1)
      64
      > (r2)
      22
      > (r2)
      781
      > ,exit
      $

Deadline: 2020/June/09 00:05 am
Put your file(s) under ~/scheme-1082/exer13