As a software engineer, you probably think of a function as a unit of code that takes some arguments and returns some value, eg:
function square(x) {
return x * x;
}That's a pragmatic definition, but it's not the actual meaning of the word function. A function is a relation between a domain and a range such that for each input there exactly one output specified.
A relation is a set of tuples where each tuple shares the same schema - in other words, a relation is a table. A tuple is a row. A value within the tuple is a cell. In this table, our domain describes the set of all valid values for our input column, while the range describes all valid values for our output column.
So here's a relational representation of the same function as above (or at least the first few rows of it):
| input | output |
|---|---|
| 1 | 1 |
| 2 | 4 |
| 3 | 9 |
| 4 | 16 |
| 5 | 25 |
| ... | ... |
We now have two different representations of the square function - our progamatically defined one has the advantage that it runs, but I'm here to tell you that when you start learning to see functions as relations in addition to seeing them as programming constructs a lot of other stuff starts to make sense.
So a function is a relation that maps inputs to outputs in a way that guarantees that the same input will always map to the same output. Ok. So let's look at the following example, and there's going to be a pop quiz at the end:
let x = 0;
// every ten milliseconds change x to a different random value between 0 and 99
setInterval(() => x = Math.floor(Math.random() * 100)), 10)
// assume timestamp() returns some string-formatted representation of Date.now()
function logX() {
console.log(`The value of x at time ${timestamp()} was ${x}`)
}My question is: is logX a function? A lot of smart folks would say no, it's not - that it takes no arguments and returns no value, so how could it possibly represent a relation between input and output?
I'm not here to tell you that those folkks are wrong - but I am here to offer a slightly different perspective. This is just a lens, perhaps something at the level of 'useful metaphor'. I'm here to tell you that logX is totally a function, provided you're willing to unlearn what you understand about inputs and outputs. Let's try to model the above relationally to see what we can figure out.
| x | timestamp | console.log |
|---|---|---|
| 72 | 1 | "The value of x at time 1 was 72" |
| 23 | 2 | "The value of x at time 2 was 23" |
| 32 | 3 | "The value of x at time 3 was 32" |
| 3 | 4 | "The value of x at time 4 was 3" |
| 68 | 5 | "The value of x at time 5 was 68" |
| ... | ... | ... |
That's interesting! This is kind of starting to look like a function, right? The only difference is that we haven't labeled any of these columns as inputs or outputs - but there's nothing stopping us from doing that.
We can just say that the INPUT of this relation is {x, timestamp} and the OUTPUT of this relation is whatever gets written to console.log. Now our three-column table does in fact represent a function - for every unique combination of timestamp and X there is a specific and unambiguous value output to the console.
The lesson here, for me at least, is just this: when you reason about your function as a relation you have nowhere to specify 'arguments' or 'return values' - you just have columns that hold facts and you can choose to arbitrarily declare that some columns are inputs and some columns are outputs, as long as each input leads to a unique and unambiguous output. Does that make sense?
So when I say you have to unlearn IO, what I mean is this: a function's input is not limited to its arguments, and its output is not limited to its return value. Rather, a function's input is the set of values available to it, and a function's output is the set of changes the function makes to its universe.
So going back to our JS example above, we can say that logX is definitely a function as long as we're willing to concede that x and the value of timestamp() can be thought of as inputs, and as long as we're willing to model writing out to the console to be a form of output.
Not convinced? Think about Object Oriented Programming, where you have a variable called this or self, depending on your language. What's the purpose of that variable? Well, two things: (1) it holds values that were computed elsewhere in your class, and (2) it allows methods to mutate it. This is (1) a mechanism for providing non-argument inputs into your function, and (2) a mechanism for allowing your function to make changes to its universe. The whole point of OOP is that grouping stuff together allows certain values to be passed around between methods implicitly, rather than explicitly - but if you understand that, relationally, you can think of this as just another column, then you're well on your way to grokking it.
Let's go back to our square function from the opening:
function square(x) {
return x * x
}What if we wanted to abstract this function out so that rather than always squaring the input it instead raised the input to the power provided in a second argument?
function raise(x, power) {
return Math.pow(x, power)
}Kind of a contrived example, but it illustrates an important point: we've added a new input to an existing function, and updated its behavior to make use of that input. What does this look like when we bring it over into a relational representation?
| x | power | return |
|---|---|---|
| 1 | 2 | 1 |
| 2 | 2 | 4 |
| 3 | 2 | 9 |
| 1 | 3 | 1 |
| 2 | 3 | 8 |
| ... | ... | ... |
Do you see what we just did? We took our original square table and added a new column. Our existing square function still exists as a subset of this table - in fact, if you took only those rows where power=2 then you'd get something identical to the square function. But by adding a power column we've added a whole new dimension to our function - this is called abstraction, and when you model functions as relations it's easy to see that abstraction is literally just adding a new column to your inputs.
So what does it mean to remove a column?
This is where stuff gets fun. Let's take our raise function and partially apply the first argument:
function raise(x, power) {
return Math.pow(x, power)
}
const raiseTwoByPower = raise.bind(null, 2)We've created a new function which is a partial application of our initial function - we've filled in the value of x to always be 2. Now when you call raiseTwoByPower you just have to pass in a single value, the power. To represent this relationally looks something like this:
| x | power | return |
|---|---|---|
| 2 | 1 | 2 |
| 2 | 2 | 4 |
| 2 | 3 | 8 |
| 2 | 4 | 16 |
| 2 | 5 | 32 |
| ... | ... | ... |
But honestly, if the value of the x column never changes then why even have it there? We no longer need it to form a complete unique input, so we can just drop it and represent our raiseTwoByPower as a simple two-column relation:
| power | return |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
| ... | ... |
This is a phenomenally powerful technique, and it works by constraining the data type of an input column to a single value. We'll get to what exactly that means in Part IV, but first I want to beat you over the head with how important concretion really is and how many ways we do it every day without necessarily realizing that we're doing the same damn thing.
// sometimes we use partial application
const sum = (a, b) => a + b
const addThree = sum.bind(null, 3) // a is now always equal to 3
// sometimes we use currying
const sum a => b => a + b
const addThree = sum(3) // again, a is now always equal to three
// sometimes we use object orientation!
class Adder {
constructor(a) {
this.a = a
}
add(x) {
return this.a + x
}
}
let addThree = new Adder(3).add // same thing!
// sometimes we use mutable global scope!
let addend = 3
const addThree = x => addend + x // again, we get the same relational structure
// (this one is less 'pure' because `a` never existed) It turns out that concretion is a thing we do all the time, and we do it so unconsciously that here are four different ways to express it in javascript and I bet you never thought of these four things as effectively the same operation, right?
So what exactly are we doing when we add/remove columns? Where do they come from, and where do they go?
Reasonable people can disagree on what exactly a Type is in programming - is it a set? Is it a predicate function? Is a type as expressed in one high level language the same as an identical type expressed in a different one?
I'm here to tell you not to worry about those questions. What you need to know about types is that they constrain the set of valid values for each of our columns. Remember how we said that a function is a relation mapping Domain to Range? At a high level, the Domain of a function is the type of its inputs, and the Range of a function is the type of its outputs. So when you see something like this:
const sum = (a, b) => a + bWhat are its types?
Well, that's kind of a trick question. Intuitively we want to answer that the domain, or input type, is something like {number, number} and its range, or output type, is just {number}. In practice, though, different languages vary wildly in their capacity to allow you to specify types. With the sum function under discussion, for instance, we get a variety of interesting behaviors that can violate our naive assumptions about types -
// sure this works:
sum(2, 2) // 4
// but then we get something like this:
sum(2, ' apples') // '2 apples'As JavaScript engineers we understand that this isn't a bug - that the + operator becomes string concatenation if one of its inputs is non-numeric - but this is a far cry from the platonic ideal sum function we imagine, right? When writing out the sum relation, it would be silly to include strings as valid inputs - that's a conceit of JavaScript, and at the relational level we've risen above such petty implementation details, right?
Other languages gives you tools that make it impossible to pass invalid types into a function. In Java, a sum function might look something like this:
public float sum(float a, float b) { return a + b }If you try to pass a string into that function as one of your arguments you'll get a compiler error when you try to build your project. Why? Because Java has some support for type-based constraints, which allows us to make our programmatic function look a little bit more like our relational function.
But look, when we're at the relational level we don't need to worry about creating executable representations of our types. A valid type can be 'The three best blue berries I ever ate' or 'a color that is hitting my optical nerve right now' or literally any other category of thing that you can imagine. Becausae we're operating at an abstract imaginary layer we can just handwave away those types - we accept that we can imagine way more types than we can actually express meaningfully in code, and that's fine.
Except that this is where bugs happen. You think, "I know, I need a sum function here!" and in your head you're picturing the relational mathematical object that purely sums numeric values - but your fingers are typing out javascript code, and suddenly your sum function has strings appearing where they shouldn't, and you come crashing back down to the understanding that the language you use is going to inform how much granular control you have over type specificity.
Look: when we think about functions, we're often thinking about pure relational structures. A lot of bugs happen because our languages give us really lossy, compromised ways to express those structures, and a part of getting good at software engineering is getting good at recognizing the delta between the relation we're reasoning about and the executable monstrosity we're typing out.
So, let's get back to our question - when we add/remove columns, where do they come from and where do they go?
Well, I think of every function as potentially infinite - we can have any number of columns and any number of rows. But when a column's value stops changing, we can just remove it from our set of inputs. Think about computing how fast something is falling - if you're on earth, in atmosphere, you can expect it to accelerate towards the ground at roughly 9.8 meters per second squared, and that's fine.
| elapsed_time | velocity |
|---|---|
| 1 | -9.8 |
| 2 | -19.6 |
| 3 | -29.4 |
| 4 | -39.2 |
| 5 | -49 |
| ... | ... |
But if suddenly you're on mars, the speed of that acceleration changes - now, rather than just a constant 9.8 m/ss, you have a variable.
| gravitational_acceleration | elapsed_time | velocity |
|---|---|---|
| -9.8 | 1 | -9.8 |
| -9.8 | 2 | -19.6 |
| -9.8 | 3 | -29.4 |
| -3.7 | 1 | -3.7 |
| -3.7 | 2 | -7.4 |
| ... | ... | ... |
That gravitational_acceration column was always "there" - it's just that when you're on earth its data type is constrained to a single value. If your function has to work on other planets as well then that column's data type expands to include more values and so becomes a part of your table.
Similarly, if you have the general function and you need a version that only has to work on mars, you can constrain that column to a single value, -3.7 - now you no longer need to represent it.
| elapsed_time | velocity |
|---|---|
| 1 | -3.7 |
| 2 | -7.4 |
| ... | ... |
The broader takeaway I'd like you to have here is this: anything not represented in the table is irrelevant for the purposes of the function. Computing the velocity of an object that has been falling for T seconds is purely a function of time as long as you're only on earth; it's only when the acceleration is variable that acceleration has to be treated as a second input.
Alright, so we've started to develop an intuition for reasoning relationally about functions. This is easy enough with simple operations, but can this really scale? What about functional composition? Or what about higher order functions? How do you even represent that in a table?
Let's create a slightly more complex contrived example:
const format(string, formatter) {
if (formatter) return formatter(string);
return value;
}
// some sample formatters
const toAllCaps = x => x.toUpperCase();
const stripSpaces = x => x.split(' ').join('')
const reverse = x => x.reverse()We've created four different functions here - a top-level function, and three subfunctions to compose. Let's create some tables for the formatters, first:
toAllCaps:
| to_capitalize | capitalized |
|---|---|
| 'hi' | 'HI' |
| 'foo'. | 'FOO' |
| 'happy new year' | 'HAPPY NEW YEAR' |
stripSpaces:
| to_strip | stripped |
|---|---|
| 'hi' | 'ih' |
| 'foo'. | 'foo' |
| 'happy new year' | 'happynewyear' |
reverse:
| to_reverse | reversed |
|---|---|
| 'hi' | 'hi' |
| 'foo'. | 'oof' |
| 'happy new year' | 'raey wen yppah' |
So, what does it look like to include one of these as an argument into our format function? It's weird, right?
| string | formatter | output | ||||||||
| 'happy new year' |
|
??!! | ||||||||
| 'happy new year' |
|
??!! | ||||||||
| 'happy new year' |
|
??!! |
Fortunately, tables have this pretty awesome property: they compose! What this means is that you can pull all of the columns out of your nested relations and add them to the top level of your outer relation - you basically treat them as additional compound inputs!
| string | to_capitalize | capitalized | to_strip | stripped | to_reverse | reversed | output |
|---|---|---|---|---|---|---|---|
| 'foo' | 'foo' | 'FOO' | 'FOO' | ||||
| 'foo' | 'foo' | 'foo' | 'foo' | ||||
| 'foo' | 'foo' | 'oof' | 'oof' | ||||
| 'foo' | 'foo' |
Do you see how this works? The input to our relation is the union of all of the columns except the last one. For every combination of input string and formatter function we've got certain rows populated and certain rows empty. You can see how the first row maps to format('foo', toAllCaps), the second to format('foo', stripSpaces), the third to format('foo', reverse) and the last to simply format('foo'). Each row is unique and maps to exactly one output.
There's a lot going on here, so let's unpack it a little bit. Because we have three different formatters, each of which takes a single input and returns a single output, we've just gone ahead and added all of the various formatter columns to our table. Depending on which formatter we're using only one set of formatter columns will be populated.
I've also left out all rows from the formatters that don't match the input data. All of those other rows still exist, they're just not relevant for the purposes of this particular composition so I'm not including them in the above example.
So, I am still reasoning through this part, but it strikes me that table composition can be thought of as a tabular join as in relational algebra. What we've done is joined the format table to the toAllCaps table, where format.string is joined on toAllCaps.to_capitalize and format.output is joined on toAllCaps.capitalzed.
Does this make sense?
So now imagine that we're also going to compose our formatters! How would this look?
format('happy new year', x => reverse(stripSpaces(toAllCaps(x)))We'd get something like this:
| string | to_capitalize | capitalized | to_strip | stripped | to_reverse | reversed | output |
|---|---|---|---|---|---|---|---|
| 'happy new year' | 'happy new year' | 'HAPPY NEW YEAR' | 'HAPPY NEW YEAR' | 'HAPPYNEWYEAR' | 'HAPPYNEWYEAR' | 'RAEYWENYPPAH' | 'RAEYWENYPPAH' |
Do you see how that worked? What are the joins, here? There would be so many intermediary steps to work through how to do this using SQL or some other relational model, right? It's super useful that javascript just lets us call functions without having to think through all of the relational entanglements - until it doesn't!
So composition, with relational functions, is just a matter of joining tables on certain columns and letting the order of your operations determine which columns get joined to what.
Now do Monads!!