----------------------------------------- Tutorial notes #6 for 3/19 or 3/20/2007 TA: Stephen McCamant Email: smcc@mit.edu Location: 36-113A or 36-115 http://people.csail.mit.edu/smcc/6.001-sp07/ ----------------------------------------- Examples with quoting and lists '5;-> 5'pi;-> pi(quote (1 2));-> (1 2)('/ 1 2);-> error ("/" isn't a procedure)(if '(= pi 3) '1 '2);-> 1(quote if then else);-> error (quote takes only one thing)(quote (list (list 3 4)));-> (list (list 3 4))(list (quote (list)));-> ((list))(car (quote (+)));-> +(car (quote (quote 1 2 3)));-> quote(car '''''''''car);-> quote(cadadr '(+ (* (/ 1 2) pi) angle));-> (/ 1 2)(map car '((apple) (pear)));-> (apple pear)(filter pair? '((1 . 2) (1 2) (1) () nil));-> ((1 . 2) (1 2) (1))(cons 'a '(b c d));-> (a b c d)(cons '(a) '(b c d));-> ((a) b c d)(list 'a '(b c d));-> (a (b c d))(list '(a) '(b c d));-> ((a) (b c d))(append 'a '(b c d));-> error (args to append must be lists)(append '(a) '(b c d));-> (a b c d)----------------------------------------- Equality predicates = eq? eqv? string=? equal? +------------------------------- | number | Y ? Y[1] err Y[1] | boolean | err Y Y err Y | symbol | err Y Y err Y | string | err ? ? Y Y | list | err [2] [2] err [3] | procedure| err [4] [4] err [4] Y = does what you would expect err = gives an error ? = does something strange or undefined [1] = exact and inexact versions of the same number are not eqv? or equal? (e.g., (eqv? 2 2.0) -> #f) [2] = compares identity of pairs [3] = compares list contents [4] = #f if procedures could have different behavior, otherwise undefined Help define the following procedure similar to "equal?": (define (my-equal? v1 v2) (cond ((eq? v1 v2) _____) ((and (______? v1) (______? v2)) (= v1 v2)) ((and (______? v1) (______? v2)) (or (and v1 v2) (and (not v1) (not v2)))) ((and (______? v1) (______? v2)) (eq? v1 v2)) ((and (______? v1) (______? v2)) (string=? v1 v2)) ((and (______? v1) (______? v2)) #t) ((and (______? v1) (______? v2)) (and (my-equal? (_____ v1) (_____ v2)) (my-equal? (_____ v1) (_____ v2)))) (else #f)))(define (my-equal? v1 v2) (cond ((and (number? v1) (number? v2)) (= v1 v2)) ((and (boolean? v1) (boolean? v2)) (or (and v1 v2) (and (not v1) (not v2)))) ((and (symbol? v1) (symbol? v2)) (eq? v1 v2)) ((and (string? v1) (string? v2)) (string=? v1 v2)) ((and (null? v1) (null? v2)) #t) ((and (pair? v1) (pair? v2)) (and (my-equal? (car v1) (car v2)) (my-equal? (cdr v1) (cdr v2)))) (else #f)))----------------------------------------- Another kind of recursion When we have a list whose elements are lists whose elements are lists, and so on down to any level, we often call it a "tree" (we'll see more examples of trees in lecture soon). For instance, we might want to square all of the numbers in a tree: (square-tree '(1 (2) ((3)) (4 5) ((6) 7))) -> (1 (4) ((9)) (16 25) ((36) 49)) (define (square-tree tree) (cond ((number? tree) (* tree tree)) ((list? tree) (map square-tree tree)) (else (error "bad tree")))) How does this manage to finish, if we never check for an empty list? Now, let's try to generalize this with a higher-order procedure: (define (make-tree-walk leaf-proc kids-proc) (lambda (tree) (cond ((number? tree) (leaf-proc tree)) ((list? tree) (map kids-proc tree)) (else (error "bad tree"))))) How can we use this HOP to define square-tree like above? Alyssa tried this: (define square-tree (make-tree-walk square square-tree)) What goes wrong with that?;-> undefined variable "square-tree"Ben suggested using a procedure: (define (make-square-tree) (make-tree-walk square (make-square-tree))) (define square-tree (make-square-tree)) But didn't have much more luck. Why not?;-> make-square-tree never finishesSo, what should we do?(define square-tree (make-tree-walk square (lambda (t) (square-tree t))))----------------------------------------- More uses of list HOPs Suppose "procs" is a list of procedures, and I want to make a list of numbers containing as many zeros as "procs" has procedures. What's an easy way to do that?;-> (map (lambda (x) 0) procs)Another feature of "map" we haven't mentioned yet is that you can give it more than one list, and a procedure that takes more than one argument, as long as the lists have the same length: (map * '(2 3 4) '(4 5 6)) -> (8 15 24) Suppose that "booleans" and "lst" are two lists of the same length, and we want a list containing all the elements of "lst" corresponding to #t values in booleans: (select-list '(#f #t #f #t #f #t) '(1 2 3 4 5 6)) -> (2 4 6) How can we write select-list using HOPs? (Hint: first map, then filter, then map)(define (select-list booleans lst) (map cdr (filter car (map cons booleans lst))))Do these problems sound familiar? In fact, both parts 6 and 7 ("prediction" and "update-weights") of Project 2 can be implemented using just higher-order list procedures, and no explicit recursion. ----------------------------------------- Commentary on tagged data We went through a good but long example on tagged data in recitation on Friday. If you skipped recitation because you were still working on project 2 (or because you were sleeping off project 2), take a look at it online. Why are we doing so many examples with things like evaluating math and differentiation? These are classic examples for Lisp-like languages, but we have another ulterior motive.Later in the class, we'll talk about how to implement a Scheme evaluator in Scheme. It will have much the same structure as the evaluators we're seeing now, it will just handle more kinds of operations. So I think we're hoping to get you comfortable with the idea of recursive evaluation.Why is coercion a useful idea?If you had n types of data, and you needed to implement a two-argument operation over all the types, you would need n^2 cases. If you use coercion instead to convert all the values to the more general type, you only need n coercion routines and n cases in the binary operation, which is a big savings of effort.----------------------------------------- Brainteaser: self-printing code Alyssa and Ben have been wondering whether it's possible to write a Scheme expression that isn't self-evaluating, but which, when you evaluate it, prints its own value. In the terminology of other languages, a program that prints its own source code. Since they heard about it in lecture on Tuesday, they're thinking that quote might be useful for this. Ben tried some examples, and thinks it isn't possible. If the output of a program is X, the program needs to look like "(quote X)". But "(quote X)" is longer than "X". In general, the source code to the program will always be longer than the output, so they can never be the same. What do you think of Ben's argument?Though Ben is correct if the program is only going to have the form "(quote X)", in general we have the possibility to do operations on the quoted data. Some of these can make the result longer: for instance, we can print the same thing out twice. In fact, it is possible to write a program like this in just a couple of lines of Scheme; the counterexample to Ben's conjecture above is intended to serve as a hint. If you're still stumped, the name for a program like this is a "quine"; that information is enough to make it easy to find the answer on the web. The best-known LISP/Scheme quine requires some slight modification to work with DrScheme's printing of quotations, but those changes should be easy to make if you understand the principle.