Out: Friday, January 18, 2008
Due: 5 PM Tuesday, January 29, 2008
Submission: Individual
This assignment is to be done individually, not in pairs.
One purpose of this assignment is to give you more practice writing procedures that process data by mirroring the inductive definitions of the data types. Another purpose is to ensure that every individual student can write such procedures without help from other students. Another purpose is to provide more practice with trees that are similar to the data structures we will use to represent computer programs. Finally, the assignment involves a simple example of the distinction between context-free grammars and context-sensitive constraints. By the end of this assignment, you should be comfortable writing small programs that process lists and trees.
contents-of procedure
should return an Int when applied to a leaf, but should
return a Symbol when applied to an interior node.)
bound-variables that
takes a single argument M, which is an element
of LcExp (defined on page 9),
and returns a list of all identifiers (in any order) that
occur as the bound variable of a lambda expression within
M.
Note that the same identifier may occur as the bound variable
of more than one lambda expression, in which case it should
appear more than once in the result. In general, an identifier
that occurs as the bound variable of n lambda
expressions should appear n times in the result.
occurs-bound? that
takes a symbol sym and an expression M
of LcExp (defined on page 9),
and returns true if sym occurs as
the bound variable of some lambda expression within M,
but returns false otherwise.
binary-search-tree?
that takes a data structure b generated by the
context-free grammar for a Binary-search-tree
(on page 10),
and returns true if b satisfies the context-sensitive
invariant for a Binary-search-tree,
but returns false otherwise. For example:
(binary-search-tree? '(20 (14 (6 () ())
())
(24 () ()))) ; returns #t
(binary-search-tree? '(20 (14 ()
(6 () ()))
(24 () ()))) ; returns #f
occurs-within?
that takes an integer m and a true binary search tree
bst (that satisfies the binary-search-tree?
predicate),
and returns true if m occurs within bst
but returns false otherwise.
mp2.scm.
This module should be written in the language
(lib "eopl.ss" "eopl"), and should
provide the 11 procedures you wrote for part 1
and the 5 procedures you wrote for parts 2 through 6.
(You may define help procedures as well, but they
should not be provided.)
"mp2-test.scm".
The module should be written in the language
(lib "eopl.ss" "eopl"), require
the modules "drscheme-init.scm"
and "mp2.scm",
and should test all of the procedures provided by
mp2.scm.
To get you started, the course staff are providing you with
a woefully incomplete prototype of
mp2-test that uses the examples from the
exercises in part 1 as tests. You will need to add more
tests to complete that module.
Note that mp2-test requires mp2.scm,
which you are to implement, and also requires
drscheme-init.scm
as in mp1.
mp2-test module,
in a file named mp2-test-output.txt.
One way to do this is to take the contents of the
DrScheme interaction window and paste it into a
fixed-width text processor.
There is also a "Save Interactions as Text..." command, under
the "Save Other" submenu of DrScheme's File menu.
Whatever technique you use, make sure you double-check that the
submission is just plain text and that it matches the output you see
when you run the mp2-test module.
Last modified: 18 January 2008