This is Guy Steele standing in for Alan Kay and you already have a list of some questions that I think you've had a chance to look over that P. Gabriel forwarded to you. I propose to go over some of those, although not necessarily in the original order. To let it flow, it would be better. I also have got a few questions you haven't seen yet, that are short and we'll leave those for later in the conversation. Why don't we start with what is your question no. 4: Who helped you the most with early ideas for Lisp and its early development?
I want to go over that because I tend to forget people. I took from Newell & Simon the idea of Lisp structure for representing data and also for representing program. They weren't aware that they were going to be helping me, but, anyway, I took it from them. I got the idea of functional programming from John Backus’ FORTRAN. The idea of ... as a function comes from Herbert Gelernter and Carl Gerberich. I was advising them on a FORTRAN-Lisp processing language, which I was advocating for doing Minsky's geometry machine.
Then Steve Russell proposed using my eval as an interpreter and 6 math graduate students in the initial AI project and 2 programmers, Russell and ... did the early development. Phyllis Fox wrote the first manual and at least some of the early programming was done by Nathaniel Rochester who came from IBM. So, those were the people who were involved early. Probably I've forgotten some of them.
Could you tell me a little more about who else worked on successive versions of the manual, after Phyllis Fox?
Mike Levin certainly, and I don't know who else. This 1.5 manual has him and me, I think, as authors.
Let's move up to the list to question no. 3. What would you add to Lisp if you could go back in time? What would you delete and what would you change?
People have added some Englishy stuff and at least the syntax of that is not in the spirit of Lisp. I don't have any objection to the content and generally I don't have any objection to things being added to Lisp, because you can always not use them. I don't have any particular ambitions to add anything in particular to Lisp right now. I'd like to add some direct logic, but I don't know how to do that in a good way.
There have been a couple of projects over the years to try to combine Lisp and Prolog in some way, to add logic. Have you looked at those at all?
I haven't looked at them. I'm sympathetic with the idea.
What's an example of an Englishy feature in Lisp that you wouldn't use?
It seems to me some of the stuff concerning objects was added in an Englishy way - I have forgotten it. You surely should remember.
Perhaps you are thinking of LOOP. I am just trying to get a sense of what you mean by the word "Englishy"
That's probably what I'm thinking of.
Up to your question no. 2: What separates a good programming language from a not so good one?
I don't have any general answer to that. I have one advocacy, now that I think about it, which Lisp has partly and maybe I advocate it something to be explicitly added to Lisp and to other programming languages and that is that a language should have access to its own abstract syntax. Abstract syntax is an idea I proposed in a paper in 1962. It's too elaborate to talk about much now, but the general idea of it is that, as far as the abstract syntax in concerned, it's indifferent whether sums are represented by a+b or (+ a b), as Lisp would do it, or as Gödel numbers would do it as 17 to the Gödel number of a x 19 to the Gödel number of b. You still need functions for distinguishing whether an expression is a sum and for getting the summands and the syntactic function for taking 2 expressions and forming the sum expression. That's abstract syntax and I believe that a programming language should have built into it its own abstract syntactic functions.
Of course, one of the important purposes to which you put abstract syntax in Lisp was being able to write its own evaluator. Do you have other purposes in mind as well for abstract syntax?
Yes, any program that works with programs in the same language, it's an evaluator or it's a compiler or something that determines whether one program is good enough for some purpose would involve the abstract syntax of the language. If you take an ordinary programming language like Java or something like that, if you want to write a Java program that deals with Java programs, then it has to scan and determine whether something is a sum, it has to go look for the + sign and see whether it makes use of the rules for its precedents.
Let's move on to your question no. 1 on your list: what has been the role of programming in AI research and what should it be?
There are 2 things there: one of them is the programs that programmers write for doing AI and the other is that the programs that they make their programs write. I haven't got anything very specific to say at the moment, the latter is very important and that's where Lisp is convenient. Concerning the abstract syntax and Lisp, Lisp doesn't explicitly have its own abstract syntax, but at least, it's very convenient to get at the syntax of Lisp. It is not hard to find out whether something is a sum or not. It almost has its own abstract syntax.
I've seen abstract syntax data structures defined for some other programming languages such as for example ADA. That seems somewhat convenient less to use or to learn because it involves dozens and dozens of very specific data structures, one for each kind of abstract syntax rather than the general use of an expression for representing all abstract syntax. Do you have any comments about the advantages or disadvantages of using that uniform expression representation?
I haven't looked at how they used it, but certainly, there are different ways in which you could define the abstract syntax of a language. First, the use of abstract syntax - after my paper advocating it, was defining the abstracts of syntax of PL 1, which was done by the IBM Group in Vienna, but I think that their work was not appreciated by the rest of their somewhat large company.
This is the Vienna definition language, isn't it, about which some books are written probably 30 years ago?
More than that - '62 it would have been.
I was too young in '62. I'd like to turn away from the list of questions you have in front of you, just to some shorter questions that some people have submitted and some of them are dealing in particular with some of the earlier events of Lisp in 1958, if you'd entertain them. The first question is: where did the idea of a property list come from?
That idea, in some sense is a realization of the idea of an object, which in my mind actually precedes Lisp. In my paper on programs with common sense, I mentioned an object as something that you add something to say about a part from its structure. The example I think that I gave, was the number 1776, which you remember apart from its arithmetic structure because of it being the date of the American Revolution. There were these objects and I gave several examples and then, in Lisp, I thought about having these property lists. They were used differently from the way I had imagined them being used.
How did you imagine and what was different?
First of all, my imagination - since it wasn't associated even with a proposed implementation, was somewhat vague, something that I can't remember. Now, I want all of you to remember that 50 years from now, people will be asking you "What were you thinking about then?" I can't give a good answer to that question.
Your remark prompts 2 more questions on my part. One is, as John says, people will be asking the people in this room, in 50 years "What were you thinking of?". I hope you are all taking good notes for historians and writing things down, or you are saving your e-mail or perhaps even printing it on dead trees so it will last longer. Actually this raises a question here on the list, John: did you throw away your notes and handwritten material when you were at Stanford. Do you still have your old MIT or your notes sitting around somewhere? Did you keep a lab notebook of any type while you were working on Lisp?
A lot of them were in old files, some of which were preserved. When Herbert Stoyan made his first trip to the US, he was very much interested in the history of Lisp and he went both to MIT and to Dartmouth and went through a lot of old file cabinets of mine, which were still there. I don't know, they probably all got thrown away. I think the situation between now and 50 years from now is a lot better, because the things are all in computer files, which hopefully will be preserved and somebody will only have to write the right programs in order to dredge the information out.
I'm hoping that Brewster Kahle’s Internet Archive will help to fill part of that gap, but I still would advice people to print things on dead trees, if you really want them to survive. We'll see how that works out. Going back to the question of property lists, I noticed that property lists record information about key-value pairs, which seems to be an important guide in programming. Association lists also provide a correspondence within keys and values. That's typically been used for variable lookup and environments. It's interesting to notice that property lists and association lists, while they serve very much the same purpose, have 2 slightly different structures in terms of consoles. Was that kind of an historical accident in Lisp or was that a reinvention? What happened there?
I think it's a historical accident.
Two different programmers are just not paying attention or not caring - it's not relevant.
I think I invented both of them and when I invented whichever one came second, I wasn't thinking about what I'd done previously.
It's a minor point, but it is something that picks my curiosity. What experience of practical computer programming did you have before 1958, before you tackled Lisp?
I'd written some FORTRAN programs. In particular, I'd written the legal move routines for a chess program that I intended to write and these legal move routines were taking over by [Alan] Kotok and [Elwyn] Berlekamp, etc. and were the basis for the MIT chess program. That is I actually didn't write the strategy there because I thought I would have grander ideas than were subsequently realized. I didn't, so they did a quite straight forward program, but the program served one nice political purpose, namely Hubert Dreyfus said no chess program would ever beat him. Dreyfus was a sufficiently bad chess player that that very primitive program did beat him.
When you began working on Lisp, in particular looking at the period of about September to November 1958, about what percent of your daily work time did you invest in working on Lisp? Was that sort of 100% of your time or partial time were you devoting your attention to other projects at the same time?
I couldn't say that, but actually, I started on it during late summer when I was at IBM and I decided to write a program for differentiating algebraic expressions. What I noticed is that I could write conditional expressions, which I'd already used in those legal move routines for the chess program and that they could be used to embody the rules that were given in the calculus text, in an extremely direct form. Differentiation of algebraic expressions was the leading example that led to the functional form of Lisp programs.
You were involved in the ALGOL design effort as well, during the late 1950s. We should know whether you considered using ALGOL 58 as a basis for the design of Lisp rather than coming out of FORTRAN or were there ways in which you were involved with ALGOL 58 indirectly with Lisp?
I wasn't at the original ALGOL 58 meeting, so the basic structure of it was established without any input from me. I wouldn't have tried to influence it very much, because they were interested in making a language that could be standardized for numerical calculations. I was perfectly sympathetic with the idea that there should be such a language. When it came to ALGOL 60, I was on the committee and the committee as a whole was much more ambitious, so I pushed for conditional expressions and for boolean expressions, although they were putting it in a bad way. The way a AND b is in ALGOL 60 is you have to evaluate both a and b before you can evaluate the end, which is not right, if you write them as conditional expressions and you only have "if a is false" and you never evaluate b.
Sometimes that matters for reasons of correctness. In fact, the way we currently use them idiomatically nowadays anyway or even earlier, let's say 1965. Evaluating the logical connectiveness and/or in that conditional way can be very important for program correctness, given that we become used to using them in that idiomatic way. Being that, it might not be correct to evaluate b if a fails, for example.
That's correct.
When did you first embrace the idea of writing computer programs using a recursive style?
In one respect, I got it from Newell & Simon. In another respect, in recursive functional style, that was in the summer of '58, when I did this differentiation program. Newell & Simon talked about that in 1956 when they visited the Dartmouth Summer Project on artificial intelligence. They had already done IPL or the first version of IPL.
This idea of organizing computer programs as recursive way was an idea that slightly proceeded Lisp itself?
Yes. But IPL had, in my opinion, very many bad aspects. They seemed to be bad enough at the time, that I was not tempted to copy them.
What were the bad aspects that you didn't want to copy?
It was not compositional, that is it wasn't based on functions that you could compose. It was based on subroutines whose names, like J45, were, according to what somebody told me, taken from an old JOHNNIAC loader.
I looked at some IPL-V code, and it does seem to be very statement or command oriented with fairly cryptic names or numbers for commands and reminded me of some kind of an assembly language for a Lisp machine. You are currently convinced that while the S expressions or programming in S expressions were a bad idea. Did you change your mind in this regard and if so, when?
My original idea was to make it like Fortran, so that you programmed in M expressions. Then, when Steve Russell took my eval, he said you could program directly in S expressions. That was an innovation and being a conservative fellow, I was inclined to reject innovation, so it took me a while to get used to that.
It's interesting we hear you put it that way because in your invention of Lisp, you were regarded as a great innovator in a number of ways, so to describe that as conservative is a little bit startling.
Everybody is conservative about what they've been doing.
I'd like to return now to the list of numbered questions that you have in front of you. At this point I'd like to start with question no. 5 and then we'll take them in forwards order. Should programming languages be designed for theoreticians to facilitate reasoning or for practitioners for getting systems built? Should there be different languages for each purpose? Are the skill sets of a language designers different?
My view is that a language should be designed in terms of an abstract syntax and it should have perhaps, several forms of concrete syntax: one which is easy to write and maybe quite abbreviated; another which is good to look at and maybe quite fancy, but after all, the computer is going to produce it and another, which is easy to make computers manipulate. There are still others maybe, but it's easy to make computers prove things about and they all should be based on the same abstract syntax. As it relates to your question, the abstract syntax is what the theoreticians will use and one or more of the concrete syntaxes is what the practitioners will use.
That actually reminds me of the distinction made fairly early in the ALGOL project, between the machine readable syntax and the reference syntax in a publication format. Did that distinction ALGOL come from you?
No, but they didn't go far enough. I didn't raise the issue about abstract syntax in the ALGOL committee - I should have, but I didn't.
None of the ALGOL formats to which I just referred qualifies as an abstract syntax at least in a way that S expressions would.
That's correct.
Do you think that these different kinds of program representations call for different designer skills? Would you recommend that an expert designes, say the core abstract syntax, then you could have different cosmetics designers plaster - say lipstick onto the front of it? Lipstick being a word that's very much in the air in this particular American political season.
I doubt it. I think people are adaptable enough to design to different specifications.
In the answer of an earlier question, you pointed out that it's important for people to write programs and also for programs to be able to write programs. Do you think the same programming language serves well for both purposes or perhaps the same abstract syntax that humans might want to use a different concrete syntax?
I think the same abstract syntax could be usable except there aren't really any good examples, so at least I am not directly acquainted with really good examples. Maybe other people are - that is of Lisp programs that write Lisp programs.
Let's move on to question 6 on your list. Lisp has had a strange history with lots of dialects, lots of implementations and lots of controversy. Do you believe the platform of ideas tried by Lisp was good for it and good for programming languages overall?
Yes, I think so. I can't elaborate that.
Experimentation is good? Do you think there is anything peculiar or special about the design of Lisp that encouraged that experimentation or made it easier?
Sure, there was no boss. I never attempted to be the boss. If we take Fortran or IPL, each of them had a boss - APL had a boss.
Nowadays Python has a boss, Guido van Rossum,and C# has a boss - there is Heilsberg - and James Gosling - he doesn't try to act as a boss to Java anymore but he is still considered a kind of boss.
If Lisp has any boss, it's you! You wrote the reference manual.
I've been trying to disclaim that boss ever since, perhaps instinctively following your example or just because I don't want to be a boss - I'm not sure. It's interesting that during the last 10 -15 years I think there has been a kind of a cult of bosses in programming languages and what you say, that may be a bad idea for the development of the language. Let's move on to question 7. What do you think was the most important contribution that Lisp made?
It provided a convenient way - more convenient than IPL - of programming using Lisp structures, so it had a practical importance. Also, Lisp programs or Lisp data had a practical importance.
Of course, those were related because you used the Lisp structures as the representation of the program?
Yes
I asked for one of the most important contributions. I am going to list 4-5 others that occurred to me and ask your comments on those as well. Close related to the idea of a Lisp program and Lisp data is that it enables you to encode, apply and eval as an universal implementation of the language. The idea of eval is a universal Turing complete function is an important idea, perhaps. Having an expression oriented language, the support of recursive functions, the McCarthy conditional expression, which is spread into all programming languages by now - even C, which has a rather strange syntax for it, but it's there -, and then garbage collection. Have I left out any important idea? Probably. I'm going to ask people from the audience: what have I left out from the list? High order functions, symbols, dynamic programming. I'd like to ask you, John, do you have any other comments about any of those things as how they fit into the overall picture of Lisp and what you were trying to accomplish?
Consider garbage collection - when I wrote this program for differentiation, it was written in a straightforward way, using cons for forming the parts of the derivatives and it was just much too awkward to write Erasure, that is erasing things. IPL had explicit erasure things, it had a notion of responsibility bits, so that, if 2 Lisp structures merged, one of them was responsible for their common substructure and that had to be programmed. So, I thought very hard "Is there some way in which we can eliminate having to have explicit erasure, in order to be able to write the differentiation function in a way corresponds to the way that mathematicians describe it?" They don't describe, they don't mention erasing anything in the calculus textbook, so I worked hard on that and came up with garbage collection.
It can be done in a different way using reference counts and I thought of that also, but there aren't enough bits in the IBM 704 Word, to include reference counts. Somebody who used CDC machine was able to do that, but I think garbage collection was needed anyway. Here was a case where making things correspond properly to the abstract notions of mathematics gave rise to an important practical advance. Of course, somebody came along and said to me "You aren't the first person to think of garbage collection. It was present in such and such program, before that." I didn't bother to look, but I suppose it was true.
Looking back, what in your career are you most proud of? What would you like to take back? Which idea that you came up with that was not picked up did you wish had more influence?
I think that if IBM had taken my ideas on time sharing, particular if Gene Amdahl had taken my ideas on time sharing when he was doing the 360, then things would have been quite a bit better in the 1960s, since what he did was copy the tape-to-tape operating system that Bell Labs had devised. In terms of what would have had the most practical influence that would have been it.
I hear "Amen!" from the audience on that. Here is a perhaps slightly more off-the-wall question - question 9 on your list. The Stanford AI lab was a unique place, away from campus and an ecclectic group of people including software people, hardware people and musicians, a volleyball game every day and its own computing infrastructure. Did these factors help make it easier to do this sort of far reaching research or are such factors irrelevant?
I suppose they are mostly irrelevant. Doug Lenat said about me that it would have been better if I hadn't bothered with the Stanford AI lab, but had sat in an office and worked on formalizing common sense in mathematical logic. I could say that Lenat would have been right if I would have been successful in formalizing common sense in mathematical logic, but I can't assure people that I would have been. Yes, I suppose the atmosphere played a role, but part of the reason for the free atmosphere was that I was unable to take the resources that DARPA had given me and put them all to work on the thing that was most important to me, which was formalizing common sense because I didn't know how to make a project to do that. So, everybody got to do what they wanted.
Is this another example of your deciding not to be the boss and let people do what they wanted?
I tell you: if I had known what I wanted them to do, I would have tried to be the boss.
Formalizing common sense was a very difficult problem and still is, I think.
That's correct. I started people on Vision, for example, partly because I've been in argument with the 1950s idea of Vision, which had to do with discrimination. I offered the slogan "Description, not just discrimination" and gave the example that, if you wanted a robot to pick something up, then you couldn't just identify it, you had to describe its shape and how it was laid out. So, we undertook to do robotics and DARPA gave us money to do it.
If memory serves, in the late '60s, MIT was also tackling robotics and in particular trying to solve the Vision problem and when they declared "We are going to solve Vision this summer" and they had the Summer Vision Project and by the end of the summer they had a nice collection of subroutines for the video camera, but I don't think they solved Vision at that point. That was 1967, give or take a year. John White reports that he wrote some matrix and version routines in Lap for that project.
What year was that?
John White: '66 was the first Vision project - Knight, myself, Sussman, Lamport and a couple of other people.
Computer Vision remains a hard problem. At this point I'm going to depart from that numbered list again and give the audience a chance to ask you a few questions directly. We've got to microphones here in the room. If anyone has another question to direct to John McCarthy, come forward. Herbert Sterns: What was the influence of Marvin Minsky on the development of Lisp?
I don't think he had any, I don't think he tried to have any. One thing that he did was that James Slagle, who did the symbolic integration program was Minsky's student. Slagle had some influence on Lisp. He had some influence on the free variable problem. He found some inadequacies in the way how I had supposed the problem would just solve itself, but I don't know whether his problems there were influenced by Marvin directly.
John White: Marvin is given credit for writing the garbage collector that dumped the memory out on to a secondary storage right getting it back in, in about 1960 time frame. That was before my time, but I read the documents that said that. That might have been his primary involvement in Lisp.
Was that garbage collection put into Lisp?
I didn't come along until 6 years later, so I don't know - not the Lisp I worked with.
It's unclear. I remember reading a memo about it. I don't know if that was actually put in the production use.
Kent Pitman: I was wondering to what extent the name Lisp, as list processing is really central to the language to you at this point. Personally, I think that issues of things like identity or dynamic typing are much more important contributions of the language than list and I'm just curious whether looking back on it you still would have named it Lisp? What do you think of this central feature?
Remind me of the previous question. I had something that I wanted to add to my answer to it.
The previous question had to do with the influence of Marvin Minsky on Lisp.
I asked "Did he get into Lisp?". That was a genuine question because, even in the early days, I wasn't really the boss of Lisp. Things could get into Lisp without anybody telling me. I wasn't - so to speak - the keeper of the gate. Remind me of the present question.
This is Kent Pitman's question regarding the naming of Lisp as list processing. Looking back on it do you still feel that list processing was the most central or salient feature of the language or would you give the language a different name because other things are more important?
I don't have an alternate name to suppose I don't think that dynamic variables are suggesting a name. Would you like to suggest a name?
Kent Pitman: I had no particular name to suggest, but I did have a related question just to follow up. What do you think it's dynamic typing which I really consider to be one of the central features of the language, whether the absence of static typing in Lisp is a bug or a feature?
I suppose both. As far as my thinking is concerned it was a bug in my thinking. Namely, I remember the first discussion of Slagle's problem and my attitude was: "Oh, you guys will fix them somehow!" and then were having a serious discussion that ended up with their talking about having two kinds of variables and so forth. I didn't really take part in that discussion or in the decisions that they made how to do it. So, here was a whole issue not merely with regard to Lisp, but regard to other programming languages, that I didn't understand all of until very much later.
JohnL: When I was an undergraduate at Carnegie the sort of a Holy Grail of Perlis was to get the formalization of mathematics to the degree of symbolic and algebraic manipulation, but he took the ALGOL route. And you did mentioned something about ALGOL and what it might be envisioned for, so he pushed for formula ALGOL for a long time to be a competitor to the Slagle's work and it wasn't until years later when he personally apologizes and said he agreed with Lisp. I wonder if you've heard that term "formula ALGOL" and if, in fact, the kind of work and proliferation that came out of the symbolic algebraic movements, the math labs, the maximums and the others and so on, could have ever been done with an ALGOL-like syntax and semantics?
I looked at formula ALGOL where they were first proposing it. I thought that was pretty bad, that it was confused and the confusion was the following: it overloaded the algebraic operations and applied them to formulas. To a certain extent, you can do that. In other words, you have algebraic operations like adding and subtracting and you can apply these to formulas and get the sum of 2 formulas and the difference of 2 formulas. But in general that's not what you want to do with formulas. At least in the example they gave, they didn't include differentiating a formula and so forth.
John, I'm going to move back to the list of numbered questions. Could you look back at question no. 14, please? What do you think about the proposition that good notation can stimulate good thinking or the poor notation can inhibit it.
I think abstract syntax is an important idea, not notation per say. Abstract syntax should be behind the particular notations. However, since people don't, in general, use abstract syntax and you can ask "Historically, what has been the role of a notation?"- I guess I'll say I don't know.
What do you think about the proposition that good abstract syntax can stimulate good thinking and that poor abstract syntax can inhibit it?
Not enough examples.
Ok. I'm just wondering: is abstract syntax just abstract and it is what it is or can be sort of good or a bad designs for abstract syntax?
I don't know what alternative abstract syntaxes there are. That is, for sums, there don't seem to be any alternatives really, at least to the abstract syntax.
It was a slightly off-the-wall question I wanted to see what kind of answer I would get. Last question, please. What suggestions do you have for the young researchers today? What do you think are the important problems to be working on?
Formalizing common sense!
An important problem back then and an important problem right now. OK, thank you very much, John. We've taken an hour of your time and we've really appreciate your dialing in. We really appreciate your inventing Lisp and the other work in logic that you've done. I think that nearly every person in the room here can say that his or her career was built more or less solidly on your work - I can certainly say that of myself. We'd just like to express our appreciation. Thank you very much!
Thank you!
7 comments
Watch Thread Reply