It Began with Babbage (51 page)

If Newell and Simon were at the forefront of this new discipline, others followed very soon thereafter. Game playing and other kinds of problem solving were the main domains of inquiry. Perhaps the most influential work to follow on the tracks of Newell and Simon was the study of how machines could learn (a topic in artificial intelligence that came to be called
machine learning
) by Arthur Samuel (1901–1990) using the board game checkers (“draughts” in Britain).

While a professor of electrical engineering at the University of Illinois, Urbana, in 1947, Samuel wrote his first checkers program. It would go through many modifications. During the 1950s, as a member of the IBM Poughkeepsie laboratory, Samuel programmed the IBM 701 to play checkers. The program, described in a paper published in 1959, “self-learnt” and thereby improved its own performance.
⁵⁴
In that same year, Herbert Gerlenter described (at the same first IFIP conference, where John Backus delivered his paper on the syntax and semantics of Algol [see
Chapter 13
, Section XVI]) a program that proved theorems in geometry at the level of “good” high school students.
⁵⁵

Such programs used heuristic reasoning and search. By the end of the 1950s, then, the
methodology
of computer science was no doubt dominated by the algorithmic approach—that is, computer scientists sought primarily to automate by inventing algorithms to solve computational problems. However, this methodology was now joined by an alternative strategy: heuristic search.

Language, thought, and reality are related intimately, as distinguished linguist Benjamin Lee Whorf (1897–1941) famously proposed.
⁵⁶
Whorf was alluding to natural languages, but the relationship is true in the realm of artificial languages. As we have seen, the two cultures of scientific and business computing that emerged during the 1950s gave rise to very different types of programming languages (see
Chapter 13
, Section XII).

The kind of computing in which Newell, Shaw, and Simon were engaged while building LT—the kind of computing with which artificial intelligence researchers became
involved—as we have seen, entailed not numeric computations, but symbol processing. Expressions in logic were manipulated as symbol structures with no numeric significance; indeed, with no
semantic
content at all. Computations of the kind LT performed involved extracting subexpressions, matching two (sub)expressions, substituting (sub)expressions for other (sub)expressions, and so on. For the purpose of implementing LT on the RAND Corporation's JOHNNIAC computer, Newell and Shaw invented a programming language they called IPL (Information Processing Language).
⁵⁷
The version of the language that was actually used to program LT was labeled IPL V, developed circa 1957 and implemented on the IBM 650, IBM 704, and other machines of the time.
⁵⁸

IPL, however, became a “dead language” within a relatively short time. Its significance is twofold: it was used to program LT and it was the first of a new genus of programming languages called
list processing languages
, of which the most dominant and influential species was named LISP (LISt Processing) invented by John McCarthy between 1956 and 1958.
⁵⁹

The basic concept underlying LISP (and other list processing languages) is that the fundamental symbol structures (in computational jargon, “data structures”) on which computations are performed are structures called
lists
. Each element in a list is a symbol consisting of some piece of information along with information of where to find the next associated symbol. The latter information is called a
pointer
. Thus, lists are not stored in sequential location in a computer's memory. The elements of a list may be scattered all over memory, but they are linked by means of pointers.

A list processing language would contain operations that can extract parts of a list (making them lists of their own), insert elements into or delete elements from a list, find the successor elements of a list element, create new lists, and so on.

Such kinds of operations (insert, alter, delete) are not specific to list structures. But, LISP as a particular list processing language has properties and characteristics that are very distinct from such languages as FORTRAN or Algol. The latter were
procedural
languages—that is, programs are composed in the form of sequences of statement constituting procedures, which can be called from other procedures. LISP was a
functional
language, drawing its computational character from the mathematical notion of functions.

In mathematics, a function is represented symbolically by the name of the function followed by the arguments of the function, usually in parentheses. Thus, the square root of a number
x
, represented conventionally as √
x
, can be given functionally as
sqroot(x)
, and the application of this function to the value of argument
x
would yield the square root of that number. An arithmetic expression such as (
a * b
) – (
w/x
) would be represented functionally as
minus (mpy(a,b), div(w,x))
. The syntax and semantics of LISP programs—or, rather, LISP functions—follows this general pattern.

For a flavor of what a LISP-like function looks like, let us look at a small example. Before we do, however, some preliminaries need to be established.

LISP incorporates a number of
basic
functions. They include the following. Suppose
x, y
are lists. Then

