fibas we would for Lab 1. If I ask the interpreter to evaluate the "symbol"
fib, it'll tell me that
fibis a name for a function:
> fib #<procedure:fib> >So, the symbol
fibhas a special meaning. We can tell the interpreter not to evaluate the symbol by "quoting" it, which means either writing
(quote fib)or, more commonly, by putting a ' in front of the symbol, i.e.
'fib. Here's a sample interpreter session:
> fib #<procedure:fib> > 'fib fib >All this is strange, I know, but here's an example. The function
inchesdefined below does some basic conversions into inches, and returns the symbol
errorif the input units are unknown. [Note:
equal?is sort of a universal equality test in scheme. It works with symbols and with lists (see below). The
=operator only works with numbers.]:
> (define (inches x u) (if (equal? u 'inches) x (if (equal? u 'feet) (* x 12) (if (equal? u 'yards) (* x 36) 'error)))) > (inches 0.5 'feet) 6.0 > (inches 0.5 'yards) 18.0 > (inches 0.5 'meters) error > (inches 0.5 yards) reference to undefined identifier: yards >Notice what happens when I forget to quote
yards- the interpreter tries to evaluate the symbol yards in order to get the arguements for
inches, and of course that name is undefined. Note: this function definition would be a lot cleaner if we used
Problem: Currency Conversion
Write a function
convert that takes an amount a
"from" currency and a "to" currency and converts the amount of
the "from" currency to the monetary equivalent in the "to"
currency. The currencies you use should be
> (convert 3.50 'usdollar 'euro) 2.83378 > (convert 20.00 'yen 'ukpound) 0.10462Here are the rates in terms of dollars:
1 US Dollar = 0.56101 British Pound 1 British Pound (GBP) = 1.78250 US Dollar 1 US Dollar = 0.80965 Euro 1 Euro (EUR) = 1.23510 US Dollar (USD) 1 US Dollar = 107.290 Japanese Yen 1 Japanese Yen (JPY) = 0.009321 US Dollar
> (+ 3 4 5) 12 > '(+ 3 4 5) (+ 3 4 5) >So, we can easily construct any list we want by simply quoting and typing away. For example
> '(A B C) (A B C) > '( 1 (1) ((1))) ( 1 (1) ((1))) > '(( + 3 4) (* 3 4)) (( + 3 4) (* 3 4)) >This last example is an interesting one. Suppose we were looking to have
(7 12)returned instead of
(( + 3 4) (* 3 4))? In other words, suppose we wanted the two subexpressions in the list to be evaluated? Well, by quoting the list, we ensure that nothing gets evaluated. However, there's an alternative to quoting. We can construct lists using the
listfunction, which takes its arguments and forms a list from them.
> (list (+ 3 4) (* 3 4)) (7 12) >Since
(+ 3 4)and
(* 3 4)are unquoted arguments to functions, they're evaluted before they're passed on to the list function. Thus,
listis passed 7 and 12, and forms a list with those two values. This is useful if you want a function to return more than one value. You can simply have it return a list of values.
Example: Write a functionThe thing about
zerosthat computes the zeros of a quadratic polynomial a x^2 + b x + c. Assume
zerosis simply passed a, b and c. You can use the quadratic formula to compute the roots: (-b +/- sqrt(b^2 - 4 a c)) / (2a). We actually have two values to return, because of the +/-. Here's how you might implement
zeros:(define (zeros a b c) (let ((d (sqrt (- (* b b) (* 4 a c)))) (nb (- b))) (list (/ (+ nb d) (* 2 a)) (/ (- nb d) (* 2 a)))))
list, is that the length of the list you return is fixed. What if we wanted to create a function that returns lists, but we don't know ahead of time how long a list? What if we'll want to simply keep adding things to the list as we go along? The
consfunction takes an object x and a list L and returns the list you get by adding x to the front of L.
> (cons 3 '(5 9 11)) (3 5 9 11) > (cons 3 '( (5) (7) (9) )) (3 (5) (7) (9)) > (cons '(1 1) '( (1 1 1) (1 1 1 1) )) ((1 1) (1 1 1) (1 1 1 1)) > (cons 'the '()) (the) > (cons 'the (cons 'end '())) (the end) >Notice that we can construct lists by multiple cons's starting with
'(), the empty list.
Example: Write a functionNot surprisingly, when we construct lists by repeated cons-ing, we run into recursion!
rangethat takes two arguments i and j and returns the list i, i+1, i+2, ..., j.> (define (range i j) (if (> i j) '() (cons i (range (+ i 1) j)))) > (range 1 10) (1 2 3 4 5 6 7 8 9 10) >Interestingly, all we'd have to do is to stick a + at the head of this list and we'd have an expression for the sum of the first 10 integers.> (cons '+ (range 1 10)) (+ 1 2 3 4 5 6 7 8 9 10) >The only problem, is that what we have is data, a list like any other. The interpreter doesn't look to see that this particular list would make sense as an expression to be evaluated. However, we can tell the interpreter to evaluate a piece of data as if it were an expression typed into the interpreter with the
evalfunction.> (eval (cons '+ (range 1 10))) 55 >In other words, we can take a piece of data, and turn it into a piece of code! That's pretty cool.
There's one more standard function for building lists:
append. Appending lists means building a new
lists whose elements are those of the first list followed by
those of the second list. For example:
> (append '(1 2 3) '(a b c)) (1 2 3 a b c)Not surprisingly,
appendcan take an arbitrary number of list arguments, e.g.
> (append '(a) '(b c) '(d e f) '(g h i j)) (a b c d e f g h i j)It's important to understand the difference between
append. Keep this example in mind:
> (list '(a b c) '(1 2 3)) ((a b c) (1 2 3)) > (cons '(a b c) '(1 2 3)) ((a b c) 1 2 3) > (append '(a b c) '(1 2 3)) (a b c 1 2 3)
car, which returns the first element in a list, and
cdr, which returns the sublist of everything but the first element in the list. Performing either of these on an empty list is a bad idea!
> (car '(a b 4 () 2.1)) a > (cdr '(a b 4 () 2.1)) (b 4 () 2.1) >Together, car and cdr are kind of like an inverse cons:
> (let ((L '(a b c d))) (cons (car L) (cdr L))) (a b c d) >Now we can do a whole bunch of interesting things with lists. Note: To test whether or not a list is empty, you can either use the predicate (function returning T/F)
(if (null? L) ...), or use the general equality predicate
(if (equal? L '()) ...). Here's a function for computing the length of a list:
(define (my-length L) (if (equal? L '()) 0 (+ 1 (my-length (cdr L)))))although,
lengthalready exists in scheme! Here's a function that sums all the even numbers in a list. Note: even? and odd? are builtin to Scheme.
(define (sum-even L) (if (equal? L '()) 0 (let ((n (sum-even (cdr L)))) (if (even? (car L)) (+ n (car L)) n))))Things get really interesting when we have nested lists. It takes cars of cdrs of cars of cdrs to get to data sometimes!
In Scheme you end up doing things like "the car of the cdr
of the car of L", which gets to be quite a hassle. Scheme
has a nice abbreviation for such nested calls.
An expression like
(car (car (cdr L)))
can be written equivalently as
Here's how it works:
Now, using our newfound global variables (ugh!) we can play with this a bit:
(car (car (cdr L)))condenses to
> (define L '( (1 2 3) (a b c) ((x) (x x) (x x x)) )) > (car L) (1 2 3) > (car (cdr L)) (a b c) > (car (car (cdr L))) a > (caadr L) a > (car (cdr (cdr (car L)))) 3 > (caddar L) 3 >
tipthat takes an amount and returns a list of two values, the first being the amount plus a 15% tip, the second the amount plus a twenty percent tip.
> (tip 30) (34.5 36.0) >
squaresthat takes integers i and j and returns list of the squares i^2, (i+1)^2, ..., (j-1)^2, j^2.
> (squares 2 12) (4 9 16 25 36 49 64 81 100 121 144) >
tip-rangethat takes an amount, and two integers defining a range of tip percentages and prints the amount + tip for each integer percentage in the range.
> (tip-range 34.50 10 25) (37.95 38.295 38.64 38.985 39.33 39.675 40.02 40.365 40.71 41.055 41.4 41.745 42.09 42.435 42.78 43.125) >
(sum-abs '(-3 2 11 -5)) 21
> (define L '( (4 a) (3 x) (3 11 4))) > (car (cdr L)) (3 x) > (car (cdr (car (cdr L)))) x >Define L to be the following ugly list:
( (a x 2) (("the") b c) (z 12)). In other words, do the following:
> (define L '( (a x 2) (("the") b c) (z 12)))Now, write car/cdr expressions to pick apart L to get the following values (save each of these in your definition file -- put a comment next to each one explaining what it is):
sum-cashthat returns the value in US dollars of a collection of amounts of different currencies (same currencies as above). The amounts will be given in a list L, such that each element of L is itself a list, whose first element is an amount and whose second element is a currency name. So, for example,
( (12.20 usdollar) (340 yen) (8.50 euro) )as an arguement to
sum-cashwould mean adding 12.20 dollars, 340 yen and 8.50 euros, and giving the total in dollars. Here's an example:
> (sum-cash '((12.20 usdollar) (340 yen) (8.50 euro))) 25.86749 >
std-devthat takes a list of numbers and returns their standard deviation. (Recall: std dev of x1, x2, ..., xn is
__________________________________________ / /(x1 - u)^2 + (x2 - u)^2 + ... + (xn - u)^2 / ------------------------------------------ \/ n - 1... where u is the average of x1, x2, ..., xn. When you write this function, use top-down design. In scheme this means writing the std-dev function using functions you wish were already defined, then going back and defining them later. Example:
> (std-dev '(34 18 25 23 29 11 28 24 27 29)) 6.460134157533676