Functional Programming and the Semantics of Change, State & Time

The “functions vs. objects” cliche is an artifact of a profound truth about program structure and semantics. Like oil and water, functions expel objects and objects functions. Moreover, the choice between them has dramatic implications for our programs, installing a “world-view” that involves concepts as fundamental as identity, change, state and even time. The object-oriented world-view may seem so obvious as to be without alternative. Look around the room, bus, park or wherever you find yourself reading this sentence, and you will likely identify objects, such as dogs, people and trees, changing over time. Many programmers approach program design the same way, identifying “distinct objects whose behaviors may change over time.” (SICP Section 3) The ubiquity of this interpretation, however, belies the fact of interpretation. Change can be reformulated along different lines. Functional programs do not include identifiable objects. Yet, they may include state. They shift the paradigm. Instead of objects that change over time, functional programs consist of state transitions between discrete moments in time that may be seen together as “streams of information that flow.” (SICP Section 3)

Preface: Why JavaScript #

Many of the insights underlying this post can be found in original form in the Structure and Interpretation of Computer Programs (SICP). There you may find a life-altering discussion of the same topics using Scheme, a Lisp dialect like Clojure. All code examples included in this post, however, will be couched in terms of JavaScript. If you know JavaScript and are unfamiliar with Scheme, this post may be immediately accessible to you without first learning how “to balance all those parens.” Little is lost in translation as well. JavaScript has first-class functions (i.e. lambdas), closures (i.e. function-delimited lexical scoping) and generally thrives when used functionally.

JavaScript’s functions are first class objects with (mostly) lexical scoping. JavaScript is the first lambda language to go mainstream. Deep down, JavaScript has more in common with Lisp and Scheme than with Java. It is Lisp in C’s clothing. — Douglas Crockford, JavaScript: The Good Parts

There is even an ongoing academic effort to translate the full text of SICP into JavaScript. Also considered, JavaScript is a close cousin of TypeScript, which enables traditional object-oriented constructs like private and public and functional constructs like readonly and as const at compile time. Perhaps in JavaScript (and TypeScript), we get enough support of functional and object-oriented programming paradigms to enable a discussion of both within a single, ubiquitous language.

Object-Oriented Programming #

Object-oriented programming has come to signify a common language for modeling the behavior of objects.^[1] Methods leverage privileged access to proscribe the ways in which private attributes may be viewed or changed. A class specifies the blueprint for creating object instances of a certain kind. Together, these constructs may create computational objects that simulate real objects. This bankAccount object in TypeScript, for example,

class BankAccount {
  private balance;

  constructor(funds) {
    this.balance = funds;
  }

  public withdraw(amount) {
    this.balance = this.balance - amount;
  }

  public checkBalance() {
    return this.balance;
  }
}

const bankAccount = new BankAccount(100);
bankAccount.withdraw(20);
bankAccount.checkBalance(); // 80

stores balance data in a private attribute and exposes privileged methods checkBalance and withdraw, which proscribe the manner in which access to balance can occur. Together, these constructs create a computational object bankAccount that behaves like a “bank account”, carrying a balance that may be diminished through “withdraw” and viewed through “check balance” actions. Less abstract objects can be modeled with the same set of tools. An apple may have a bite method that reduces an internal bites state in order to model an “apple” and a house may have a paint method that changes an internal color state in order to model a “house.” More abstract objects can be modeled with the same set of tools as well. A userMetaData object may have a setEmail method that updates an internal email state in order to model “user meta data.”

An Evolution of Imperative Programming #

And a key characteristic here is that objects have methods… They are operationally defined. And we use them to provide a layer of abstraction over the places that our program uses. — Rich Hickey, The Value of Values

Private state enforces the object abstraction together with privileged, public methods. Expose balance directly (i.e. make it public), for example, and it can “magically” change from say 100 to 10 despite no withdrawal ever having occurred.

class BankAccount {
  public balance;
  ...
}

const bankAccount = new BankAccount(100);
bankAccount.balance = 80; // 80

Expose color directly and it can magically change from say WHITE to BLUE despite no painting ever having occurred. In other words, object-oriented programming provides the means for identifying objects (bankAccount) and associated behaviors (withdraw)

bankAccount.withdraw(20);

in place of imperative, direct manipulation of variables (balance) ad hoc.

let balance = 100;
balance = balance - 20;

Coincidentally, the private data / public methods dynamic also provides the means for data encapsulation. That data is stored in private attributes, accessible only through privileged methods, proscribes the ways in which such data may be viewed or changed. The balance data of bankAccount can only be changed by withdraw or read by checkBalance, in one sense, because it may not be accessed directly.

Place-Oriented Programming #

Nevertheless, object-oriented and imperative programming share a fundamental orientation towards places in memory.

But mutable objects are actually abstractions of places. They do not actually have meaning other than that. They are little barricades we have set up in front of memory, so that we do not have to directly manipulate memory addresses any more. So we have this abstraction that is an object, that helps us manipulate that place without too much craziness…So I have a new label for this. It is called PLOP, and PLOP is place-oriented programming. — Rich Hickey, The Value of Values

