Lisp50 Notes part III: McCarthy Reaffirms the Importance of Having Access to the Abstract Syntax

Due to health reasons, John McCarthy could not attend the conference. Alan Kay was (I hear) heading somewhere else in the evening– it would be a tight fit for his schedule if he was going to be there and also make his other “date”. Seeing as McCarthy couldn’t make it, Kay decided not to come. Instead, Guy Steele conducted the interview by phone.

(What as most striking to me about this was just how careful Steele was and how precise he was with his language. He appeared to already know the answers to all the questions… and if things got sidetracked or drifted off in a random or unclear direction, he always knew just what to say to pull things back together and pin things down. Just observing this interview process, it was clear that Guy was exactly the kind of person that you’d want to have running a massive language standards type project. It’s no accident that Steele is as influential as he is. He was very different from the traditional stereotype of a Lisp hacker. Throughout the day, I’d run into people and say… that’s Guy Steele over there! That’s the guy who wrote the lambda papers!  Unfortunately, this didn’t seem to mean much to the typical conference goer….)

When asked what should have been added to Lisp, McCarthy said he would like to add some direct logic, but he didn’t know how to do that in a good way. Steele mentioned something about the Lisp-Prolog people in an aside. (I think Norvig implemented Prolog in Common Lisp in PAIP….)

When asked what separates a good programming language from a bad one, McCarthy said he had one advocacy: a language should have access to its own abstract syntax. Any program which works with programs involves abstract syntax. If you take Java and you want to write a program that deals with Java programs, then you’ve got to scan it and look up the plus sign and its precedents. (What a mess!)

Steele asked about the variation in the implementation of key-value pairs and association lisps. Was this an accident or a reinvention? McCarthy said he invented both– when he invented the second, he wasn’t thinking about what he’d done the first time.

Steele asked if s-expressions were good or bad. McCarthy said his original idea was to make it like Fortran. (With m-expressions, that is.) Steve Russel took McCarthy’s eval and said you could just program in s-expressions. Being a “conservative guy”, McCarthy thought this was a bad idea. Steele appeared to be slightly taken aback by the idea of such a revolutionary figure describing themselves as “conservative.” McCarthy said, “everybody’s conservative about what they’ve been doing.”

(I have several notes on the significance and uses of abstract syntax, but I don’t understand them. If anyone out there knows what he meant about having different versions of it– say, one to write in and one that’s pretty– then please help elucidate this. He also said something about not having really any good examples of Lisp programs that write programs. I think that’s what he said; I’d like to know more about this, too.)

Steele noted that most new languages have a “boss”. (Perl has Larry, Python has Guido, etc.) Steele then asked who was that boss of Lisp. McCarthy cracked back, “if Lisp has any boss, it’s you! You wrote the language manual!” The audience laughed. “There was no boss,” McCarthy said. “I never attempted to be the boss.” (And of course, as we had seen in the historical perspectives on Lisp earlier in the day, there were tons of Lisp implementations in the sixties and seventies. Each “tribe” was going off in their own directions and people couldn’t really consolidate them at the time because of hardware limitations.) “Even in the early days I wasn’t the boss of Lisp,” he said. “People could get things into Lisp without me knowing it.”

Steele asked what’s his one idea that could have had the most practical impact if it had actually gotten implemented. McCarthy said, if IBM had taken his ideas about time sharing… then things would have been quite a bit better in the 1960’s. At this point, JonL stood up and started clapping.

The final parts of the interview covered Perlis’s attachment to Formula-Algol before “apologizing” and agreeing with the Lisp approach. McCarthy said he had looked at Formula-Algol when they first proposed it and thought it was pretty bad: it overloaded the algebraic operations and applied them to formulas, he said. He concluded by saying he didn’t know what the alternatives were to abstract syntax. The most important problem we can be working on, he said, was formalizing common sense.

