4.6. Application: Programming with Functions*#

Functions are fundamental in computer programming, although not everything in programming that goes by the name of ‘function’ is a function according to the mathematical definition.

Important

In this section we go into detail about functions in computer programming. You won’t be examined on this in Reasoning & Logic! You will find that there is again quite some overlap with your study materials from Object-Oriented Programming and later on in your curriculum with Concepts of Programming Languages.

In computer programming, a function is a routine that is given some data as input and that will calculate and return an answer based on that data. For example, Java, a function that calculates the square of an integer could be written

int square(int n) {
	return n*n;
}

In Java, int is a data type. From the mathematical point of view, a data type is a set. The data type int is the set of all integers that can be represented as 32-bit binary numbers. Mathematically, then, \( int \subseteq\mathbb{Z}\). (You should get used to the fact that sets and functions can have names that consist of more than one character, since it’s done all the time in computer programming.) The first line of the above function definition, int square(int n), says that we are defining a function named square whose range is int and whose domain is int. In the usual notation for functions, we would express this as \( square \colon int \to int \), or possibly as \(*square*\in{*int*}^{*{int}*}\), where \({*int*}^{*{int}*}\) is the set of all functions that map the set int to the set int.

The first line of the function, int square(int n), is called the prototype of the function. The prototype specifies the name, the domain, and the range of the function and so carries exactly the same information as the notation \(f\colon A\to B\). The ‘\(n\)’ in the prototype int square(int n) is a name for an arbitrary element of the data type int. We call \(n\) a parameter of the function. The rest of the definition of square tells the computer to calculate the value of \( square (n)\) for any \(n\in int \) by multiplying \(n\) times \(n\). The statement return n*n says that \(n*n\) is the value that is computed, or ‘returned’, by the function. (The \(*\) stands for multiplication.)

Java has many data types in addition to int. There is a boolean data type named boolean. The values of type boolean are true and false. Mathematically, boolean is a name for the set \(\{ true ,\, false \}\). The type double consists of real numbers, which can include a decimal point. Of course, on a computer, it’s not possible to represent the entire infinite set of real numbers, so double represents some subset of the mathematical set of real numbers. There is also a data type whose values are strings of characters, such as ‘’Hello world’’ or ‘’xyz152QQZ’’. The name for this data type in Java is string. All these types, and many others, can be used in functions. For example, in Java, \(m\,\%\,n\) is the remainder when the integer \(m\) is divided by the integer \(n\). We can define a function to test whether an integer is even as follows:

boolean even(int k) {
	return k 
}

You don’t need to worry about all the details here, but you should understand that the prototype, boolean even(int k), says that even is a function from the set int to the set boolean. That is, \( even \colon int \to boolean \). Given an integer \(N\), \( even (N)\) has the value true if \(N\) is an even integer, and it has the value false if \(N\) is an odd integer.

A function can have more than one parameter. For example, we might define a function with prototype int index(string str, string sub). If \(s\) and \(t\) are strings, then index \((s,t)\) would be the int that is the value of the function at the ordered pair \((s,t)\). We see that the domain of index is the cross product \( string \times string \), and we can write \( index \colon string \times string \to int \) or, equivalently, \(*index*\in*int*^{*string*\times*string*}\).

Not every Java function is actually a function in the mathematical sense. In mathematics, a function must associate a single value in its range to each value in its domain. There are two things that can go wrong: the value of the function might not be defined for every element of the domain, and the function might associate several different values to the same element of the domain. Both of these things can happen with Java functions.

In computer programming, it is very common for a ‘function’ to be undefined for some values of its parameter. In mathematics, a partial function from a set \(A\) to a set \(B\) is defined to be a function from a subset of \(A\) to \(B\). A partial function from \(A\) to \(B\) can be undefined for some elements of \(A\), but when it is defined for some \(a\in A\), it associates just one element of \(B\) to \(a\). Many functions in computer programs are actually partial functions. (When dealing with partial functions, an ordinary function, which is defined for every element of its domain, is sometimes referred to as a total function. Note that—with the mind-bending logic that is typical of mathematicians—a total function is a type of partial function, because a set is a subset of itself.)

