IPL(ID:13/ipl001)
The first list-processing language
for Information Processing Language
Allen Newell, J.C. Shaw, H. Simon, RAND ca. 1954
The first list-processing language, also the first language to support recursion.
IPL-I was a theoretical design and never actually implemented. IPL-II written on JOHNNIAC, said by Sammet to be "one of the most significant events that has ever occurred in programming." IPL-V the first widely used non-numeric system
People: Hardware:
- IBM 650 IBM
Structures:
Related languages
| IPL | => | IPL-II | Implementation of | |
| IPL | => | LISP | Influence |
References:
in IBM Journal of Research and Development, 2(4), 1958 view details
Newell, Allen; Shaw, J. C.; and Simon, H. A. Chess-play~ng programs and the problem of complexity. IBM J. Res. Develop. 2 (1958), 320-335.
The authors compare recent attempts to describe intricate mechanical procedures which search for and select appropriate moves in chess. In all cases these procedures are discussed or presented as feasible programs for general purpose digital computers. They begin with Shannon's analysis [ Philos. Mag. (7) 41 (1950), 256-275; MR 11, 543 ] of the game as a large tree of valid positions with an appropriate selection of alternative moves, an appropriate exploration of continuations to a suitable depth, an evaluation of each continuation by a suitable criterion, and a selection method of a next move by means of an appropriate criterion. Shannon proposed searching all continuations to a fixed depth, evaluating by a single numerical function of stated position parameters, and selecting by a minimaxing procedure. The limitations in speed and storage capacity of present machines severely restrict the quality of the resulting play, not only by Shannon's procedure but by those further ones discussed, all of which essentially follow his analysis with occasional variations. These include programs by Turing for hand simulation [ B. V. Bowden, Faster Than Thought, Pitman, London, 1953; MR 15, 901; chap. 25 ] , the Los Alamos machine program [ Mister, Stein, Ulam, Walden and Wells, J. Assoc. Comput. Mach. (1957), 174-177 ] and the IBM 704 program [ Bernstein, Roberts, Arbuckle, and Belsky, "A chess playing program for the IBM 704", Proc. 1958 Western Joint Computer Conference, May, 1958 ] . Turing's evaluation function was mainly based on 'material value' at the static conclusion of those continuations involving exchanges. His program was a weak player. The Los Alamos program restricted itself to a 6 X 6 board (no bishops, no castling, etc.), considered all continuations two moves deep, and included mobility as well as material value in its evaluating function. It could beat a weak player, required 12 minutes per move, and needed only 600 machine instruction words. Finally, the IBM 704 program was for a full 8 X 8 board, considered only 7 plausible moves, with all continuations to a depth of two moves, and used an evaluation function including the consideration of king defense and area control, as well as mobility and material. A novelty in the programming technique is a sequence of 'plausible move generators'. The program required eight minutes per move and some 7000 machine instruction words. It was beaten by a good player.
The program designed by the authors for the Rand JOHNNIAC presents a number of notable advances. First of all it does not use a single evaluation number, but rather a vector of evaluations, accepting from a variable number of plausible moves the first achieving a number of goals whose priority can be changed in the program as the game proceeds. As in the Turing program, continuations are pursued until static positions with respect to the various goals are reached; and, as in the 704 program, a sequence of plausible move generating subroutine is used.
The second innovation is a powerful advance in the direction of flexibility. An automatic coding technique is used. Instead of programming in machine code, an interpretive routine permits the authors to program directly in an information processing command language of their own design [ see Newell, Shaw, and Simon, Psych. Rev. 65 (1958), 151-1661. They can therefore analyze heuristically human motivations and evaluations with respect to various types of subgoals in the game, specify these and program them as subroutines in their information processing language. The language (IPL) itself is designed for easy handling of tree structures and ready modification of programs operating upon them. Thus, as the programmer sees his program beaten, he can question the victor and add a new goal subroutine to the program, which therefore does not really have a fixed size. ).!
The authors estimate that their stated plan will need some 16,000 instruction words, both machine and IPL, and that each move might require from one to ten hours. A good part of the slowness is due to the translation time the machine needs in interpreting the IPL instructions.
The reviewer ventures to guess that not only will such limitations disappear with the design of a new generation of machines, but that the programs will be capable of simulating human intelligence in still another direction. The authors' program has the simulation built into it by the programmer. The same program, faced with the same position, will always produce the same move. However, it is possible, using the very programming techniques invented by the authors, as well as stochastic learning models, to program the machine to store its experience in successive games so as to modify its own response program. Any example of this in a game as complex as chess must wait for the next generation of computing machines, further advances in programming techniques, and advance in the design of formal languages.
S. Gore, Philadelphia, Pa. (Courtesy Mathematical Reviews)
in ACM Computing Reviews, January-December 1960 view details
in [ACM] CACM 4(01) (Jan 1961) view details
in Artificial languages view details
In the earliest days of 1954, most programming was done in machine language and in absolute octal at that. In 1955 Jules Schwartz wrote the first assembly routine for JOHNNIAC and Cliff Shaw produced a revised assembler in 1956. Then came QUAD, an interpretive programming system, and SMAC, a small compiler. Each was noted for being foolproof. The non-professional programmer could use these systems comfortably; his errors would be reported to him in great detail by the machine. There were other significant contributions to the programming art as well; among them were items with such names as EASY-FOX, CLEM, JBL-4, J-100, MORTRAN done by Mort Bernstein, and Load-and-Go.
In the late fifties, the nature of JOHNNIAC's task changed. The rental equipment from IBM carried most of the computing load from the RAND staff. JOHNNIAC became a free good; its time was available for research use. The cost of operation was sufficiently low that one need not be concerned about using large amounts of machine time. Much of its time was consumed by research on the general questions of artificial intelligence and the initials NSS came to be closely associated with JOHNNIAC. These are the initials of Allen Newell, Cliff Shaw, and Herb Simon who used the machine extensively for research. During this period came such achievements as:
in Artificial languages view details
in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details
in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details
in [ACM] CACM 15(06) (June 1972) view details
In late 1954, the authors began a collaboration with J. C. (Cliff) Shaw in research on complex information processing with computers. The initial goal was to develop a computer program that could learn to play chess, but in the autumn of 1955 this target was displaced by the interim goal of writing a program that could prove theorems in the propositional calculus of Principia Mathematica. Newell and Shaw, both on the staff of the Rand Corporation in Santa Monica, had access to the newly completed JOHNNIAC computer there, while Simon, on the faculty of Carnegie Institute of Technology, was a consultant to Rand.
In order to achieve our goals, we decided that it was essential to devise a programming language capable of handling large, complex symbol structures whose size and configuration would be extremely difficult to predict in advance, and would have to be modified during run time. Our solution was to organize memory in terms of list structures and to construct a language designed to operate on lists. By the end of 1955, the first list-processing language, IPL-II, had taken shape; early in the following year it was operating on the JO INNIAC and a theorem-proving system had been coded in it.
Meanwhile, Newell had moved to Pittsburgh in order to take a doctoral degree there, having interrupted his graduate education when he began work at Rand some years earlier. In Pittsburgh, he retained his affiliation with Rand, and the research continued vigorously, but with Shaw and Newell on opposite ends of a teletype wire that connected them across the continent -- a sort of prehistoric network with human node processors similar to Arpanet IMPs.
On the campus of Carnegie Institute of Technology, a few faculty members had been exposed, in the early 1950s, to the new electronic computers. As we have seen, one of these was Simon, another was Charles C. Holt, an economist and engineer. Both were associated with the Graduate School of Industrial Administration (GSIA), a "new- look" business school established in 1949 with a strong emphasis on the developing tools of operations research and management science. Holt Newell, and Simon thought the time ripe to bring a computer to the CIT campus, and were successful in persuading the dean of GSIA, G. L. Bach, and the dean of Science and Engineering, Richard Teare, to underwrite the cost. Since the electrical engineers on campus were mainly concerned with avoiding responsibility for maintaining such a machine if it arrived, and most mathematicians and scientists could not see how or why they would use one, there was no objection to locating the computer in the basement of GSIA.
Choosing an appropriate computer called for consultation with other universities that already had one, and consultation led to Alan Perlis at Purdue, with the result that an IBM 650 and Alan arrived in Pittsburgh in the spring and summer, respectively, of 1956. Perlis has told his own story of the 650 at Carnegie in the preceding article in this issue. Here, we need only record our deep gratitude for his imaginative and productive leadership of computing at the university during the decade and a half he was our colleague.
By the spring of 1956, a number of graduate students, enrolled in Simon's course on Mathematical Methods in Social Science, were considering doing theses on complex information processing (alias artificial intelligence). These included Edward A. Feigenbaum, Julian Feldman, Robert K. Lindsay, Fred M. Tonge, and soon afterward Geoffrey Clarkson. Although we could provide them with some access to the Rand machines (Tonge wrote his thesis program in IPL-IV on the JOHNNIAC), it became imperative that we bring up a list-processing language for student and faculty use at Carnegie. Today, a programmer might have second thoughts about putting a list-processing language on a machine with only 2000 words of highspeed memory. When we remember that the highspeed store of the JOHNNIAC was only 4096 words (supplemented by a drum with about 10,000 words of usable capacity), the memory limits of the 650, while severe, seemed manageable.
IPL-V, the language developed for the IBM 650, "started out in late 1957 to be a 'modified copy' of IPL-IV (then being implemented on JOHNNIAC) (Newell 1963, p. 86). An initial running system was produced under Newell's direction in early 1958, mainly by Carleton B. Hensley and Tonge (Hensley, Newell, and Tonge 1958). Meanwhile, since the Rand Corporation had acquired an IBM 704, it was decided that the language should be designed to run on both the 650 and the 704. The revised language, with Newell, Tonge, Feigenbaum, Bert Green, Jr., and George Mealy as its principal designers, was described, in June 1958, in a preliminary version of the IPL-V manual, and the system became operational on the 704 at the end of the summer of 1959 (Newell 1963).
Thus, IPL-V having been coded for both 650 and 704, and provided with a manual (first edition, 1961; second edition, 1964), became the first list-processing language to be made available for public use. Subsequently, IPL-V was brought up on a substantial number of other computers and continued for a decade to be an important language, both for research in artificial intelligence and cognitive science and for teaching the basic concepts of list processing.
A glance at the pioneering research that is collected in Feigenbaum and Feldman's Computers and Thought (1963) shows that the IPL-V system on the 650 at Carnegie made important contributions to the foundations of AI and cognitive science. Among the programs written at that time were Feigenbaum's EPAM, a simulation of verbal learning processes, Feldman's program for simulating human decisions in the binary choice experiment, Kenneth Laughery's program for concept formation, Lindsay's SAD SAM, an early program with natural language and reasoning capabilities, and Clarkson's simulation of the investment decisions of a bank trust officer. As can be seen from this list, most of this research focused on the simulation of human cognitive processes.
Although these programs were written in IPL-V, and at least partially debugged on the 650 at Carnegie, most experience in running them on actual tasks was gained on other machines. Both the small memory of the 650 and its brief tenure at Carnegie after IPL-V became available prevented extensive runs of large programs with it. So the greatest significance of the machine in the history of AI was as the instigator and test bed of the first public list-processing language, and as an instrument for teaching list processing to the first generation of students in cognitive science.
The availability of IPL-V on the 650, and of a carefully written manual describing the language (Newell et al. 1961; 1964), contributed much also to the diffusion of knowledge of list-processing techniques to other university campuses and AI research groups. Because it could be run on a wide variety of computers of the 1960s, someone quipped that IPL-V was a machine-independent language, and that the machine it was independent of was the 650.
An interesting, but probably undecidable, historical question is whether IPL-V made a significant contribution to the set of concepts that were some years later labeled "structured programming." At the time IPL-V was produced, mainstream systems programmers and researchers on algebraic programming languages paid little attention to list-processing languages, which were generally regarded as esoteric and unbearably wasteful of machine time and memory. It was probably Chapter II of Knuth's memorable Fundamental Algorithms (1969) that first gave them a measure of credibility outside the AI community. Therefore, although a strong case can be made that the central principles of structured programming were developed and employed extensively by users of list-processing languages, almost from the day those languages became available, the principles were likely largely unknown to the developers of algebraic languages who independently reinvented them.
The IPL-V manual is quite explicit in its advocacy of top-down programming and independent closed subroutines. A few brief quotes will indicate the explicitness of its conceptions in this domain.
One programming strategy, often called the "top- down" approach, is to divide each large process, no matter how complicated, into a small number of subprocesses. Each of these subprocesses is given a name, and its function -- the processing it accomplishes -- is defined precisely by specifying exactly what inputs it requires and what outputs it produces. How the subprocess will carry on this processing does not matter at this stage. (Kelly and Newell 1964, pp. 104-105)
Once any process is coded, attention can be directed to developing and coding each of its subprocesses, using exactly the same strategy of decomposing these into subprocesses. Ultimately, subprocesses are reached that can be defined directly in terms of the IPL primitive processes, so that the decomposition comes to a stop. Although apparently at each stage all the complexities are being relegated to the subprocesses and only codes for trivial processes are being written, it will be found at last that nothing complicated remains to be done at the bottom of the hierarchy. (1964, p. 105)
Another principle may be called the principle of isolation. The flexibility in hierarchical organization depends on each subroutine being isolated from the rest of the program, except for a small number of well-defined connections.... Concretely, one subroutine should not link to another. (1964, p. 109)
The top-down approach (with some needed qualifications, not quoted here), the characterization of processes solely in terms of inputs and outputs, hierarchical structure, and wariness of COTOS are all here, quite explicitly. Nearly a quarter-century later, the principles of programming enunciated in the IPL-V manual sound as modern and relevant as when they were written. It can be seen that the IBM 650 at Carnegie Institute of Technology played a significant role in the early research on artificial intelligence and cognitive science, not so much because it provided computing cycles -- although it did that, too -- as because it provided the occasion for developing the first widely used list-processing language, and a facility for training many early computer scientists in the concepts and skills required for using computers to do complex information processing.
in Annals of the History of Computing, 08(1) January 1986 (IBM 650 Issue) view details
in Annals of the History of Computing, 08(1) January 1986 (IBM 650 Issue) view details
Resources
- The IBM 650
external link