TheHans255.com

What Is A Function?

This month, I decided to go for a discussion that was altogether a bit more pedagogical, veering away from the more advanced topics and missives I usually cover. Instead of diving into something like a research paper or some deep obscure code, I'm going to ask a very straightforward question:

In software engineering, what, exactly, is a function?

You see them all the time in programs - nearly every programming language has them. For instance, here's a simple function written in JavaScript that prints a nice greeting with someone's name:

function hello(name) {
    console.log("Hello " + name + "!");
}

In Python:

def hello(name):
  print("Hello " + name + "!")

In Java:

void hello(String name) {
    System.out.println("Hello " + name + "!");
}

Even as far back as C:

void hello(char *name) {
    printf("Hello %s", name);
}

But what is it, exactly? What are we creating when we spell out a function like this? And what interesting things can we do with it?

Starting With Math - What Is A Function?

The modern programming language concept of a function comes from a sister discipline to computer science: mathematics. If you took algebra in high school, you may recall writing, or having seen written, something like this:

f(x)=x2−2x+1f(x) = x^2 - 2x + 1

This line here states that f is a function, such that if you give it an input value x, it will give you back an output value equal to x times itself, minus 2 times x, plus 1. To illustrate that, you may have drawn something like this:

One of those function machine diagrams

In other words, a function is like a machine - put a given value in, you get another value back out. And more importantly, every time you put the same value in, you would get the same value back out. Simple.

You then likely practiced that by plugging in random values into functions:

f(2)=22−2×2+1=4−4+1=1f(0)=02−2×0+1=0−0+1=1f(10)=102−2×10+1=100−20+1=81f(3t)=(3t)2−2×3t+1=9t2−6t+1\begin{array}{cc} f(2) = 2^2 - 2 \times 2 + 1 = 4 - 4 + 1 = 1 \\ f(0) = 0^2 - 2 \times 0 + 1 = 0 - 0 + 1 = 1 \\ f(10) = 10^2 - 2 \times 10 + 1 = 100 - 20 + 1 = 81 \\ f(3t) = (3t)^2 - 2 \times 3t + 1 = 9t^2 - 6t + 1 \end{array}

and by including functions in larger expressions:

2×f(x)=2(x2−2x+1)=2x2−4x+2f(y)=y2−2y+1f(f(2))=f(2)2−2×f(2)+1=12−2×1+1=−1\begin{array}{cc} 2 \times f(x) = 2 (x^2 - 2x + 1) = 2x^2 - 4x + 2 \\ \sqrt{f(y)} = \sqrt{y^2 - 2y + 1} \\ f(f(2)) = f(2)^2 - 2 \times f(2) + 1 \\ = 1^2 - 2 \times 1 + 1 = -1 \end{array}

In addition to writing your own functions, you likely also learned about some very common functions, such as sine (sin), cosine (cos), and tangent (tan) for angles, as well as the square root (√), natural logarithm (ln), and base-10 logarithm (usually log) - basically, all the magic buttons your scientific calculator had. Each of these, like our function f here, took one value and gave you a new value.

In discussing functions, we also usually discuss their domain and their range:

Finally, when discussing functions, we state one most important rule: each value in the domain is only allowed to map to one value in the range, and it must map to the same value every time. For instance, the sine of 45 degrees is always, forever, and only 1/√(2), or about 0.707. By contrast, the arcsine, or inverse sine, relationship is not a function - the domain of -1 to 1 maps to an infinite number of angles. If we draw both of these on a graph, we can see that the arcsine doubles back on itself across the horizontal x-axis, while the sine does not:

A graph of sine and arcsine. Double-back points on the x-axis are labeled.

A Little Deeper Math - Functions of Other Things

We are, however, allowed to bend these rules a bit. While it is always true that a function is only allowed to take one thing in, one thing out, there isn't really anything that says that these things going in and out have to be numbers, per se. For instance, we can construct this function that can take a tuple, or series, of four numbers and give us a number back:

