ML Basics

In this document we introduce the basic concepts of the ML functional language.

We note that anything you type into the interpreter (or in an ML program) will be either:

an expression, which the interpreter will (try to) evaluate, giving an answer, or
a definition, recording something for use later on

In what follows we look at some expressions and at two types of definitions: value definitions and function definitions.

1. Expressions

The basic purpose of a top level interpreter for ML (or most other functional languages) is to evaluate expressions.

In general terms, an expression would be something like:

Some constant value like 4, "a string"
A constant name to which we have previously defined a value
Some appropriate operator applied to expressions of the relevant type, e.g. i + 1
A function applied to some arguments, e.g. fact 1

Basically, given a value for any relevant variables, an interpreter should be able to take an expression, work it out, and print out the value that results.

To each expression we can associate a type to which it belongs; the basic types in ML are:

int

the type of integers, which includes positive and negative (note the sign character ~) whole numbers, such as 4, 56, 0, ~2, and ~12345678.

The basic operators are + for addition, - for subtraction, * for multiplication, div for division and mod for remainder after division.

The comparison operators <, >, <= and >= work as expected.

The function real converts an integer to a real.

real

the floating point numbers, being numbers with a decimal point, such as 2.5, 3.14, ~0.4, 3E5, and ~3.5E~7.

The basic operators include +, -, *, and / is for division, and the comparison operators are the same as for int; however expressions cannot contain mixed data types.

The function trunc truncates a real to an integer, and the function round rounds a real to the closest integer.

bool

the type of Booleans, including the constants true and false

The main operators are andalso for conjunction, orelse for disjunction and not for negation. Both andalso and orelse use "short circuit evaluation", in that they only evaluate their second operand if necessary.

string

the type of strings involving some sequence of characters between quotes, such as "a string"

The main operator is ^ which is used for string concatenation.

In addition, each type supports the two operators to check for equality after evaluation: = for equality, and <> for inequality; however types cannot be mixed for comparison.

1.1 Evaluating Expressions

To evaluate an expression in ML, simply type it in followed by a semi-colon.

Note: In what follows we assume that the interpreter prompt is a "-"; the interpreter's response is preceded by ">".

Thus we might try typing:

- 3+4;

The interpreter then responds as follows:

> val it = 7 : int

The interpreter responds with its most recently evaluated expression; in this case it is telling us that the value of this expression is 7, which is of type int. The value is also represented by the constant "it", thus the constant "it" can be used in the next expression.

- it + 2;
> val it = 9 : int

Here are some more examples of ML's expression evaluation:

- 3+4*6;
> val it = 27 : int

- (3+4)*6;
> val it = 42 : int

- 5 div 2;
> val it = 2 : int

- 5 mod 2;
> val it = 1 : int

- 65.0 / 4.0;
> val it = 16.25 : real

- 4 > 1+2;
> val it = true : bool

- (3>6) orelse (3>2);
> val it = true : bool

- (3>6) andalso (3>2);
> val it = false : bool

- "abc" ^ "def";
> val it = "abcdef" : string

- "ab" ^ "DE" ^ "fg";
> val it = "abDEfg" : string

If we use an operator with the wrong type of expression, the interpreter responds with a suitable error message. For example, we might get:

- 9 / 4;
! Toplevel input:
! 9 / 4;
! ^
! Type clash: expression of type
!   int
! cannot have type
!   real

1.2 Conditional Evaluation

Expressions can be evaluated conditionally using the if ... then ... else ... construct; for example:

- if (3>2) then 4 else 5;
> val it = 4 : int

Note that:

The condition must always be of type bool
The expressions may be of any type, but both must have the same type
There is always an else ... part; since this is an expression we must always have something to evaluate if the condition is false.

1.3 The Unit Type

There is one special type called unit, which only has a single element, written (). Thus:

- ();
> val it = () : unit

There are no associated operators.

We use the unit type when we are interested in some expression for its side-effects, rather than for its value - a common example of this is input/output.

Every function must take some arguments and return a result: specifying the unit type for these indicates that we're not really interested in them (e.g. a function that has return type unit is a little like a function with return type void in C).

While the unit type is common to many functional languages, its use should be taken as an indication that we are departing from a purely functional style of programming.

2. Definitions

