Ancient Scrolls and Mystical Tomes
Several months ago I embarked on an epic adventure down a deep, twisting rabbit hole. I became a wild-eyed wizard, poring over ancient tomes of forbidden knowledge, searching for lost secrets that were best left unknown.
OK, this is going to require a bit of background: In college, my Intro to CS course used Structure and Interpretation of Computer Programs and Scheme. I’ll admit it, at first I hated Scheme. It was awkward, uncomfortable, and felt like I had to program everything inside out. And don’t get me started on parentheses—I hate to think about the hours I lost because I didn’t pair them properly.
However, something unexpected happened. I ended up TAing the same course for over two years. Turns out, the second time through, I had more context and could better appreciate Scheme. By the second term, I was digging into Common Lisp, and after the third term, I was using Lisp for my own projects whenever possible.
My main limiting factor was always the GUI. I’ll admit, I’m something of a GUI snob—especially when it comes to Mac software. As a hard-core Mac user, I want my apps’ GUI to support all of macOS’s built-in features. I hate using non-native GUIs or web interfaces, It feels like I’m working while wearing oven mitts. As a result, any attempts to create a GUI in Lisp always left me disappointed. I often felt that building a backend in Lisp and a native interface with SwiftUI would give me the best of both worlds, but I haven’t had good reason to explore it (yet).
Still, every couple of years I would get the itch to brush up on my Lisp skills. Each time, I dug a bit deeper and uncovered more secrets. My appreciation for the language grew. I loved the way it forced me to bend my thinking in odd and unusual ways. After all, learning to think about problems in new ways is always useful, regardless of what language you use.
So, about six months ago, I began digging deeply into Lisp metaprogramming. I started with On Lisp, then dug into Let Over Lambda, The Art of the Metaobject Protocol. and others. The Let Over Lambda chapter, “Lisp Moving Forth Moving Lisp,” was particularly intriguing. It described implementing a simple Forth compiler in Lisp.
Now, I vaguely remembered trying Forth back when I was programming a ZX81 attached to an old black-and-white TV—but I couldn’t remember much except the name. Doug Hoyte described Forth as a language that—while different from Lisp—shared many important characteristics: most notably, powerful tools for metaprogramming. As a result, I ended up reading Starting Forth, Thinking Forth, and A Problem Oriented Language: Forth – how the internals work.
During this quest, I often found myself digging through information from the 70s, if not earlier. Many of the resources existed only as physical books—often only as used physical copies. It felt both odd and amazing, to pore over their yellowed pages, absorbing insights from the dawn of computer science. Surprisingly, there’s a lot we can learn from these languages, even if we never actually code in them. They shed an interesting light on today’s programming languages—and they hold surprising secrets that modern programming languages are still rediscovering.
History of Lisp
John McCarthy began developing Lisp in the late 50s. It is hard to pin down an exact date because he had been developing the core ideas for years. But let’s set the date to 1960, when John published an article describing the language: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (as an aside, he never published Part 2).
At the time, John and his graduate students handwrote M-expressions, a meta-language that looked like Fortran, but included many features that Fortran lacked and used characters not available on the IBM keypunch. Instead, the students converted these into S-expressions (symbolic expressions) that used Lisp’s now-infamous parenthesized lists of lists and atoms. Finally, they hand-converted the S-expressions into machine code, which they could run on the IBM 704.
These handwritten S- and M-expressions served as a convenient tool for John and his graduate students to explore and develop ideas. However, one night one of the graduate students, Steve Russell, realized that their existing eval function could act as a general interpreter for S-expressions. So, to avoid the tedious task of hand-converting back and forth between S-expressions and machine code, he wrote the first Lisp interpreter essentially overnight. Fortunately, no one had told him that creating a new computer language was a massive, difficult process best left for specialists.
John’s team never intended to use S-expressions as a programming language. They had planned to continue developing M-expressions into a more precise language which they could then compile. In History of Lisp, John said, “The unexpected appearance of an interpreter tended to freeze the form of the language, and some of the decisions made rather lightheartedly for the Recursive functions … paper later proved unfortunate.”
The simple cons cell is one example of how early decisions based on existing hardware influenced Lisp’s long-term development. The IBM 704 had a 36-bit word, which it further divided into two 15-bit sections, called the address and the decrement. Additionally, it used 15-bit addresses for words and had special instructions to access both the address and the decrement portions of a word. This structure conveniently matched Lisp’s basic building block, the cons cell.
A cons cell is an ordered pair. In a basic list, the first item in the pair represents the cell’s value. The second item points to the next cons cell in the list. During the early planning and development, John and his team used the abbreviations car (contents of the address register) to refer to the first item in a cons cell and cdr (contents of the decrement register) to refer to the rest of the list (Clearly, in the late 50s, people didn’t put the same emphasis on expressive, meaningful names that we do today).
Flash forward 60+ years and car and cdr are still used extensively in Lisp (though Lisp also has more modern aliases, first and rest that you can use instead). In fact, we can tie many of the odd aspects of Lisp directly back to its accidental creation as a programming language. Most importantly, however, as more and more people began using Lisp, they found that the simple structure of S-expressions has significant advantages over other language syntaxes. Despite multiple attempts at “improving” the syntax, S-expressions remain.
Lisp gained popularity among early artificial intelligence researchers, and it is still used today. Many people (like myself) find the discovery of Lisp an eye-opening, mind-expanding experience. Lisp has even spawned multiple more modern variants, such as Scheme, Clojure, and Julia.
The History of Forth
Charles Moore started developing Forth in 1968 to automate telescopes and other scientific instruments at the National Radio Astronomy Observatory. He then shared it with other people working at NRAO in the early 70s.
I believe Charles originally saw Forth as less of a programming language and more as a system for solving problems. In his book, A Problem Oriented Language: Forth – how the internals work, he tells readers that they should create their own programming language—one explicitly designed to fit the problem they are trying to solve. He then walks the reader through the steps needed to implement a simple version of Forth.
As a stack-based language, Forth avoids the overhead of setting up and tearing down functions. In theory, this should make it faster than C. However, the increasing complexity of modern computer systems means Forth may not be able to take full advantage of all the CPU’s available power. A Forth program may not be able to take advantage of branch prediction, vector processing, or the GPU. Even the efficiency of threading can vary between implementations. Still, Forth produces tiny executables, especially compared to modern programming languages.
Forth gained popularity in the 80s because its speed and small size worked well on the limited memory available to computers at the time. It continues to be popular on embedded processors, firmware, and anywhere else where size and speed are critical. There is even a modern, post-apocalyptic version of Forth: Collapse OS so people can continue to use existing microcontrollers after the inevitable collapse of civilization.
Unfortunately, because Forth is so easy to implement, many people have implemented their own version. Many, many people. As a result there is a wide range of implementations. The Forth community tried to create standards, leading to FORTH-79 and FORTH-83. They then released an ANSI standard in 1994 and updated it in 2012. However, the old adage remains true. If you learn one version of Forth, you know one version of Forth.
Uncommon Common Features
Both Lisp and Forth share features that are unusual in modern programming languages. These languages expect a different relationship between the developer, the hardware, and the programming language. One indication is that their documentation refers to someone programming the language as a “user” rather than a “developer”.
This is a subtle difference—but it’s surprisingly significant. Viewing developers as the language’s users blurs the line between using a programming language to create an application and using an application to solve a problem. Emacs is the prime example of this paradigm. Yes, you can use Emacs efficiently without knowing how to code in Emacs Lisp, but knowing the programming language lets you bend the text editor to your will. You can customize it based on the needs of your particular workflow—or even a particular project. The general idea that tools should adapt to their users, rather than forcing users to adapt to the tool, is a common theme throughout both languages.
Ironically, the paradigm of adapting and building tools reminds me of a much older technology—blacksmithing. It’s often said that the forge is the original self-replicating fabrication process. As a blacksmith, you can make a complete set of tools needed to set up a new forge. Historically, apprentices made all their own tools before they left as journeymen. And today, even though it’s often more convenient to buy your tools, you typically customize them. With a little heat and a couple of taps, you can change the angle of the handles on a set of tongs—or adjust the mouth of the tongs to better fit the piece you’re working on. You can take a hammer to a grinder and adjust the shape of its head—in fact, you typically need to dress a new hammer (grind down and soften the edges) before you begin using it. I’ve personally carved down and shaped the handles on all my hammers, customizing them to perfectly fit my grip.
Trust
Lisp and Forth also trust their users (developers) in a way that might make modern programmers uncomfortable. One of Swift’s greatest features is the way it eliminates entire categories of bugs. However, it does so by tightly controlling the features the developer can access. Lisp and Forth don’t have these guard rails. They give you a great deal of power but also expect you to use it responsibly.
Yes, you can do dumb things that break the entire system. I once wrote a reader macro that left my Lisp instance unable to parse Lisp code. I had to force quit the entire environment and relaunch it to get back to a good state. Fortunately, this type of bug is immediately obvious and easily fixed. It’s the more subtle bugs—the ones that occur intermittently and in unrelated parts of your code—that really cause problems.
Open and Extendible
Another example of trust is that both Lisp and Forth are almost completely open and extendible. In Forth, you can replace any of the built-in words (basically Forth’s equivalent to functions). Furthermore, when you remove your custom word, the system automatically reverts to the original definition. Lisp, similarly, lets you change almost every aspect of the system—especially when you are using CLOS (Common Lisp’s object-oriented system). With CLOS, instead of replacing a built-in method, you can add advice—blocks of code that get executed either before or after the original method. This lets you examine and modify parameters passed into a method, alter the return value, or even decide whether the program calls the original method at all.
CLOS also lets you hook into and control the object system. You can observe and change how it creates and destroys objects. For example, you could decide to have a particular class automatically borrow and return instances from a pool, rather than instantiating a new version each time. You can change how method lookup works. How inheritance works. You can change an object’s class. Or add methods to a specific instance. Honestly, I struggle to come up with a reasonable use for many of Lisp’s extensibility features, but I’d rather have them and not need them, than need them and not have them.
Interactive Programming
Lisp and Forth both encourage interactive programming. Both languages run inside a REPL. Traditionally, a user would interactively build and test their code directly in the REPL. When they felt the code was correct, they could save their changes. Companies even created Lisp and Forth machines—computers where the language acted as the computer’s operating system, and you only interacted with the computer through the REPL. Modern versions of Lisp still use a launch image when opening the REPL, and you can save the current state of the REPL as a new image. You can also replace the default launch image with your custom image, letting you control the state of the language when it launches.
Integrated Documentation
Both languages help you access documentation directly in the REPL. You don’t need any additional steps to build the documentation or additional tools to view it. Documentation is an integral part of the language itself.
Forth’s standard defines the documentation requirements for the language, and almost all built-in words are well documented. Unfortunately, like Swift, the documentation is just comments appended to the code in a prescribed way; however, words like words, find, search-wordlist give you different ways to search through the current list of available words, while words like dump and see let you view the word’s code—which includes the documentation comments.
In Lisp, the story is even better. Any time you define an item, you can include a documentation string as an argument. For example, if you create a new function:
(defun my-function () "my-function does not do anything." ; <- This is my-function's document string. nil)
The documentation is part of the code. You can search for potentially useful items using apropos, and then view the document string using the documentation function. Additional functions, like describe and inspect, provide even more information, including the source code when available. You can even change a symbol’s document string, if you really want to.
Personally, while the REPL is great for experimentation and testing, coding in it gets tedious quickly. I prefer to write and save my code in a source file. Fortunately, a good, modern IDE or text editor lets you have the best of both worlds. Often, a quick series of keystrokes lets you select a block of code, compile it, and run it in the REPL. The editor even launches the REPL if you don’t already have one. This lets you easily switch between your source and the REPL as you interact with and test your code.
Accessing documentation and even source code directly from the REPL raises issues of access and privacy. In both Lisp and Forth, it’s virtually impossible to create truly private code. For example, Lisp uses packages to manage related chunks of code. These are similar to Swift’s modules. When you define a new package, you can declare which symbols you export, and those exported symbols define the interface you expect others to use, making them a bit easier to access. However, it doesn’t prevent anyone from using any of the other symbols in your package.
Metaprogramming
Both languages expect you to modify the language to better fit your problem. This is often listed as the key advantage of Lisp—but it took me a long time to really understand it, and longer still before I could use it effectively. The process of writing code that changes the language can go by many different names: metaprogramming, domain-specific languages (DSL), and (in both Lisp and Swift) macros.
The idea of modifying the language to better fit your problem seems simple enough, until you really start to look at it. Turns out, it’s a blurry concept. After all, I can write a function or library in Swift that lets me solve a specific type of problem more easily. What makes metaprogramming different from designing a good library?
To me, metaprogramming means writing code that writes or modifies code. Specifically, it means writing code that can examine, analyze, and modify other code as needed. It is often used to make changes to the way a programming language works—changes that, in other languages, only the engineers developing the language could make. Writing a library adds features to a language, but it doesn’t change the language.
Still a bit vague? Fortunately, there’s a well-known example of metaprogramming in Swift—SwiftUI.
SwiftUI is more than just an API for creating user interfaces; it is an internal DSL for creating them. It makes fundamental changes to how Swift works in the context of SwiftUI code. SwiftUI cannot do what it does with pure Swift code. It requires macros to modify the Swift language itself.
Sure, you could build a similar API in pure Swift and release it as a library—but the resulting code would be much harder to use. Much of SwiftUI’s syntactic sugar wouldn’t exist, and you would probably have to manage and track administrative details that SwiftUI handles behind the scenes. The result would be bulkier, larger, and more difficult to use.
So, if metaprogramming exists in Swift, why do I list it as a primary advantage of Lisp and Forth? Both Lisp and Forth encourage developers to use metaprogramming to solve everyday problems. Swift, on the other hand, reserves macros for special projects. Regular developers are actively discouraged from using macros. For example, look at the Swift Macro API. It’s complex, difficult to use, and you often need to understand several other complex topics—like SwiftSyntax—before you can use it effectively.
Code and Data
Don’t get me wrong. Metaprogramming is a complex topic in Lisp and Forth as well, but those languages have features that make it easier to approach. First, Swift tries to lock down and define exactly what macros can do. You can only interact with Swift through a restrictive API. Again, Lisp and Forth don’t have those guard rails.
Both Lisp and Forth let you easily run code at compile time, as well as letting you compile code at runtime. Specifically, Lisp blurs the line between code and data. Lisp code exists as s-expressions—basically a list of symbols. Take any list in Lisp. If the first symbol has a function associated with it, you can execute the list as a function call. On the other hand, it still just a list of symbols. You can save it, examine it, modify it—anything you could do with any other list.
Syntax
And both Lisp and Forth use a syntax that is incredibly easy to parse. In Forth, the parser breaks code into tokens separated by whitespace. This occasionally makes Forth look extremely odd to modern readers. For example, " This is a string." Notice the space after the first double quotes. that’s because " is a word. Forth needs a space after it to parse it properly. When Forth executes the " word, it scans through the remaining input, looking for the next double quote. It then grabs that input (everything after the space but before the double quote) and stores it as a literal string.
Similarly, Lisp defines everything using nested lists. Each list has an opening parenthesis, a space-separated list of symbols and values, and a closing parenthesis. Symbols can represent both functions and variables, while everything else is a value of some sort (for example, a number, string, or character). There are a few exceptions, such as reader macros, but in general, Lisp keeps its syntax as simple as possible. Remember, the original Lisp users wrote and compiled their code by hand. They needed a structure that let humans keep all the details in their heads as they used it.
As a result, it’s trivially easy to write a parser for either Lisp or Forth; however, there’s no reason to do so. Both languages provide a parser, an interpreter, and a compiler that developers can use in their own code.
Now, a simple syntax is—by modern eyes—somewhat controversial. Lisp and Forth optimize the language for the parser and compiler, not for the human users. On the other hand, almost all modern languages are optimized for the humans reading and writing the code. The common assumption is that code should be easy to read and write, while the computer can manage all the complex details behind the syntax.
However, there are advantages to a simple syntax. Most importantly, it makes metaprogramming much, much easier. If you’ve ever tried to use SwiftSyntax to examine the syntax tree of some Swift code, you know what I mean. Even a simple declaration quickly becomes a nested mess of structures. This makes it much harder to programmatically inspect, generate, or modify Swift code. On the other hand, the simple syntax of Lisp and Forth greatly simplifies metaprogramming.
Ultimately, like most engineering decisions, syntax is a place where you need to make compromises. You need to weigh the costs and benefits of a simple syntax with those of a more readable syntax. For me, I love that the simple syntax lets me use metaprogramming as a primary tools in Lisp (I’ll admit, I haven’t quite mastered it in Forth yet). However, I’m not sure if it would be a significant advantage if it weren’t for Lisp’s general philosophy of openness. If a programming language is locked down and unchangeable, I feel that metaprogramming (and therefore simple syntax) would be much less useful.
Dynamic Variables
Finally, Lisp has another feature that I find incredibly powerful, but almost unheard of in modern programming languages: dynamic variables. Most languages use lexical binding. When you create a variable, it becomes available anywhere within the current block of code. The major advantage of this is that you can see exactly where and how your code uses that variable. If you define a variable inside a function, you can only use it in that function. The only way to get the variable out of the function is to explicitly pass it as an argument or return value.
Dynamic variables are essentially a safer alternative to global variables. You can access them from any block of code. This includes code in other functions or even other files. However, like lexical variables, you can shadow a dynamic variable inside a code block. Any code called inside that block uses the shadowed version of the variable. Then, as soon as that block returns, the variable is automatically reset to the default global value.
OK. Let’s look at an example. Imagine we have a variable named *value*. Now, I want to write a function that uses that variable. With lexical binding, you’d have to define that function in a location where the variable is in scope. A good example is creating a closure that captures the variable.
With dynamic binding, you can define your function anywhere—even in a different file. As long as you call the function while your version of *variable* is in scope, the will access your version. Every function that calls your function can define a separate value for *variable*, or it could just leave it undefined and use the default value.
This is great for tasks like modifying a program’s standard input and output. Lisp defines *standard-input* and *standard-output* as dynamic variables. This means you can redefine them to use your own streams in specific parts of your code, and then call system functions that interact with the standard input streams. Most importantly, the variables automatically revert to the default streams as soon as your code returns.
EnvironmentValues in SwiftUI provides a feature that feels similar. It gives you an option for passing data between layers of your code without having to pass the value as an argument from function to function. However, as far as I can tell, EnvironmentValues act more like global variables. If you change the value anywhere in your code, that change affects all code that uses the value. Dynamic variables limit the effect to just functions called while that particular version is in scope. This means you don’t need to worry about other parts of your code changing the values out from under you.
Lessons for Swift
OK. So, Metaprogramming and extensibility are the killer features of both Lisp and Forth. When used appropriately, these features can greatly simplify your code. For example, in Lisp, a good set of macros can provide a simple interface for an otherwise complex problem. Furthermore, as annoying as Lisp’s parentheses can be, its simple syntax makes it much easier to write macros, making them a tool that average developers can actually use.
Swift, on the other hand, locks down the language and treats macros as a specialty tool that even experienced developers should use only in very special circumstances. However, that doesn’t mean Lisp programmers should have all the fun. I’d like to look at how we can recreate many of Lisp’s most common macros in Swift. But, I’m going to save that topic for a later post.