-->
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.
- Read section 1.1.
- 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
- Read section 1.2.
- 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.)
9. parsing
due Thu Nov 18
- Read about parsing and recursive descent parsing.
- Study the starting code for our dickinson language , and read the discussion in the comments about parsing.
- Propose some additional grammar rules for dickinson which add at least (a) variable assignment, (b) function definition, and (c) function evaluation, along with some examples of the corresponding code. Explain why you like those rules and whether or not they can be parsed with an LL(1) parser.
- Over the next few weeks, as an entire class we'll try to turn this into a small, simple but complete programming language.
- Expect to have an end-of-term assignment to discuss and explain this language, and your contribution to the project.
10. compiler project
due Thu Dec 9
- As an end-of-term project, your job is to study, explore, and discuss an example of interpreter or compiler design and implementation. You may choose any one of several ways to accomplish this :
- Work on an aspect of the dickinson language class project, either implementing a piece of it - for example coming up with a grammar, lexer, parser, and interpreter for functions - or in testing, evaluating, and explaining what we manage to come up with. You may work in a language other than the guile/scheme one we're working on as a class project; if so, be clear about how to install, run, and test your code.
- Work though the core ideas in section 4.1 of SICP, the "metacircular evaluator" - a scheme interpreter in scheme, trying some of the exercises, running the code, and explaining what's going on.
- Study and discuss one of the following "I wrote a compiler" articles, including getting its code to work and adding some debugging "print" statements here and there to show your understanding of how it works:
- Whatever your work on, please submit a short paper discussing your understanding of the ideas involved and connecting them back to the SICP material including its discussion of functions and their environments.
11. course evalution
due Fri Dec 17