d(x1,y1,x2,y2)=(x2−x1)2+(y2−y1)2d(0,0,3,4)=(3−0)2+(4−0)2=9+16=25=5\begin{array}{cc} d(x_1, y_1, x_2, y_2) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \\ d(0, 0, 3, 4) = \sqrt{(3 - 0)^2 + (4 - 0)^2} \\ = \sqrt{9 + 16} = \sqrt{25} = 5 \end{array}

Or, better yet, take a tuple of four numbers and give us back a pair of two numbers:

dm(x1,y1,x2,y2)=(x2−x1,y2−y1)dm(1,1,5,6)=(4,5)\begin{array}{cc} d_m(x_1, y_1, x_2, y_2) = (x_2 - x_1, y_2 - y_1) \\ d_m(1, 1, 5, 6) = (4, 5) \end{array}

Indeed, you could think of most of the basic arithmetic operations, such as +, -, ×, and ÷, as functions over pairs of numbers - and some disciplines of math even more or less write them that way (e.g. "×(÷(6, 2), +(1, 2))"). These functions also have their own domains and ranges - for instance, the ÷ function does not include in its domain any pairs where the second number is zero.

In general, we can use any sort of structure we want in our functions - numbers, pairs of numbers, colors, shapes, lists, eldritch horrors, and more. For practical purposes, though, we usually want our values to be enumerable, more or less meaning that we can write some function that can tell us everything about them in terms of numbers, given enough time (sorry, Cthulhu).

Some examples:

Perhaps wildest of all: functions themselves can be found in the domain and range of other functions. For instance, the function map takes a pair of a function and a sequence, and returns a new copy of that sequence where every element has been replaced with its output from that function:

f(x)=2xmap(f,(1,2,3))=(2,4,6)\begin{array}{cc} f(x) = 2x \\ \mathbf{map}(f, (1, 2, 3)) = (2, 4, 6) \end{array}

In fact, one of the earliest accomplishments of the field of computer science in the 1930s is the work of Alonzo Church, who invented a system of calculation called the Lambda Calculus that consisted entirely of functions that inputted and outputted other functions, where numbers and other datatypes were created by Frankensteining a bunch of functions together. Exactly how he did that is way outside of the scope of this post, but it helps to drive home the point that functions can input and output any mathematical construct you can imagine.

And finally, it's actually possible to take any well-defined function, such as those in the Lambda Calculus, and turn it back into a unique whole number. So really, in most cases we're not breaking any rules at all - by turning our pairs, sets, sequences, matrices, and functions into really, really big numbers, we're right back to having functions that input one number and output one number. (Of course, we can't always do that - irrational numbers give us a particular problem - but for enumerable objects, we usually can).

In summary, with a mathematical function, you can:

The great multitude of possible function inputs and outputs

Transitioning to Programming - How Do Functions Stay The Same?

Since functions can be thought of as such a fundamental building block of mathematics, it is not surprising that they made their way into programming languages as a fundamental building block of computation. Let's look at another example of a declared function, this time in Java, and see what similarities we can find:

double f(double x) {
    return x * x - x * 2 + 1;
}

// ... elsewhere

    double x = 2.0;
    System.out.println("x = " + x + ", f(x) = " + f(x));

Like with our mathematical functions, we can have more complex ranges and domains, including multiple outputs, sequences, and even other functions as before:

// Java function that takes a sequence and returns the sum
int sum(List<Integer> values) {
  // ... code here ...
}

// C# function that takes a string - a sequence of characters - and gives the reverse
string Reverse(string s) {
  // ... code here ...
}

// C function that returns the distance between two points
double distance(double x1, double y1, double x2, double y2) {
  // ... code here ...
}

// JavaScript function that maps another function over an array/sequence
// (note that JavaScript allows us to leave out the domain and range,
// which is useful here since only the domain of f and the values in the sequence
// have to match)
function map(f, array) {
  // ... code here ...
}

