Standard ML (SML)

What is SML?

Now, we’ll talk about functional programming in the context of SML for some concrete examples.

SML (Standard ML) is a functional programming language, with some imperative features.

Etymology — Stands for Standard ML, because it’s a modern version of ML (Meta-Language) a functional lang. made by Robin Milner in 1973. ML was made to talk about languages.

One of the few fully formal language specifications (it’s literally all math).

Industrial Strength Compilers:

SML/NJ (Standard ML of New Jersey)
Moscow ML
MLton

Overview

Expressions: Everything is built from expressions.
Functions are first-class citizens: They are values like any other and can be bound to variables. Function values are closures.
Static Type System: Powerful type inference statically determines types of values.
Module System: Allows definition of parametric, polymorphic abstract data types.
Management: Includes Exception handling and Garbage Collection.

Example: Memory Management

val x = 1;

val declares a new symbol.

= is a binding, NOT an assignment.

Allocates new memory M' which creates a persistent value.

val x = 3;

Binds a new symbol x to 3. It shadows the old x, but does not destroy the old value.

Because we create “garbage” (unreachable values) via shadowing, we need a Garbage Collector.

Simple Types & Operators

Types:

int (integers)
real (floating point)
string (strings)
bool (booleans)
char (characters)

Arithmetic Operators:

Integers: +, -, *, div.
Reals: +, -, *, /.
Note: div is for integers, / is for reals.

Unary Negation:

Use ~ for negative numbers, not -.
Example: ~5 + 47 evaluates to 42.

Logical Operators:

>, >=, <, <=, =, <> (not equal).
Example: 42 <> 7 evaluates to true.

String Concatenation:

Use ^.
Example: "Hello" ^ " " ^ "world!".

Declarations

Bindings between names and values.

Values can be constants, functions, structures, etc.

Don’t forget, they’re NOT assignments!

Functions

Functions are defined using the fun keyword.

Example: Functions

- fun f(x) = x+42;
val f = fn : int -> int

int -> int is telling us this maps integers to integers

Functions are pure (they have no side-effects), aka: it doesn’t modify any memory.

Lambda Functions

Created with fn.

Example: Lambda Functions

fn x => x * x

Multiple Parameters

You can declare multiple parameters as a tuple or in Curried form.

Definition — Curried Form: TODO

Example: Multiple Parameters

Tuple:

fun add(x,y) = x + y;
val add = fn : int * int -> int

Curried Form:

- fun add x y = x + y;
val add = fn : int -> int -> int
- add 3 4;

---