A method call to withdraw effectively overwrites a balance reference

const bankAccount = new BankAccount(100); // (this.balance = 100)
bankAccount.withdraw(20); // (this.balance = this.balance - 20)

just as any direct assignment that circumvents a method.

let balance = 100;
balance = balance - 20;

A mutable variable underlies the reassignment in both cases, whether or not an object method mediates such reassignment, and a place in memory underlies every mutable variable.^[2]

Functional Programming #

Procedures that produce the same result when provided the same argument can be viewed as computing mathematical functions. For example, a decrement100 procedure in JavaScript,

const decrement100 = function (x) {
  return 100 - x;
};

decrement100(20); // 80

or, more succinctly,

const decrement100 = (x) => 100 - x;

decrement100(20); // 80

can be viewed as computing the mathematical function f(x) = 100 — x:

f(20) = 80; where f(x) = 100 - x

since the return value of decrement100 depends only on the input value just as f(x) depends only on x. Invoke decrement100 a second time with 20 and it will return 80 once again, regardless of time and place within a program’s runtime. By contrast, an alternative implementation

let oneHundred = 100;
const decrementOneHundred = (x) => oneHundred - x;

decrementOneHundred(20); // 80
oneHundred = 80;
decrementOneHundred(20); // 60

involving a mutable binding does not model computing a mathematical function, since its behavior may depend on variable information in addition to its input. Invoke decrementOneHundred a second time with 20 and it will not return 80 once again when such binding is intermediately reassigned.

Functional procedures are not limited to numbers. Procedures that involve character strings, for example,

const space = (w1, w2) => `${w1} ${w2}`;

space("hello", "world"); // => "hello world"

a list of strings,

const space = (w1, w2) => `${w1} ${w2}`;
const sentence = (words) => `${words.reduce(space)}.`;

sentence(["i", "heart", "functions"]); // => "i heart functions."

or other arbitrary data types and compositions may return the same value provided the same argument. Larger functional procedures can be composed of smaller ones,

const square = (x) => x * x;
const sum = (x, y) => x + y;

const sumOfSquares = (x, y, z) => sum(sum(square(x), square(y)), square(z));

sumOfSquares(1, 2, 3); // 14

as can programs themselves.

const square = (x) => x * x;
const sum = (x, y) => x + y;

// PSUEDO CODE
sum(sum(square(USER_INPUT_1), square(USER_INPUT_2)), square(USER_INPUT_3));

// REPL PSUEDO CODE
// > run functionalProgram.js with USER_INPUT_1=1, USER_INPUT_2=2, USER_INPUT_3=3,
// > 14

When the output of one functional procedure becomes the input of another, the wrapping program or procedure itself can be viewed as computing a mathematical function; a second run with the same input results in the same output.^[3]

Semantics, Not Syntax #

Syntactic constructs like this, new, class, private and public clearly express object-oriented intent — this instance of a class of things privately maintains data through publicly available APIs — and are common to object-oriented programming languages. However, they are not necessary. Object-oriented semantics may be achieved with nontraditional syntax. For example, this bankAccount object also stores the balance data privately;

const makeBankAccount = (balance) => ({
  withdraw: (amount) => (balance = balance - amount),
  checkBalance: () => balance,
});

const bankAccount = makeBankAccount(100);
bankAccount.withdraw(20);
bankAccount.checkBalance(); // 80

balance is accessible only through the functions checkBalance and withdraw, which proscribe the manner in which such access can occur. bankAccount behaves like a “bank account” even though the functions checkBalance and withdraw have gained privileged access to private data through the use of a function closure, instead of through explicit syntax. Object-oriented syntax is also insufficient in and of itself to achieve object-oriented semantics. A bankAccount “object” that avoids maintaining any underlying balance state

class BankAccount {
  public withdraw(balance, amount) {
    return balance - amount;
  }

  public checkBalance(balance) {
    return balance;
  }
}

const bankAccount = new BankAccount();
bankAccount.withdraw(100, 20); // 80
bankAccount.checkBalance(100); // 100; whoops, shouldn't this be 80?

allows “its” balance to evolve in an unspecified manner, undermining the “bank account” abstraction. new, class and public constructs belie the actual semantics in this case. The same can be said of a bankAccount object that publicly exposes the balance attribute, as was alluded to above.

class BankAccount {
  public balance; // <-- now public

  constructor(funds) {
    this.balance = funds;
  }

  public withdraw(amount) {
    this.balance = this.balance - amount;
  }

  public checkBalance() {
    return this.balance;
  }
}

const bankAccount = new BankAccount(100);
bankAccount.balance = 80;
bankAccount.checkBalance(); // 80, eventhough no funds have been withdrawn

Now, balance can magically change without a withdrawal ever having occurred, which undermines the “bank account” abstraction. new, class and public constructs belie the actual semantics in this case.^[4]