Definitions in ML allow us to associate names with expressions for use in later expressions; in this section we examine value (i.e. constant) and function definitions.

2.1 Value Definitions (Constants)

In order to improve the readability of our code we can declare (global) constants; the format is:

the keyword val
The name of the constant
An "=" symbol
An expression

For example:

- val pi = 22.0 / 7.0;
> val pi = 3.14285714286 : val pi : real

The only change in the interpreter's reaction is to acknowledge that it now has a different name for this value.

These constants can them be used in later expressions:

- pi * 2.0;
> val pi = 6.28571428571 : real

2.2 Functions

Functions in ML consist of:

The keyword fun
The name of the function
The names of the parameters (and, optionally, their types)
An "=" symbol
The body of the function

A function body is simply an expression; there is no need to explicitly indicate the value to be returned, since it is taken to be the value of this expression.

As an example, the following function simply adds 1 to its argument:

- fun succ n = n+1;
> val succ = fn : int -> int

Note the differences in the interpreter's response this time:

Since a function has no basic "value" as such, it just prints out fn
The type of a function is written using a "->" to separate the parameter type from the return type; thus int -> int is a function whose parameter has type int and which returns a value of type int.

To apply this function we simply give its name followed by the argument, thus:

- succ 5;
> val it = 6 : int

We can also apply the function using parenthesis around arguments, thus:

- succ(10);
> val it = 11 : int

2.2.1 Currying

Suppose we wanted to define a multiply function that simply uses addition. Calling this function mult, we might write:

- fun mult x y = if y=0 then 0 else x + (mult x (y-1));
> val mult = fn : int -> int -> int

Here, x and y are the parameters, and we are making use of the fact that x * y = x + x * (y-1).

Remember that we are using the "functional" style when we apply a function to its arguments in the case of the application of mult to the arguments x and y-1. In a procedural language we might have written mult(x,y-1), but in a functional language we simply write mult x (y-1).

Note that function application binds to the left, so that if we write mult x y-1 it would actually be interpreted as (mult x y) - 1, hence the extra parenthesis.

The second point to note is the type of the function: int -> int -> int. This is the type of a function that takes a parameter of type int and returns something of type int -> int. Thus

- mult 2;
> val it = fn : int  -> int

Even though we have not given the mult function all of its arguments, we still do not get an error! What's going on here is a process of "partial application" of the function known as currying. When the interpreter sees that we have only given one argument, it is quite happy to carry out the normal substitution, and wait for the second argument.

Thus mult 2 is the same as the function double defined as:

- fun double y = if (y=0) then 0 else 2 + (mult 2 (y-1));
> val double = fn : int -> int

This is a function which, given any y, will evaluate to 2 * y, and is indeed of type int -> int.

Whenever we define a function with more than one parameter, we can always supply it with less arguments than necessary to get specialized versions.

So when we write e.g. mult 2 3, what effectively happens is that:

We apply mult to 2 to get a function "(mult 2)" of type int -> int
We then apply (mult 2) to 3 to get a result of type int

Thus mult 2 3 could also be written as (mult 2) 3 - we don't need to write down all the extra brackets since function application always associates to the left.

2.2.2 Calling Functions

The syntax for calling functions is different to that of an imperative language. It is important to remember the following:

If you want to call a function f with two arguments, say a and b, you write:
```
  f a b
```
If either of the arguments is a compound expression (like a+1, etc.) you should put it in brackets to make sure its evaluation doesn't conflict with anything else; eg:
```
  f (a+1) (b mod 2)
```
As a corollary of this, if the result of the function call is going to be supplied as an argument to some other function, it's a good idea to bracket the whole thing, e.g.:
```
  (f a b)
```

What you do *not* do is to try and bracket it as you do with an imperative language. If you write "f (a b)" then you are telling ML to apply the function a to its argument b, and apply the function f to the result of this evaluation. If this was not the intended meaning, then you will get a type error, since the (presumably) constant-valued a is being treated like a function.

You also do *not* try to bracket it and add the comma. If you write "f(a,b)" then you are telling ML to apply the function f to a single argument, the "pair" (a,b).

3. "Side-Effect Free" Programming

