2.5: Application- Programming with Functions
- Page ID
- 6719
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Functions are fundamental in computer programming, although not every- thing in programming that goes by the name of “function” is a function according to the mathematical definition.
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, in the C++ programming language, a function that calculates the square of an integer could be written
int square(int n) { return n*n; }
In C++, 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 ⊆ \(\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: int → int, or possibly as square ∈ \(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 : A → B\)”. The “n” in “int square(int n)” is a name for an arbitrary element of the data type int. In computer jargon, \(n\) is called 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.)
C++ has many data types in addition to int. There is a boolean data type named bool. The values of type bool are true and false. Mathematically, bool is a name for the set {true, false}. The type float 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 float 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 C++ is string. All these types, and many others, can be used in functions. For example, in C++,\(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:
bool even(int k) { if ( k % 2 == 1 ) return false; else return true; }
You don’t need to worry about all the details here, but you should under- stand that the prototype, bool even(int k), says that even is a function from the set int to the set bool. That is, even: int → bool. 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 × string, and we can write index : string × string → int or, equivalently, index ∈ \(int^{string x string}\).
Not every C++ 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 C++ 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 pro- duce 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 behavior of a mathematical function!
Even though many functions in computer programs are not really math- ematical functions, I will continue to refer to them as functions in this sec- tion. Mathematicians will just have to stretch their definitions a bit to accommodate the realities of computer programming.
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, C++ does take a step in this direction. It is possible for a function to be a parameter to another function. For example, consider the function prototype
float sumten( float f(int) )
This is a prototype for a function named sumten whose parameter is a function. The parameter is specified by the prototype “float f(int)”. This means that the parameter must be a function from int to float. The parameter name, \(f\), stands for an arbitrary such function. Mathematically, \(f ∈ float^{int}\), and so sumten: float\(^{int}\) → float.
My idea is that \(sumten(f)\) would compute \(f(1) + f(2) + · · · + f(10)\). A more useful function would be able to compute \(f(a) + f(a + 1) + · · · + 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
float sum( float f(int), 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: float^{int} × int × int → float \nonumber\]
It’s interesting that computer programmers deal routinely with such complex objects.
One thing you can’t do in C++ is write a function that creates new functions from scratch. The only functions that exist are those that are coded into the source code of the program. There are programming languages that do allow new functions to be created from scratch while a program is running. In such languages, functions are first-class objects. 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 Web pages. (Although the names are similar, JavaScript and Java are only distantly related.) 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 C++ 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 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: data →data.
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)+· · ·+f(b)\). Then we could compute \(1^{2} +2^{2} +· · ·+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.
Exercises
1. For each of the following C++ function prototypes, translate the prototype into a standard mathematical function specification, such as func: float → int.
a) int strlen(string s)
b) float pythag(float x, float y)
c) int round(float x)
d) string sub(string s, int n, int m)
e) string unlikely( int f(string) )
f ) int h( int f(int), int g(int) )
2. Write a C++ function prototype for a function that belongs to each of the following sets.
a) string\(^{string}\)
b) bool\(^{float×float}\)
c) float\(^{int^{int}}\)
3. It is possible to define new types in C++. For example, the definition
-
struct point { float x; float y; }
defines a new type named point. A value of type point contains two values of type float. What mathematical operation corresponds to the construction of this data type? Why?
4. Let square, sum and monomial be the JavaScript functions described in this section. What is the value of each of the following?
a) sum(square, 2, 4)
b) sum(monomial(5,2), 1, 3)
c) monomial(square(2), 7)
d) sum(function(n) { return 2 ∗ n; }, 1, 5)
e) square(sum(monomial(2,3), 1, 2))
5. Write a JavaScript function named compose that computes the composition of two functions. That is, \(compose(f,g)\) is \(f ◦g\), where f and g are functions of one parameter. Recall that \(f ◦g\) is the function defined by \((f ◦g)(x) = f (g(x))\).