Freedom to Tinker

My previous postings on the program vs. data distinction have drawn quite a few comments. (To see them, click the “followups” links on my previous postings.) I’m going to let the conversation settle a bit before commenting again. But just to stir things up, here is another challenging case.

Some programs are never meant to be executed. They do instruct a computer to do something, but their author never intends them to be executed, and they never are executed. Why would somebody write a program that they know will never be executed? Let me explain.

Suppose you are studying mathematical logic, and you want to know whether a particular assertion can be proven from some set of initial axioms. It turns out that there is a deep equivalence between mathematical logic and programming languages, such that a given statement is provable in a logic if and only if a computer program of a certain type exists. It follows that you can show that a statement is provable by demonstrating the existence of a certain type of program. You don’t have to run the program; you just have to show that it is a valid program according to the rules of a particular programming language.

This isn’t just a theoretical parlor trick. Researchers often use this equivalence to show the provability of logical statements by exhibiting the existence of programs. I myself have done this and have published two papers about it. In the course of doing this, I wrote lots of program code, but never once did I run any of it.

If you believe that the author’s intent is what makes something a program, then the code I wrote is not a program, since I never meant it to control a computer (and it never did). If, on the other hand, you believe that program-ness is inherent in the potential capability of the object itself, then my code is a program.

Karl-Friedrich Lenz reacts to my previous posting on how to distinguish programs from data, by insisting on the importance of having a simple definition of “program.” He is right about the value of a simple definition. And he is right to observe that my previous posting doesn’t argue against the existence of such a definition, although it does imply that the definition might be difficult to apply in practice. Lenz suggests a simple definition: “If the object instructs a computer to do something, it is a program. The remaining cases are data.”

Maximillian Dornseif weighs in with a thought-provoking example to show difficulty of applying this seemingly simple definition.

Another troublesome cases arises in logic programming, a style of programming that is implemented by programming languages like Prolog. In logic programming, you don’t tell the computer what to do or even how to do it. Instead, you specify the attributes of an object you want, and the computer figures out how to find or construct such an object. You state facts and relationships, and then you ask a question. At no point do you tell the computer what steps to execute or how to go about doing anything; that is all handled by a pre-packaged program called the Prolog Interpreter. Computer scientists talk about Prolog programs, but a Prolog program doesn’t seem to meet Lenz’s definition.

Now, we might try to stretch Lenz’s definition by saying that the Prolog program, even if it is only a listing of facts, does “instruct” the computer to do something, because the programmer wrote it knowing that it would cause the computer to behave in a certain way. But such a definition is too broad. A Word document is written with the purpose of causing the computer to do something, but that doesn’t make it a program. Besides, it seems unsatisfactory to call something a program or not based on the state of mind of its author.

Still, I’m not giving up on the quest for a simple definition.