Question	Required definitions	Sample usage
1	`type 'a PriorityQ exception emptyQueue val nullQueue = - : 'a PriorityQ val enter = fn : int * 'a * 'a PriorityQ -> 'a PriorityQ val front = fn : 'a PriorityQ -> 'a val remove = fn: 'a PriorityQ -> 'a PriorityQ val contents = fn 'a PriorityQ -> 'a list val size = fn 'a PriorityQ -> int`	`- val q1 = nullQueue : string PriorityQ; val q1 = - : string PriorityQ - front(q1); uncaught exception emptyQueue - val q2 = enter(10,"life",q1); val q2 = - : string PriorityQ - val q3 = enter(1,"love",q2); val q3 = - : string PriorityQ - val q4 = enter(20,"money",q3); val q4 = - : string PriorityQ - front(q4); val it = "love" : string - contents(q4); val it = ["love","life","money"] : string list - val q5 = remove(q4); val q5 = - : string PriorityQ - size(q5); val it = 2 : int`
2a	`val listify = fn int list -> int list list`	`- listify [1,2,3,10,5,7,6]; val it = [[1,2,3,10],[5,7],[6]] : int list list`
2b	`val duplicates = fn int list -> bool`	`- duplicates [1,2,3,4,5,6]; val it = false : bool`
2c	`val duplicates2 = fn int list -> bool`	`- duplicates2 [1,2,2,3,4,5,6]; val it = true : bool`
3a	`val f = fn int -> int`	`- f 5; val it = 13 : int`
3b	`val fastF = fn int -> int`	`- fastF 5; val it = 13 : int`
4a	`datatype 'a lazyList = cons of 'a * (unit -> 'a lazyList) \| nullList datatype 'a option = none \| some of 'a val seq = fn int * int -> int lazyList val infSeq = fn int -> int lazyList val firstN = fn 'a lazyList * int -> 'a list val Nth = fn 'a lazyList * int -> 'a option`	`- val s1 = seq(10,400); val s1 = cons(10,fn) : int lazyList - val s2 = infSeq(10); val s2 = cons(10,fn) : int lazyList - firstN(s2,11); val it = [10,11,12,13,14,15,16,17,18,19,20] : int list - Nth(s2,20); - val it = some 29 : int option - Nth(s1,1000): - val it = none : int option`
4b	`datatype 'a lazyList = cons of 'a * (unit -> 'a lazyList) \| nullList val filter = fn bool lazyList * 'a lazyList -> 'a lazyList`	`- val c = cons(false, fn () => cons(true, fn () => nullList)); val c = cons(false,fn) : bool lazyList; - val s = filter(c,infSeq(1)); val s = cons(2,fn) : int lazyList; - firstN(s,3); val it = [2] : int list`
4c	`datatype 'a lazyList = cons of 'a * (unit -> 'a lazyList) \| nullList val primes = fn unit -> int lazyList`	`- val p = primes(); val p = cons(2,fn) : int lazyList - firstN(p,10); val it = [2,3,5,7,11,13,17,19,23,29] : int list`

CS538: Spring 2003

Assignment#2: SML

IMPORTANT: make sure to see required definitions and sample usage below, and notes & hints at the bottom of this page

Handin procedure

Your handin folder is in ~cs538-1/public/handin/proj2/login where login is your login name.
Put your solutions in a SEPARATE FILE for each sub-part: 1, 2a, 2b, 2c, 3a, 3b, 4a, 4b, 4c. You can also include a file called README with any notes about your submission, including the timing results for part 3b. PLEASE NOTE: name your files 1, 2a, 2b ... without an extension and not 1.sml, 2a.sml ... or anything else. Put all the files in the handin directory and do not make separate subdirectories for each question.
Make each file SELF-CONTAINED. Don't load code used in another question (e.g., do not load file 2a in your solution for 2b), and don't assume that your code will execute in the handin folder. To achieve this, you may need to make copies of code that is common to multiple sub-parts of the same question. E.g., copy the definition of listify from file 2a into file 2b.

