CSE 505, Autumn 1996

D. Notkin

Homework #3
Assigned: 10/11/96

Due: 10/18/96

This assignment is intended to ask a few questions in slightly greater depth about functional programming and also to do a little more complicated programming in ML (but it surely isn't exceptionally complicated). You will have to read about a few of the concepts, such as defining your own data types and using exceptions in ML, as well as reading more about signatures, structures, and functors. (I may add one more question on Monday.) You may work in pairs, turning in a single assignment with both names, receiving a single, shared grade. Assignments are by the beginning of class on the due date; remember, Kurt wants them in hardcopy now, not by email. This assignment is worth 10% of the quarter's assignments (which in turn are worth 50% of the total grade).

1. (10 points) (Re)write your solution to tails from the last assignment using reduce or any higher-order functions you wish..
   
2. (10 points) Devise a datatype whose values represent propositional logical expressions (that is, have logical variables, represented as strings, connected by the usual connectors AND, OR, and NOT). Write a function eval e l that takes a logical expression e and a list of true propositional variables l and determines the truth value of e on the assumption that the propositional variables on l are true and the other variables are all false. (Due to Ullman.)
   
3. (10 points) Write a function that behaves consistently with the following invocations:
   
   - yourFunc succ [1,1,1,1,1,1,1];
   val it = [2,3,5,9,17,33,65] : int list
   - fun db x:int = 2*x;
   val db = fn : int -> int
   - yourFunc db [1,1,1,1,1];
   val it = [2,4,16,256,65536] : int list
   - fun zero x = 0;
   val zero = fn : 'a -> int
   - yourFunc zero [4,3,4,5];
   val it = [0,0,0,0] : int list
   
4. (10 points) Define an implementation of a simple symbol table using signatures and structures. A symbol table manages names and information associated with those names; the primary operations are lookup, which finds a name in a symbol table (if it exists) and returns the associated information, and insert, which adds a name and associated information into the symbol table. Don't worry about performance, but do think about the way you use types.
   
5. (10 points) Write a signature SIM that describes structures that are an element type with a similarity relation on that type. Write a functor MakeSimSet that takes as arguments a structure Sim that includes an element type and a function that decides on similarity (e.g., similarity might mean that two values are identical, that they are strings with differences only in upper- and lower-caseness, etc.). The result of your functor should be a structure that implements sets with the given type and notion of similarity. The operations in the result structure should include a function findSim that takes an element x and a set S and returns the set of elements in S that are similar to x. It should also include a value create to be an empty set, and a function insert to return a set with a new element created.
   
   Then write a structure Misspell that defines elements to be strings and defines two strings to be similar if they differ in at most one character. Apply your functor to produce the structure MisspellSet that implements sets of strings and allows searches for slightly misspelled words.
   
6. (10 points) In no more than one page of text (and perhaps less), do a high-level comparison of using ML functors vs. a parameterized type mechanism in any other language; candidates include Ada generic packages, C++ templates, etc.
   
7. (10 points) Hudak's paper says (p. 383): "Furthermore, … normal-order reduction allows recursion to be emulated with the Y combinator, thus giving the lambda calculus the most powerful form of effective computability, captured in Church's thesis." He later implies that applicative-order reduction can't exploit the Y combinator he described to handle recursion. Is the implication accurate? If so, why? If not, why not?
   
8. (5 points, extra credit) Write a self-replicating program in ML (I've never seen one, but what do I know).