Functions

By Brandon Wu, May 2020

Functions are a familiar concept in programming. In most languages, functions seem to capture a notion of a list of instructions to be carried out, with each invocation of the function resulting in another round of executing its instructions. In this class, however, we will take another perspective on functions - one that identifies the function more with the values that it outputs than the instructions that it executes.

What is a Function?

What is a function? To most seasoned programmers, the definition given in the above section seems to be the most obvious. A function (or subroutine) is simply identified with the instructions that it executes, which have some effect on the state of the program as a whole, such as incrementing some variable, or setting some flag.

Before most programmers were programmers, however, they had a different notion of a function. To a mathematician, a function is something else entirely. Instead of being an algorithmic sequence of instructions, a function is simply an entity that maps inputs to outputs - for example, (f(x) = x + 1). Something rather notable is that mathematical functions are pure - given the same input, they always return the same output. So while it is a valid question in programming to ask how a function's behavior changes over time, this is a nonsensical question in terms of mathematical functions.

To be more concrete, let us consider a Python program.

x = 0
def f(y):
    x += 1
    return x + y

This program instantiates a variable x outside the scope of the function f (which takes a single argument y), and the behavior of f is to increment the value of x, then return the sum of x and y. What we would find is that the first time that we run f(0), for instance, we obtain 1. The second time that we run f(0), it will return 2, and so on and so forth. We cannot even say that f(0) = f(0)! The output behavior of this function changes every time that it is run. This makes it difficult to reason about the function - in order to do so, we must know the number of times that it has been called before, at a given step in the program. While this is a fairly tame example, this problem only compounds with more complicated functions.

Clearly, this function is impure. Can we do better?

Function Types and Function Application

So far we have seen basic types such as int and string, among others. Functions allow us to compose types in new ways.

In SML, we denote the type of a function that has input type t1 and output type t2 (for some arbitrary, fixed t1 and t2) to be t1 -> t2. By SML's strict typing rules, functions of type t1 -> t2 can only take in inputs of type t1 and return outputs of type t2, for any types t1 and t2. Additionally, we write e1 e2 for the expression consisting of the function e1 being given as input the expression e2 (so we may write the mathematical function (f(x)) instead as f x).

[APP] An expression e1 e2 has type t2 if and only if e1 : t1 -> t2 and e2 : t1.

We call the above rule [APP] since it concerns the types of expressions during function application, or the process of applying a function to an argument.

Note that a function must always have type t1 -> t2 (for some types t1 and t2, though t1 and t2 may be complicated types in their own right). As such, all functions in SML can only take in one input - though the input type t1 may be one that "contains" multiple values. For instance, a function may have type int * int -> bool. For such a function, it takes in only one argument (a tuple containing two integers).

Functions in SML

We can declare a function with the fun keyword.

fun fact (0 : int) : int = 1
  | fact (n : int) : int = n * fact (n - 1)

The above example serves to initialize a function that computes the factorial function, and then bind it to the identifier fact. Function declarations create a closure which includes all bound variables in the scope of the function when it was declared, so the behavior of fact will always be as if it was in the same environment as when it was first declared. As such, we can also declare functions such as:

val x = 1
fun addX (n : int) : int = n + x
val x = 2

When addX is bound, it is bound in a closure that includes the binding of the value 1 to the identifier x (we may denote this as [1/x]). As such, even though the body of addX refers to the identifier x, it is not affected by the later re-binding of the value of x, since it only matters what the value of x was when addX was first bound. Seen in this way, then, reasoning about functions which use bound variables is very intuitive - you simply have to look up for the most recent time that that variable was bound.

We also can use anonymous lambda expressions to bind functions. These are denoted by the fn keyword, and are called lambda expressions for historical reasons having to do with a model of computation called the lambda calculus. For instance, we can declare:

val addOne : int -> int = fn x => x + 1

Lambda expressions can also be multi-clausal, by pattern matching to multiple different clauses. For instance, we can define the following function, which simply returns true when given 0 and 1, and false otherwise.

val isBinary : int -> bool = fn 0 => true | 1 => true | _ => false

Note that the right hand side of this declaration is an expression in its own right, and can be used independently of just being bound. The above binding simply binds the anonymous lambda expression (which simply increments an integer) to the identifier addOne. We could also do the following binding:

val two : int = (fn x => x + 1) 1

where we bind the result of evaluating the expression (fn x => x + 1) 1 to the identifier two. Clearly, this expression evaluates to 2, as 1 is substituted in for the local variable x, and then simply summed with 1.

NOTE: fun and fn differ in that functions declared with fun can be recursive, whereas val bindings using fn cannot unless you use rec. As such, while we can define the function fact as we did above, using fun, the following code does not work:

(* DOES NOT WORK *)
val fact : int -> int = fn 0 => 1 | n => n * fact (n - 1)

We will explore later on in the course what lambda expressions are useful for. In the meantime, usage of fun is sufficient to declare any functions that you may need.

It is also important to note that SML is an eager language, or call-by-value. This means that functions evaluate their arguments before stepping into their function bodies. This is explored more in the article on evaluation.