With functional programming, syntax is also beside the point. The use of functional syntactic constructs is necessary to perform computation against arguments. function and => (the “arrow function”) constructs may express functional programming intent as well. However, they cannot alone achieve functional semantics. Indeed, a method of an object may use the => construct without correctly modeling computing mathematical functions.

const makeBankAccount = (balance) => ({
  withdraw: (amount) => (balance = balance - amount),
  checkBalance: () => balance,
});

Subsequent calls to checkBalance return different results despite identical inputs (i.e. undefined) by design.

const bankAccount = makeBankAccount(100);

bankAccount.checkBalance(); // 100
bankAccount.withdraw(20);
bankAccount.checkBalance(); // 80

Additionally, an alternative implementation of “decrement one hundred” in JavaScript may fall short of correctly modeling a mathematical function even though an => construct is used, as was alluded to above.

let oneHundred = 100;
const decrementOneHundred = (x) => oneHundred - x;

decrementOneHundred(20); // 80
oneHundred = 80;
decrementOneHundred(20); // 60

Invoking this procedure a second time with the same argument produces a different result when the let binding is amended between invocations.

Changeability is Fundamental to Object Semantics #

Since objects can change - an apple can be bitten, a house painted, and a bank account withdrawn from - effective object representations must follow suit.

[W]e make computational objects…whose behavior changes with time. We model state with local state variables, and we model the changes of state with assignments to those variables. — SICP Section 3.1.2

biteing an apple changes bites state, painting a house changes color state and withdrawing from a bankAccount changes balance state. The class implementation of a bank account object

class BankAccount {
  private balance;

  constructor(funds) {
    this.balance = funds;
  }

  public withdraw(amount) {
    this.balance = this.balance - amount; // <-- assign `this.balance` a new value
  }

  public checkBalance() {
    return this.balance;
  }
}

const bankAccount = new BankAccount(100);
bankAccount.withdraw(20);
bankAccount.checkBalance(); // 80

involves overwriting balance as much as the closure implementation does.

const makeBankAccount = (balance) => ({
  withdraw: (amount) => (balance = balance - amount), // <-- assign `balance` a new value
  checkBalance: () => balance,
});

const bankAccount = makeBankAccount(100);
bankAccount.withdraw(20);
bankAccount.checkBalance(); // 80

As mentioned above, a stateless “object” (e.g. bankAccount) that avoids maintaining any underlying state (e.g. balance)

class BankAccount {
  public withdraw(balance, amount) {
    return balance - amount;
  }

  public checkBalance(balance) {
    return balance;
  }
}

const bankAccount = new BankAccount();
bankAccount.withdraw(100, 20); // 80
bankAccount.checkBalance(100); // 100; whoops, shouldn't this be 80?

also avoids modeling any underlying object (e.g. “bank account”).

Unchangeability is Fundamental to Functional Semantics #

On the other hand, changeable things undermine functional semantics. The decrement100 procedure can be viewed as computing a mathematical function because its output depends only on its input; there is no other variable information on which it depends. By contrast, as the value of the mutable let binding underlying decrementOneHundred changes, so does the behavior of decrementOneHundred as a side-effect. Consequently, decrementOneHundred depends on the ongoing value of some contextual thing in addition to its input x and cannot resemble computing a mathematical function.

Conversely, unchangeability restores functional semantics. No contextual changes means no side-effects, and no side-effects means functional behavior:

So long as we do not use assignments, two evaluations of the same procedure with the same arguments will produce the same result, so that procedures can be viewed as computing mathematical functions. Programming without any use of assignment…is accordingly known as functional programming. — SICP Section 3.1.3

Even an externally scoped variable cannot change the semantics of decrementOneHundred when unchangeable.

const oneHundred = 100; // <-- now a `const` instead of a `let`
const decrementOneHundred = (x) => oneHundred - x;

decrementOneHundred(20); // 80
// oneHundred = 80; <-- would be runtime error: "TypeError: Assignment to constant variable."
decrementOneHundred(20); // 80

Since JavaScript’s const binding endows oneHundred with immutability, it simply cannot change (without throwing a runtime error). And without change, the output of decrementOneHundred can depend only on the single thing that can: its input.^[5]

“Object” Names Changeability #

Moreover, changeability implies an object. The rational number “2/3” cannot change, for example. Change the denominator of “2/3” from 3 to 5 and its identity changes as well to “2/5”. Neither can the integer “24.” Increase the number of units represented by “24” and it may change to “25.”

const HOURS_IN_DAY = 24;

/**
 * NOT VALID; imagined API for mutating numbers
 */
24.increment();

HOURS_IN_DAY === 25; // true

