CSPP 51091
Winter, 2007

Homework 6 Solutions
Due 2/27/07

1. Read Chapters 7 and 8 (through 8.2) of Ulmann, and do the following Exercises:
a. 7.1.3
----------------------------------------------------------------------
(* Part (a) *)
type student = {ID: int, name: string, courses: string list}

(* findName: student list * string -> student list *)
fun findName (students: student list, name0: string) : student list =
    List.filter (fn (s as {name,...}) => name = name0) students

(* Part (b) *)
(* findCoursesByID: student list * int -> string list option *)
fun findCoursesByID (nil: student list, id) = NONE
       (* no student with that ID found *)
  | findCoursesByID ({ID,courses,...}::students, id) =
      if ID = id then SOME courses else findCoursesByID(students,id)

(* Part (c) *)
(* findStudentsByCourse: student list * string -> string list *)
fun findStudentsByCourse (nil: student list, course) = nil
  | findStudentsByCourse ({name,courses,...}::rest, course) =
      if member(course, courses)
      then name::findStudentsByCourse(rest,course)
      else findStudentsByCourse(rest,course)
----------------------------------------------------------------------

b. 7.5.4 
   Do two versions of the solution.  Version 1 should use a single
   one dimensional array to represent the 2-dimensional array or matrix.
   Version 2 should represent the matrix as an array
   of arrays (in this case, use Array.tabulate for the matrix function).
----------------------------------------------------------------------
(* Version 1: one-dimensional array representation *)
(* we have to store the dimension information as part of the matrix
 * representation, along with the array containing the elements. We
 * use "row major" layout of the matrix on the array. *)

type 'a matrix = {content: 'a Array.array, rows: int, cols: int}

(* matrix : int * int * 'a -> 'a matrix *)
fun matrix(n,m,v) = {content=Array.array(n*m,v), rows=n, cols=m}

(* matrixSub : 'a matrix * int * int -> 'a *)
fun matrixSub({content,rows,cols},i,j) = Array.sub(a,i*cols+j)

(* matrixUpdate : 'a matrix * int * int 'a -> unit *)
fun matrixSub({content,rows,cols},i,j,v) = 
    Array.update(content,i*cols+j,v)

(* Note that we didn't actually need the value of rows (number of
rows) in the matrix representation, so we could have gotten 
away with only storing the number of columns (cols) *)

(* Version 2: representation as an array of arrays *)

type 'a matrix = ('a Array.array) Array.array

(* matrix : int * int * 'a -> 'a matrix *)
(* Note that we use tabulate to create a new array for each row *)
fun matrix(n,m,v) = Array.tabulate(n,(fn i => Array.array(m,v)))

(* matrixSub : 'a matrix * int * int -> 'a *)
fun matrixSub(m,i,j) = Array.sub(Array.sub(m,i),j)

(* matrixUpdate : 'a matrix * int * int 'a -> unit *)
fun matrixSub(m,i,j,v) = 
    Array.update(Array.sub(m,i),j,v)
----------------------------------------------------------------------

c. 8.2.4 (give both signature and structure definitions)
----------------------------------------------------------------------
signature STACK =
sig
  type 'a stack
  
  exception EmptyStack
 
  val create : unit -> 'a stack
  val push : 'a * 'a stack -> 'a stack
  val pop : 'a stack -> 'a stack 
  val isEmpty : 'a stack -> bool
  val top : 'a stack -> 'a
end

structure Stack : STACK =
struct
  type 'a stack = 'a list
  
  exception EmptyStack
 
  fun create () -> nil
  fun push (x,s) = x::s
  fun pop nil = raise EmptyStack
    | pop (_::xs) = xs
  fun isEmpty s = null s
  fun top nil = raise EmptyStack
    | top (x::_) = x
end
----------------------------------------------------------------------


2. Modify the lexer in ex5_2_7b.sml to add alphanumeric identifiers to
the set of legal tokens, where an alphanumeric identifier is a string
of one or more letters or digits, starting with a letter. You will
need to add a new variant "ID of string" to the token datatype. The
library functions Char.isAlpha and Char.isAlphaNum should prove useful
here.  Then modify the grammar and parser so that the atomic
expressions can be either integers or identifiers (the expr datatype
also needs to be extended appropriately).

3. The lexer and parser have an imperative style, where the lexer is
using and imperative I/O type (TextIO.instream) for the source of
input characters, and the lexical analyzer it produces is represented
by an imperative function of type unit -> token. The lexer is also
limited because it can use only one kind of character source -- it
cannot, for instance, take its input characters from a string.

Revise the lexer and parser so they use a purely functional style.

Major Hints: 

The new lexer should have the type

   val lexer : (char, 'a) reader -> (token, 'a) reader

where 

   type ('a, 'b) reader = 'b -> ('a, 'b) option

(this is the same as StringCvt.reader). This will make it possible
to apply lexer to, e.g., SubString.getc to use a substring as a
source of characters.  Note that the EOF token can be dropped, since
the function that this lexer returns already produces an option, which
will be NONE if the character source is exhausted. If an illegal
character is encountered, the new lexer should raise an exception
(Lexer) rather than return EOF.

Now the parser could be revised to have type:

   val parser : (token, 'a) reader -> expr

but the nondestructive peek operator (to peek at the next token)
is awkward to write in terms of a reader.  So from the parser's
perspective, a more convenient form of input would be a token
stream (in the sense of Homework 5).

   val parser : token stream -> expr

Lets define a type abbreviation

   type source = token stream

so the type of parser becomes:

   val parser : source -> expr

The token stream has to be "threaded" through the parser
functions, so for instance,

  fun parse (toks : source) = 
  let
      ...
      (* exp : (expr, source reader *)
      fun exp (src : source ) : (expr * source) option = 
      ...

      (* exps : (expr list, source) reader *)
      and exps (src: source) : (expr list * source) option = 
      ...

  end

Now the peek function is just taking the stream head (shd) of src,
and advance is taking the stream tail of src (stl).  As usual,
using pattern matching on the stream data constructors Snil and
Scons is better than calling shd and stl (and combines the functions
of peek and advance), so the first few lines of the exp function 

      fun exp () : expr =
          case peek()
            of INT n => (advance(); Int n)
            ...

would become 

      fun exp (src: source) : (expr * source) option =
          case src
            of Scons(INT n,rest) => SOME(Int n, rest())
            ...

To connect the lexer and parser functions, we must be able to
convert the (token,'a) reader returned by lexer into a token stream.
To do this we will also need a (character) producer to feed the reader.

    fun readerToStream (reader: ('a,'b) reader: producer : 'b) : 'a stream =
        case reader producer
          of NONE => Snil
           | SOME(x, producer') =
               Scons(x, (fn () => readerToStream(reader,producer')))

Now to parse the contents of string is easy:

    fun parseString (s: string): expr =
        let val ss = Substring.full s
                (* turn the string into a Substring.substring *))
            val lex : (token, Substring.substring) reader =
                lexer Substring.getc  
                (* Substring.getc : (char, Substring.substring) reader *)
            val src : source = readerToStream (lex, ss)
         in parse(src)
        end

But now how do we parse the contents of a file?

   fun parseFile (filename: string) = ??? 

Also, it is now possible to change the parser slightly so that its
type is:

   parser : (expr, source) reader

Show how to do this.