# Structure andInterpretationof ComputerPrograms

Fall 2021
##### site -->

# assignments

## 1. section 1.1 - starting scheme due Thu Sep 9

• Install either racket or guile with the links in the resources page and as described in class.
• Get a copy of the SICP textbook.
• Do exercises 1.1 through 1.4 (scheme basics practice).
• If you still have time (4 credits = 12 hrs/week total), do 1.5 & 1.6 (evaluation subtleties).
• And if you still have time, do 1.7 & 1.8. (recursion and conditional practice using Newton's method)
• Describe what you did and how this is going.

## 2. section 1.2 - recursion due Thu Sep 16

• Explain in your own words the difference between what the authors call an "iterative process" and a "recursive process". (Note that both can be coded with a procedure that refers to itself.) Use ,trace on factorial and fact-iter from the text to illustrate the difference.
• Do exercise 1.9. Include a "by hand" application of the "substitution model", and using ,trace to see the execution.
• Do exercise 1.11. Again use ,trace to illustrate the difference between the "iterative process" and "recursive process".
• Do exercise 1.15. (This is a "divide-and-conquer" algorithm, which is a hint for the O() behavior.)
• If you still have time and/or the inclination ...
• exercise 12 asks you to calculate the (n m) element of Pascal's Triangle.
• exercise 16, 17, 18 work through a very cool "logarithmic time multiplication" idea.
• exercises 1.21 - 1.28 look at classic algorithms for testing prime numbers, used in cryptology.

## 3. lambda, let, cons, car, cdr due Thu Sep 23

• Read enough of 2.1 and 1.3 (or google to find other explanations) to understand cons, car, cdr, lambda, and let. (Yes, the names are terrible. We can find aliases for some ...)
• Explain the relation between cons, car, cdr, and list in scheme. Give an example, with some pictures.
• Explain what let does, and how it can be implemented with lambda.
• What is this trying to do, and why does it fail : (let ((a 1) (b (+ 1 a))) (+ a b)) ?
• Do exercise 2.2 : a line segment API
• Do exercise 2.17 : find the last pair of a list
• Do exercise 1.34 : substitution rule ; functions as arguments
• Do exercise 1.35 : the golden ratio as a fixed point
• optional
• 2.5 : encoding two numbers into one integer
• 2.6 : encoding numbers with only functions (i.e. Church encoding ... very cool)

## 4. higher order functions : accumulate , map due Thu Sep 30

• Read as much of 1.3, 2.2.1, and 2.2.2 as you need to do the following exercises. The material at wikipedia: fold and these berkely notes may be helpful. ("Fold" is another name for accumulate.)
• Do exercises 1.30, 1.31, 1.32 all related to accumulate.
• Test your answers to 1.32 by evaluating $$1/2 + 1/3 + 1/4 + 1/5 + 1/6$$ .
• Add a debugging print statement to the op function in your two solutions to 1.32, so that you can see the order in which the numbers are combined. Discuss what you see.
• Do exercises 2.20, 2.21, 2.22 : map and for-each.

## 5. trees, fold due Thu Oct 7

• Read the related sections in chapter 2 and do exercises
• 2.24 (a tree) and 2.28 (traversing a tree)
• 2.33 (map, append, length using accumulate)
• 2.38 (foldl and foldr) and 2.39 (reverse using foldl and foldr)
• optional : 2.32 (generating all subsets)

## 6. pictures, tagged data due Thu Oct 14

• Read section 2.2.4, "a picture language", at least enough to do exercises 2.44 and 2.45. I have a starting DrRacket file for you at picture_start.rkt. (You'll need to have other/wave.bmp to run it.)
• Read 2.3.1 on symbols and quotes, and do exercises 2.53, 2.54, 2.55. (Just to make sure symbols and quotes make sense.)
• Read sections 2.4 and 2.5 which discuss "tagging" data to indicate its type, and managing function packages to do the right thing on various sorts of data, enough to understand the main points. To illustrate that understanding, describe what the authors mean by these terms and give an example of each :
• "tagged data"
• "generics"
• "dispatching on type"
• "data-directed programming"
• "message passing"
• "coercion"

## 7. state; mutations due Thu Nov 4

• Read chapter 3 up through section 3.3.2 (queues).
• Do exercises
• 3.3 (local state)
• 3.9, 3.11 (environment model)
• 3.12, 3.13, 3.14 (set-car! , set-cdr!)
• 3.21 (print-queue)
• Warning: both the guile and racket schemes that we're using have both a mutable cons (which works fine with set-car! set-cdr!) and an immutable one; this leads to some differences from the code in the text. In particular, in guile's scheme '(1 2 3) cannot be be modified while (list 1 2 3) can be. That means that for exercise 3.14, in the code that they give for mystery, replace '() with (list ), and don't create lists with quote. I'll discuss this in class on Monday.

## 8. grammar due Thu Nov 11

• Read about grammars, and start reading about lexers and parsers - I've posted a number of places to start on the resources page.
• In Basics of Compiler Design, read
• chapter 1 (intro)
• chapter 3, sections 3.1 - 3.5 (grammars)
• chapter 2, sections 2.1 - 2.3 and 2.9 (lexing, regexexps, DFAs)
• Do the following exercises from that book :
• 3.3 (balanced parens)
• 3.4 (several examples of sequences of a's and b's)
• 3.21, parts (a) and (b).
• Start looking at examples of BNF grammars for programming languages, and thinking about a simple one to invent for our class. (There's an example in chapter 5 of that book.)