Exercises for Wednesday, October 27, 2004 Make sure that your DrScheme language is set to 'Pretty Big (includes MrEd and Advanced)'. To do so click on the 'Language' menu in DrScheme and you'll find 'Pretty Big (includes MrEd and Advanced)' under 'Professional Languages' (you'll have to click on the 'PLT' tab to show the 'PLT' family of languages). The 'Student Languages' impose too many restrictions and cause more confusion than they are worth. Once you make this change you'll find that 'first' and 'rest' are not defined. So, either use 'car' and 'cdr' or define 'first' and 'rest'. To do the latter, open a file in DrScheme, type in the following two definitions and then 'Execute' the file. (define first car) (define rest cdr) Here are the notes that were handed out in class along with some additional help and hints to make the assignment easier. Please follow the instructions; there really is method in my seeming madness - I'm not just assigning you busywork. I want you to actually type the expressions to the DrScheme interpreter; don't just read the text. Typing the expressions to the interpreter is a very effective learning strategy; it is just like typing sentences in an unfamiliar foreign language - since you can't rely on filling in the details from your knowledge of your native language, you have to attend to the syntax carefully. Trust me it works. If you make a typing mistake, Scheme will likely complain and you'll have to retype the expression thereby learning something in the process. These exercises are designed with this learning strategy in mind. Look carefully at the examples. If you understand the examples, it should be easy to generalize enough to solve the exercise problems. If you really want to know more about the commands, then use the 'Help Desk' under the DrScheme 'Help' menu, but only do that as a last resort. These exercises do assume that you've read Chapter 5 in the text. Basic (Primitive) Data Types Symbols: any sequence of characters including at least one character other than a digit. There are some exceptions: you can't include the single quote, double quote, back quote or any parentheses {},[],(). In addition, the first character of a symbol can't be a sharp sign #. To define a symbol 'name' to have the value of some 'expression', type (define name expression). Try variations on the following: > (define foo 1) > foo 1 > (define foo_bar 2) > foo_bar 2 > (define 1_foo 3) > 1_foo 3 > (define n (+ 1 2 3)) > n 6 If you type a defined symbol to Scheme, it will respond by printing the 'value' of the symbol. If you type a symbol that hasn't been defined, Scheme will complain: > bar reference to undefined identifier: bar So far we've been defining symbols to have values corresponding to integers. There are other sorts of numbers available in Scheme including rationals, real numbers in decimal notation and various kinds of floating point numbers: > (define third 1/3) > third 1/3 Another primitive data type is the string; in Scheme, strings are always enclosed in double quotes: > (define my_name "Tom Dean") > my_name "Tom Dean" Unlike symbols that have values assigned to them by 'define'. Strings and numbers always evaluate to themselves: > "Vanessia Wu" "Vanessia Wu" > 2.712 2.712 The single quote is shorthand for the 'quote' function. The quote function suppresses evaluation. The following two invocations are equivalent: > 'foo foo > (quote foo) foo Note that by quoting a symbol you can refer to the symbol rather than any value that it might have; you can also refer to a symbol that doesn't have a defined value. Every symbol has a name but not all symbols have values. List Processing in Scheme Finally, one of the most important data types in Scheme is the list; lists are used to store information, create more complex data structures and even represent programs. The 'list' function takes any number of arguments and constructs a list whose elements correspond to the values of its arguments: > (list 1 2 3) (1 2 3) > (define ones (list "one" 1 'one )) > ones ("one" 1 one) > (define twos (list (+ 1 1) (/ 6 3) (/ (* 2 3) 2))) > twos (2 2 2) Reflect on the last two definitions; the 'list' function evaluates its arguments (arguments are like the words to the right of a shell command). The strings and the numbers evaluated to themselves and we used to the quote to suppress the evaluation of the symbol 'one'. You can 'nest' lists simply by calling the 'list' function as one of the arguments to 'list': > (define nest (list 1 2 (list 3 4) 5 6)) > nest (1 2 (3 4) 5 6) You can also create lists using quote; in this case, the resulting list is specified literally and no evaluation takes place: > (define nums '(1 2 3 4)) Notice what happens when we incorrectly try to create a nested list inside a list specified with quote: > (define nest '(1 2 (list 3 4) 5 6)) > nest (1 2 (list 3 4) 5 6) To achieve the intended effect we just specify what we want literally: > (define nest '(1 2 (3 4) 5 6)) > nest (1 2 (3 4) 5 6) It doesn't do much good to create lists if you can't subsequently take them apart and access their contents. The most basic functions for accessing lists are called 'car' and 'cdr'. These names refer to locations called 'registers' in the memory of a now defunct computer. You can use these name if you like but you can also give them more mnemonic names. The 'car' of a list is the first element of the list and the 'cdr' of a list is the list consisting of all the rest of the elements of the list but the first one. As mentioned in class, often programmers define 'first' and 'rest' as aliases for 'car' and 'cdr': > (define first car) > (define rest cdr) What do think the value of 'car' is? > car # > cdr # This indicates that 'car' and 'cdr' are defined as primitive functions. And now we've defined 'first' and 'rest' to have the same definitions as 'car' and 'cdr' respectively. > first # > rest # Now we can use these functions to access the contents of lists: > (define nums '(1 2 (3 4) 5 6)) > nums (1 2 (3 4) 5 6) > (first nums) 1 > (rest nums) (2 (3 4) 5 6) We can use various combinations of 'first' and 'rest' to access any element or sublist of given list. For example, suppose that you want to grab the 4 in '(0 (1 (3 4)) 5). First we'll do it in several steps: > (rest '(0 (1 (3 4)) 5)) <<< step 1 ((1 (3 4)) 5) > (first '((1 (3 4)) 5)) <<< step 2 (1 (3 4)) > (rest '(1 (3 4))) <<< step 3 ((3 4)) > (first '((3 4))) <<< step 4 (3 4) > (rest '(3 4)) <<< step 5 (4) > (first '(4)) <<< step 6 4 Now we put this all together and apply these steps in the order of evaluation which actually looks as if we're doing it backwards or at least inside out, but you should convince yourself that this is actually in the appropriate evaluation order. step 6 step 5 step 4 step 3 step 2 step 1 > (first (rest (first (rest (first (rest '(0 (1 (3 4)) 5))))))) 4 1. Given the following list structure: > (define nums '(1 2 (3 4) 5 6)) What do the following expressions return? > (first (rest (rest nums))) > (rest (first nums)) 2. Now use 'first' and 'rest' (or 'car' and 'cdr') to return each of the components 2, (3 4), 5 and 4, given 'nums' as defined above. Your solutions should look like (first (rest (rest ... '(1 2 (3 4) 5 6)))) with a different sequences of 'first' and 'rest' invocations. Predicates for Testing and Comparing Primitive Types Each of the primitive data types has a corresponding function for testing membership. A predicate is just a function that returns true or false. In scheme, '#f' means 'false' and '#t' means 'true'. > (number? 1) #t > (string? "string") #t > (list? '(1 2 3)) #t > (list? "string") #f > (symbol? 'a) #t You can also check for special cases: > (zero? 0) #t > (null? '()) #t There are also variants of equality and inequality for every primitive type (substitute '>', '=', '<=', '>=' for '<' in the following to get the other variants): > (< 1 2) #t > (string Note that in Scheme '=' means numerical equality in contrast to the C-shell where '=' is used for assignment. There is also an equality predicate defined on more general types (note that for symbols, lowercase/uppercase doesn't matter - case does matter for strings): > (equal? 'a 'A) #t > (equal? 'a "a") #f > (equal? 1 (first (rest '(0 1 2 3)))) #t > (equal? "a" "A") #f > (equal? 1 (- 2 1)) #t Building Boolean Expressions Using Boolean Operators We can combine these with the boolean operators: 'and', 'or', 'not'. The first, the so-called conjunctive operator 'and' takes any number of arguments including zero. > (and #t #t) #t > (and #t #t #f) #f > (and) #t The disjunctive operator 'or' works similarly: > (or #f #t #t) #t > (or #f) #f > (or) #f See if you can explain why '(or) => #f' and '(and) => #t'. The negation operator 'not' accepts exactly one argument. > (not #t) #f > (not #f) #t We can combine these operators and use our various predicates for testing for primitive types. > (not (and (number? 1) (or (string? "") (null? '(1 2 3))))) #f Note that functions defined on strings, numbers, non-empty lists, etc., will complain if you call them with the wrong type of inputs: > (rest '()) cdr: expects argument of type ; given () > (string=? 1 "one") string=?: expects type as 1st argument, given: 1; other arguments were: "one" For this reason, it is often important to check the type of arguments before evaluating them. Note that in evaluating an 'and', the Scheme interpreter won't evaluate the second conjunct if the first conjunct returns #f; we can use this fact to check arguments and avoid errors of the sort illustrated above. > (and (not (null? lst)) (not (null? (rest lst))) (= 1 (first (rest lst)))) #f 3. Write a boolean expression for the body (the '...') of the following function: (define (special-list-type? arg) ... ) such that it returns #t for the following type of data structure: (list number number (list string) symbol) and #f otherwise; so, for example: > (special-list-type? '(1 2 ("foo") a)) #t > (special-list-type? (list 1 4 (list "foo") 'a)) #t > (special-list-type? (list 1 7 '("foo" "bar") 'a)) #f To help you out, here's a solution for a somewhat simpler example: (list symbol number (list)) (define (my-special-list-type? arg) (and (list? arg) (not (null? arg)) (symbol? (first arg)) (not (null? (rest arg))) (number? (first (rest arg))) (not (null? (rest (rest arg)))) (null? (first (rest (rest arg)))))) Note that the first two conjuncts (list? arg) and (not (null? arg)) have to be there to make sure that the third conjunct (symbol? (first arg)) won't cause an error on an input like '(). The fourth conjunct (not (null? (rest arg))) has to be there to make sure that the fifth conjunct (number? (first (rest arg))) won't cause an error on an input like '(1). Similarly, the sixth conjunct prevents the seventh conjunct from causing an error. Here are some examples showing my-special-list-type? in action: > (my-special-list-type? '(a 1 ())) #t > (my-special-list-type? (list 'foo 1.2 (list))) #t > (my-special-list-type? (list 'foo 1.2)) #f > (my-special-list-type? 3.14) #f > (my-special-list-type? (list 'foo 1.2)) #f Working With Conditional Statements Scheme conditionals are simpler and easier to use than conditionals in the C-shell. The 'else' clause is optional; however, if the condition of a conditional statement lacking an 'else' clause evaluates to '#f' then the result of the statement is undefined. > (if (symbol? 'a) 1 2) 1 > (if (null? '(1 2)) 1) > (if (and (number? 1) (string? "a")) 1 2) 1 There is also a generalized conditional statement 'cond' which works like nested if-then-else statements and is very convenient for all sorts of complicated tests. Here's the general format: (cond ( test_1 expression_1 ) ( test_2 expression_2 ) ( test_3 expression_3 ) ( test_4 expression_4 ) ( else expression_5 )) => (if test_1 expression_1 (if test_2 expression_2 (if test_3 expression_3 (if test_4 expression_4 (if #t expression_5 ))))) Each ( test_n expression_n ) is referred to as a 'clause'. Note that the first test to evaluate to #t will cause its corresponding expression to be evaluated. The keyword 'else' evaluates to '#t' in the context of a conditional statement. It should only be used as the test for the last clause - usually referred to as the 'default' clause. If no test evaluates to #t then the result of the 'cond' statement is undefined. > (define exp 1.2) > (cond ((list? exp) (printf "It's a list!~%")) ((symbol? exp) (printf "It's a symbol!~%")) ((number? exp) (printf "It's a number!~%")) (else (printf "I haven't the foggiest!~%"))) It's a number! Note that 'printf' behaves pretty much like the C-shell 'printf' except that we use '~%' for '\n' and to interpolate a variable into the format string, so instead of printf "the $last number is $num\n" you would write (printf "the ~a number is ~a~%" last num) For each appearance of '~a' in the format string there must be one additional argument to 'printf'. > (define one 1) > (define two 2) > (define three 3) > (printf "~a is less than ~a is less than ~a~%" one two three) 1 is less than 2 is less than 3 > (printf "~a is less than ~a~%" one) > (printf "~a is less than ~a~%" one) printf: format string requires 2 arguments, given 1; arguments were: "~a is less than ~a~%" 1 4. Now rewrite your solution to Exercise 3 using 'cond' so that it prints out useful informative statements about whether or not the input subscribes to the expected format: > (special-list-type-cond? '(1 2 ("foo") a)) Looks good to me. > (special-list-type-cond? (list 1 "" (list "foo") 'a)) I was hoping to see a number as the second element of your list. > (special-list-type-cond? (list 1 7 '("foo" "bar") 'a)) Expecting a list consisting of a single item but got (foo bar). A Word About Computer Literal-Mindedness I thought it might be useful to reflect on the differences between learning to program (where I am assuming that this involves actually writing programs and trying to make them run on a computer) and learning about some branch of history or philosophy or for that matter learning mathematics. The computer is stern task master; it allows no lapse in precision. Some of the requirements for precision may seem picayune - why should it matter if you leave out a semicolon! But the computer isn't smart enough to resolve ambiguities on its own; nor would we want it to in many cases. Most programmers learn to like the fact that the computer calls us to task when we are less that perfectly precise. In discussing philosophy with a professor, usually the professor gives you, the student, the benefit of the doubt, and you probably give the professor more credit that he or she deserves. It's easy to be lax in talking with another human. Even in learning, say, calculus, you can make mistakes on a test and often get partial credit; the human grader fills in what you meant. But late at night trying to get your programming assignment finished, the computer is obstinate and unforgiving. Somewhere in your code there is a missing semicolon but you can't find it and every time you try to run your code, it crashes spitting out cryptic comments. We're not used to such unflagging and obstinate adherence to rigid convention and we find it annoying - an affront to our intelligence. But it is worth keeping in mind that such precision is a boon to a skillful programmer. It assures that the machine will carry out his or her commands with perfect precision and repeatability. It's quite possible to write a program that doesn't do what the programmer intends, but at least we are assured that the computer will execute a piece of code the same today as tomorrow, the same whether you wrote it or someone else wrote it and the same whether it is run on one kind of a machine rather than another.