Each file should make available (at least) the SML functions and types required by the question. Here's the complete list of definitions that need to be present in each file. Note that you can have more functions defined, this are just the minimum definitions required in each file. Sample function usage is also shown below.
Also make sure to define your types, functions, values, exceptions to be EXACTLY the same type as shown here, and they should behave in EXACTLY the same way as shown below. Functions should be of the right type and take arguments in the right order, e.g., function enter in question 1 should take a single tuple of 3 elements (priority, value, queue in that order) as its single argument rather than 3 separate arguments. Furthermore, 'priority' should be an integer, 'value' can be any type T, and 'queue' should be of type T PriorityQ (matching the type T of 'value').
Also, be sure to see below the notes and hints for each question.
If you are unclear about the types or format or purpose of function arguments and return values, please clarify the matter with the instructor or TA before submitting the code.

Question Required definitions Sample usage

1 type 'a PriorityQ exception emptyQueue val nullQueue = - : 'a PriorityQ val enter = fn : int * 'a * 'a PriorityQ -> 'a PriorityQ val front = fn : 'a PriorityQ -> 'a val remove = fn: 'a PriorityQ -> 'a PriorityQ val contents = fn 'a PriorityQ -> 'a list val size = fn 'a PriorityQ -> int - val q1 = nullQueue : string PriorityQ; val q1 = - : string PriorityQ - front(q1); uncaught exception emptyQueue - val q2 = enter(10,"life",q1); val q2 = - : string PriorityQ - val q3 = enter(1,"love",q2); val q3 = - : string PriorityQ - val q4 = enter(20,"money",q3); val q4 = - : string PriorityQ - front(q4); val it = "love" : string - contents(q4); val it = ["love","life","money"] : string list - val q5 = remove(q4); val q5 = - : string PriorityQ - size(q5); val it = 2 : int

2a val listify = fn int list -> int list list - listify [1,2,3,10,5,7,6]; val it = [[1,2,3,10],[5,7],[6]] : int list list

2b val duplicates = fn int list -> bool - duplicates [1,2,3,4,5,6]; val it = false : bool

2c val duplicates2 = fn int list -> bool - duplicates2 [1,2,2,3,4,5,6]; val it = true : bool

3a val f = fn int -> int - f 5; val it = 13 : int

3b val fastF = fn int -> int - fastF 5; val it = 13 : int

