# 3.5: 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.

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

n 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 ⊆ 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 com- puter 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 : int → int, or possibly as square $$\in i n t^{i n t},$$ where $$i n t^{i n t}$$ 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 : A B. The ‘n’ in 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 ∈ 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 namedboolean. 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:

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 setboolean. That is, even: int → boolean. Given an integer N, even(N) has the value true if Nis 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 func- tion with prototype int index(string str, string sub). If s and t are strings, thenindex(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 × string, and we can write index: string $$\times$$string$$\rightarrow$$int or, equivalently, index$$\in i n t^{\text { string } \times \text {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 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-boggling 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, I 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.