The rational number “2/3” and the integer “24” are unchangeable things, and are not recognizable as objects. Similarly, change the molecular construction of “iron” and it may very well change to “gold,” or the wave length of “green” and it may change to “red”. Conversely, find changeability and find an object. A cup that is two-thirds full of water can be poured, an iron rod can be dented and a green house can be painted. “That cup” remains that cup notwithstanding less water; “that rod” remains that rod notwithstanding a dent; “that house” remains that house notwithstanding a fresh coat of paint. A “cup”, “rod” and “house” are changeable things that are recognizable as objects. Coincidence of “changeability” and “object” is not happenstance. That parts can change without changing the identity of the whole distinguishes an identity distinct from underlying parts. Changeability distinguishes an object. “Object” in a sense articulates this ability to change.

Said another way, a new notion of “sameness” emerges with changeability. Unchangeable things can be identified as “the same” simply by examining contents. For example, because immutable rational number implementations, r1 and r2,

type RationalNumber = readonly [
  number /* numerator */,
  number /* denominator */
];

// turn into decimal form before comparing in order to reduce fraction
const isEqual = (a: RationalNumber, b: RationalNumber) =>
  a[0] / a[1] === b[0] / b[1];

const r1: RationalNumber = [2, 3];
const r2: RationalNumber = [2, 3];
const r3: RationalNumber = [2, 5];

isEqual(r1, r2); // => true
isEqual(r1, r3); // => false

will always be comprised of 2 in the first slot and 3 in the second and reduce to two-thirds, a reasonable conclusion is that they are the same. To be sure, substitute one for the other and the meaning of a program is unchanged.^[6] By contrast, consider when two mutable rational number implementations may be deemed the “same.”

type RationalNumber = [number /* numerator */, number /* denominator */];

// turn into decimal form before comparing in order to reduce fraction
const isEqual = (a: RationalNumber, b: RationalNumber) =>
  a[0] / a[1] === b[0] / b[1];

const r1: RationalNumber = [2, 3];
const r2: RationalNumber = [2, 3];
const r3: RationalNumber = [2, 5];

r2[1] = 5;

isEqual(r1, r2); // => false
isEqual(r2, r3); // => true

r1 may have the same contents as r2 to start, but this affect is shortly lived. Substitute one for the other and the meaning of the program is changed — references to r2 now incorrectly reduce to two-fifths instead of two-thirds. r1 and r2 are not exactly “the same” in this case. Since two changeable things may evolve independently notwithstanding an analysis of parts performed at any one point in time, a new notion of “sameness” above an examination of parts must be admitted. Remarkably, this “new” notion is less remarkable with intentional object-oriented programming, where the creation of a new identity — i.e. an object — is precisely the goal. georgesAccount and elainesAccount, for example,

/**
 * Reference equality check
 */
const areAccountsEqual = (a: BankAccount, b: BankAccount) => a === b;

const elainesAccount = new BankAccount(100);
const georgesAccount = new BankAccount(100);

elainesAccount.checkBalance(); // 100
georgesAccount.checkBalance(); // 100

areAccountsEqual(elainesAccount, elainesAccount); // true
areAccountsEqual(elainesAccount, georgesAccount); // false (eventhough identical funds)

georgesAccount.withdraw(75);

elainesAccount.checkBalance(); // 100
georgesAccount.checkBalance(); // 25

areAccountsEqual(elainesAccount, elainesAccount); // true
areAccountsEqual(elainesAccount, georgesAccount); // false

may share a balance at some point in time. But even if they start with the same funds, georgesAccount and elainesAccount can register different balances at some other point in time because they are in fact different objects. Of course, that two distinct objects can evolve independently goes without saying. That is because “object” clearly articulates the creation of an identity that is not tied to any part, arrangement or quality; “object” names the ability to change.^[7]

Diametric Opposites #

In this light, object-oriented programming can be seen as the diametric opposite of functional programming. Objects are inherently changeable. Moreover, changeability and “object” are intertwined as concepts. Yet, changeability undermines functional programming. Just as oil cannot inhabit the same physical space as water, object-oriented programming cannot occupy the same virtual space as functional programming. Use of one excludes the other. As a result, when writing programs, we may choose mutability or immutability, objects or functions, but not both at once.

Programs Though! #

Thus far, we have only shown excerpts; the remainder of any surrounding program has been omitted. Of particular concern, our functional excerpts have been stateless. Some complete programs are stateless, designed to produce output based solely on input - compilers ideally output the same binaries provided the same input files. More frequently, however, programs require state. Some input together with the current state of the program determine the output (or next state) of the program. Such is the case with our ATM example, where the current balance is crucial to calculating any subsequent balance post withdrawal. To be generally useful, a programming paradigm should include a model for state.

Stateful Object-Oriented Programs #

Modeling with objects is powerful and intuitive, largely because this matches the perception of interacting with a world of which we are part. — SICP Section 3.5.5

Creating stateful object-oriented programs is straightforward. An ATM program, for example, that allows the user to set a “withdrawal amount” and effect a withdraw,

decomposes naturally into withdrawalAmount and and bankAccount objects, representing the chosen amount to be withdrawn and the user account underlying the session, respectively. The withdrawal amounts are incorporated by and read from withdrawalAmount. Withdrawals are incorporated by, and balance confirmations are read from, bankAccount. The current balance and the amount to potentially withdraw — the state of the program — are reflected directly by the state of bankAccount and withdrawalAmount — the state of its composite objects.