It’s also very common for a ‘function’ in a computer program to produce a variety of values for the same value of its parameter. A common example is a function with prototype int random(int N), which returns a random integer between 1 and \(N\). The value of random(5) could be 1, 2, 3, 4, or 5. This is not the behaviour of a mathematical function—but it’s very useful when programming!

Even though many functions in computer programs are not really mathematical functions, we will continue to refer to them as functions in this section. Mathematicians will just have to stretch their definitions a bit to accommodate the realities of computer programming.

4.6.1. Functions as first-class objects#

In most programming languages, functions are not first-class objects. That is, a function cannot be treated as a data value in the same way as a string or an int. However, newer versions of Java do take a step in this direction with ‘lambda expressions’. In Java it is not yet possible for a function to be a parameter to another function. For example, suppose in Java we could write the function prototype

double sumten(Function<Integer,Double> f)

This is a prototype for a function named sumten whose parameter is a function. The parameter is specified by the prototype Function<Integer,Double> f. This means that the parameter must be a function from int to double. The parameter name, \(f\), stands for an arbitrary such function. Mathematically, \(f\in *double*^{*int*}\), and so \(*sumten*\colon *double*^{*int*}\to*double*\).

My idea is that sumten(\(f\)) would compute \(f(1)+f(2)+\cdots+f(10)\). A more useful function would be able to compute \(f(a)+f(a+1)+\cdots+f(b)\) for any integers \(a\) and \(b\). This just means that \(a\) and \(b\) should be parameters to the function. The prototype for the improved function would look like

double sum(Function<Integer,Double> f, int a, int b)

The parameters to sum form an ordered triple in which the first coordinate is a function and the second and third coordinates are integers. So, we could write \(*sum*\colon *double*^{*int*} \times*int*\times*int*\to*double*\) It’s interesting that computer programmers deal routinely with such complex objects.

Languages where functions are first-class objects are for example Python and Scala. These languages support what is called functional programming.

One of the most accessible languages that supports functional programming is JavaScript, a language that is used on webpages. (Although the names are similar, JavaScript and Java are only distantly related. You probably knew that.) In JavaScript, the function that computes the square of its parameter could be defined as

function square(n) {
	return n*n;
}

This is similar to the Java definition of the same function, but you’ll notice that no type is specified for the parameter \(n\) or for the value computed by the function. Given this definition of \text{square}, square(\(x\)) would be legal for any \(x\) of any type. (Of course, the value of square (\(x\)) would be undefined for most types, so square is a very partial function, like most functions in JavaScript.) In effect, all possible data values in JavaScript are bundled together into one set, which I will call data. We then have \( square \colon data \to data \).[1]

In JavaScript, a function really is a first-class object. We can begin to see this by looking at an alternative definition of the function square:

square = function(n) { return n*n; }

Here, the notation function(n) { return n*n; } creates a function that computes the square of its parameter, but it doesn’t give any name to this function. This function object is then assigned to a variable named square. The value of square can be changed later, with another assignment statement, to a different function or even to a different type of value. This notation for creating function objects can be used in other places besides assignment statements. Suppose, for example, that a function with prototype function sum(f,a,b) has been defined in a JavaScript program to compute \(f(a)+f(a+1)+\cdots+f(b)\). Then we could compute \(1^2+2^2+\cdots+100^2\) by saying

sum(function(n) { return n*n; }, 1, 100)

Here, the first parameter is the function that computes squares. We have created and used this function without ever giving it a name.

It is even possible in JavaScript for a function to return another function as its value. For example,

function monomial(a, n) {
	return (function(x) { a*Math.pow(x,n); });
}

Here, Math.pow(x,n) computes \(x^n\), so for any numbers \(a\) and \(n\), the value of monomial (\(a\),\(n\)) is a function that computes \(ax^n\). Thus,

f = monomial(2,3);

would define \(f\) to be the function that satisfies \(f(x)=2x^3\), and if sum is the function described above, then

sum( monomial(8,4), 3, 6 )

would compute \(8*3^4+8*4^4+8*5^4+8*6^4\). In fact, monomial can be used to create an unlimited number of new functions from scratch. It is even possible to write monomial(2,3)(5) to indicate the result of applying the function monomial(2,3) to the value 5. The value represented by monomial(2,3)(5) is \(2*5^3\), or 250. This is real functional programming and might give you some idea of its power.

4.6.2. Exercises#