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.
Mike Levin certainly, and I don't know who else. This 1.5 manual has him and me, I think, as authors.
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.
5. 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.
7. 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.
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.
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 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.
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.
13. 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.
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.
16. 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.
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.
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.
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.
21. 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.
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.
23. 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.
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.
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.
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.
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.
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.
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.
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.
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 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.
39. 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.
40. 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.
What year was that?
John White: '66 was the first Vision project - Knight, myself, Sussman, Lamport and a couple of other people.
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.
44. 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.
46. 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.
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?
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.
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.
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.
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.