Time #

If we wish to write programs that model this kind of natural decomposition in our world (as we see it from our viewpoint as a part of that world) with structures in our computer, we make computational objects that… must change with time. — SICP Section 3.5.5

When we model objects, we also model time. Objects change — as we discussed, the notion of an “object,” having parts that change without changing the identity of the whole, articulates this ability. The flip-side to changing objects is time. Since objects change, when an object is examined is vital to the examination, it goes without saying.

Look no further than the object representations of our computer programs. The “having parts that can change without changing the identity of the whole” quality of bankAccount in our ATM program, for example, is implemented by withdraw.

class BankAccount {
  ...
  public withdraw(amount) {
    this.balance = this.balance - amount;
  }
  ...
}

Underlying withdraw lies a mutable balance binding that may be assigned new values. Calls to withdraw change the associated balance of bankAccount as a side-effect, without altering the identity of bankAccount, by design.

const bankAccount = new BankAccount(100);

bankAccount.checkBalance(); // 100
bankAccount.withdraw(20);
bankAccount.checkBalance(); // 80

The flip-side to changing objects is time. In addition to changing the associated balance, any call to withdraw also “delineates moments in time” when balance may change. Whether bankAccount.checkBalance() resolves to 100 or 80 “depends not only on the expression itself, but also on whether the evaluation occurs before or after these moments.” As a result, by modeling objects, “we are forced to admit time into our computational models.” (SICP Section 3.4)

Stateful #

Object-oriented programming reifies objects. Further, objects can be composed in other objects, received by object methods, and generally manipulated like numbers, strings and other first-class citizens of the program. No such affordances are made for state, on the other hand. State is a quality (i.e. “stateful” or “statefulness”) adjacent to objects. Unlike the objects to which they belong, state can only be observed at runtime, rather than expressed through language.

bankAccount and withdrawalAmount identify objects, for example. They can be composed in other objects, received by object methods and generally manipulated like other first-class citizens of the program. By reifying these objects, however, balance and amount state are relegated to object qualities, observable at runtime only through calls to bankAccount.checkBalance and withdrawalAmount.get.

That objects indeed lack any express notion of state is highlighted by object signatures with more than one getter, where any such notion may only exist through definition, signature by signature:

How can you perceive a mutable object that has more than one getter? … How do you it? … Who could say right now how to do this? No one can, right? You cannot do this, because you need this other thing. You need the recipe for doing this, and the recipe is something that everybody has to make up over and over and over again. … We cannot actually perceive the whole. Cannot do it without help. Without these recipes. — Rich Hickey, The Value of Values

An object with a single read method (like bankAccount) in a sense defines the method for accessing the whole of an object’s state. However, each additional read method dilutes this claim, underscoring the need for a method specific to the task (e.g. toJSON, serialize, inspect, etc.). In stark contrast to numbers, string and objects themselves, state may be expressed only through programmer-defined constructs evaluated at runtime.

Stateful Functional Programs #

Is there another approach? Can we avoid identifying time in the computer with time in the modeled world? Must we make the model change with time in order to model phenomena in a changing world? — SICP Section 3.5

Building stateful functional programs is less straightforward. To start, notice that imperative iteration can be restructured into functional iteration by recursively calling an iterative function with the results of the previous call. An imperative implementation of factorial, for example,

const factorial = (n) => {
  let total = 1;
  while (n > 0) {
    total = total * n;
    n = n - 1;
  }
  return total;
};

factorial(0); // => 1
factorial(1); // => 1
factorial(2); // => 2
factorial(3); // => 6

maintains iteration and running total state through assignments to n and total, respectively, with every iteration. An alternative implementation avoids mutation by returning the iteration and running total state from an iteration function,

const factorial = (n) => {
  const iterate = (total, i) => {
    if (i === 0) return total;
    return iterate(total * i, i - 1);
  };
  return iterate(1, n);
};

factorial(0); // => 1
factorial(1); // => 1
factorial(2); // => 2
factorial(3); // => 6

which may be used by the same function to calculate the next values in the next iteration.

Stateful functional programs can be constructed in a similar fashion — state that is returned from the previous turn of some larger, iterative “program” function becomes the starter state for the next — with one caveat. With synchronous iteration, results of the previous run can simply be passed to the next. The total result from factorial iteration, for example, is passed directly to the next. In a JavaScript web application, however, events are initiated asynchronously as the user interacts with the page, calling callbacks bound to such events, which run pieces of the program so encoded.

event → callback → javascript
event → callback → javascript
...

Communication between asynchronous scripts is performed through shared references. One script updates (mutates!) a place in memory from which another script may later read. Look no further than the object-oriented ATM program above for a concrete example. A user may begin the program by first selecting a withdrawal amount, then clicking withdraw:

select → onchange → "withdrawalAmount.set(value)"
click → onclick → "bankAccount.withdraw(withdrawalAmount.get())"
...

