The Paper Metaphor

Summary: Functional programs follow a simple rule: never write on the same paper twice. Imperative programs are free to define their own rules. Both have interesting consequences.

I just read Functional Programming for Everyone Else by Emily St. It's a good read about the fundamental differences between Turing Machines and Lambda Calculus. Near the end, she mentioned this:

I think of functional programs as ones which do their jobs without stopping to take notes along the way.

That got me thinking of the metaphor of taking notes. It's an interesting metaphor because as she mentions in the article, modern computers are based more on Turing Machines, with their tapes (notes), rather than Lambda Calculus. Lambda Calculus being abstract instead of mechanical (what instead of how), it doesn't show its work.

In the spirit of more perspectives being better than fewer, I'd like to give my metaphor, inspired by idea above. Functional programs are those that have a very simple rule: never write on the same paper twice. In Turing Machine terms, it means never write on the same piece of tape twice. This rule is simple enough that you can build it into the compiler and runtime to enforce it. In programming language theory, we call this immutability. Once a paper is written on, it is immutable.

Imperative programs, on the other hand, don't have such a rule. They can write on any piece of paper, even write over or erase what's written. They rely on their own code to enforce rules for how to organize these pieces of paper so that it still makes sense. They might use locks, which are notoriously hard to get right.

The nice thing about functional programs is you get a nice record of what's happened. You can step through all of the intermediate work because it was never overwritten. It's like an artist keeping their old sketches that led up to their masterpiece. Imperative programs are like finding out that it was all done on the same canvas, art painted over art, irrevocably lost. There is no x-ray to uncover it.

The other nice thing about functional programs is multiple programs can share the same stack of paper. Since they're following a rule, they will never overwrite someone else's work. But imperative programs need to have complex coordination rules to make sure that they aren't writing on the same page at the same time, or overwriting something that someone else will need.