PS2

Home Assignments Lecture Blog Resources Project Discussion Group

91.301 Organization of Programming Languages
Prof. F. Martin

Out: Jan 31, 2011
Due: Feb 4, 2011

Problem Set 2: Iterative vs. Recursive Processes and Higher-Order Procedures

We will delve into the difference between iterative and recursive processes. A recursive procedure may actually invoke an iterative or recursive process! (Warning -- by the time you are done with this problem set, you may be sick of this topic. Sorry about that)

Also we will study higher-order procedures. This is the idea of passing procedures as inputs to other procedures, and procedures that construct and output new procedures.

What To Turn In

In a file named ps2-ans.rkt, turn in the file that holds all the Scheme code and evaluated results.

Put the problem number in a comment before the code for that problem. Scheme's comment character is a semi-colon; a comment may start anywhere on the line.

Submit your solutions electronically by logging into the cs.uml.edu cluster and typing

submit fredm 301-ps2 ps2-ans.rkt

Reading

Read SICP, Section 1.2 and Section 1.3. You may skip 1.2.6, unless you are really enjoying the mathematics and number theory.

The Problems

Make sure you do the readings before doing these!

Please note, if you are working from a printout, go to the course web site to find links to the exercises in the online version of the text, and the code for exercise 10.

  1. SICP exercise 1.9 (pp. 36). In this problem, you will study two implementations of addition in terms of increment and decrement, and analyze whether the implementations are iterative or recursive.
  2. SICP exercise 1.11 (pp. 42). In this problem, you implement a recursive mathematical function using both recursive and iterative processes.
  3. When implementing an iterative process in Scheme, the Scheme interpreter uses tail-recursion. Explain what this means.
  4. SICP exercise 1.16 (pp. 46).
  5. More iteration: SICP exercise 1.30 (pp. 60).
  6. Working towards higher-order procedures: Do SICP exercise 1.31 (a) and (b) (pp. 60–61).
  7. SICP exercise 1.32 (a only): Implement accumulate and show how sum and product can be defined with calls to accumulate. Specify whether you have built the iterative or recursive version.
  8. SICP exercise 1.41 (pp. 77): Procedures that return procedures.
  9. SICP exercise 1.42 (pp. 77): More procedures that return procedures.
  10. Here is an implementation of expnt, a procedure that generates a procedure for raising its input to its argument. E.g., (expnt 2) generates a procedure for squaring a number. The provided implementation of expnt generates a recursive process. Re-implement it as an iterative process (probably using a helper procedure).

Honors, Graduate Students, and Undergrads Looking for More

11. SICP exercise 1.43 (pp. 77): Repeated application of procedures.