The advantage of this functional style of programming is that the functions we write have no "side-effects". Thus when we use an expression we are only interested in its value (and for functions, in its return value); nothing else can have any effect on the rest of our program. This property is known as referential transparency - basically, if we take an expression anywhere in a program, and replace it with another expression that gives the same value, we will not have changed the overall result of the program.

Imperative languages have many features which violate referential transparency:

Global Variables: If the evaluation of a block of code changes some global variable, then its effects is not limited to the value it returns, and simply replacing the function with that value would give us a different program
Assignments: Assignment statements mean that the effect of executing a block of code persist after it has been executed since it may have updated the value of one or more variables, on which other pieces of code depend
Value-Result Parameters: In a functional language we only pass parameters by value; after we return from a function call the value of the arguments has not been changed in any way. Imperative languages which have call by value-result, or reference parameters, are not referentially transparent
Pointers: Languages which allow pointer arithmetic effectively allow you to "step outside" the type safeguards of the language, and work with arbitrary pieces of memory. This kind of program, which necessary for certain low-level operations, can be exceptionally difficult to debug, since it complicates the task of keeping track of the effect of one piece of code on the rest of the program.

Thus, when you are looking at some code from an imperative programming language with a view to changing it (or simply understanding what it does), you have to take all of these side-effects into account. In a functional program you need only worry about the overall result of the expression; once this does not change, any alteration you make can have no adverse effect on the operation of rest of your program.

This side-effect free style of programming does take some getting used to, particularly if you are used to having updateable variables (and using assignment statements), but pays substantial dividends when it comes to debugging and maintaining your code.

The important thing to remember is that:

When you are looking at some piece of a functional program, any variable that appears there will have one, and only one, value during the current evaluation of this piece of code.

3.1 Recursive Functions

When we remove assignments and other forms of updatable variables from a programming language, there are a few other casualties: in particular, the iterative constructs like while and for loops no longer make sense, since we cannot change the variables that might appear in the conditions that control the iteration.

Hence the main way of implementing iteration in a functional language is through the use of recursive functions.

3.2 Caveat: Input and Output

There is one main exception to ML's exclusion of side-effects - input and output. Whenever we read from the input or write to the output we are changing something outside the program, and so this type of operation necessarily has side effects that cannot be captured entirely in terms of the return value of the expression.

For example, the function in ML to print a string is called print and has type string -> unit. Normally something which has return type unit effectively returns no information so, in terms of referential transparency, this function appears to do nothing. The real situation of course is that it does nothing other than printing its argument; for example:

- print "Hi there!\n";
Hi there!
> val it = () : unit

The evaluation of the function simply yields (); the string that is printed on screen is a side-effect.

Similarly, function that we define which contains just the print function will also return nothing:

- fun howdy name = print ("Hello " ^ name ^ "\n");  
>val howdy = fn : string -> unit

- howdy "John";
Hello John
> val it = () : unit

Performing output (and input) in ML is an exception to the rule of referential transparency; this is somewhat to be expected, since the input and output environments that ML is dealing with are outside the scope of the interpreter.

3.3 Sequencing Expressions

A number of expressions may be evaluated in sequence by separating them by semi-colons (and, in the interpreter, surrounding them with parenthesis so that the semi-colon is not mistaken for the end of the input). The value of a sequence of expressions is the value of the last expression.

Thus we might write:

- ("abc"; 1; true);
> val it = true : bool

With ordinary expressions sequencing does not have much use, since the values of all expressions other than the first are effectively lost. Thus sequencing is mainly used when some expressions in the sequence have side-effects, as is the case with input and output.

An example of this might be the simple function:

- fun printPlus n =
    if (n=0) then print "\n"
    else (print "+"; printPlus (n-1));
> val printPlus = fn : int -> unit

- printPlus 4;
++++
> val it = () : unit

Since print expressions are probably the only non-pure expressions you'll be using, it is worth noting this simple rule of thumb:

Only use expression-sequencing when the first expression is a print expression

For any two expressions e1 and e2, if you write "(e1 ; e2)" then you are telling ML to evaluate and then throw away the value of e1. Thus, if e1 is anything other than a print expression (which we only use for its side-effect), you're probably doing something wrong!

4. Comments

Comments are an essential part of readable and maintainable programs. In ML a comment is any text enclosed between "(*" and a matching "*)".

Written by James Power
Revised September 2010 by M. van Bommel