read


read or learn more

In the Shadow of John McCarthy

Nov 3, 2011

John McCarthy was a genius of the highest order. Much is known about his contribution to Lisp as its inventor, but he was also the mind behind much of early AI research, the progenitor of much of computer chess, and the initiator of time-sharing. As a Lisp advocate I have many thanks due to John McCarthy and it saddens me that I will never have the chance to give them. However, like many geniuses McCarthy was surrounded by likewise brilliant creators and thinkers. This post is devoted to some of the brilliant minds that influenced, provoked, and in one case defied McCarthy for the betterment of the early LISP history spawning the Lisp world that we now enjoy. So goes the history of monumental minds that their likewise monumental shadow engulfs those whose help was critical to the larger historical significance.

Steve Russell

That Steve Russell created the first LISP evaluator is fairly well known, so to include his name on this list is questionable. However, it’s important to note that has it not been for his effort the history of LISP as a language might have never occurred and if it had then it would have manifested very differently. In early 1959, Steve Russell took the theoretical idea that was LISP devised by his employer John McCarthy and hand-compiled the “Universal LISP Function” to operate on the IBM 704. In a survey of one, I suppose the lesson is to never listen to your boss.

The implementation was novel in that it utilized the machine capabilities to maximum effect. However, unbeknownst to Russell, and early decision would “haunt” LISP even up to today:

Because of an unfortunate temporary lapse of inspiration, we couldn’t think of any other names for the 2 pointers in a list node than “address” and “decrement,” so we called the functions CAR for “Contents of Address of Register” and CDR for “Contents of Decrement of Register.”

As a contributor to Clojure it always brings a smile to my face when people deride its lack of car and cdr. What seems a priceless nostalgic gem to some is but the leavings from a lack of inspiration some 50+ years ago.

Dan Edwards

Dan Edwards (gc) during June/July of 1959 wrote the garbage collector that would serve up to the 1.5 release of LISP. (McCarthy 1962) According to McCarthy, the garbage collector worked as such:

At any given time only a part of the memory reserved for list structures will actually be in use for storing S-expressions. The remaining registers (in our system the number, initially, is approximately 15,000) are arranged in a single list called the free-storage list. A certain register, FREE, in the program contains the location of the first register in this list. When a word is required to form some additional list structure, the first word on the free-storage list is taken and the number in register FREE is changed to become the location of the second word on the free-storage list. No provision need be made for the user to program the return of registers to the free-storage list.

Edwards, Michael Levin, and Hart (below) also proved the equivalency between the alpha-beta and minimax search algorithms, (Edwards 1961) that was also overshadowed by McCarthy given that he seemingly invented alpha-beta out of thin air in 1955.

Timothy Hart

Macros are a ubiquitous element for any Lisp language in use today, but the fact is that they were not part of the early LISP implementations. Instead, LISP macros were invented years after Russell’s first implementation by Hart and were described in a scrawled 3-page document called MACRO Definitions for LISP published as an MIT memo. (Hart 1963) This short but epic document described an extension to the original seven-function LISP eval that looked effectively like the following:

((eq (caar expr) (quote macro))
 (cond
   ((eq (cadar expr) (quote lambda))
    (eval (eval (car (cdddar expr))
                (cons (list (car (caddar expr)) 
                            (cadr expr)) 
                      binds))
          binds))))

I’ve extended my Lithp interpreter with Hart-style macros if you’d like to play with such a beast.

Nathaniel Rochester and Herbert Gelernter

It’s hard to imagine how Rochester, the creator of the first assembler, could be overshadowed by McCarthy, but from a LISP perspective he certainly is. The influence of Rochester and Gelernter are likely deeper than I know, but in one instance theirs is a negative influence. That is, McCarthy at one point was considering an extended version of Fortran with list processing capabilities for his AI research, of which such a system was developed by Rochester and Gelernter. However, McCarthy realized that such a library did not adequately serve his needs which led him to explore the creation of a language more suited to his AI explorations and LISP was the result.

Alan R. Kotok

Alan Kotok, one of the designers of the PDP-10 was driven to design a machine that could effectively host a LISP system. The PDP-10 is, at its core, is built with an eye toward LISP. Indeed, the 36-bit word size is there because LISP implementations benefited from two 18-bit pointers per word (the elements of a cons cell). It’s unclear how the PDP-10 influenced LISP, if at all,1 but I thought that this was a great story and a preview of the Lisp Machines that would come years later.

Others and Inaccuracies?

Did I misrepresent something here? Please let me know.