7 Responses to “Lisp50 Notes part III: McCarthy Reaffirms the Importance of Having Access to the Abstract Syntax”

  1. Josh Says:

    Regarding the alternate abstract syntaxes, here’s my guess. Some people suggest having two different compilable syntaxes for a Lisp — one with more semantics that’s friendlier, with fewer parentheses, some more notation, etc. The other would be the raw AST-style s-expressions.

    This way, the real language geek can write his macros that write Lisp programs because it’s much easier when the language IS its AST. Then, the plebes who don’t understand crazy macros can *use* his awesome code in their pretty-syntax code.

    If it was well-designed, the compiler could transform from one syntax to the other and back, so you could really interchange them. There have been a variety of suggestions on how to remove the parentheses in Lisp while preserving the “syntax”. None have caught on.

    This may not be what he meant, but it was the only thing that came to my mind.

  2. Mark Miller Says:

    My conception of what McCarthy was talking about is like what Josh said. If you read the Lisp 1.5 Programmer’s Manual McCarthy uses a “prettier” syntax for some of the expressions, which he calls m-expressions. As far as I can tell there’s a direct mapping between the s-expressions and m-expressions, so there would be a way to translate between the two.

    Richard Stallman, as I’m sure you’re aware, pursued a similar goal by creating Guile. In a speech you talked about once he said he created Guile extensions for all GNU projects, with the idea of having language-X-to-Guile translators, so that people could use any language they wanted to extend features in a GNU project. I think he might’ve also mentioned that he hoped there would be Guile-to-language-X translators as well so that people could understand each other’s code without having to understand the other’s language. I have no idea how well that whole idea took off. Anyone know?

  3. Faré Says:

    @Mark Miller

    The GUILE guys quickly realized that the difficulty with language translation is not syntax but semantics. A scheme with C syntax doesn’t bring you much, and neither does a C with scheme syntax. Mixing C code and Scheme does help, but then you’re going to spend a lot of time getting one to cope with the assumptions of the other regarding memory & register discipline.

    Platforms like the JVM or .NET help move some concerns away by handling memory management and low-level calling-conventions for you — but they won’t help you bridge differences in object/class models, method dispatch, scoping, rebinding, continuations, non-determinism, mutability, concurrency, persistence, etc.

    Ask Tom Lord who worked on Guile, or the PyPy guys who have a system to describe language semantics, or anyone who has implemented a particular language translator: the devil is in the details, and a compiler that gives you the “exact same” semantics modulo interpretation in a simulated environment is very different from something that would try to get the “high-level idea” and make an “analogous” program in a different environment (see Hofstadter’s book on fluid concepts for how hard the latter thing is even for trivial languages).

  4. Mark Miller Says:


    Hmm. Good points. I did not know they were trying to mix different languages together in the same modules. I thought what Stallman talked about was straight translation: compile X into Guile, and decompile Guile to X, not part X and part Guile (except for the original GNU project which likely would’ve been written in C/C++). As I recall he didn’t sound hopeful about the Guile-to-X translation aspect, but he at least wanted to accomplish X-to-Guile translation so that people could write extensions in their own language, and Guile would act as a kind of universal VM. It seems to me that in a language like Guile that a compiler could put in metadata that would add some description of semantics so that decompilers could use some heuristics about what was going on. The problem becomes what to do with future languages that didn’t exist at the time an extension was written. Metadata likely would not anticipate the needs of these languages. It brings to mind what Alan Kay said, “We haven’t figured out what computing is yet,” hence the need for more research, and this difficulty you describe is definitely a sign of that.

  5. Ted Says:

    I have no idea what McCarthy was actually talking about, but C# 3.0’s lambda expressions are a practical example of different syntaxes for the same semantics. You can write a simple expression in code with x => 2 * x; but also Expression.Lambda(Expression.Add(xParam, Expression.Constant(typeof(double), 2.0)), xParam).Compile(); using an API. They have an interesting interplay that’s typical of two-sided economies: make it very easy to write expressions using the => syntax so people can do it without thinking, but also make it possible to analyze them using the AST API which they do infrequently so it can be more cumbersome. S-expressions are a middle ground where it’s a little harder to write them but they’re also a little easier to manipulate.

  6. Dan Weinreb Says:

    You are entirely right about Guy Steele’s amazing diplomatic skills, and why he was exactly the right person to lead the Common Lisp effort. He’s also the best writer of programming language descriptions and standards in the world. In addition to “Common Lisp: The Language”, he was responsible for a lot of the writing of the orignial Java Language specification, and his book with Harbison about C is in many ways the definitive practical standard (it took into account the differences between the real implementations of C very well).

    I like what McCarthy said about having many surface syntaxes for one underlying abstract syntax. There’s a lot you can do with this idea. A simple example would be a representation designed for people reading code, which could use fonts and color and graphic layout (it would have to be done tastefully) and provide easy ways to see cross-reference information (e.g. let you click on the name of a function to get to its definition). You might want to have a language that could be written both in a Lispy style (with parens and prefix syntax) as well as a C/Java style.

  7. Kartik Agaram Says:

    Any programming language that can self-describe its core in half a page is bound to spawn a tower of babel. The amount of feedback you get from hacking on it will be irresistible, at least at the start. So lots more people hack on it.

    Python and ruby have one canonical implementation because in the early days a competitor would be too hard to build.

    So don’t ask why lisp doesn’t have a boss. Embrace its anti-boss-itude.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: