CSC 123 Scheme Lab and Assignment Due Wednesday 10/1 --- To run scheme at Hofstra, first execute the statement setenv PATH /shared/csc/local/bin:$PATH Also put this in your .cshrc to make it permanent. ---- 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 (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. 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))) (+ x (g x)))) 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 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) ; 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) ; consult MIT Scheme Reference for full set of built-ins ; begins a comment, terminating at the end of the line. Instructions for loading a file of definitions are in the problems below: ---- 0. a. Start scheme with "scheme" (quit with control-d). 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. Use a text file this time and load it in with (load "filename"). Define "mylist" in the text file, and load it. c. 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? d. define a function to add all the numbers in a list: (listsum '(2 4 3)) should return 9. The sum of the '() list should be zero. This function will be similar to the "add1" function above, except you'll be returning a number, not a new list. 1. define a function "doubles," that , given a list L, will return a list with every element in L repeated, e.g: (doubles '(a b c d)) --> (a a b b c c d d) if given the empty list, it should just return the empty list 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. 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 (l) (begin (map (lambda (x) (display (ascii->char x))) (reverse l)) (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 message: '(2063 193 758 2227 1020 1528 1239 660 1751 1020 131 1528 2227 2243 1020 169 169 2227 1860 758 2227 660 2504 2227 728 131 1684 170 660 1528 1952 196) Swallow it after you read it. Trust no one. Use your encryption algorithm to encrypt a message for other people in the class to decode. 3. Using the code for binary trees that I wrote, write a function that checks if a given binary tree is a binary search tree (bst). A bst is a tree of integers such that, for every node in the tree, (data node) is >= to every integer on the subtree (left node) and is < every integer on (right node). Note that is property holds for *all* nodes - that is, it recursively applies to (left node) and (right node). For the algorithm, you can assume that all numbers in the tree are between 0 and 10000. Then, you can pass two additional parameters into your function, min and max, that indicates the valid range of values a node can contain. Your recursive calls will then adjust these values accordingly. See if you can write this function without using if expressions - the booleans operators themselves, as you learned while studying the lambda calculus, already have the ability to make decisions. 4. Using the fold and mapfn higher-order functions discribed in class, it's possible to write a function "forall" (like in predicate logic) that determines if every element of a list satisfies some given property. The property is a boolean function passed to the "forall" function as an argument. ; 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)))) (define (forall p l) (fold (lambda (a b) (and a b)) (map p l) #t)) (forall (lambda (x) (> x 3)) '(4 5 6)) --> #t (forall (lambda (x) (> x 3)) '(4 2 6)) --> () (or #f) To understand what's happening, read inside-out. (map p l) will return, for list '(4 5 6) , the list (#t #t #t) (since 4,5,6 are all >3). Then the fold operation will apply and to these boolean values sucessively (and #t (and #t #t)) is true. Unfortunately in this version of Scheme I can't just use the the built-in and (which is call-by-name) in this way - I must redefine it as (lambda (a b) (and a b)). Following the example of forall, you are to write a function "exists" that returns true if there is at least one element in a list that satisfies the given property. Demonstrate it on some lists. ----- In all these problems, if you need an auxiliary function define it *within* the main function to be defined. You will probably need an auxiliary function in the last problems, i.e, you would probably want to first define a function that adds just a pair of minutes and seconds before doing it for a whole list. Be careful: In scheme extra parentheses around expressions change their meaning. In particular, "(f)" is a function call of f on zero arguments - same as "f()" in C. ((f)) is not the same as (f) in Scheme!