• Oct 30 - Fixed the weights to include reading comprehension.
• Oct 29 - Fixed type code join.

In this homework, you will practice programming in SML. To run your SML programs, use Moscow ML, which is in /usr/sup/bin/mosml. To start Moscow ML, use

    ledit mosml -P full -I /comp/105/lib

If everything is working correctly, you should see this prompt:

    Moscow ML version 2.10-3 (Tufts University, April 2012)
    Enter `quit();' to quit.
    - 

Let us know if you see anything different. To compile your files, use /usr/sup/bin/mosmlc -toplevel -I /comp/105/lib -c a.sml

Here are the code skeletons for this project:

• warmup.sml
• join.sml
• imp.sml

For guidance on writing SML code, see Learning Standard ML. Also, the fourth Lesson in Program Design explains how to apply our nine-step design process with types and pattern matching. This lesson includes the key code excerpts needed to design and program with standard type constructors list, option, bool, int, string, and order, among others. Immediately following the lesson, you'll find a handy one-page summary of ML syntax.

As in previous homework, we expect you to use the initial basis, i.e., the Standard ML Basis Library. Here are a few key parts:

• Type constructors list, option, bool, int, string, and order
• Modules List and Option, including List.filter, List.exists, List.find, and others
• Other module functions Int.toString, Int.compare, and String.compare
• Top-level functions o, print (for debugging), map, app, foldr, foldl
• Our own Unit module, which is not part of the Basis Library but is described in Learning Standard ML; more on this next.

The most convenient guide to the basis is the Moscow ML help system, which can be accessed via

    - help "";

at the mosml interactive prompt.

As just mentioned, we've provided you with a Unit module you'll use to write regression tests. You'll write unit tests by calling Unit.checkExpectWith, Unit.checkAssert, and Unit.checkExnWith. The details are in Learning Standard ML. Here are a couple of examples: Here are some examples:

    val () =
        Unit.checkExpectWith Int.toString "2 means the third"
        (fn () => List.nth ([1, 2, 3], 2)) 
        3

    val () =      (* this test fails *)
        Unit.checkExpectWith Bool.toString "2 is false"
        (fn () => List.nth ([true, false, true], 2)) 
        false

    val () = Unit.reportWhenFailures ()

If you include these tests in a file a.sml file, you can run them on the Unix shell command line:

    $ mosmlc -o a.out -I /comp/105/lib a.sml && ./a.out
    In test '2 is false', expected value false but got true
    One of two internal Unit tests passed.
    $ 

Note: Do not try using unit tests at the interactive prompt. Doing so is messy and will create confusion if it winds up in an .sml file.

Each call to Unit.checkExpectWith needs to receive a string-conversion function. These functions are written using the string-conversion builders in the Unit module. Here are some examples of code you can use:

    val checkExpectInt     = Unit.checkExpectWith Unit.intString
    val checkExpectIntList = Unit.checkExpectWith (Unit.listString Unit.intString)
    val checkExpectStringList = Unit.checkExpectWith (Unit.listString Unit.stringString)
    val checkExpectISList =
       Unit.checkExpectWith (Unit.listString (Unit.pairString Unit.intString Unit.stringString))
    val checkExpectIntListList = 
      Unit.checkExpectWith (Unit.listString (Unit.listString Unit.intString))

• Code that does not compile without warnings or errors will earn no credit.
• Your functions must have both the names and types specified in the assignment. Otherwise your solution will earn no credit.
• Your code must include effective unit tests. If a function is simple, do take a minute to validate it with a unit test. If a function is not so simple, develop unit tests in the same way you have done for past assignments: one unit test per case in the code.
• Your code must avoid redundant case analysis.
  1. For example, in the following code, the first case is subsumed by the second. It can be eliminated without changing the behavior of the code.

         fun append ([], ys) = ys
           | append (xs, ys) = foldr op :: ys xs

  2. As another example, the two cases in the following code:

         fun sum []        = 0
           | sum (n :: ns) = foldl op + n ns

     should be replaced by a single case:

         fun sum ns = foldl op + 0 ns

• You need not write algebraic laws. We expect you to continue using a systematic design process, but because ML code is so close to algebraic laws, writing them next to the code is typically unnecessary. If you come to office hours, however, we do expect you to be able to talk about algebraic laws and to write them on the board.
Use acceptable coding style. A good resource is the style guide we've provided. In terms of the readings, avoid imitating Ullman (if you have that book), but do emulate Harper, Ramsey (Chapter 5), and Tofte (from the readings).
• Avoid redundant parentheses. Adding extra parentheses is a useful trick when you're first learning ML, since the syntax is different from other languages. But you should take them out once your code works. Run sml-lint your_file.sml to find redundant parentheses, and then remove them.
• The following functions and constructs are forbidden, and using them will earn no credit.
  • List.length
  • null, mynull, hd, and tl; use pattern matching instead
  • Except for in Part C, do not define helper functions at the top level. Instead, use local or let.
  • open; if needed, use short abbreviations for common structures. For example, if you want frequent access to the ListPair structure, you can write structure LP = ListPair LP.map.
  • Any imperative features unless explicitly exempted.

Submit your answers to this part in a file cqs.ml.txt.

1. Read section 5.1 of Harper about tuple types and tuple patterns. Also look at the list examples in sections 9.1 and 9.2 of Harper. Now consider the pattern (x::y::zs, w). For each of the following expressions, tell whether the pattern matches the value denoted. If the pattern matches, say what values are bound to the four variables x, y, zs, and w. If it does not match, explain why not.
   1. ([1, 2, 3], ("COMP", 105))
   2. (("COMP", 105), [1, 2, 3])
   3. ([("COMP", 105)], (1, 2, 3))
   4. (["COMP", "105"], true)
   5. ([true, false], 2.718281828)
2. Read the descriptions of patterns and example values (steps 3 and 2) in the fourth “Lesson in Program Design.” Look at Table 4.1, including the Types of parts column. Using the ideas you find there, prepare to answer questions about this expression:

       case f (x, y, z) 
         of []      => raise Empty
          | w :: ws => if p w then SOME w else NONE

   You are told that the subexpression f (x, y, z) has type 'a list. Using that information, give the type of each of these code fragments, which are built from parts of patterns:
   1. The type of the pattern w :: ws
   2. The type of the variable ws
   3. The type of the expression SOME w
3. Read the section on unit testing in the Guide to learning ML. Read about infix function names in step 3 of the “design steps” section of the handout “Program Design with ML Types and Pattern Matching”. And read the section on unit testing in this homework. Now, using the interpreter to be sure your answer is well typed, translate the following failing unit test into ML:

       (check-expect (foldl + 0 '(1 2 3)) 7)

Write your answers to this part in warmup.sml (click the previous for a link to a code skeleton). Do not use the Standard Basis for any functions in this part unless otherwise specified. At the very end of your warmup.sml, please place the following line:

 val () = Unit.reportWhenFailures () (* put me at the _end_ *)

This placement will ensure that if a unit test fails, you are alerted.

• Define a function mynull (xs:'a list):bool, returns true if xs is empty and false otherwise. Avoid if, and make sure the function takes constant time.
• Define a function firstVowel (xs:char list):bool that takes a list xs of lower-case letters and returns true if the first character is a vowel (aeiou) and false otherwise (including if the list is empty). Use the wildcard symbol _ whenever possible, and avoid if.
• Define a function list_swap (zs:''a list) (x:''a) (y : ''a):''a list that returns zs, except instances of x have been replaced by y and instances of y have been replaced by x. (Bonus content: The ''a is an equality type variable, which means ''a stands for any type that supports equality. This is a weirdness that you don't really need to understand for this class. For a better approach to equality and polymorphism, see Haskell's type classes.)
• Define a function zip (xs:'a list) (ys:'b list):('a*'b) list that takes a pair of lists (of equal length) and returns the equivalent list of pairs. If the lengths don’t match, raise the exception Mismatch, which you must define. You are welcome to translate a solution from μScheme, but you must either use a clausal definition or write code containing at most one case expression. Do not use if.
• Define a function count (f:'a -> bool) (xs:'a list):int that returns the number of times f returns true for an element of xs. Duplicates are counted as many times as they occur.
• Define a function pairup (xs:'a list) (ys:'b list):('a * 'b) list that returns a list of pairs containing every possible combination of one element from xs (on the left) and ys (oon the right). For example, pairup [1,2] [3,4,5] = [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)].

Write your answers to this part in join.sml (click the previous for a link to a code skeleton).

In SML, a list is either the empty list or a list element "consed" onto a tail. As a result, SML lists are singly linked, so to append two lists together requires a linear-time traversal of the first list.

In this problem, you will implement join lists, which suppose similar operations as SML lists but have a constant-time append operation. Join lists are defined with the following type:

datatype 'a jlist =
  EMPTY
  | ONE of 'a
  | JOIN of 'a jlist * 'a jlist

From top to bottom, a join list is either empty, contains a single element, or is the concatenation of two join lists. For example, the SML list [1,2] could be represented as Join(One 1, One 2). Notice that this structure turns appending two lists into a constant time operation. However, it has the downside that list representations are no longer unique, and other operations can be more expensive. For example, [1,2] could also be represented as Join(Join(Empty, One 1), One 2) or Join(One 1, Join(One 2, Empty)), among others. And finding the first element of a list is no longer a constant-time operation.

Your job is to implement the following interface for join lists:

val empty : () -> 'a jlist (* Return the empty list. *)
val one : 'a ->  'a jlist (* Return join list containing just x. *)
val join : 'a jlist -> 'a jlist ->  'a jlist (* Return concatenation of xs and ys. *)
val of_list : 'a list -> 'a jlist (* Return join list containing same elements as xs, in same order. Any join list structure is fine. *)
val to_list : 'a jlist -> 'a list (* Return list containing same elements as xs, in same order. *)
val is_empty : 'a jlist -> bool (* Return true iff xs has no elements. (Note that (join empty empty) is empty...) *)
val length : 'a jlist -> int (* Return number of elements in xs. *)
val first : 'a jlist -> 'a option (* Return first element of xs, or return None if list is empty. *)
val rest : 'a jlist -> 'a jlist (* Return all elements of xs except first element, or throw (any) exception if xs has no elements. *)
val for_all : ('a->bool) -> 'a jlist ->  bool (* Return true if p returns true for all elements of xs. Your knowledge of math will tell you what this should return for an empty list. *)
val exists : ('a->bool) -> 'a jlist -> bool (* Return true if p returns true for at least one element of xs. Your knowledge of math will tell you what this should return for an empty list. *)
val rev : 'a jlist -> 'a jlist (* Return join list with elements of l, but reversed. *)
val map : ('a->'b) -> 'a jlist -> 'b jlist (* Return new join list of same shape as xs, but with f applied to each element. *)
val filter : ('a->bool) -> 'a jlist) -> 'a jlist (* Return new join list containing element of xs for which p returns true, in same order as in xs. *)
val fold_left ('a*'b->'b) -> 'b -> 'a jlist -> 'b (** If list = [x1, x2, ..., xn], return (f xn ... (f x2 (f x1 a))). *)

In your solution, you may not implement any of the above functions via SML lists. In other words, to implement function f on join list l, you may not write code that translates l to an SML lists, runs the corresponding list function on it, and then translates that back to a join list.

Write your answers to this part in imp.sml (click the previous for a link to a code skeleton). For this part, you may use top-level helper functions.

In this problem, you will write an interpreter for Imp, a statement-oriented language that is related to ImpCore. You'll notice as you do this project that your code will look remarkably similar to the operational semantics rules. In fact, your code will probably be noticeably shorter than the description of this problem.

• Imp includes arithmetic expressions whose AST is represented by the following data type:

      datatype aexpr =
               AInt of int                (* integers n *)
               | AVar of string           (* integer-valued variables x *)
               | APlus of aexpr * aexpr   (* addition e1 + e2 *)
    

  where we represent variable environment with an association list:

      type env = (string * int) list
    

  For example, 1+x is represented as APlus(AInt 1, AVar "x"). Here are the operational semantics:

                                  
  --------------------------
    <a, AInt(n)> → n
  
     x ∈ dom(a)
  -------------------------
   <a, AVar(x)> → a(x)
  
    <a, ae1> → n1     <a, ae2> → n2
  -----------------------------------------------------
    <a, APlus(ae1, ae2)> → n1+n2
  

  Implement the above rules as a function aeval (a:env) (ae:aexpr):int that takes a variable environment a and an arithmetic expression ae. For the case when a variable is not in the domain of a, your implementation should raise Not_found, a new exception you should create. Note: The Basis Library for SML does not include association lists, so you probably need to write your own association list functions. Also, we are being less verbose in the description of the rules than usual; one of the skills you should be picking up by this point of the semester is how to read these rules.
• Imp also includes boolean expressions whose AST is represented by:

      datatype bexpr =
               BBool of bool
               | BNot of bexpr
               | BAnd of bexpr * bexpr
               | BLeq of aexpr * aexpr
  

  For example, true && (x<=2) is represented by BAnd(BBool true, BLeq(AVar "x", AInt 2)). Here are the semantics:

                                  
  --------------------------
    <a, BBool(true)> → true 
  
  --------------------------
    <a, BBool(false)> → false
  
    <a, be> → b
  --------------------------
    <a, BNot(be)> → not b
  
    <a, be1> → b1    <a, be2> → b2
  ----------------------------------
    <a, BAnd(be1, be2)> → b1 && b2
  
    <a, ae1> → n1    <a, ae2> → n2
  ----------------------------------
    <a, BLeq(ae1, ae2)> → n1 ≤ n2
  

  Implement the above rules as a function beval (a:env) (be:bexpr):bool that takes a variable environment a and a boolean expression be.
• Finally, Imp includes commands, whose AST is represented by:

      datatype cmd =
               CSkip
               | CAssn of string * aexpr
               | CIf of bexpr * cmd * cmd
               | CWhile of bexpr * cmd
  

  For example, if x<=0 then y:=1 else y:=2 is represented by CIf(BLeq(AVar "x", AInt 0), CAssn("y", AInt 1), CAssn("y", AInt 2)). Note that unlike expressions, commands do not produce values. They are evaluated for their side effects on the environment only. Here are the operational semantics:

  
  --------------------------
    <a, CSkip> → a
  
    <a, ae> → n
  --------------------------
    <a, CAssn(x, ae)> → a[x↦n]
  
    <a, be> → true   <a, c1> → a1
  ----------------------------------------
    <a, CIf(be, c1, c2)> → a1
  
    <a, be> → false   <a, c2> → a2
  ----------------------------------------
    <a, CIf(be, c1, c2)> → a2
  
    <a, be> → false
  ----------------------------------------
    <a, CWhile(be, c)> → a
  
    <a, be> → true     <a, c> → a'    <a', CWhile(be, c) → a''
  ----------------------------------------------------------------
    <a, CWhile(be, c)> → a''
  

  Implement the above rules as a function ceval (a:env) (c:cmd):env.

• cqs.ml.txt containing your answers to the reading comprehension questions.
• warmup.sml containing your answers to Part A.
• join.sml containing your solution to Part B.
• imp.sml containing your solution to Part C.