CSC 123 Scheme Lab and Assignment Due Monday 10/11 --- It is assumed that you have read the material I've given to you on Scheme. If you have not done so, stand in a corner and cover your face in shame. It's highly recommended that you use MIT scheme. ---- 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))) (+ 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) ; (member 'a '(b c a d)) --> (a d) (#t with a little extra info). ; 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. Use a text file this time and load it in with (load "filename"). Define "mylist" in the text file, and load it. To get more meaningful error messages when loading insert the following line at the beginning: (set! load-noisily? #t) 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 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. (the rest should be put inside a separate .scm file) 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. Scheme have no problems computing (expt c 157), which would be a bit more difficult for languages using only 32 and 64 bit integers. 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))) 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. You can use the following function to transform a string to a list of ascii values: (define (makeasciis S) (map (lambda (x) (char->ascii x)) (string->list S))) for example, (makeasciis "hello") returns (104 101 108 108 111) 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 N in the tree, (N 'head) is >= to every integer on the subtree (N 'left) and is < every integer on (N 'right). This property must hold 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. 5. Using forall, and exists, one can now define many similar operation. For example, to see if one list A is a sublist of B (that is, if every element in A is also in B), one can use: (define (sublist A B) (forall (lambda (x) (member x B)) A). This is an example of "declarative programming" in that it's just saying that A is a sublist of B if every element x of A is also in B. 5a. Define (intersect A B), which should return true iff there's an element that exists in both A and B. Here's another higher order function that filters out only those elements that satisfy some boolean property: (define (suchthat p l) (if (null? l) l (if (p (car l)) (cons (car l) (suchthat p (cdr l))) (suchthat p (cdr l))))) For example, (suchthat (lambda (x) (> x 3)) '(1 4 2 7)) will return '(4 7) - all elements that are greater than 3. 5b. Use this predicate to define list intersection (that is, instead of just true or false, return the actual intersection of two lists). Also define list difference: (diff A B) should contain all elements of A that are NOT in B. For example: (intersection '(1 3 2 5 7) '(6 2 7 4)) --> (2 7) (difference '(1 3 2 5 7) '(6 2 7 4)) --> (1 3 5) You don't have to worry about repeat elements, i.e. (3 3) is OK. ----- 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!