CIS 352   —   SPRING 2009

Homework 3

Coverage

• Essentials of Programming Languages (EOPL): Chapter 2.

Logistics

• You may work singly or in pairs on this assignment.

• Be sure to include contract and purpose statements for each procedure you are asked to write.
  (See the Homework Policy for more details.)

What to turn in:

• A copy of the source code and which includes reasonably complete equal?? tests for each procedure you write.

• A run of your code that verifies that it passes all your tests.

How to turn in your work:

1. If you have more than one file to submit, bundle them into a zip or tar archive.

2. Click on this electronic-submission link, and use your NetID and password for authorization.
   Important: Make sure you select CIS 352 as the course for which you're submitting.

PROBLEMS

1. Environments via a-lists

   1. (12 points) EOPL, Exercises 2.5 + 2.8.

   2. (6 points) EOPL, Exercise 2.9.

   3. (6 points) EOPL, Exercise 2.10.

2. Environments via define-datatype

   • (16 points) EOPL, Exercise 2.21.

3. Using the s-list and s-expr representations of page 48 of EOPL, define the following procedures.

   1. (12 points) Define procedures countOccExp and countOccLst such that

      (countOccExp sexp sym)

      returns the number of occurrences of the symbol sym occur in the s-expression sexp

      
      

      (countOccLst slst sym)

      returns the number of occurrences of the symbol sym occur in the s-list slst

   2. (12 points) Define procedures dt->lst-se, dt->lst-sl, lst->dt-se, and lst->dt-sl such that

      (dt->list-se sexp)

      returns the list-representation of sexp when sexp is the data-type version of an s-expression,

      (dt->list-sl slst)

      returns the list-representation of when slst is the data-type version slst of an s-list,

      (list->dt-se sexp)

      returns the datatype-representation of when sexp is the list version of an s-expression,

      (list->dt-sl slst)

      returns the datatype-representation of when slst is the list version slst of an s-list,

   3. (12 points) Define a version of flatten (see EOPL Exercise 1.27) for the data type representation of s-lists.

4. A version of the lambda calculus

   • (24 points) EOPL, Exercise 2.29 plus do a version of unparse for this representation.

Notes

• The list-of procedure is defined as part of the EOPL package in DrScheme.

• The map procedure will be handy for parse and unparse in Problem 4.

• To test the procedures of Problem 3b and parse and unparse of Problem 4, is it OK to do something like:

  (equal?? (unparse (parse '((lambda (x y) (y x a)) (u w) z)))
           '((lambda (x y) (y x a)) (u w) z))
  

• Also, you can use procedures of Problem 3b and parse and unparse of Problem 4 in stating other tests. E.g.,

  (equal?? (countOccExp (list->dt-se '(a (b c (a) a) a)) 
           4)