**Using Curried Form**: 
```sml
- val plusFour = add 4;
val plusFour - fn : int -> int
- plusFour 3;
val it = 7 : int

Recursive Function

fun fac(x) = if (x=0) then 1 else x * fac(x-1);

Iteration v. Recursion — They both perform an action over-and-over. The difference is, in recursion, you repeat by calling the same function again; while in iteration you repeatedly jump until a condition is true.

The short of it: Recursion consumes more memory (unless you do tail recursion), but is easier to reason about.

Polymorphic Function

Definition — Polymorphism: The ability of an element to appear to have multiple forms or behaviors depending on context.

If the type engine can’t determine a type, it gives a polymorphic type.

Example: Polymorphic Function

- fun toList x = [x];
val toList = fn : 'a -> 'a list
- toList 42;
val it = [42] : int list
- toList "hello";
val it = ["hello"] : string list

This is very different from taking an object in Java.

This is more similar to templates in C++.

Tuples

Values from cross-products of different sets.

They’re effectively groups of various elements, of potentially different types.
We can use tuples to return multiple values.

Example: Tuples

fun sumAndProd(x,y) = (x+y, x*y);
val result = sumAndProd(25, 17);
val sum = #1(result);
val prod = #2(result);

Lists

Sequences of value of the same type.

Empty List: [] or nil

Operations

::: Prepend value (constant time)
@: Concatenate two lists (linear time)
hd: Return head
tl: Return tail

Aside — SML does have arrays, but you want to avoid them as much as possible.

Example: Simple list operations

- 42::[21, 7];
val it = [42,21,7] : int list
- [3, 12]@[52];
val it = [3,12,52] : int list
- hd [42, 72, 0];
val it = 42 : int
- tl [13, 42, 5];
val it = [42,5] : int list

Pattern Matching

SML features a powerful pattern-matching mechanism for multi-part functions.

Example: Pattern matching examples

Factorial:

- fun fact 0 = 1
| fact x = x * fact(x-1);
= val fact = fn : int -> int

Fibonacci:

- fun fib 0 = 1
| fib 1 = 1
| fib k = fib(k-1) + fib(k-2);
= val fib = fn : int -> int

Avoiding Stack Overflow

Stack overflow is when the stack collides with the heap.

To avoid stack overflow, do tail recursion so that the stack doesn’t grow.

Recall — Recall that memory is organized into four sections:

Stack: Activation Records

Heap: Dynamically Allocated Data

Data: Statically Allocated Data

Text: Program Data

Definition — Activation Record: Stores everything you need for a function (local variables, arguments, etc.)

Let Expressions

We can create local bindings to simplify function definitions.

Example: Let expression

fun heads(l1, l2) =
  let
    val h1 = hd l1
    val h2 = hd l2
  in
    (h1, h2)
  end;

Higher-Order Functions

Functions can be passed to other functions easily.

Example: Higher-Order Function

fun plusOne x = x+1
fun apply f [] = []
| apply f (x::xs) = f(x)::(apply f xs);
apply plusOne [41,41,41]

Notice how we did not do anything special to pass the function.

Because we use f like a function, SML knows it must be a function.

User-Defined Data Types

New types can be defined through a powerful system of enumated types (disjoint unions).

Example: User-defined data types

Simple Enum:

datatype color = Red | Green | Blue;
val x = Red;

Parametric/Polymorphic (Binary Tree):

datatype 'a binaryTree = Empty
        | Node of 'a * 'a binaryTree * 'a binaryTree;

val tree = Node(42, Empty, Empty);

Exception Handling

SML provides exception handling.

Example: Raising and handling exceptions

Raising Exceptions:

exception divByZ of int;
fun safeDiv (y,x) = if (x = 0) then raise (divByZ y)
                    else (y div x);

Handling Exceptions:

safeDiv(4,0) handle (divByZ x) => x + 38;
(* Result: 42 *)

And much more…

SML provides sophisticated features like structures, signatures, and functors. It also supports imperative features like I/O and arrays for interactive applications.

Professor’s Rec: 99 Lisp Problems: A website containing small logic problems relevant to mastering any functional language.

Assorted Practices

Example: Summing a List

Goal: Compute the sum of a list of integers.

1. Naive Implementation (Stack Heavy) Concept: Base Case (Empty list -> 0), Inductive Case (Add head to sum of tail).

fun sum nil = 0
  | sum (x::xs) = x + sum xs;

2. Tail Recursive Implementation (Optimized) Concept: Use an accumulator to pass state forward, allowing the compiler to optimize the stack (similar to a loop).

fun tailSum [] acc = acc
  | tailSum (x::xs) acc = tailSum xs (x + acc);

(* Wrapper to hide the accumulator *)
fun sumV2 list = tailSum list 0;

Example: List Length

Goal: Compute the length of a list.

fun len nil = 0
  | len x = 1 + len(tl x);

Note: This naive implementation is not tail-recursive.

Example: Reversing a List

Goal: Return the reverse of the input list.

1. Naive Implementation (Quadratic Time)

fun rev nil = nil
  | rev (x::xs) = (rev xs) @ [x];

Why this is inefficient: The append operator @ runs in linear time O(n). Since it runs recursively for every element, the total time complexity is Quadratic O(n^2).
Stack Issue: The stack of activation records grows linearly with the list size, risking overflow.

2. Tail Recursive Implementation (Linear Time)

Concept: We take the first element and move it to the accumulator. Effectively, we pick from the front of the source and push to the front of the accumulator.

fun tailRev [] acc = acc
  | tailRev (x::xs) acc = tailRev xs (x::acc);

fun brev l = tailRev l [];

Trace ([1,2,3]):
1. tailRev [1,2,3] []
2. tailRev [2,3] [1]
3. tailRev [3] [2,1]
4. tailRev [] [3,2,1] -> Returns [3,2,1]

Example: Last Element

Goal: Return the last element of a list as a list.

fun lastBox [] = raise Empty
  | lastBox [x] = [x]
  | lastBox (x::xs) = lastBox xs;

Example: K-th Element

Goal: Find the k-th element. Returns an Option type because the element might not exist.

fun get [] _ = NONE
  | get (x::xs) 0 = SOME(x)
  | get (x::xs) k = get xs (k-1);

Example: Consecutive Duplicates

Goal: Eliminate consecutive duplicates. Input: [1, 1, 2, 3, 2, 2] \to [1, 2, 3, 2]

fun nodups [] = []
  | nodups [x] = [x]
  | nodups (x1::x2::xs) =
      if x1 = x2
      then nodups (x2::xs)      (* Skip x1, keep checking from x2 *)
      else x1 :: nodups (x2::xs); (* Keep x1, check from x2 *)

Example: The Packing Problem

Goal: Pack consecutive duplicates into sub-lists. Input: [1,1,2,3,3,4] \to [[1,1], [2], [3,3], [4]]

(* Helper: Takes a list, returns (first_run_of_duplicates, rest_of_list) *)
fun split [] = ([], [])
  | split [x] = ([x], [])
  | split (x::y::ys) =
      if x = y then
          let val (group, rest) = split (y::ys)
          in (x::group, rest) end
      else
          ([x], y::ys);

(* Main Function *)
fun pack [] = []
  | pack l =
      let val (firstGroup, remainingList) = split l
      in firstGroup :: pack remainingList end;