// Java example of the above
// (a "generic" syntax like this one is how we specify the domain and range
// when the language requires us to do it)
<INPUT, OUTPUT> List<OUTPUT> map(Function<INPUT, OUTPUT> f, List<INPUT> input) {
  // ... code here ...
}

Programming functions can work like math functions

One difference that quickly pops out is that a single programming function can have multiple statements, or lines:

double distance(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return Math.sqrt(dx * dx + dy * dy);
}

Usually, these lines exist to compute intermediate values, which mostly make the function easier to read. This can also be used to save values that need to be used multiple times in order to save a little computation time.

However, these extra lines are also where programming functions start to get a bit messy - because these extra lines allow functions to perform additional commands, it becomes very possible to write "functions" that are, in the mathematical sense, not functions at all.

Only one of these kinds of functions can also walk off and brew coffee

When Functions Get Messy - Non-Determinism and Side-Effects

Functions in programming can deviate from functions in math in two key ways: either returning different values for the same inputs, or causing what are known as side effects - events that are visible to the user when the function is called.

Non-deterministic functions

A "non-deterministic" function is a function that does not return the same values every time it is called with the same inputs. This is usually because these values are functions, but reference additional inputs that are beyond your control as a programmer. Some examples of these:

Side-effects and mutations

A side-effect is when a function, in addition to computing its output, also does something that can affect the visible state of the program. Some examples of these:

One of the most common side effects is mutation, or changing a value that is visible to another function or a future call to that one. For instance, consider these two functions:

double x = 0;
double y = 0;

function length() {
  return Math.sqrt(x * x + y * y)
}

function setX(value) {
  x = value
}

function setY(value) {
  y = value
}

The functions setX() and setY() each change the values of x and y - subsequent calls to length() will now change what they return, since they use x and y as hidden inputs.

Mutation is also how a lot of the non-deterministic functions work, such as the random number generator from earlier.

As an aside, most (but not all!) functions that perform side effects do not return any useful values, so the language will have some way to specify this has happened:

Pure/impure functions

This issue of "not-function functions" is widespread enough that computer scientists have come up with terms to effectively distinguish them. Specifically, a function that acts exactly like a mathematical function is called a "pure" function, while a function that exhibits side effects or runs non-deterministically is called an "impure" function.

For instance, this function is an impure function for a random number generator, because the state is kept internally:

long state;

int randNext() {
  state = /* ... do some wibbly-wobbly, timey-wimey stuff with the state ... */
  int result = /* ... do some math from the state to get a result ... */
  return result;
}

In this pure version of a random number generator, the state is exposed to the caller, and can be provided again for the same value:

// Returns the next number and the state.
// Note that we really shouldn't use the state value for anything
// except another call to randNext.
(int, long) randNext(long prevState) {
  long nextState = /* ... do some wibbly-wobbly, timey-wimey stuff with the state ... */
  int result = /* ... do some math from the state to get a result ... */
  return (result, nextState);
}

In another pure version of a random number generator, instead of calling the same function every time, we return new functions that each return a value and the next function to call, hiding the new seed inside hidden inputs (which do not change):

function getRandSequence(long seed) {
  // here we construct a function and immediately return it
  return function next() {
    long nextState = /* ... do some wibbly-wobbly, timey-wimey stuff with the state ... */
    int result = /* ... do some math from the state to get a result ... */
    return (result, getRandSequence(nextState)); // return the result and the next function to call
  }
}

In both of these cases, we could put together a pure mathematical expression that would get us the same effects. The initial seed we would provide ourselves - either a constant value that gets us the same sequence every time, or some non-deterministic value like the system time.

There are some languages, such as Haskell and Scheme, that go deep into the pure function concept to make all their functions as pure as possible, encouraging all computation to happen in the input and output values and only performing side effects through structures like monads.

With a little ingenuity, math can also brew coffee

Other, smaller questions

For a few, staggered items of interest:

Copyright © 2022-2023, TheHans255. All rights reserved.