Values are expressions that cannot be further simplified. Thus all values are expressions, but expressions are not always values.
One very powerful feature of functional language is that the contents of a binding cannot be changed. You may shadow a variable but the original variable name in the original environment will always point to the original expression. This is called immutability.
As SML uses pattern-matching to process arguments passed to the function in the form of tuples, it is not necessary to write types for each member of the tuple.
In SML, some functions may accept multiple types of arguments.
There are basic types and compound types. For example, int, bool and unit are basic types. int list or int * bool are compound types. Compound types can be constructed using 3 basic building blocks:
- Each of (product type, and): quite common, such as types of tuples and lists;
- One of (sum type, or): contain a type or not. Often implemented with datatype bindings in SML;
- Self-reference: refer to itself in definition to describe recursive data structures. For example,
int listis defined as a type that contains nothing or anintand anotherint list.
In SML, sometimes you need a value to stand for “there isn’t a value you are looking for” or “there is a value you may be interested”, and they use options.
An option value is either NONE or SOME e where e can be evaluated to v. The type of NONE is \'a option and SOME e t option if e has type t. One can use isSome to see if an option is NONE and valOf to extract value v carried by SOME e.
A way to construct “one-of” types. Syntac-wise, a datatype binding binds the name of the type to a series of constructors.
A constructor is either: a function to create values of the new type or a value of the new type. For example, in
datatype mytype = TwoInts of int * int
| Str of string
| Pizza TwoInts is a function of type int * int -> mytype, Str is a function of type string -> mytype, and Pizza is a value of type mytype.
The datatype expression is essentially a case expression, and the retrieval of the binding is usually done with case expressions.
Lists and options are datatype bindings too, and this is why you can use pattern matching to access list and option values.
One can use the type keyword to give a type a name that is easier to refer to.
In ML, the syntax to construct a pair is (e1, e2). When evaluated it yields (v1, v2). Both e1 and e2 can themselves be pairs, and pairs can be used to construct many other useful data structures such as lists.
By generalizing the concept of pairs we get tuples. But tuples are in fact records with syntactic sugar that saves the trouble of writing field names.
{1=e1, ... n=en} => (e1, ..., en)In ML lists do not have to declare their length when type-checking. Functions dealing with lists are almost always recursive.
In ML, a program is a series of bindings. A function binding is how we define and use functions.
A function binding in ML often look like this:
fun x0 (x1 : t1, ..., xn : tn) = eThis is binding for a function named x0. During type-checking, type of x1 is mapped to t1, …, xn to tn, and x0 to t1 * ... * tn -> t. Because x0 is in the environment, it is possible to recursively call the function. For the whole function binding to type-check, e must have type t.
Evaluation of a function binding is trivial. It just adds x0 to the environment. Function calls are more significant. It finds the expressions corresponding to variables x1, ..., xn, evaluate them to get values v1, ..., vn, and use them to evaluate e (bound to function name x0) to obtain the result e. In the process everything must type-check.
Every function in SML has exactly one argument. The argument can be a tuple. When the function is called, the values in the tuple are extracted using pattern matching.
Let-expressions allows local expressions. Or one can say it defines a special area in the environment where only the e in the let-expression can use. This area can have variables with the same name as those outside the let-expression, and when evaluating the let-expression the outside variables with the same name will be shadowed.
Better still, one can define a local function with let-expression in functional programming, which is a powerful feature.
Difference from the “usual” recursion: tail recursion uses a local helper function. The base case in the non-accumulator version becomes the initial accumulator and the base case is the accumulator version return the accumulator.