Additionally, there are many others involved with the early days of LISP whose contributions were not easy to find, including:

  • Paul W. Abrahams
  • Robert K. Brayton
  • Saul Goldberg
  • David Luckham
  • Michael Levin
  • More…

If you have any information about these pioneers, or are the pioneers themselves, then please comment here with pointers to more information and I will add it to the main post body.

References

:F

  1. Much of the early AI work, done with Lisp, was hosted on the PDP-10, so I imagine there must have been some level of bidirectional influence. ↩

No related posts.

7 Comments, Comment or Ping

  1. Nick Caruso

    I worked with Michael Levin some years ago, at a company called Gensym, and I recently spoke with some folks who are in touch with him. I will see if I can put you in touch, if you are interested.

    Nov 3rd, 2011

  2. fogus

    I would indeed be interested.

    Nov 3rd, 2011

  3. David Luckham

    I would add some remarks to the above.

    A substantial contributor to the theory of Lisp was David Park (D.M.R. Park, now deceased). He joined the McCarthy’s Lisp group as a Math grad student assistant in 1959. He proved that some of McCarthy’s basic Lisp functions were definable in terms of a smaller set of basic functions, thus leading McCarthy to drop them from his writings on Lisp. McCarthy never gave Park credit until years later when Park wrote him complaining of his omission from the Lisp credits. Park became a leader in British Computer Science during the 1970’s.

    I was a Math grad student and a research assistant on the Lisp/AI project from 1958 – 1961. I was responsible for some of the basic Lisp library functions, Maplist and the Program feature (called Nomap and later renamed Map) that enabled many Lisp functions to operate “in-line” without copying their List arguments. I also coded the first on-line Lisp system that was demonstrated on an IBM 709 to a meeting of the American Mathematical Society in summer 1959.

    At that time the MIT AI project employed six or more Math graduate students. In summer 1960 there was a general student revolt against McCarthy because the AI project seemed to have lost direction and lacked motivation. The students, including many named above, went to other projects for support. I was one of them.

    Nevertheless McCarthy invited me to join the Stanford AI Lab in 1968 when I was already teaching in England. I accepted and served until 1976 when I joined the EE faculty.

    McCarthy was a strange fellow with many odd attitudes in human relationships, one being that he would never lift a finger to help any of his own people. As a result he continuously lost long serving staff such as Steve Russell, Dan Edwards, and others. Those were days when McCarthy was championing the idea of large central computers serving hundreds of users. Even in 1969 the AI lab had a direct news feed from the New York Times. And on-line text chatting between users, with video support was possible. Thus the lab supported the kind of Internet features we are all accustomed to today.

    In the early 1970’s McCarthy seemed to become disinterested in the projects of his staff, and to retire to his office and read the newspapers on-line. The lab depended more and more upon senior staff for research funding.

    However it must be said that the AI Lab pioneered many technologies that led to start-ups in Silicon Valley and established companies today.

    Nov 3rd, 2011

  4. Liz

    John’s papers, notes, and letters are in the Stanford archives and they might shed some light on this. I worked for him a few years ago and as we went through his files he did talk about people who had either collaborated with him or had fought with him. So he did think about it even years later in his general social isolation. “A strange fellow with many odd attitudes in human relationships” describes him well.

    Nov 3rd, 2011

  5. mike vidal

    Hi,

    Robert K. Brayton contact information can be found on these pages.

    http://www.eecs.berkeley.edu/~brayton/ http://www.eecs.berkeley.edu/Faculty/Homepages/brayton.html

    Nov 4th, 2011

  6. SI Hayakawa

    Typo: “but in one instance their’s is a negative influence” — “theirs” without the apostrophe is the correct spelling for the possessive pronoun.

    Nov 18th, 2011

  7. Carol Harlow

    I recommend that you contact Paul W. Abrahams directly to discuus his, McCarthy’s and the roles of others you mention in the development of AI. My undrstanding that Abrahams was Marvin Minsky’s first graduate student at at MIT with his Sc.D. Dissertation on the topic of Artificial Intelligence. This work at MIT was accomplished in MIT’s Math Department before it had established a separate, new Department of Computer Science. If I have my history correct, Minsky’s and Abrahams’ work on AI predated the full establishment of the new field called Computer Science — the sequence of who was on first –was it Minsky-Abrahams-McCarthy, McCsrthy-Minsky-Abrahams or some other sequence of individuals whose earliest work was on the new speculative field of Artificial Intelligence, itself within the new field of Computer Science. Paul W. Abrahams is the person who could elucidate these matters for you, as well as his role and those of others in development of LISP.I recommend that you Google him for his contact information.

    Feb 5th, 2017

Reply to “In the Shadow of John McCarthy”