Learning a new language entails learning:
- syntax of its programming constructs: For example, how do you write a conditional?
- 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.
- idioms: There could be multiple ways to do a certain task, but which way is better?
- libraries: What pre-existing code can I use without re-inventing? for example, file I/O
- 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.
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:
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.
- 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
eis found, which becomes the type of binding
x. Static environment is updated with this binding.
- Evaluation: Expression
eis 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.
- 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 -
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.
- 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.
- Evaluation: x0 simply evaluates to x0 itself, which is added to the dynamic environment.
- fun square_n(n: int) = n * n; val square_n = fn : int -> int -
Besides the expressions involving binary operators (e1 / e2, e1 mod e2 or e1 <> e2), following three expressions will help us write more useful programs:
if e1 then e2 else e3;
- 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).
- Evaluation: Under the current dynamic environment, if e1 evaluates to
truethen e2 is evaluated and its value is the value of the whole conditional expression. If e1 evaluates to
falsethen e3 is evaluated and its value is the value of the whole conditional expression.
- Example: In ML,
~is used for negation.
- if x > 0 then x else ~x; val it = 5 : int -
After we declare a function binding, we can use it in a function call expression to evaluate it.
e0(e1, ..., en)
- 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.
- 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.
- 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 expressions allow you to create bindings with local scope.
let b1 b2 ... bn in e end. Here b1,…, bn are local bindings. Note that these could be variable bindings or function bindings.
- 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.
- 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.
- let val a = 5 in a+1 end; val it = 6 : int -
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:
- 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.
- Evaluation: if e1 has a value v1 and e2 has a value v2, then the pair has a value (v1, v2).
- 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 prwill give first component of the pair pr and
#2 prwill give second component.
Tuples is simply pair extended to more than two components. All the above rules apply otherwise.
Lists can contain any number of components and length is usually unknown at compile time. Thus they can contain components of only one type.
[e1, ..., en]. This is a list containing n elements. Usually lists are created dynamically by consing an element to the front using
e1 :: e2where e2 is a list of type t and e1 is an element of type t.
- Type-check: if t is the type of list elements, then the list has type
- Evaluation: If e1,…, en evaluates to v1,…, vn then the value of list is $[v1,…, vn]$
- Example: Here, 1 is consed to the front of the list of two integers.
- 1 :: [2, 3]; val it = [1,2,3] : int list -
null levaluates to
truefor empty list and
hd lgives the first elements and
tl lgives the list excluding the first element.
- hd [1, 2, 3]; val it = 1 : int - tl [1, 2, 3]; val it = [2,3] : int list -
Option is useful when a container either contains nothing or only one thing.
NONEis an options containing nothing.
SOME eis an option containing value of expression e.
SOME ehas type
t optionwhere t is the type of e.
SOME ehas value v if e evaluates to v.
- NONE; val it = NONE : 'a option - SOME true; val it = SOME true : bool option -
isSome oevaluates to
falseif o is NONE and true otherwise.
valOf oevaluates to value carried by SOME option.
- isSome NONE; val it = false : bool - valOf (SOME 2); val it = 2 : int -