Note to instructors: I don't expect you to necessarily get through all of this material. Go only as fast as the students can absorb it, and use more examples as necessary. Remind students that they can read the notes online and come to consulting hours for additional help. Make sure the students know that there's extra material that you didn't cover.
Today we're going to start by introducing a few imperative features of SML that you will need on the first assignment (which will be given out tomorrow). Up to this point, all of the expressions we've used have been purely functional. This means that evaluating an expression does not modify the state of the machine, so any expression may be replaced by its value without changing the result of a program.
Imperative language features modify the state of the machine. Our first imperative feature is the function print, which prints a string. For example, we can write
- print("Hello, world!\n");
Hello, world!
val it = () : unit
and the compiler prints the usual greeting. Notice that the compiler treats escape characters just as Java does. Notice also that print returned the 0-tuple, called unit, which is the only value of type unit. The function print actually has type "string -> unit". The type unit is very much like the type void in Java; a function is defined to return unit when its only purpose is to cause a side effect. You will have functions like this in your first assignment because your program will be drawing a fractal, not just computing a value. The print function is not functional because replacing our print expression by its value (unit) does not yield an equivalent program.
Once you have functions that modify the state of the machine, you need a way to string them together. In SML, this is done by separating expressions with semicolons. For example, you can write
let val magicnumber : int = 42 in print("The magic number is "); print(Int.toString(magicnumber)); print("\n"); square(magicnumber) end
This expression evaluates the three print expressions in sequence, throwing away their return values, and then evaluates the square expression, returning the result of the final expression as the value of the whole let expression. In general, writing
( e1 ; e2 ; ... ; en )
causes the sequential evaluation of e1, e2, ..., en. (The parentheses may be omitted when the sequence appears in the body of a let expression as above.) The value of the expression is the value of en; the values of the other expressions are discarded. Notice that the semicolons are expression separators, not statement terminators as in Java; do not put a semicolon after the final expression! Also, the semicolons are very different from the semicolons we've used to terminate input to the interactive compiler. The top-level semicolons terminate sequences of declarations or expressions and tell the compiler to process the current input. Sequencing semicolons occur only between expressions inside parentheses or inside a let expression and therefore cannot terminate an expression or declaration.
If magicnumber is defined elsewhere, we could have written the above expression as
( print("The magic number is " ^ Int.toString(magicnumber) ^ "\n"; square(magicnumber) )
Notice that without imperative language features, sequencing is not needed because expressions only compute values, and sequences cause those values to be thrown away.
Functions are values just like any other value in SML. What does that mean exactly? This means that we can pass functions around as arguments to other functions, that we can store functions in data structures, that we can return functions as a result from other functions. The full implication of this will not hit you until later, but believe us, it will.
Let us look at why it is useful to have higher-order functions. The first reason is that it allows you to write more general code, hence more reusable code. As a running example, consider functions double and square on integers:
fun double (x:int):int = 2 * x fun square (x:int):int = x * x
Let us now come up with a function to quadruple a number. We could do it directly, but for utterly twisted motives decide to use the function double above:
fun quad (x:int):int = double (double (x))
Straightforward enough. What about a function to raise an integer to the fourth power?
fun fourth (x:int):int = square (square (x))
There is a totally unexpected and unplanned similarity <yeah... right.... k> between these two functions: what they do is apply a given function twice to a value. By passing in the function to apply twice as an argument, we can reuse code:
fun apply_twice (f:int -> int, x:int):int = f (f (x))
Using this, we can write:
fun quad (x:int):int = apply_twice (double,x) fun fourth (x:int):int = apply_twice (square,x)
The advantage is that the similarity between these two functions has been made manifest. Doing this is very helpful. If someone comes up with an improved version of apply_twice, then every function that uses it profits from the improvement.
The function apply_twice is a so-called higher-order function: it is a function from functions to other values. Notice the type of apply_twice is ((int -> int) * int) -> int
In order not to pollute the top level namespace, it can be useful to locally define the function to pass in as an argument. For example:
fun fourth (x:int):int = let fun square (y:int):int = y * y in apply_twice (square,x) end
However, it seems silly to define and name a function simply to pass it in as an argument to another function. After all, all we really care about is that apply_twice get a function that double its argument. So let's do that, using new notation:
fun fourth (x:int):int = apply_twice (fn (y:int) => y*y,x)
We introduce a new expression to denote "a function that expects such and such argument and returning such an expression":
e ::= ... | fn id:t => e
The type makes things actually clearer. What is the type of fn (y:int) => y*y?
Answer: int -> int
The declaration val square : int -> int = fn (y:int) => y*y has the same effect as fun square (y:int):int = y * y.
The fn expression creates an anonymous function, that is a function without a name.
Anonymous functions are useful for creating functions to pass as arguments to other functions, but are also useful for writing functions that return other functions! Let us revisit the apply_twice function. We now write a function twice which takes a function as an argument and return a new function that applies the original function twice:
fun twice (f:int -> int):int -> int = fn (x:int) => f (f (x))
This function takes a function f (of type int -> int) as an argument, and returns a value fn (x:int) => f (f (x)), which is a function which when applied to an argument applies f twice to that argument. Thus, we can write
val fourth = twice (fn (x:int) => x * x) val quad = twice (fn (x:int) => 2 * x)
and trying to evaluate fourth (3) does indeed result in 81.
Here are more examples of useful higher-order functions that we will leave you to ponder (and try out at home):
fun compose (f:int -> int, g:int -> int):int -> int = fn (x:int) => f (g (x))
fun ntimes (f:int -> int,n:int):int -> int = if (n=0) then (fn (x:int) => x) else compose (f, ntimes (f,n-1))