The “click withdraw” script occurs asynchronously sometime after the “select withdrawal amount” script has completed. Communication between the two scripts occurs through shared reference to the amount variable underlying the withdrawalAmount object. Calls to withdrawalAmount.get() will return updates by withdrawalAmount.set(value), notwithstanding the asynchrony of such reads and writes.

Synchronous functions can communicate by simply passing around results. The result from one function becomes the input of another. Asynchronous scripts, by contrast, share a mutable place in memory instead of the values themselves. Consequently, we must also share a mutable place in memory to communicate between asynchronous scripts in the functional program implementation. On the other hand, with a light amount of infrastructure, we can usher such imperative code to the application perimeter and carve out space for a functional core, creating a “functional core, imperative shell.”

The program now consists of functions parseInt and withdraw, called against specific events WITHDRAWAL_AMOUNT and WITHDRAW. The state of the program has not been reflected directly into distinct objects. Instead, a program function is called with the state resulting from the previous call, together with event data from any user interaction, in order to produce the starter state for the next. program resembles an iterative, recursive function. Yet, calls to program occur asynchronously. Just as with the object-oriented ATM program, a user may begin the functional ATM program by first selecting a withdrawal amount, then clicking withdraw:

select → onchange → "store.publish('WITHDRAWAL_AMOUNT', {amount:value})"
click → onclick → "store.publish('WITHDRAW')"
...

The imperative shell (i.e the store) maintains a reference to the state resulting from the previous call to program, in order to pass such state to the next, orchestrating communication between asynchronous calls to program.

Time as a Series of States #

Unlike object-oriented programming, functional programming provides no model for traditional time. Mathematical functions are timeless. Computation of a function f(x) a “second time” with the same argument will produce the same result whenever computed; a mathematical statement like f(20) = 80 will not be made any less true by insinuating time. Similarly, time is no matter against procedures that model mathematical function computation. Simple functions,

const decrement100 = (x) => 100 - x;

decrement100(20); // 80

compositions of functions,

const square = (x) => x * x;
const sum = (x, y) => x + y;

const sumOfSquares = (x, y, z) => sum(sum(square(x), square(y)), square(z));

sumOfSquares(1, 2, 3); // 14

as well as “program” functions like the ATM program introduced above,

const withdraw = (balance, amount) => balance - amount;

const ATM = (state = { balance: 100, amount: 10 }, event) => {
  switch (event.type) {
    case "WITHDRAW":
      return {
        ...state,
        balance: withdraw(state.balance, state.amount),
      };
    case "WITHDRAWAL_AMOUNT":
      return {
        ...state,
        amount: parseInt(event.amount),
      };
    default:
      return state;
  }
};

will produce the same output provided the same input whenever evaluated, independent of time.

Where we once saw object state change as time elapsed, we now see the program jump from one state to the next at individual (i.e. discrete!) moments in time, as if producing entries in a list, log, “stream of information,” or other time-denominated series. Iterative, recursive functions model this same behavior. The functional factorial implementation shown above, for example, produces a value, say F, for each step, say i:

F₀: 1
F₁: 1
F₂: 2
...
factorial(i): iterate(Fᵢ₋₁ * i, i - 1)

Each run of iterate against the result of the previous run produces a new value just after the last — a discrete piece of information that can viewed together with the rest on the same list. Individual program events can be similarly listed,

E₀: DEFAULT_EVENT
E₁: WITHDRAWAL_AMOUNT, amount:20
E₂: WITHDRAWAL
...
E(i): Eᵢ

as can individual program states:

S₀: balance:100, amount:10
S₁: balance:100, amount:20
S₂: balance:80, amount:20
...
S(i): program(Sᵢ₋₁, Eᵢ)

Each run of program against the result of the previous run, together with event data, produces a new value after the last. Yet, program is a timeless function.

With the object-oriented approach, we decompose the state of the program into objects within the program. Each object houses mutable state, and each piece of state may underly a mutative expression that “delineates moments in time” when evaluated.

We modeled real-world objects with local state by computational objects with local variables. We identified time variation in the real world with time variation in the computer. We implemented the time variation of the states of the model objects in the computer with assignments to the local variables of the model objects. — SICP Section 3.5

A collection of objects, each delineating moments in time when state may change within the program, embeds a simulation of time within the program. By contrast, with the functional approach, state is kept at the application perimeter and functions are composed together in order to transition the program from one state to another. No simulation of time can be found within the program; no moments can be found within the program when state may change. Rather, the program provides change from one state to the next (i.e. it produces state). As a result, program states represent discrete moments in time when state has changed.

Think about the issue in terms of mathematical functions. We can describe the time-varying behavior of a quantity x as a function of time x(t). If we concentrate on x instant by instant, we think of it as a changing quantity. Yet if we concentrate on the entire time history of values, we do not emphasize change — the function itself does not change — SICP Section 3.5

