-----------------------------------------
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 finishes
So, 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.