What Is a Program?

What is a program? Is it the source code that a programmer typed? The physical state of the machine on which it is run? Or something more abstract, like the data structures it creates? This is not a purely philosophical question: it has consequences for how programming languages are designed, how development tools work, and what programmers do when we go to work every day.

How much information can we determine about a program without evaluating it? At the high end, we have the Halting Problem: for any Turing-complete programming language, we cannot determine if a given program written in that language will terminate. At the low end, consider an easier problem: can we determine the names of all of the invokable functions/procedures/methods in a given program? In a language in which functions are not first-class entities, such as C or Java, this is generally easy, because every function must have a specific lexical representation in source code. If we can parse the source code, we can find all the functions. At the other extreme, finding all function names in a language like Ruby is nearly impossible in the face of method_missing, define_method, and other “metaprogramming” tricks.

Again, these decisions have consequences. Ruby code is flexible and concise, but it’s hard to parse: ten thousand lines of YACC at last count. I find that documentation generated from Ruby source code tends to be harder to read — and less useful — than JavaDoc.

Here’s another example: can I determine, without evaluating it, what other functions a given function calls? In Java this is easy. In C it’s much harder, because of the preprocessor. To build a complete call graph of a C function, we need to run the preprocessor first, in effect evaluating some of the code. In Ruby — Ha! Looking at a random piece of Ruby code, I sometimes have trouble distinguishing method calls from local variables. Again because of method_missing, I’m not sure it’s even possible to distinguish the two without evaluating the code.

I do not want to argue that method_missing, macros, and other metaprogramming tools in programming languages are bad. But they do make secondary tooling harder. The idea for this blog post came into my head after observing the following Twitter conversation:

Dave Ray: “seesaw.core is 3500 lines of which probably 2500 are docstrings. I wonder if they could be externalized somehow…”

Chas Emerick: “Put your docs in another file you load at the *end* of seesaw.core, w/ a bunch of (alter-meta! #'f assoc :doc "docs") exprs”

Anthony Grimes: “I hate both of your guts for even thinking about doing this.”

Chas Emerick: “Oh! [Anthony] is miffed b/c Marginalia doesn’t load namespaces it’s generating docs for. What was the rationale for that?”

Michael Fogus: “patches welcomed.”

Chas Emerick: “Heh, sure. I’m just wondering if avoiding loading was intentional, i.e. in case someone has a (launch-missiles) top-level.”

(As an aside, it’s hard to link to a Twitter conversation instead of individual tweets.)

Clojure — or any Lisp, really — exemplifies a tension between tools that operate on source code and tools that operate on the running state of a program. For any code-analysis task one might want to automate in Clojure, there are two possible approaches. One is to read the source as a sequence of data structures and analyze it. After all, in a Lisp, code is data. The other approach is to eval the source and analyze the state it generates.

For example, suppose I wanted to determine the names of all invokable functions in a Clojure program. I could write a program that scanned the source looking for forms beginning with defn, or I could evaluate the code and use introspection functions to search for all Vars in all namespaces whose values are functions. Which method is “correct” depends on the goal.

Michael Fogus wrote Marginalia, a documentation tool for Clojure which takes the first approach. Marginalia was inspired by Literate Programming, which advocates writing source code as a human-readable document, so the unevaluated “text” of the program is what it deals with. In contrast, Tom Faulhaber’s Autodoc for Clojure takes the second approach: loading code and then examining namespaces and Vars. Autodoc has to work this way to produce documentation for the core Clojure API: many functions in core.clj are defined before documentation strings are available, so their doc strings are loaded later from separate files. (As an alternative, those core functions could be rewritten in standard syntax after the language has been bootstrapped.)

One of the talking-point features of any Lisp is “all of the language, all of the time.” All features of the language are always available in any context: macros give access to the entire runtime of the language at compile time, and eval gives access to the entire compiler at runtime. These are a powerful tools for developers, but they make both the compiler and the runtime more complicated. ClojureScript, on the other hand, does not have eval and its macros are written in a different language (Clojure). These choices were deliberate because ClojureScript was designed to be compiled into compressed JavaScript to run on resource-constrained platforms, but I think it also made the ClojureScript compiler easier to write.

Chas’s last point about code at the top-level comes up often in discussions around Clojure tooling. The fact that we can write arbitrary code anywhere in a Clojure source file — launch-missiles being the popular example — means we can never be sure that evaluating a source file is free of side effects. But not evaluating the source means we can never be sure that we have an accurate model of what the code does. Welcome back to the Halting Problem.

Furthermore, maintaining all the metadata associated with a dynamic runtime — namespaces, Vars, doc strings, etc. — has measurable costs in performance and (especially) memory. If Clojure is ever to be successful on resource-constrained devices like phones, it will need the ability to produce compiled code that omits most or all of that metadata. At the same time, developers accustomed to the “creature comforts” of modern IDEs will continue to clamor for even more metadata. Fortunately, this isn’t a zero-sum game. ClojureScript proves that Clojure-the-language can work without some of those features, and there have been discussions around making the ClojureScript analyzer more general and implementing targeted build profiles for Clojure. But I don’t think we’ll ever have a perfect resolution of the conflict between tooling and optimization. Programs are ideas, and source code is only one representation among many. To understand a program, one needs to build a mental representation of how it operates. And to do that we’re stuck with the oldest tool we have, our brains.