91.301 Organization of Programming Languages
Prof. F. Martin
Problem Set 3: Data Abstractions & Data Structures
- Use the Standard (R5RS) language in DrScheme
- You should define nil as follows in your evaluation buffer:
(define nil '())
What to turn in
Keep your Scheme answers in a file named
ps3-ans.scm and your Python answers in
ps3-ans.py. Put your name at the top of the file in a comment block. Put the code for each problem sequentially in the definitions buffer. Put the problem number in a comment before the code for that problem (use a semi-colon to make a line a comment). Underneath the code for each problem, cut and paste the appropriate sample runs. You can put semi-colons (Scheme) or hash-marks (Python) in front of the sample runs, which will comment them out and allow you to load the entire buffer in another session.
If you have any hand-written content, print the answers buffer and turn it in at the beginning of class on the due date. Staple any handwritten portions of the assignment to your code file that you turn in. Also submit your answer buffer using the submit command on Mercury:
submit fredm 301-ps3 ps3-ans.scm ps3-ans.py
- SICP exercise 2.2 (pp. 89-90). In this problem you create data structures in Scheme representing line segments in a plane.
- SICP exercise 2.3 (pp. 90). Here you represent rectangles and construct procedures to compute perimeter and area.
- For each of the following definitions,
a. Draw the box and pointer diagram
b. Give the sequence of
cdrs needed to return the number 4
(define a (list 1 2 3 4))
(define b (cons (cons 3 4) (cons 5 6)))
(define c (list 1 (list 2 3) 4))
- Draw a box and pointer diagram for each of the lists
fdefined as follows:
(define d (list 1 2))
(define e (cons d d))
(define f (append d d))
What would be printed by Scheme when asked for the values of d, e and f sequentially?
- Consider the following recursive procedure:
(define (list-prod lst) (if (null? lst) 1 (* (car lst) (list-prod (cdr lst)))))a) How many times is list-prod called when evaluating the expression
(list-prod '(1 2 3 4))?b) What is the order of growth in space and time for the
list-prodprocedure above?c) Write an iterative version of the procedure
list-prod.d) What is the order of growth in space and time for your iterative
list-prodprocedure from part c?
- *Write a procedure called
double-listin three different ways:a) Write a list manipulation procedure of your own to do this.b) Use the
scale-listprocedure on pp. 105 in your definition.c) Use the
mapprocedure on p. 105 in your definition.
- SICP exercise 2.20 (pp. 104), on the dotted-tail notation.
- *SICP exercise 2.21 (pp. 106), on
- *SICP exercise 2.33 (pp. 119), implementing
- *SICP exercise 2.35 (pp. 120), redefining
count-leavesas an accumulation.
- Learn about object-orientation in Python by reading this quick intro (http://linuxgazette.net/issue56/orr.html) and/or parts of Chapter 13 in CP.
print-ratonly) in Python. Do it three different ways:
- Using procedures with Python lists as the data structure. (Python does not have
cdr. Instead, construct and slice (extract list elements) using normal Python list techniques.)
- Using standard OO techniques.
- Can you implement the data abstraction using Python's lambda function and closures? If yes, give the code and demonstrate it working. If no, explain why not.