Sample Code for this Chapter

So far Standard ML is just a glorified calculator supporting operations of various primitive types and allowing intermediate results to be bound to identifiers.  What makes it possible to do more than just calculate the values of expressions is the possibility to abstract the data from the pattern of the computation so that the same computation may be easily repeated for various data values.  For example, if we calculate the expression 2*(3+4), the data might be the values 2, 3, and 4, and the pattern of calculation might be written in skeletal form as ( ) * ( ( ) + ( )) with "holes" where the data used to be.  We say "might be" because it's not at all clear, given the original expression, what is the data and what is the pattern.  For example, we might regard 2 as the data and ( ) * (3+4) as the pattern, or even regard * and + as the data and 2 ( ) (3 ( ) 4) as the pattern!  What is important here is that the original expression can be recovered by filling the holes with the missing data items and, moreover, different expressions can be obtained by filling the same hole with different data items.  Thus, an expression with a "hole" in it is may be thought of as a function that, when applied to an argument value determines its result by filling the hole with the argument.

This view of functions is similar to our experience from high school algebra.  In elementary algebra we manipulate polynomials such as x2 + 2x + 1 as a kind of expression denoting a real number, but with the variable x representing an unknown quantity.  We may also think of a polynomial as a function of the real numbers: given a real number x, a polynomial determines another real number y computed by some combination of arithmetic operations.  In fact, we sometimes write equations such as y = x2 + 2x + 1 or  y(x) = x2 + 2x + 1 to denote the function determined by the polynomial.  In the univariate case we can get away with just writing the polynomial for the function, but in the multivariate case we must be more careful since we may regard the polynomial x2 + 2xy + y2 as a function of x, a function of y, or a function of both x and y.   In these cases we write f(x) = x2 + 2xy + y2 when x varies and y is held fixed, and g(y) = x2 + 2xy + y2 when y varies for fixed x, and h(x,y) = x2 + 2xy + y2, when both vary jointly.

It is usually left implicit that the variables x and y range over the real numbers, and that f, g, and h are functions mapping real numbers to real numbers.  To be fully explicit, we sometimes write something like

f : R -> R  :  x in R |--> x2 + 2x + 1

to indicate that f is a function on the reals mapping an element x of R to the element x2 + 2x + 1 of R.  This notation has the virtue of separating the binding of the function to a name (f) from the description of its behavior (x in R |--> x2 + 2x + 1).  It also emphasizes that functions are a kind of "value" in mathematics (namely, a set of ordered pairs satisfying the usual uniqueness and existence conditions), and that the variable f is bound to that value (i.e., that set) by the declaration.  This viewpoint is especially important once we consider operators, such as the differential operator, that map functions to functions.  For example, if f is a differentiable function on the real line, the function Df is its first derivative, also a function on the real line.  In the case of the function fdefined above the function Df sends x in R to 2x+2, another function defined on the real line.

The treatment of functions in Standard ML is very similar to our mathematical experience, except that we stress the algorithmic aspects of functions (how they determine values from arguments), as well as the extensional aspects (what they compute).  Just as in mathematics, a function in Standard ML is a kind of value, namely a value of function type.  A function type has the form typ->typ', where typ is the domain type (the type of arguments to the function), and typ' is the range type (the type of results).  We compute with a function by applying it to an argument value of its domain type and calculating the result value of its range type.  The values of function type are the lambda expressions of the form fn var : typ => exp; the variable var is called the parameter, and the expression exp is called its body. It has type typ->typ', where exp has type typ' under the assumption that var has type typ.  The result of applying such a function to an argument value val is determined by temporarily adding the binding val var = val to the environment, and evaluating exp to a value val'.   The temporary binding is then removed, and the result value, val', is returned as the value of the application.

For example, sqrt is a (built-in) function of type real->real that may be applied to a real number to obtain its square root; for example, the expression sqrt 2.0 evaluates to 1.414....  Observe that function application is written by juxtaposition: we simply write the argument next to the function.  We can, if we wish, parenthesize the argument, writing sqrt 2.0 for the sake of clarity; this is especially useful for expressions like sqrt (sqrt 2.0).  The function sqrt is special in that it is a built-in, or primitive, operation of the language.  We may also define functions as templates using a notation similar to that introduced above.  The fourth root function on the reals may be written in Standard ML using lambda notation as follows:

fn x : real => sqrt (sqrt x)

Notice that we don't (at this stage) give this function a name, rather we simply define its behavior by a template specifying how it calculates its result from its argument.  This template defines a function of type real->real since it maps real numbers to real numbers.  It may be applied to an argument by writing, for example,

(fn x : real => sqrt (sqrt x)) (4.0)

