Home
Blog Tags

Hello SML!

Wednesday, Sep 2, 2020
Functional

Standard ML is a functional language. It's data is immutable and thus assignments are not allowed. It is strongly typed, meaning type of all values and variables can be determined at compile time. These features are in stark contrast with JavaScript that I have been learning lately and thus I thought to spend some time learning it.

Learning a new language entails learning:

  1. syntax of its programming constructs: For example, how do you write a conditional?
  2. symantics of those constructs: That is, what rules are used to type-check (if it has types) its constructs and what rules are used to evaluate those constructs.
  3. idioms: There could be multiple ways to do a certain task, but which way is better?
  4. libraries: What pre-existing code can I use without re-inventing? for example, file I/O
  5. Tooling: What tooling is available, for example, REPLs, debuggers, compilers etc.

Since it usually is a long shot to do all at once, it seems more effective to just focus on learning syntax and symantics first.

Bindings

An ML program is made up of bindings. Each binding is first checked for syntax which (if correct) is followed by type-checking the binding following which (if it type-checks) it is finally evaluated. We will start with two types of bindings:

Variable Bindings

  1. Syntax: val x = e;. Here, x is the variable name and e is an expression. The expression may contain sub-expressions, which may further contain more sub-expressions and so on.
  2. Type-check: All bindings preceding the current one have a type. This mapping of var : type is stored in this thing called static environment. Using this information, type of expression e is found, which becomes the type of binding x. Static environment is updated with this binding.
  3. Evaluation: Expression e is evaluated, using values of preceding variables (this variable -> value mapping exists in this thing called dynamic environment) to a value v, and this becomes the value of the binding. Dynamic environment is updated with this binding.
  4. Example: Here, the expression is 2+3, which has a type int because 2 and 3 have type int. Static environment is updated with x: int and then expression is evaluated. This expression does not depend on any preceding bindings and evaluated to 5. Dynamic envionment is updated with x -> 5.
- val x = 2 + 3;
val x = 5 : int
-

Function Bindings

  1. Syntax: fun x0(x1: t1, ..., xn: tn) = e;. This function, x0, has n parameters, x1…xn that have type t1…tn and e is an expression.
  2. Type-check: A new static environment is created with preceding bindings and x1: t1, …, xn: tn and x0: t1*…*tn->t additional bindings. Using this static environment, type of e is determined which must be of type t for this function binding to type-check. ML's *type inference* does this magic job. After this, x0 is added to the top-level static environment.
  3. Evaluation: x0 simply evaluates to x0 itself, which is added to the dynamic environment.
  4. Example:
- fun square_n(n: int) = n * n;
val square_n = fn : int -> int
-

More Expressions

Besides the expressions involving binary operators (e1 / e2, e1 mod e2 or e1 <> e2), following three expressions will help us write more useful programs:

Conditional Expression

  1. Syntax: if e1 then e2 else e3;
  2. Type-check: Under the current static environment if e1 is of type bool and e2 and e3 have same type, then the type of whole expression is the type of e2 (and e3).
  3. Evaluation: Under the current dynamic environment, if e1 evaluates to true then e2 is evaluated and its value is the value of the whole conditional expression. If e1 evaluates to false then e3 is evaluated and its value is the value of the whole conditional expression.
  4. Example: In ML, ~ is used for negation.
- if x > 0 then x else ~x;
val it = 5 : int
-

Function Call

After we declare a function binding, we can use it in a function call expression to evaluate it.

  1. Syntax: e0(e1, ..., en)
  2. Type Check: e0 must have a type t1*…*tn->t and e1,…, en have type t1,…,tn respectively. Then the whole expression has type t.
  3. Evaluation: Using the environment at the point of call, e1,…, en are evaluated to values v1,…, vn. Also e0 is evaluated to v0, which must be a function. Then the dynamic environment at the point where the function was defined is extended with the function's arguments mapped to v1,…,vn, using which the function's body expression e is evaluated. This mechanism is called lexical scoping.
  4. Example: Here we use our previous function binding to square a number. It only has one argument which is evaluated to 5 and then the function body is evaluated.
- square_n(2+3);
val it = 25 : int
-

Let Expression

Let expressions allow you to create bindings with local scope.

  1. Syntax: let b1 b2 ... bn in e end. Here b1,…, bn are local bindings. Note that these could be variable bindings or function bindings.
  2. Type-check: Scope (where the binding can be used) of each binding in a let expression is subsequent bindings and its body e. Thus b2 can use b1, b3 can use b1 and b2 while e can use b1,…,bn (in addition to other bindings in the static environment). Variable and function binding type-check rules apply as described above. Type of e is the type of entire let expression.
  3. Evaluation: Each binding is sequentially evaluated to create a larger dynamic environment for the subsequent binding. e is finally evaluated using values of all previous bindings (in addition to other bindings in the dynamic environment leading up to let expression call). The value of e is the value of entire let expression.
  4. Example:
- let val a = 5 in a+1 end;
val it = 6 : int
-

Compound Data

One can use atomic data like integers (2, ~5, etc.), reals (3.14, 6.23e23 etc.), booleans (true, false), or strings (“hello world”), to build more complex data structures. We will start with pairs, tuples and lists:

Pairs

  1. Syntax: (e1, e2)
  2. Type-check: if e1 has a type t1 and e2 has a a type t2, then the pair has a type t1*t2. Note that t1 and t2 can be different types.
  3. Evaluation: if e1 has a value v1 and e2 has a value v2, then the pair has a value (v1, v2).
  4. Example: Note that pair can contain pairs and so on.
- (3, 3.14);
val it = (3,3.14) : int * real
- ((true, false), (1, 1));
val it = ((true,false),(1,1)) : (bool * bool) *  (int * int)
-
  1. Access: #1 pr will give first component of the pair pr and #2 pr will give second component.

Tuples

Tuples is simply pair extended to more than two components. All the above rules apply otherwise.

Lists

Lists can contain any number of components and length is usually unknown at compile time. Thus they can contain components of only one type.

  1. Syntax: [e1, ..., en]. This is a list containing n elements. Usually lists are created dynamically by consing an element to the front using e1 :: e2 where e2 is a list of type t and e1 is an element of type t.
  2. Type-check: if t is the type of list elements, then the list has type t list
  3. Evaluation: If e1,…, en evaluates to v1,…, vn then the value of list is $[v1,…, vn]$
  4. Example: Here, 1 is consed to the front of the list of two integers.
- 1 :: [2, 3];
val it = [1,2,3] : int list
-
  1. Access: null l evaluates to true for empty list and false otherwise. hd l gives the first elements and tl l gives the list excluding the first element.
- hd [1, 2, 3];
val it = 1 : int
- tl [1, 2, 3];
val it = [2,3] : int list
-

Options

Option is useful when a container either contains nothing or only one thing.

  1. Syntax: NONE is an options containing nothing. SOME e is an option containing value of expression e.
  2. Type-check: NONE has type 'a option while SOME e has type t option where t is the type of e.
  3. Evaluation: SOME e has value v if e evaluates to v.
  4. Example:
- NONE;
val it = NONE : 'a option
- SOME true;
val it = SOME true : bool option
-
  1. Access: isSome o evaluates to false if o is NONE and true otherwise. valOf o evaluates to value carried by SOME option.
- isSome NONE;
val it = false : bool
- valOf (SOME 2);
val it = 2 : int
-