Substitution vs. State Transition

With a traditional curly-brace language, you have a model of a machine. A program specifies a sequence of state transitions that the machine should go through. When all the state transitions have taken place, the machine is in a final state, and the program is done.

As a programmer, you have to keep a mental model of the state of the machine at various points in the program. Your mental model has to include a temporal element — you have to remember what instruction you are working on, and what comes next. For each instruction, you have to consider the state before and after executing the instruction.

Lisp is very different from this. A Lisp program isn't a series of instructions, it is a tree of symbols. If you don’t use side effects, you can think of the Lisp interpreter as a simple substitution engine that operates on this tree. The interpreter just substitutes symbols with their values. You don’t have to consider any state before and after substitution because substitution doesn’t change anything.

Even if you do use side effects, you can still think of the interpreter as a substitution engine, but the substitution algorithm is more complicated. You will need a mental model that includes state and a temporal component, but it is still basically a substitution model.

Substitution models are easier to reason about than state transition models. This is why Lisp is so powerful. It takes a little practice to get used to programming with a simple substitution model. That’s why Lisp has a learning curve, especially for people who expect, and are used to, a state transition model.

You can also reason about a Lisp program using a state transition model. You can switch between the two models and use whatever mental model is most appropriate for the problem at hand.

You can impose a substitution model on curly-brace language, but it is more difficult. Curly-brace languages are designed to make you think about state transitions — indeed, many such languages force you to use a state transition to accomplish even the most simple conditionals and iterations — and the language doesn’t make it easy to ignore them and focus on the final value.

If Lisp is your first computer language, you learn the simple substitution model first. You’ll eventually have to learn about state transitions because they are needed to explain side effects. But you’ll mostly want to write programs that you can reason about using a substitution model. If you learn a curly-brace language first, you’ll have to think beyond the state transition model you have been taught and are using to reason about programs.

Many people find it difficult to learn how to reason with a new model. After all, the old model should work — it is universal. “Just assign the variable, don’t make me jump through hoops.” People who have a hard time wrapping their heads around substitution will probably find Lisp confusing and frustrating. But some people are able to embrace the substitution model and learn how it relates to the state transition model. These people will find Lisp to be a mind-expanding, powerful, expressive language.