I hope for all our sakes that I can make this short …

In the latter part of the 50s John McCarthy got more and more interested in what he started to call “Artificial Intelligence”. He was also doing some consulting and this brought him in contact with the SAGE air defense system: large systems of very large computers attached to radar stations and each other and usable by graphical display systems with pointing devices.

John’s reaction was “Every home in America will have one of these”. He could see that the networked computers could be thought of as an “Information Utility” (as a parallel to the existing utilities for electricity, water, gas, etc…) and that the terminals in the homes could provide many kinds of “information services”. Among other things, this got him to advocate that MIT etc do “time-sharing” of their large mainframes …

He also realized that the computer milieu of the 50s — machine code and the new Fortran — did not intersect well with “most people in US homes”. This got him to write a paper in 1958 — “Programs With Common Sense” — and to suggest that what was needed for the user interface was an active semi-intelligent agent — the “Advice Taker” — that could interact with users in their commonsense terms, could learn from “taking advice”, could problem solve on behalf of the user and itself, and so forth (MIT AI Memo 17).

This got him thinking about how to implement such an Advice Taker, whose main mechanisms would be various kinds of logical deductions including those that required actions. There wasn’t much to go on back then but a few gestures at “list processing”, so he decided to invent a language that could be used to make the Advice Taker (and other kinds of robots), and more generally allow symbolic computation to take its place alongside the existing numerical computation.

John was an excellent mathematician and logician, and so he also wanted to come up with “A Mathematical Theory of Computation” to put ideas old and new on a firmer basis.

His result was LISP (for “LISt Processing”). I have written elsewhere about its significance.

Meanwhile, he was pondering just what kind of logic, math, and programming (he thought of these as highly intertwined) could be used to deal with a robot in the real world.

<eliminating detail here> A conflict was between at (robot, philadelphia) and at (robot, new york) which could not happen simultaneously, but could happen “over time”. This was like the problem of contemporary programming where variables would be overridden (and sometimes even files) — basically, letting the CPU of the computer determine “time”.

This destructive processing both allows race conditions and also makes reasoning difficult. John started thinking about modal logics, but then realized that simply keeping histories of changes and indexing them with a “pseudo-time” when a “fact” was asserted to hold, could allow functional and logical reasoning and processing. He termed “situations” all the “facts” that held at a particular time — a kind of a “layer” that cuts through the world lines of the histories. cf McCarthy “Situations, Actions, and Causal Laws” Stanford, 1963 prompted by Marvin Minsky for “Symbolic Information Processing”.

One of the ways of looking at this scheme is that “logical time” was simply to be included in the simulations, and that “CPU time” would not figure into any computation.

<more detail excluded here> This idea did not die, but it didn’t make it into the standard computing fads of that day, or even today. The dominant fad was to let the CPU run wild and try to protect with semaphores, etc. (These have the problem of system lockup, etc., but this weak style still is dominant.)

Systems that have used part or all of John’s insight include Strachey’s CPL, Lucid, Simula, etc. Look at Dave Jefferson’s TimeWarp schemes, Reed’s NetOS, Lamport’s Paxos, the Croquet system, etc.

To just pick just one of these, Strachey in the early 60s realized that tail recursion in Lisp was tantamount to “a loop with single simultaneous ‘functional assignment’ ”. And that writing it this way would be much clearer by bringing the computation of the *next* values for the variables together.

There are no race conditions possible because the right hand side of the assignments are all computed using old values of the variables, and the assignment itself is done to furnish new values for the variables all at once. (Looping and assignment can be clean if separate “time zones” are maintained, etc.)

More main stream is that big data systems used *versions* instead of overwriting, and “atomic transactions” to avoid race conditions.

Back to McCarthy and — now — objects. One of the things we realized at Parc was that it would be a very good idea to implement as much of John’s “situations” and “fluents” as possible, even if the histories were not kept very long.

For example, this would allow “real objects” to be world-lines of their stable states and they could get to their next stable state in a completely functional manner. In the Strachey sense, they would be “viewing themselves” with no race conditions to get their next version.

This would also be good for the multiple viewing we were starting to use. You really only want views to be allowed on stable objects (/relationships) and this can be done by restricting viewing to already computed “situational layers”.

Parc was also experimenting with “UNDO” and the larger community was starting to look at “parallel possible worlds reasoning”.

The acts of programming itself also wanted to be in terms of “histories and versions” and systems should be able to be rolled back to previous versions (including “values”, not just code). cf Interlisp, and especially the PIE system (done in Smalltalk by Goldstein and Bobrow).

This was another motivation for “deep John” in future systems. I.e. do everything in terms of world-lines and “simulated time”. A recent paper by Alex Warth shows some ways that “Worlds” can be quite fine-grained. http://www.vpri.org/pdf/tr201100...

The last point here is that “Histories R US”. I.e. we need *both* progression in time for most of our ideas and rememberings *and* we also want to reason clearly about how every detail was arrived at (and to advance the system).

John McCarthy showed us how to do this 60 years ago this year and wrote it down for everyone to read and understand.

So: both OOP and functional computation can be completely compatible (and should be!). There is no reason to munge state in objects, and there is no reason to invent “monads” in FP. We just have to realize that “computers are simulators” and figure out what to simulate.

I will be giving a talk on these ideas in July in Amsterdam (at the “CurryOn” conference).