Data Types

In MiniML: bool, int option, int list

datatype shape = Circle of real * real * real

Recursive Types

  • Context-free Grammar
  • Inductive (leaves are just ints)

Using Abstraction

Fold is your friend! fold takes a list, state (accumulator), and a folder.

internal function loop.

base case: empty list

induction step: apply folder to (head, state), and recursively call loop on the tail

map:

Generative Datatypes

Pattern Matching

like switches except not just on ints (or enums)

can be:

case s
  of x => e1 (* any subject matches this pattern *)
   | _ => e2 (* same as x but discarded *)
   | 3 => e3 (* matches when s = 3 *)
   | (p1, p2, pn) => e4 (* provided s is a tuple
                         * and the correct arity
                         * (guaranteed already by
                         *  the type checker)
                         * pn can be a pattern
                         *)
   | C y => e5 (* Matches Constructor AND
                * y can be a tuple, constructor,
                * record, etc.
                *)

Quirks

case s
  of (1, 2) => e1
   | (1, 3) => e2

A naive compiler would ask “Is the 1st element 1?” twice. In general, this is NP complete.

Infeasible/Silly

case s
  of x => e1
   | 3 => e2

x will always match

fun diff(nil, y) = y(1)
  | diff(x, nil) = x(1)

Overlapping (nil, nil) so y(1) will never be executed.

Questions?

case s
  of Cons(x)      => e (* 1-tuple = variable *)
   | Cons(y, nil) => e (* redundant *)

One cannot call functions ins a pattern, or match on the value of a ref. However, SML lists can be deconstructed using :: as in the following:

case s
  of []         => e (* empty list *)
   | hd :: tail => e (* non-empty list *)

Example

case s : (bool * intlist)
  of (true, _)            => p1
   | (false, nil)         => p2
   | (false, Cons(x,Nil)) => p3
   | (false, Cons(y,z))   => p4

Is the order of matching important?

If the ordering is right to left, then the correct match will not happen until both arguments are matched (since _ is the wildcard)

Are p3, p4 redundant?

No, because p3 is more specific but overlapping. It matches specifically Nil while p4’s last argument matches anything and assigns the value to y

Is case s of x => e | 3 => e redundant?

Yes, because x will always match because of ordering and 3 will never

Here’s some random stuff I found useful after discussing with Phil on “how to start writing ML.”

1. use eval_be to handle binary operations and eval_ue for unary operations.

2. use conv() to handle A.Const_e and A.DataCon_e

3. patMatch() basically handle two cases: “Let val …” and “case … of …” both of these requires pattern matching (that’s why it is there).

4. Before you handling A.Let_e(A.Val_d(…)) in patMatch, it is a good idea to study how A.Case_e() works in patMatch. That should give you some hint on how to proceed.

5. Don’t worry about the A.Id_t(“pat”) or A.Id_t(“patType”) that you found in interp.sml. They are not used at all.

6. http://www.standardml.org/Basis/list-pair.html contains useful function to use when handling A.Tuple_p and A.Record_p in pat_compile. Specifically you need to walk down the tuple/records and perform matching one by one. ListPair is different from List where ListPair walk down two lists simultaneously (your root and p) whereas List do the same thing on one list.

7. Lastly, the assignment statement “x := 3” returns a unit “()”.

I’m leaving the country Tuesday Aug 29 until Sept 21. JC has volunteered to add everyone who wishes to contribute to the projects posts and post scribe notes while I’m gone.

Best of luck!

For Sale!!! 1 MiniML interpreter for the LOW LOW price of just countless hours!! Seriously though, here are some (possibly) useful notes on how to tackle this beast (Make sure you start early)

Basically there are two parts, evaluate and pattern_compile. For evaluate, I’d suggest the following (in order):

  1. Const/Id
  2. Unop/Binop
  3. Fn/App
  4. Ref/Deref/Assign
  5. Tuple/Ith
  6. Datacon/If
  7. Let(Fun)
  8. Case/Let(Val)
  9. Record/Field

You won’t need to touch patterns until Case/Let(Val). And you’ll need DataCon to do If, and everything before to do Case/Let(Val).

ML-Dev Screenshot

A lot of time with SML, at least initially, will probably be spent fighting with the compiler. Specifically the cryptic compiler errors that are spit out. For those that are not fearful of IDE’s here’s a nifty plugin for eclipse that parses your SML and puts thosse infamous squigglys under the BAD parts of code. It works (hehe) and has been tested but I offer little support for the plugin. Attached is the zip file that you extract unto your eclipse/plugins dir.

The plugin creates a SML perspective and does all the nifty syntax highlighting for your sml (and sig) files. If you have smlnj installed, you can also optionally run the program from withing eclipse, or use MLton to typecheck every time you save (useful, but possibly time consuming). If there is interest, I’ll post how to do all of those.

Unlike the java editor however, it has no debugging/breakpoint support. After all, it’s only written by two people (but eclipse hackers are welcome to contribute!)

So, without further ado, here’s the link to the zip file:

http://www.cs.purdue.edu/homes/schatzp/cs502/ml-dev_2006-08-26.zip

And the user guide (a little older):

http://www.cse.iitd.ernet.in/~csu02132/mldev/userguide/

If anyone wants to check their project, pasting the code into smlnj is the best way, but if you’re on a linux machine you can run my compiled binary. It has a debug option that will print out the expression tree on every iteration of eval (type “:d” into the interpreter to toggle)

Changes to get interpreter to work on MLton:

  1. Run MLton versions of ml-lex and ml-yacc (smlnj uses Unsafe structure)
  2. Change some matches in typecheck.sml
  3. Add mlb, and main SML file that just runs the interpreter

The following tar.gz file has the MLton modifications and my compiled interpreter:

http://www.cs.purdue.edu/homes/schatzp/cs502/cs502-interp_mltonized_2006-08-26.zip

OK, I think I’m just about done with the project (anyone else? or have you not started yet?)

You can run the miniML code (for sanity sake) in SML/NJ simply by doing the following:

  1. type [datatype 'a list = Nil | Cons of 'a * 'a list;] into SML/NJ
  2. In a separate editor, open the test case and replace “\nval” with “\n;val” (so the values are printed to stdout) (but don’t save the file since miniML doesn’t like “;”)
  3. Paste the code into SML/NJ.

Time permitting, I may compile compiled my interpreter (it’s NOT A REFERENCE IMPL) using MLton (http://mlton.org) and post linux/windows binaries.