Said another way, in object-oriented programs, we hold the identity of objects constant through change. Objects endure change as time elapses, and thus we model time. In functional programs, we forgo object identity. Change creates something new instead of altering something of old, and thus we model change directly. Change is described succinctly by functions as well as by an “entire time history,” list, log, stream, or other series of resulting states.

Reified State #

Unlike object-oriented programs, functional programs reify state. State can be passed to functions, returned by functions, and generally manipulated like numbers, strings, lists, and other citizens of the program. With a small addition to the ATM program, for example,

we can print (to the console) a representation of the each state of the program in sequence. This change is trivial precisely because state is a known quantity of the program and generally manipulable by program code. inspectReturn takes direct advantage of this quality, printing state to the console and returning state from the internal curried function.

Resolving the Time Paradox #

“No man can ever cross the same river twice.” Because what’s a river? I mean, we love this idea of objects; like there’s this thing that changes. Right? There’s no river. Right? There’s water there at one point-in-time. And another point-in-time, there’s other water there. — Rich Hickey, Are We There Yet, quoting Heraclitus.

From the perspective of a user, a functional program may appear stateful. Interact with the functional ATM program above and notice the program remembering previous encounters. On the one hand, this is not surprising. We included an imperative layer to remember previous states. Instead of decomposing the state of the program into distinct objects, like bankAccount and withdrawalAmount, we created a single global object, the store. On the other hand, focusing on the “object” portion of the program betrays an object-oriented predisposition. The imperative piece of the program is merely a construct used to facilitate a computation based asynchronously on another. One can even imagine a programming language where such a construct is built into the language itself, hiding any imperative implementation from the programmer’s view. In fact, such a language exists that compiles to JavaScript.^[8] In other words, it is syntax, not semantics. The semantics of the program better align with the semantics of a recursive, iterative function, having state S at a discrete step i — run the functional ATM program with the output of the previous run to produce the input for the next.

That a program with a functional, stateless and timeless core can maintain state is surprising, to say the least. Look around the room, bus, park or wherever you find yourself reading this sentence, and you will likely identify “a collection of distinct objects,” such as dogs, people, and trees, “whose behaviors may change over time.” Look around the functional ATM program, on the other hand, and there are no identifiable objects to be found. Yet, the program appears to have state just like any other object in the room.

However, the ostensible paradox dissipates when the augmentation of our conception of time extends beyond the functional program to include the rest of our physical reality.

One way to resolve this paradox is to realize that it is the user’s temporal existence that imposes state on the system. If the user could step back from the interaction and think in terms of streams of balances rather than individual transactions, the system would appear stateless — SICP Section 3.5.5

Instead of viewing the world as the sum of its objects, each reflecting its latest state as time elapses, we may also think in terms of discrete state histories. We may interpret the dog at the park as moving in discrete steps S(i) to S(i+1), just as we interpret the state of our functional program as moving in discrete steps S(i) to S(i+1).

Consider video media. To movie scenes, we may attribute the same object-oriented semantics. Character and inanimate objects shift, interact and evolve as time elapses.

While playing the above video, for example, we may conclude that “a cat is dancing.” Yet, videos are comprised of static frames stitched together in a certain sequence at discrete time intervals. Each frame corresponds to a state of the video at a moment in time and the frames, taken together, a time-denominated series of discrete states. The media chosen above is intentionally “meta”: the video includes a TV animation of a scene mirrored by a flip-book^[9], showing static frames strung together at discrete time intervals, which itself is mirrored by a flip-book in “real” life, showing static frames strung together at discrete time intervals. Take another step back to notice that the above gif media (or mp4 if your browser supports html5) being played on your computer is comprised of static frames, strung together at discrete time intervals.

There is nothing stopping you from taking another step back and interpreting the real world in which your computer currently sits as static frames, strung together at discrete time intervals. We may attribute normal object-oriented semantics to the above gif, concluding that “a cat is dancing.” However, we may also attribute functional semantics, concluding that “a cat has arms above its head on frame fᵢ.” At a park in the real world, we may conclude that “a dog is chasing a squirrel.” However, we may also conclude that “a dog is in the running motion behind a squirrel in the running motion on frame fᵢ.” In both cases, we may identify a time-series of states instead of objects that change over time. The functional programming paradigm can be coherently applied to world and program alike.

With a model for discrete time in mind, it is less surprising that functional programs can appear stateful. A user of the program may be viewed as a series of states, just like the program itself. A specific series of user states, for example,

U₀: "Open up this blog post"
U₁: “Select 20 option”
U₂: “Click withdraw”
...
U(i): Uᵢ

directly precipitate a series of program states:

S₀: balance:100, amount:10
S₁: balance:100, amount:20
S₂: balance:80, amount:20
...
S(i): program(Sᵢ₋₁, Eᵢ)

In both cases, pieces of static information may be listed, one after another. Moreover, both lists can be plotted along the same discrete timeline i. User interactions come in a certain order U(i), triggering a run of the program function against the result of the previous run S(i-1) and event data E(i), in order to produce S(i). Our reality can be viewed as a time-series of states, just as it can be viewed as a collection of objects. Functional programming models a time-series of states, just as as object-oriented programming models objects. When the program and world alike can be viewed as “streams of information that flow in the system,” (Section 3) the world can flow into the program, and the program back into the world.

