CSC 123 Scheme Lab and Assignment

                 Due one week from date assigned




In Linux, type scheme to run the interactive interpreter.  Inside the
interpreter, type (load "/path/filename") to load and interpret scheme
file as a script.

(On Adams 204 linux workstations, set path first:
export PATH=/home/shared/liang/bin:$PATH)

----

Scheme Basics Review:

All expressions are written in prefix form : (+ 3 4), (f x y)
(define x 3) ; associates a value with a variable
(define f (lambda (x y) (+ x y))) ; this time the value is a function
(f 3 4);  applies a function to arguments
(if (= 2 2) 4 5) is the same as 4 (5 if false)
#f is false, #t is true.  another representation for false is '() - the
  empty list or "null".  and non-null value can also be considered true.
(begin 3 4) - same as 4; i.e. evaluates a sequence of expressions and
return the final value as the value of the entire expression.  Only useful
for when printing as in (begin (display "a") (display "b"))

(let ((x 4)) (+ x 5))  : same as ((lambda (x) (+ x 5))  4)
  - binds a variable to a value in a temporary scope.  

(define f (lambda (x) 
  (define g (lambda (x) (* x x)))  ; local function definition
 (+ x (g x))))                     ; body of outer function 
  
The above code shows a function declared *locally* within a function,
just as you define local variables in C inside functions.  g is
not visible outside of the body of f.  (We're getting closer to having
objects with this example).

(+ 1 2)   --> 3
'(+ 1 2)  --> (+ 1 2)  : the ' operation delays evaluation.

List Data Structure:

'() : empty list, equivalent to null pointer
(cons 2 (cons 3 (cons 4 '()))) list with three elements; same as
'(2 3 4)

(car '(2 3 4))  --> 2, the head of the list
(cdr '(2 3 4))  --> (3 4), the tail of the list

Some misc. operations:
(= (+ 1 2) 3)    --> #t  works like ==  (#t is true, #f is false)
(equal? '(1 2) (cons 1 '(2)))    -->  works like .equals on complex structures
(and A B)   -->  boolean and  (or, not similar)
(list? '(1 2 3))  -->  #t because argument is a list
(list? 2)  --> #f, not a list
(null? ()) --> #t empty list is null
(list 2 3 4)  --> '(2 3 4): constructs list of given elements
(let ((x 2) (y 3)) (+ x x y))  ; locally bind x and y, only visible inside let
(let ((x 2)) (+ x x))  ; need them parenthesis.
(cond ((< x 0) "negative")  ; like if -elif sequence, ending in default
      ((> x 0) "positive")
      ( #t     "zero"))

;Scheme definition of operation that adds one to each element of a list:
(define add1 (lambda (l)
  (if (null? l) '()
      (cons (+ 1 (car l)) (add1 (cdr l))))))
; (add1 '(1 3 5 7)) --> (2 4 6 8)

; We can also define function with (define (add1 l) ..., which is just 
; shorthand for (define add1 (lambda (l)...

; built-in operations on lists:
; (length '(a b c))  --> 3
; (append '(a b) '(c d)) --> (a b c d)
; (reverse '(a b c))  --> (c b a)
; (member 'a '(b c a d)) --> (a d) (#t with a little extra info).
; (map (lambda (x) (* x 2)) '(1 2 3 4))  -->  (2 4 6 8)
; consult MIT Scheme Reference for full set of built-ins

Instructions for loading a file of definitions are in the problems below:

-----------------------------------

0. (warm up - do directly inside interactive interpreter)

  a. Start scheme.  
     Using "cons", construct the list (2 4 6 8) one element at a time.
     Then use "car" and "cdr" to extract the 2, 4, and 6 from the list.
     That is, you want to have something like:
     (define mylist ...)  --> (returns) (2 4 6 8)
     XXX  (some expression with car and cdr on mylist) --> 2
     YYY  (some expression with car and cdr on mylist) --> 4
     ZZZ  (some expression with car and cdr on mylist) --> 6

  b. Euclid's algorithm for finding the greatest common divisor of
     two numbers can be written in C as follows

     int euclid(int a, int b)  
      {  if (b == 0) return a;
  	   else return euclid(b,a%b);
      }

     Write this function in Scheme.  a%b is (remainder a b) in Scheme.
     Is this function tail-recursive?

  c. define a function to find the product of all the numbers in a list:
     (lproduct '(2 4 3))  should return 24.  The product of the () list
     should be 1.  This function will be similar to the "add1"
     function above, except you'll be returning a number, not a new list.

  c2. Do this function in two styles, one using tail-recursion (hint:
      use another parameter as the accumulator)

(the rest should be put inside a separate .scm file)

    Use a text file and load it in with (load "c:\\..\\filename") (on windows).
    To get more meaningful error messages when loading insert the
    following line at the beginning: (set! load-noisily? #t)

1. define a function that returns the last element in a list.  For 
   example, (lastelement '(a b c)) should return c.  Remember that
   the cdr of the list is (b c).  If the list is empty, return 'error

2. The Rivest-Shamir-Adleman (RSA) public key encryption algorithm works
   as follows:  two very large prime numbers p and q are chosen and 
   kept secret.  Let n = p*q (the idea is that it's hard to figure out
   what q and p are given n).  Two more numbers, d and e, are picked so
   that (e*d) % ((p-1)*(q-1)) == 1.  The pair (n,e) is called the
   public key or encryption key, and is used by everybody to encrypt 
   messages.  The private key consists of the number d, which is
   kept secret.  A message can be represented as a number m between 0 and
   n-1.  To encrypt the message, compute m to the eth power mod n, in 
   Scheme this would be written (remainder (expt m e) n).  To decrypt
   a "cipher" message c, we use (remainder (expt c d) n).  That is,
   if c = (remainder (expt m e) n), then (remainder (expt c d) n) will
   give us the original message m.

   For our excercise, the prime numbers are kept small (47 and 59),
   and e = 17, d = 157, and n = 2773.  We encode text messages 
   character by character using their ascii values.  For example, 
   "hello" is encoded with the list of ascii values:

      '(104 101 108 108 111)

    If we apply the encryption algorithm to each number in the list,
    we get the "ciphertext"
   
       (193 758 169 169 131)

    Decrypting it will give us back the original list.

    Calulating something like (expt x 157) will give a very large
    number.  Even though Scheme allows "large" integers, sometimes the
    numbers can be too large and take too much memory.  But we don't
    need x**157, just x**157%n.  So it is better to define our own
    "exponent-modulo" procedure, which avoids large numbers by taking
    the remainder at each step:

;calculate (x**n)%m  in log(n) steps by binary factorization of n:
(define (fastexp x n m)
   (define (iter n ax fct)
     (cond ((= n 0) ax)
	   ((= 1 (remainder n 2)) (iter (quotient n 2) 
					(remainder (* ax fct) m)
					(remainder (* fct fct) m)))
	   (#t (iter (quotient n 2) ax (remainder (* fct fct) m)))))
 (iter n 1 (remainder x m)))

(display (fastexp 2 10 10000))) ;prints 1024
(display (fastexp 65 157 1000000000)) ; prints last 9 digitis of 65**157


You are to implement two functions: encrypt-list and decrypt-list that
will encrypt and decrypt lists of values.  I suggest you first define
functions to encrypt/decrypt individual values.  I'm giving you the
following function so that you can print a list of ascii values as a
string:

    (define printasciis (lambda (m)
      (begin (map (lambda (x) (display (integer->char x))) m)
	 (display "\n"))))

    for example, 
      1 ]=> (printasciis '(104 101 108 108 111))
      hello

    Don't try to print the ciphertext.

Use your decryption program to decrypt the following top secret message:

'(2063 193 758 2227 1860 131 131 169 758 660 1528 1751 2227 660 1684 758 2227 660 169 1020 1239 758 207)

Chew and swallow the message after you read it.  If captured by the enemy, 
hit your head on something hard to induce amnesia.

Use your encryption algorithm to encrypt a message for other people in
the class to decode.  You can use the following function to transform
a string to a list of ascii values:

(define (makeasciis S) (map (lambda (x) (char->integer x)) (string->list S)))

for example, (makeasciis "hello") returns (104 101 108 108 111)


3. Using the following code for binary trees:

; binary trees
(define (node x l r)   ; x is data, l is left, r is right
  (lambda (s)
    (cond  ((= s 0) x)
           ((= s 1) l)
           ((= s 2) r)
           (#t 'error))))

(define (data t) (t 0))
(define (left t) (t 1))
(define (right t) (t 2))

; sample tree
(define t1 (node 5 (node 3 '() '()) (node 8 (node 7 '() '()) '())))

;          5
;        /   \
;       3     8
;            /
;           7

; sample functions:

; return size (number of non-null nodes) in a tree:
(define (size t) (if (null? t) 0 (+ 1 (size (left t)) (size (right t)))))

(define (search x t)   ; assuming a binary search tree
  (and (not (null? t))
       (or (= x (data t))
           (and (< x (data t)) (search x (left t)))
	   (and (> x (data t)) (search x (right t))))))


Write a function that returns the product of all the numbers in the tree
in the same way as for lists in problem 0c.



4. The following are some higher-order functions on lists: 

(define (mapfun F L) 
  (if (null? L) L (cons (F (car L)) (mapfun F (cdr L)))))
; (mapfun (lambda (x) (+ x 1)) '(1 2 3 4)) returns '(2 3 4 5)

; fold operator f over l, where f has identity id
(define (fold f l id) 
  (if (null? l) id
    (f (car l) (fold f (cdr l) id))))

; usage:
(fold (lambda (x y) (+ x y)) '(2 4 1 5) 0)  ; returns 12, the sum of the list

; FYI: here's the fold function in C, adopted to zero-terminated vectors:
;int fold( int (*f)(int,int), int* l, int id)
;{
;   if (!l) return id; else return *f(l[0], fold(f,++l,id));
;}

; a similar function to fold is "reduce"
; f is assumed to be a binary function, M is assumed non-empty.
; unlike fold, it is tail-recursive:
(define (reduce f M)
  (if (null? (cdr M)) (car M)
      (reduce f (cons (f (car M) (cadr M)) (cddr M)))))

Study these and use them as examples.  Write a function "howmany" on
binary trees.  The function takes a tree and a lambda term as arguments.
The lambda term represents a boolean function, for example,
(lambda (x) (< x 2)).  Your function should traverse the tree and 
return the number of elements for which the boolean property is true.
For example, if the tree t contains 4 positive numbers, and the
rest of the numbers are <=0, then (howmany (lambda (x) (> x 0)) t) should
return 4.