What Is A Function?

In which the author describes the ins and outs of one of the most basic blocks of programming languages - the function.

By: TheHans255

7/16/2023

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:

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:

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:

and by including functions in larger expressions:

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:

• The domain of a function is all of the values that it can take as input (e.g. all numbers, only positive numbers, everything except zero, etc.). A function will give you one output value for every value inside its domain, and has an "undefined" output otherwise. For instance, trying to calculate ln(0) on a calculator will give you an error, because the natural logarithm does not include 0 in its domain.
• The range of a function is all of the values it can output - each value in the domain will map to one value in the range. For instance, the sine and cosine functions will always give you a value between -1 and 1, meaning that their ranges are all the real numbers between those two values.

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 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:

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

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:

• Some functions use Boolean values, which are simple true/false truth values. For instance, the AND function returns TRUE only if both of its inputs are also TRUE.
• Some functions use sequences, which are arbitrarily large lists of the same type of values. For instance, the max function takes a sequence of numbers and returns the largest element.
• Some functions use matrices, which are lists of numbers arranged into rows and columns. They can be added and multiplied (their own ordered-pair functions), and have some functions of their own, such as the determinant which calculates a single value from entries of a square matrix. There is also the identity matrix function, which takes a positive integer and spits out a special square matrix of that size.
• Functions can also take shapes (e.g. area and perimeter), colors (complimentary colors, anyone?), text (which is really just a sequence of characters), and more.
• Some functions can take absolutely anything. These functions are usually one of two things:
  1. The identity function, which simply outputs its input
  2. A function that doesn't actually care at all about its input and gives the same output value every time. In these situations, it is usually better to write the function as taking a meaningless unit value, such as a tuple of numbers with exactly 0 numbers in it (which you could write as just an empty pair of parentheses, e.g. "f()")

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:

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:

• Define new functions, which map values in an input set (called the domain) to values in an output set (called the range)
• Input (or apply) values from the domain into the function to get values from the range
• Include that application inside other expressions
• If within the domain of the host function, supply the function itself as input to another function.

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));

• f is the name of the function, just as our mathematical function had the name f. Like our mathematical functions, we can also have longer names, and unlike our mathematical functions, we don't need to worry about writing them differently to convey that idea.
• The double in both cases represents the range and domain, respectively, of the function - the function both takes and returns values in the set of IEEE 754 double-precision floating point numbers, which are essentially equivalent to real numbers for most purposes.
• Inside the function, we have the same mathematical expression as f from before: x times itself, minus x times 2, plus 1. We do have to write the return keyword to indicate that we want to get the result of this expression as an output to our function, but the principle is the same - put a value in, get this specific value out.
• Once the function is written, we supply inputs to it (or call it) using the same syntax - the function's name followed by the input in parentheses.

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 ...
}

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.

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:

• The current time - there's usually a function called getCurrentTime() or Date.now() that gives you a measure of what day and time it is - you provide no inputs, but the code looks at what time it is (which is forever ticking forward) and returns it to you.
• A random number generator (e.g. Math.random()), which returns a different, unpredictable number each time. These are almost always dependent on some internal state that is both used as a hidden input to the function and is changed, or mutated, every time the function is called - in other words, every time you call this function, you are actually calling it with different inputs which are supplied on your behalf. (Really good random functions will also be based on chaotic events happening across the computer's hardware).
• The keys that the user most recently pressed - there's usually a function for reading input, such as C's getchar(), that returns a new recent key as the user presses more keys. Note that this function also usually maintains some internal state to keep you from reading the same pressed key twice, and might make your program wait until another key is pressed.

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:

• Printing or drawing to the screen while the function is running - print() is written as a function in most languages, for instance, but its use is to write text to the screen and doesn't actually return anything useful.
• Playing a sound effect
• Sending a logging message to a web server
• Opening another window on the screen
• Closing the program prematurely
• Waiting an inordinate amount of time (such as waiting for user input)

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:

• If you have a dynamic language that does not require you to specify types for the domain and range, a common choice is to have some "none" value that is returned by default if there's nothing interesting - for instance, JavaScript's undefined or Python's None.
• If you do have to specify the type, a common choice in languages like C or Java is void, meaning that no value is returned by the function. The language will then disallow you from putting that function in an expression and instead will force you to put it on its own line.
• A few languages, such as Rust and Haskell, use the unit type concept to represent this idea, and will have functions return a tuple with zero things in it (()) or something similar. This also allows them to distinguish functions that never return at all, using a type like Never or !.

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.

Other, smaller questions

For a few, staggered items of interest:

• What is a "method"?: In object-oriented programming, functions are usually attached to "objects" that bundle of interesting inputs/outputs together - in this case, they are called "methods", and take the object they are being called on as an additional, "receiver" input, usually called this or self. (For instance, a vector object v might hold x and y values and have a length() method - you would call it as v.length(), and while there's nothing in the parentheses, length() is still taking v as an input - allowing it to stay separate from other vectors you might have lying around).
• What are "closures"?: Essentially, the changeable hidden inputs from before. If you have a programming language that allows you to create new functions on the fly (such as by returning them from other functions), then under the hood, when you want to pass that function to another function, you actually have to pass both a function pointer (the location of the code, which doesn't usually change) and a bundle of all the hidden inputs you might have given it. Most languages with this feature handle this bundling for you.
• Are there languages that don't use functions?: Yes! Many older languages, such as BASIC, operate entirely on commands and mutations. They may have "subroutines", which are sets of commands that get reused from multiple other locations in the program, but they do not have any special way of inputting or outputting values. This is also how assembly code works - at the end of the day, functions are a convenience, and we need to use carefully managed side effects to make them work on actual computers.