CAR
x
returns the first element of
x
as a list

CDR
x
returns
x
with the first element deleted

CDDR
x
returns
x
with the first two elements deleted

CONS
x, y
returns a list in which list
y
is appended to list
x

NULL
x
returns
T
(true) if list
x
is empty

A list of elements are always depicted in parenthesis separated by a space. For example, (
A B C)
is a list of elements
A, B, C
each of which may be an “atomic” element or a list. So as examples of the use of the previously mentioned operations, we may have:

Now suppose we wish to define a function
ALT
that, given a list, returns the alternative elements of the list beginning with the first element. Then, in LISP, the function will be

What this says is that if
X
is either the empty list or if it consists of just one element (that is, CDR
X
is empty), then the function
ALT
returns as its value
X
. Otherwise, select CAR
X
and append to it the list returned by recursively calling the function
ALT
with CDDR
X
as argument.

In Algol-like notation, this same function would appear as follows:

For example, if
X
is the empty list ( ), then ( ) will be returned. If
X
is the list containing a single element (A), then (A) will be returned. Suppose
X
is a list (A B C D E). Then,
ALT
will return the list (A C E).

LISP was fundamentally different from such languages as Algol and FORTRAN in that it was a language that was intended to cope with a different kind of computer culture. In its implementation, it differed from procedural languages in that programs written in the latter languages were
compiled
into a machine's “native” language before
execution, whereas LISP (like APL; see
Chapter 13
, Sections XXII
et seq
.) was an
interpretive
language. The LISP interpreter examines a LISP program statement; it determines what each statement specifies and executes it on the computer before moving to the next statement.

  
1
. G. Polya. (1957).
How to solve it
(2nd ed.). Princeton, NJ: Princeton University Press (original work published 1945).

  
2
. Ibid., p. vii.

  
3
. Ibid., p. 113.

  
4
. Ibid.

  
5
. H. A. Simon. (1991).
Models of my life
(p. 199). New York: Basic Books.

  
6
. Ibid.

  
7
. S. Dasgupta. (2003). Multidisciplinary creativity: The case of Herbert A. Simon.
Cognitive Science, 27
, 683–707.

  
8
. H. A. Simon. (1976).
Administrative behavior
(3rd ed.). New York: Free Press (original work published 1947).

  
9
. H. A. Simon. (1947). The axioms of Newtonian mechanics.
Philosophical Magazine, 7
, 889–905.

10
. H. A. Simon, D. R. Smithburg, & V. A. Thompson. (1950).
Public administration
. New York: Alfred A. Knopf.

11
. Simon, 1991, op cit., p. 101.

12
. H. A. Simon. (1952a). On the definition of the causal relation.
Journal of Philosophy, 49
, 517–528.

13
. H. A. Simon. (1952b). Application of servomechanism theory to production control.
Econometrica, 20
, 247–268.

14
. H. A. Simon. (1952c). A formal theory of interaction in social groups.
American Sociological Review, 17
, 202–211.

15
. Simon, 1991, op cit. pp 197-198.

16
. S. Carlson. (1979). The prize for economic science. In
Les Prix Nobel 1978
. Stockholm: The Nobel Foundation.

17
. C. I. Barnard. (1938).
The function of the executive
. Cambridge, MA: Harvard University Press.

18
. Simon, 1976, op cit., p. 76.

19
. H. A. Simon. (1957). Rationality in administrative decision making. In H. A. Simon.
Models of man
(pp. 196–206). New York: Wiley.

20
. H. A. Simon. (1950).
Administrative aspects of allocative efficiency
. Cowles Commission discourse paper, economics no. 281.

21
. H.. A. Simon to T. C. Koopmans, September 29, 1952. Herbert A. Simon papers. Carnegie-Mellon University Archives, Pittsburgh, PA. Further reference to material contained in these archives will be abbreviated HASP.

22
. H.. A. Simon to J. von Neumann, June 24, 1953, HASP, op cit.

23
. Simon, 1991, op cit., p. 201.

24
. Ibid.

25
. Ibid.

26
. A. Newell. (1955). The chess machine: An example of dealing with a complex task by adaptation.
Proceedings of the Western Joint Computer Conference, 7
, 101–108.

27
. H. A. Simon. (1955). A behavioral model of rational choice.
Quarterly Journal of Economics, 69
, 99–118.

28
. Ibid., p. 99.

29
. Ibid., p. 104.