A Language to Build Languages

I’ve been fascinated by computers since before I graduated from high school. One of the early ideas that captured my imagination was the possibility of creating a program that could think like a person. Throughout my career I have pondered the possibility and I have come to the conclusion that while we may be able to write programs that provide the fundamental structures and operations upon which intelligence may emerge, we are far from understanding how intelligence works well enough that we can reproduce it constructively by design. That puts me in the camp that is sometimes labeled emergent AI, although I prefer the term digital intelligence to artificial intelligence.

One of the aspects that I feel will be required for emergent digital intelligence (let’s abbreviate it EDI, shall we), is the ability to introspect, that is, to examine its own thought process. This is something that I have felt for a long time, in fact, for almost as long as I  have been interested in computers. I have always looked for ways that programs could examine themselves. For instance, I was fascinated by the fact that I could write code that examined its own representation in memory and even modify itself while running in Microsoft Basic as early as 1979.

Much of my early introduction to programming was due to a subscription to Byte magazine, an early journal aimed at amateur microcomputer enthusiasts. Every August, Byte published their annual computer language issue in which they explored the features of a different language. I suspect that this was my first exposure to the Lisp language. Lisp is the second oldest high level computer language, predated only by FORTRAN.

It is also the first computer language that focused on symbolic processing instead of being primarily concerned with numerical computation. That is to say, it was written to facilitate the manipulation of lists of symbols. A symbol, in this case, is an arbitrary label or name. For example, you might have a list:

(alice bob ralph sally)

The parenthesis denote the beginning and end of the list. The four names are symbols and make up the elements of the list and they are considered in the order that they are written between the parenthesis, that is alice is the first element of the list, bob is the second, ralph the third, and sally the fourth and final.

Further, Lisp code was represented by lists, just like its data. Consequently, program code could be manipulated by the language as easily as data could. This jumped out at me immediately as giving Lisp the ability to introspect over its own code. Another, more subtle capability of Lisp is the ability to take a list and rewrite it according to a template called a macro. This turns out to be incredibly useful in allowing repetitive operations to be condensed to their essence.

Lisp is typically implemented as an interpreter. It accepts a line of input, processes it and prints a result. This is called a Read, Eval, Print Loop or REPL for short. The reason that I bring this up at this point is to point out that the component that does the Read portion of the REPL is a very interesting piece of the picture. It takes a list of input characters and parses them into symbols and builds them into a small program. It is responsible for recognizing if there are any macros in the list and if so, expanding them into their translations. When it is finished, it has a complete, correct lisp expression to hand to the Eval portion of the REPL. Either that or it detects that something is wrong and prints an error message.

This Read operation is very powerful, even more so in the standard Common Lisp version of the language. In Common Lisp, the Read function is table driven. That means that by substituting a different read table, the reader can parse a language with a different syntax. The implication of this is that Lisp is not only a language, it is a framework for building new languages.

This has been a long story and you may be feeling a little lost by now but the point is that Lisp is exactly the kind of substrate upon which EDI can most easily be built. There are many modern computer languages that implement many, if not most, of the features of Lisp. The point is that Lisp implemented them first and best.

The idea that the structure of a Lisp program is similar to its syntax, a property called homoiconicity by the way, is at the heart of its power and responsible for its longevity. It also make it the prime candidate for building the environment in which EDI will emerge.