Assignment 7: ML Warm-up
CSE 341: Programming Languages
The University of Washington, Seattle, Winter 2012
Purposes: The purpose of this assignment is gain familiarity with the ML programming language.
Due: Thursday, March 1 at 11:00 PM via Catalyst CollectIt. The target date, however, is Feb. 28.
Individual Work.
Do this assignment individually. DO NOT COLLABORATE on this assignment. This is not a partnership or teamwork assignment.
What to Turn In: You should turn in the following files:
Your files should begin with comment lines that give the name of the file, a program name (that is more descriptive and English-like than the filename), and the author's (your) name.

Read chapters 1-3 of Elements of ML Programming. Part 1: From the Book
(80 points) Do the following exercises from the book.
Exercise 2.1.1 b, d, f, h.

Exercise 2.1.2 b, d, f, h

Exercise 2.2.2 b, f, g.

Exercise 2.3.2

Exercise 2.4.2 b, d, f, h.

Exercise 2.4.3 b, d.

Exercise 2.4.5 b, d.

Exercise 3.1.3 b, f

Exercise 3.2.1 b, e.

Exercise 3.2.3 b, d.

Exercise 3.3.1 b, c.

Exercise 3.3.2.

Exercise 3.3.5 b.

Part 2: Not from the Book
  1. (20 points) Define a function Encipher k plainText that takes an integer k, returning a function that then takes a string of characters and replaces each character by another which is obtained by going k positions further into the 8-bit ASCII character set and wrapping from chr(255) to chr(0). For example
    - encipher 25 "Madam I'm Adam!" ;
    val it = "fz}z\1349b@\1349Z}z\134:" : string
    You may define any helping functions needed.
  2. (Optional for 5 points of extra credit) Define a function Verify(propFormula) that takes a string in the propositional formula language described below and tells whether it is a tautology, contradiction, underDetermined, or poorlyFormed (if it's not a legal formula). Your function should return values of a new type tval defined as follows.
    - datatype tval = tautology | contradiction | underDetermined | poorlyFormed ;
    - Verify("t") ;
    val it = tautology : tval
    - Verify("~t v ~t") ;
    val it = contradiction : tval
    - Verify("~t v f v f") ;
    val it = contradiction : tval
    - Verify("~t v f v ~f") ;
    val it = tautology : tval
    In this exercise, you can assume that each formula is well-formed and uses only the symbols f, t, ~, v, . Assume that "v" is a binary operator, and that "~" is unary negation. These formulas are clauses involving only the possible literals f, t, ~f, and ~t. Here f means false and t means true. (This problem may offer ideas for solving a problem in Assignment 8.)
  3. (Optional for 5 points of extra credit) Given a definition of the function ngrams, described below, using a functional programming approach. The function should be defined in curried form, with an argument n that tells how long each n-gram should be. Then there is a list argument which is the source for constructing the n-grams. An n-gram is a list of n consecutive elements from the source list.
    - ngrams 3 [0,1,2,3,4] ;
    val it = [[0,1,2],[1,2,3],[2,3,4]] : int list list
Last updated 27 February at 2:12 PM