Monday, November 24, 2014

RAND Corporation's contributions to computer science

What comes to mind when you hear the word Rand? Ayn Rand? Rand Paul? For me, it is the RAND Corporation. Project RAND (research and development) was housed at Douglas Aircraft in Santa Monica, California immediately after World War II, and became an independent, nonprofit organization in 1948. Perhaps the first "think tank," they spun off their development work, creating the the System Development Corporation (SDC) in 1957.

I don't know how one ranks research institutions, but, for me, RAND ranks right up there with Bell Labs, IBM Research and newcomers Microsoft and Google research. The following are summaries of a some of the computer science advances made by RAND researchers and consultants.

Communication satellites: Science fiction writer Arthur C. Clark outlined the vision of geostationary communication satellites in a short article published in October, 1945. Five months later, Frank Collbohm and James Lipp published a comprehensive engineering study on a "Preliminary Design of an Experimental World-Circling Spaceship."

Arthur C. Clarke's vision (left) and RAND's design 

Artificial intelligence: Herbert Simon, Allen Newell and Cliff Shaw did early work on artificial intelligence at RAND and Carnegie Tech. They asked people to talk out loud while proving theorems and noted that their strategy was to apply operations that reduced the differences between the current state of the proof and the theorem they were trying to prove. Their programs, Logic Theorist and General Problem Solver, did the same -- and so does this pigeon:



A pigeon solves Wolfgang Kohler's box-and-banana
problem by applying the Box Move operator.
Operations research: George Dantzig and Richard Bellman invented mathematical techniques for finding optimal or near-optimal solutions to complex, but well defined problems. This work has applications in network design and you use Dantzig's simplex algorithm whenever you build an Excel spreadsheet to solve a linear programming problem.


SIMSCRIPT: Harry Markowitz and Bernard Hausner invented the SIMSCRIPT programming language for simulating systems like customers moving through checkout stands at a market. SIMSCRIPT was an early object-oriented language in that it modeled the world as sets of entities and their attributes. Entities could be created and destroyed and their attribute values and set memberships changed when events in simulated time occurred. (SIMSCRIPT is close to my heart because it was the subject of the first class I ever taught. Unfortunately, my wife threw out my SIMSCRIPT t-shirt years ago).

T-shirt -- Entities, Attributes and Sets

An early research computer: Early computers were built as research projects at universities. You can recognize them by their names ending in "AC" for automatic calculator. RAND's JOHNNIAC (named in honor of mathematician and computer architect John von Neumann) was a stored program computer. It was used for applications including the early artificial intelligence research and operations research mentioned above.

JOHNNIAC

Timesharing: Terminals and drum storage were added to the JOHNNIAC, enabling Cliff Shaw to create JOSS (JOHNNIAC Open Shop System), one of the first interactive time sharing systems. JOSS was "open shop" in that users interacted directly with the computer rather than dropping off jobs to be run at a later time by a computer operator. I was fortunate to see demonstrations of both JOSS and QUICKTRAN, an interactive FORTRAN interpreter built by John Morrisey of IBM. The advantage of these systems over batch processing was immediately and strikingly apparent. This led me to SDC (mentioned above), which by then had a more advanced time sharing system that I used for my dissertation research on man-machine data analysis.

Programmer at a JOSS terminal
The RAND tablet: The RAND Tablet, the great grandfather of the iPad, was built by Tom Ellis and his colleagues. Their GRAIL (graphical input language) software featured object-oriented drawing and character recognition. Their publications are some of the earliest work on human-computer interaction -- GRAIL was the great grandfather of Macdraw. (The following video clip is narrated by Alan Kay of Dynabook fame).



Object-oriented drawing and character recognition on the RAND tablet

Large, packet-switching networks: I've saved the best for last. Paul Baran published a series of eleven reports on Distributed Communications Networks in 1964. In Volume 2, he described the network architecture:

Traffic to be transmitted is first chopped into small blocks, called Message Blocks or simply messages. These messages are then relayed from station to station through the network with each station acting as a small "post office" connected to adjacent "post offices."
After simulating this system and considering the technology of the day, Baran concluded in Volume 11 that
It appears theoretically possible to build large networks able to withstand heavy damage whether caused by unreliability of components or by enemy attack.
He was right!
Paul Baran's distributed network arhitecture

In the following video, Baran reviews RAND's work on distributed networks and packet switching -- from early concern over the possibility of a nuclear attack disrupting military communications through skepticism about packet switching and the creation of the ARPANet. (Since the ARPANet was just a research project, they did not need to bother with security and encryption).



Paul Baran on distributed networks and packet switching (38 minutes plus Q&A)

Two of the people cited here went on to win Nobel prizes. Harry Markowitz received the Nobel Prize in economics for his work on portfolio theory -- perhaps not tied to his work on digital simulation.

Herbert Simon also received the Nobel Prize in economics for his work on decision making. He noted that we do not make optimal decisions when choosing among alternatives because information about outcomes is incomplete, gathering more information has a cost and outcomes are multidimensional. In real life we make satisfatory decisions. This realization no doubt guided his studies of the thought processes of chess players and theorem provers and therefore his work on artificial intelligence.

(A personal note: I took a class from professor Simon as an undergrad. All I recall was that I liked him a lot and he told us about the chess game his "computer" -- whatever that was -- was playing with a computer in Arizona. I also met him much later, and he was modest and helpful -- told me he stored most of what he knew in his friend's heads).

You can learn more about any of this work on Wikipedia or using Google, but -- better yet -- download the historic reports by these researchers from the RAND Web site.

-----
Update 11/29/2014

As noted above, RAND spun off its development work in 1957 when SDC was set up to build the SAGE (Semi-Automatic Ground Environment) air defence system, designed to defend the U.S. against nuclear attack.

SAGE was the first computer network and the project trained most of the computer programmers in the US at the time. The project also produced many innovations in programming and programming project management.

After SAGE, SDC built an advanced general purpose time-sharing and software development system on an AN/FSQ-32 (Army Navy Fixed Special eQuipment) computer built by IBM. The Q-32 was used for ARPA-sponsored research projects in man-machine interaction -- including my dissertation project. More on SDC in a forthcoming post.

The AN/FSQ-32 supported research on man-machine systems.