Addendum: Functional Programming as a Scientific Revolution #

We were all object-oriented programmers at one point in time — Rich Hickey, The Value of Values

Assimilation of functional semantics with any regular conception of the physical world is no easy task. Look again around the room, bus or park and you will likely still identify distinct objects that may change over time. I kicked around chapter 3 of SICP for over a year before wrapping my head around it. That we may still be experiencing disbelief at the thought of a new model for time suggests a larger game at play.

Dominant scientific paradigms pervade our language, on the one hand, and way of thinking, on the other.

Scientific practice always involves the production and the explanation of generalizations about nature; those activities presuppose a language with some minimal richness; and the acquisition of such a language brings knowledge of nature with it. When the exhibit of examples is part of the process of learning terms like “motion,” ‘‘cell,‘‘ or ‘‘energy element,’’ what is acquired is knowledge of language and of the world together. On the one hand, the student learns what these terms mean, what features are relevant to attaching them to nature, what things cannot be said of them on pain of self-contradiction, and so on. On the other hand, the student learns what categories of things populate the world, what their salient features are, and something about the behavior that is and is not permitted to them. In much of language learning these two sorts of knowledge — knowledge of words and knowledge of nature — are acquired together, not really two sorts of knowledge at all, but two faces of the single coinage that a language provides. — Thomas Kuhn, What are Scientific Revolutions?

As a result, a new discovery “that cannot be accommodated within the concepts in use before” may elicit surprise or even disbelief. “One cannot get from the old to the new simply by an addition to what was already known. Nor can one quite describe the new in the vocabulary of the old or vice versa.” (Thomas Kuhn) Rather, in order to “make or to assimilate such a discovery one must alter the way one thinks about and describes some range of natural phenomena”; even the articulation of an observation that runs counter to the dominant paradigm can only be “formulated by altering the language with which nature [is] described.” (Thomas Kuhn)

Consider the compound sentence, “In the Ptolemaic system planets revolve about the earth; in the Copernican they revolve about the sun.” Strictly construed, that sentence is incoherent. The first occurrence of the term “planet” is Ptolemaic, the second Copernican, and the two attach to nature differently. For no univocal reading of the term “planet” is the compound sentence true. — Thomas Kuhn, What are Scientific Revolutions?

Similarly, object-orientation pervades our language, on the one hand. That “objects change as time elapses” is a statement of obvious fact betrays the object-oriented presumption embedded in our language. “Object” (and “identity”), “change” (and “state”), and “time” work together to describe a coherent object-oriented view. On the other hand, objects orient our perception of our own physical reality.

Modeling with objects is powerful and intuitive, largely because this matches the perception of interacting with a world of which we are part. — SICP Section 3.5.5

Look again around the room, bus, park or wherever you find yourself reading this sentence, and you will likely identify “a collection of distinct objects,” such as dogs, people, and trees, “whose behaviors may change over time.”

Yet, the behavior of a functional program cannot be described in terms that attribute change to the enduring identity of objects as time elapses. And because of the dominance of object-orientation as reflected in the presumptions of our natural language, we cannot so much as describe the semantics of a functional program except through altering our language and reconstituting our physical reality. Meaningful “identity” must disappear in favor of change itself. “State” must describe the result of change instead of an object quality. “Time” must describe discrete state changes rather than any continuous dynamicness attributable to all objects.

No wonder the functional model may still elicit disbelief. This essay can be seen as an uphill climb against the gravity of a dominant paradigm; the functional view is perhaps expressible now, but only because of the arduous work put in above. Our natural language is not so easily distorted, violated and repurposed and our thought patterns are comorbid with our language.

Until those changes had occurred, language itself resisted the invention and introduction of the sought after new theories. The same resistance by language is, I take it, the reason for Planck’s switch from ‘‘element’’ and ‘‘resonator’’ to ‘‘quantum’’ and ‘‘oscillator.’’ Violation or distortion of a previously unproblematic scientific language is the touchstone for revolutionary change. — Thomas Kuhn, What are Scientific Revolutions?

As a result, teaching functional programming to anyone is like teaching Copernican astronomy to a Ptolemaic astronomer or quantum mechanics to a Newtonian physicist. We lack the basic language to articulate the underlying concepts. Worse still, the language we do have is endemic to a conflicting paradigm. Perhaps the disparity between the efficacy^[10] and popularity^[11] of functional programming languages is best explained in this light.

A new scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die, and a new generation grows up that is familiar with it — Max Plank, autobiography, quoted by Thomas Kuhn, The Structure of Scientific Revolutions

Nevertheless, the functional view is indeed expressible as a result of the work put in above. We can see change as creating something new, instead of altering something of old, and time as a series of successive states. We can alter our language and reimagine our physical reality to support a functional view of change, state and time.

← Home