4a datatype 'a lazyList = cons of 'a * (unit -> 'a lazyList) | nullList datatype 'a option = none | some of 'a val seq = fn int * int -> int lazyList val infSeq = fn int -> int lazyList val firstN = fn 'a lazyList * int -> 'a list val Nth = fn 'a lazyList * int -> 'a option - val s1 = seq(10,400); val s1 = cons(10,fn) : int lazyList - val s2 = infSeq(10); val s2 = cons(10,fn) : int lazyList - firstN(s2,11); val it = [10,11,12,13,14,15,16,17,18,19,20] : int list - Nth(s2,20); - val it = some 29 : int option - Nth(s1,1000): - val it = none : int option

4b datatype 'a lazyList = cons of 'a * (unit -> 'a lazyList) | nullList val filter = fn bool lazyList * 'a lazyList -> 'a lazyList - val c = cons(false, fn () => cons(true, fn () => nullList)); val c = cons(false,fn) : bool lazyList; - val s = filter(c,infSeq(1)); val s = cons(2,fn) : int lazyList; - firstN(s,3); val it = [2] : int list

4c datatype 'a lazyList = cons of 'a * (unit -> 'a lazyList) | nullList val primes = fn unit -> int lazyList - val p = primes(); val p = cons(2,fn) : int lazyList - firstN(p,10); val it = [2,3,5,7,11,13,17,19,23,29] : int list

Your submission must work correctly with SML/NJ installed here in CS (in /s/std/bin/sml). You are free to work on your own with a newer version of SML which you might have downloaded and installed at home but before submission, you must make sure your code runs with our version of SML. If you use SML library functions, please make sure that these library functions are also available in the SML/NJ installed here in CS.
Your code will be tested for correctness using automatic scripts and a test suite. So please make sure that the code you submit does not generate extraneous output by calling print or other SML output functions. Each of the functions listed above should silently return values as required by the question. Also, please make sure that your files are free of any top-level tests or timings that you may have used during testing and debugging. This extra code can confuse the automatic tester we use.
You can assume that your functions will always be passed valid input of the right type, so you do not need to check, for example, that the input argument is a list or a number and so on. But your functions should be able to correctly handle all valid input, including boundary conditions such as empty lists.
Your handins will be picked up by automatic scripts on the midnight of the due date (Apr 21), and then again on the midnights of each of the 3 allowed later days (Apr 23, 25, 28). Any files found in a handin folder by our scripts on these 4 days will be deemed to be part of a submission. So if you plan to submit late, make sure that your handin directory is empty on the earlier submission days. You can also email me at plakal@cs.wisc.edu to let me know that you are submitting late.

Grading criteria

The first and foremost criteria for grading is correctness. Your programs should execute without errors and produce the correct output with our test suite. Points are awarded for each test input successfully handled by your code.

You can use any algorithms or SML functions to produce the correct output, you are not restricted to following the exact path set by the questions. But you must follow the question when it comes to mandatory requirements, such as using abstract data types to hide internal representation in Q.1, exceptions to exit early in Q.2(c), memoization to avoid recomputations in Q.3., and lazy evaluation for sequence processing in Q.4.

No extra points for the most elegant programs but you are encouraged to write in a functional style, making best use of SML's natural abstractions: lists, pattern-matching, recursion, higher-order functions, and so on. These will invariably reward you with compact, natural-looking code which is easy to read and understand. See the lecture notes and look online for SML programs to get a flavor of ML programming.

We will penalize programs that are excessively kludgy and hard to read or understand. Don't try to write C++ or Java in SML. In particular, the excessive use of the reference operators (ref and ! and != and their cousins) is frowned upon and will be penalized. Note that this does not apply when an imperative update using references might be required or natural, as with memoization in question 3(b).

Partial credit will be given for programs that seem to be on the right track.

SML Tips

First of all, check out the 538 SML page for information on SML/NJ and how to use it in the CS Department.

Also see the SML/NJ home page for latest information on the language and available libraries (including the Standard Basis library).

SML/NJ has strong static typing, forcing you to make your program type-correct before it can be run (leading to a slogan of ML fans: "if it type-checks, it just runs"). But its error messages can be very cryptic leading to much time being wasted trying to figure out what SML is trying to tell you. Style note: it is better to use SML's type inference system and not put explicit type annotations everywhere.

When in doubt, parenthesize. It's a common error to omit parentheses around parameters in patterns, e.g., a list pattern should be written as (h::t) and not just h::t. Also, each definition requires you to use the val or fun keywords, even definitions within a let clause.

When pattern matching, make sure you cover all combinations of possibilities for arguments. You may not care about all combinations, and some of them might be impossible, but the compiler does not know that. It will warn you of non-exhaustive matches if your pattern-matching clauses are not sufficient.

Also, it is preferable to use pattern matching rather than tuple selectors like #1 or #2, or list selectors like hd or tl. In some cases, using tuple selectors might cause type errors (the inscrutable unresolved flex record) since there is not sufficient information for SML to deduce the exact number of elements in a tuple. In such cases, you should explicitly specify the size of the tuple in the pattern, e.g., write

     fun f (a,b) = b

rather than

    fun f t = #2(t)

See this page for some help with deciphering SML error messages, and see the SML/NJ errors list for the definitive reference.

Assignment Notes, Hints, FAQ

Question 1.

A straightforward extension of the abstype 'a stack defined in class. We're not looking for the most efficient implementation, rather more for getting the functionality and for defining the abstract type in the right way, hiding the representation.
It is NOT CORRECT to have your funtions take queues of type (int * 'a) PriorityQ, or other representation-specific types. Your functions should handle priority queues parameterized by a single type 'a: the type of the value that can be put in the queue, as shown in the sample usage above for 'a = string. Your queues should not make the internal representation of the queue (e.g., tuples of integer priority and queue value) visible to the outside world. 'a PriorityQ is an ABSTRACT DATA TYPE and hence hides its internal representation. Consumers of PriorityQ are only aware of one type parameter 'a which is the type of values that can reside in the priority queue. But consumers are not, and should not be, aware of the internal representation. It should be possible to substitute another PriorityQ which has the same type but a completely different representation and still have everything work.
As an example, consider a standard (non-priority) queue which we implement as a list with a head and a tail pointer (indices into the list). The type we expose to the outside world is the type variable 'a, the type of the elements in the queue, and declared in the first line below. The representation type is declared in the second line, and is a tuple of 2 integers (head and tail indices) and a list of elements of the same type 'a. Note that the representation type can have completely arbitrary structure, of our choosing, as long as it is linked to the external type via the type variable 'a. It is hidden from the outside world and is only available to our queue functions. The outside world only sees values of type int queue, string queue and so on, while our queue functions see values of type int list * int * int, string list * int * int and so on.
```
    abstype 'a queue =
      Q of 'a list * int * int
    with
      val enqueue(Q(l,h,t)) = ...
      fun dequeue(Q(l,h,t)) = ...
	  ... etc ...
    end; 
 
```

You can construct queues in at least two ways: either start with the null queue and insert elements into it (as shown in the sample usage for Q.1 above), or you can define your own constructor function that makes a queue out of some initial values.

When using the null queue, you might get this warning message: Warning: type vars not generalized because of value restriction are instantiated to dummy types (X1,X2,...). This particular warning is not a problem in your code, it is a quirk of SML/NJ's type checking system. It is safe to ignore it as long as your functions are computing the right values. You can avoid the warning by specifying a concrete type for the null queue when first using it, as shown in the sample usage for Q.1 above where q1 is given an explicit type of string PriorityQ when it is assigned the null queue.

Question 2.

Direct translation of your solutions to Proj#1 Q.5 from Scheme into SML.

Please note that duplicates and duplicates2 take ordinary lists of integers as input and check for duplicates. They don't take a listified list as input, they call listify internally. Please see the sample usage above.

Question 3.

As the question says, memoization simply means remembering computed values to avoid recomputing them in the future. A simple way to do this is to record the values computed by the function f in a table (i.e., a cache of function values), and then look up the table before you recompute the same values in the future. Your task is to figure out how to maintain this table inside the function fastF. You will not be graded by speed (as long you don't submit something that's as slow as the original function f!), but by how you implemented the memo table.

There are at least two methods to implement memoization. One method uses the imperative update operators of SML (ref, !, :=, which are allowed in Q. 3b) to maintain a hidden table that remembers the return values across calls to function f. This will probably be the fastest implementation. The other method does not use imperative updates, and only remembers computed values in a table within a single sequence of recursive calls to f. Either way is fine for this question, and will receive full points.

To aid timing measurements, you can use this timing function:

 
fun time f n =
    let
      val t = Timer.startCPUTimer()
      val v = f n
      val usrsecs = Time.toReal(#usr(Timer.checkCPUTimer(t)))
    in
       print(Real.toString(usrsecs));
       v
    end;

Call it using time f 28 or time fastF 28. Repeat measurements a few times to get a stable average.

Question 4.

Straightforward lazy list processing, similar to Question 4.(b) from Proj#1.

Reminder: Functions can be used just like any other values either by naming the function:
```
let fun f = x+2  in (f,0) end; 
```
or by using an anonymous function:
```
( (fn x => (x+2)), 0 )
```
. Both of these evaluate to a tuple of a function and integer zero. Functions of no arguments are defined using () (of type unit) as the argument.
When defining primes, it may be helpful to break the task into sub-tasks, and first define a function that can filter multiples of a given integer from a lazy list of integers. Then think about how you can use this to generate the lazy list of primes.

- Manoj Plakal <plakal@cs.wisc.edu>