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 *x ^{2} + 2x + 1* as a
kind of expression denoting a real number, but with the variable

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 |--> x^{2}+ 2x + 1

to indicate that *f* is a function on the reals mapping an element *x* of
*R* to the element *x ^{2} + 2x + 1 *of

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:

- Evaluate
`fourthroot`

to the function value`fn x : real => sqrt (sqrt x)`

. - Evaluate the argument
`2.0`

to its value`2.0`

- Bind
`x`

to the value`2.0`

. - 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...`

. - 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,

Values:`fn`

var`:`

typ`=>`

exp

Operations:applicationexp exp'

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