to calculate the fourth root of 4.0.  The calculation proceeds by binding the variable x to the argument 4.0, then evaluating the expression sqrt (sqrt x) in the presence of this binding.  When evaluation completes, we drop the binding of x from the environment, since it is no longer needed.   (There is a subtle issue about the temporary binding of x that we will return to later.)

We may give a function a name using the declaration forms introduced in the previous chapter.  For example, we may bind the fourth root function to the identifer fourthroot as follows:

val fourthroot : real -> real = (fn x : real => sqrt (sqrt x))

We may then write fourthroot 4.0 to compute the fourth root of 4.0.   This notation quickly becomes tiresome to write down, so Standard ML provides a special form of function binding that alleviates the burden.  In practice we write

fun fourthroot (x:real):real = sqrt (sqrt x)

rather than the more verbose val declaration above.  But it has (almost) precisely the same meaning: the fun binding binds a lambda expression to an identifier.

These examples raise a few additional points about functions in Standard ML.   First of all, the general form of an application expression is exp exp', where exp is an expression that evaluates to a function, and exp' is an expression that evaluates to its argument.  Standard ML is a call-by-value language: the argument to a function is evaluated before the function is applied.   (You may reasonably wonder what is the alternative.  In a so-called call-by-name language the argument is passed in unevaluated form to the function, and is only evaluated if the function requires it to be.  This behavior is expressible in Standard ML by other means, which we shall return to later.)  Thus, when to evaluate an expression such as fourthroot 2.0, we proceed as follows:

  1. Evaluate fourthroot to the function value fn x : real => sqrt (sqrt x).
  2. Evaluate the argument 2.0 to its value 2.0
  3. Bind x to the value 2.0.
  4. Evaluate sqrt (sqrt x) by a subsidiary calculation to 1.189....
    a. Evaluate sqrt to a function value (in this case the primitive square root function).
    b. Evaluate the argument expression (sqrt x) to its value, 1.414... (by a subsidiary calculation).
        i. Evaluate sqrt to a function value (in this case the primitive square root function).
        ii. Evaluate x to its value, 2.0.
        iii. Compute the square root of 2.0, yielding 1.414....
    c. Compute the square root of  1.414..., yielding 1.189....
  5. Drop the binding for the variable x.

Second of all, notice that we evaluate both the function and argument positions of an application expression --- both the function and argument are arbitrary expressions yielding values of the appropriate type.  The value of the function position must be a value of function type, either a primitive function or a lambda expression, and the value of the argument position must be a value of the domain type of the function.   In this case the result value (if any) will be of the range type of the function.   The point here is that functions are first-class values, meaning that they may be obtained as the value of an arbitrary expression; we are not limited to applying only named functions, but rather may compute "new" functions on the fly and apply these to arguments.  This is a source of considerable expressive power, as we shall see later in these notes.

So far, we've only considered functions on the real numbers, but we may also define functions of other types.  For example,

fun pal (s:string):string = s ^ (rev s)
fun double (n:int):int = n + n
fun square (n:int):int = n * n
fun halve (n:int):int = n div 2
fun is_even (n:int):bool = (n mod 2 = 0)

Thus pal "ot" evaluates to the string "otto", and is_even 4 evaluates to true.

There are a few subtleties that we must be aware of when thinking about functions.   The first is: the name of the parameter is not important.   Consequently, it may be systematically renamed without changing the meaning of the function, provided that we don't rename it in such a way as to clash with some other name that is currently in scope.  An example will illustrate the point:

fun f(x:real):real = x+x
fun g(y:real):real = y+y

These two functions are completely equivalent; they differ only in the name of the parameter (in one case, x, in the other, y).  The second subtlety is the static scope principle: a use of a variable refers to the nearest enclosing binding of that variable in the text of the program.  Just as one value binding can shadow another, so can parameters of functions shadow value bindings (or other parameters).  Here's an example:

val x:real = 2.0
fun h(x:real):real = x+x
fun i(y:real):real = x+y

The first function, h, introduces a parameter x that shadows the outer value binding; the value binding has no effect on the meaning of the function h.   The second function, i, makes use of the variable x introduced by the val binding; from within the body of i this is the nearest enclosing binding occurrence of x in the program.  (The parameter x of the function h does not enclose the definition of the function i.)  The use of x within the function i introduces some constraints on the possible renamings of the parameter of i.   Specifically, we may certainly rename y to z without changing the meaning of the function i, but we may not rename y to x without changing the meaning completely.  That is, the function j has the same meaning as the function i, but the function k has a different meaning:

fun j(z:real):real = x+z
fun k(x:real):real = x+x

While these may seem like minor technical issues, it is essential that you master these ideas now to avoid confusion later on!

We close this section with a brief summary of function types:

Type name: typ->typ'
primitives, fn var : typ => exp
Operations: application exp exp'

Once we develop some additional machinery we will return to the function type to discuss recursive functions.

Sample Code for this Chapter