nach oben

Minds and Machines

Erschienen in:

02.05.2017

AI and the Origins of the Functional Programming Language Style

verfasst von: Mark Priestley

Erschienen in: Minds and Machines | Ausgabe 3/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Lisp programming language is often described as the first functional programming language and also as an important early AI language. In the history of functional programming, however, it occupies a rather anomalous position, as the circumstances of its development do not fit well with the widely accepted view that functional languages have been developed through a theoretically-inspired project of deriving practical programming languages from the lambda calculus. This paper examines the origins of Lisp in the early AI programming work of the mid-to-late 1950s, and in particular in the work of Allen Newell, Cliff Shaw and Herbert Simon. Their 1956 program, the Logic Theory Machine, introduced new ideas about data and program structures that were articulated in response to perceived limitations in existing programming technique. Later writers, notably John Backus, have described these features as constituting a “programming language style” distinct from the traditional style that preceded it. The paper examines the origins of the earlier style in practices of manual computation, analyses the key technical differences between it and the style first manifested in the Logic Theory Machine, and concludes that programming practice and experience play a large and underappreciated role in the development of programming styles and languages.

Vorheriger Artikel Information and the Internet: An Analysis from the Perspective of the Science of the Artificial

Nächster Artikel Artificial Intelligence, Cybercities and Technosocieties

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

For the text of the lecture, from which the inline quotes in this section are taken, see Backus (1978).

Rosen (1967) and Sammet (1969) are the classic references from the 1960s. Backus (1981) reflected on the history of Fortran at the first ACM SIGPLAN History of Programming Languages conference in 1978. The papers from that conference were collected and published as Wexelblat (1981).

See, for example, Feigenbaum and Feldman (1963), vi, Rosen (1967) and Sammet (1969).

For a more extended discussion of the historiography of programming languages, see Priestley (2008), 12–17.

Best known as an economist, in 1964 Black completed a thesis at MIT which “combined the fundamentals of logic with computer science” and spent a year at the consultancy Bolt, Beranek and Newman working on the “theory of handling information for libraries and hospitals of the twenty-first century” (Merton and Scholes 1995). Sammet (1969) may have been familiar with Black’s article, as the book containing it is included in the list of references on Lisp on page 467.

Floyd was the Turing award winner in 1978, and his lecture was published as Floyd (1979).

Newell and Simon (1956b) give a comprehensive description of LT.

McCarthy et al. (1955). McCorduck (2004), 119, notes that “[a]rtificial-intelligence workers continually use machine when they mean what an outsider would call a program”. This usage is reminiscent of the equivalence that Turing noted between individual machines and their symbolic representations in a universal machine, but this may not its source. Early AI shared the cybernetic fascination with special-purpose gadgets, and was slow to fully internalize Turing’s point about the universality of the computer. See Priestley (2011), 147–153, for more on this.

Simon’s recollection is quoted in McCorduck (2004), 148. The historical narrative in the following paragraphs draws extensively on McCorduck’s book.

Newell (1954), 1. See Selfridge (1955) and Dinneen (1955) for details of their work on pattern recognition.

Newell and Simon (1956a) introduces the term “complex information process” and gives the earliest description of LT.

See Feigenbaum and Feldman (1963). For the historical background, see McCorduck (2004) and Boden (2006).

Newell and Shaw (1957), 220, 218. The Oxford English Dictionary cites this paper as the earliest computer-oriented use of the term “heuristic”.

See Goldstine and von Neumann (1947). In 1946, Haskell Curry and Willa Wyatt used a “Flow Chart” to illustrate the structure of an ENIAC program, but they did not use it in the development of the program and their notation differed “in principle” from von Neumann and Goldstine’s (Curry 1949, 7).

They wrote that “the first step has nothing to do with computing or machines … the second step has, at least, nothing to do with mechanization: It would be equally necessary if the problems were to be computed ‘by hand’ … [the third step] is necessary because of the computational character of the problem, rather than because of the use of a machine” (Goldstine and von Neumann 1947, 19).

For a comprehensive history of mathematical tables and their use, see Campbell-Kelly et al (2003).

For the EDVAC subroutine, see Lubkin (1947), 20, 28. Lubkin’s rather casual use of the term “library” suggests that it already had some currency within the EDVAC group. The work of Bartik’s group is discussed in Bartik (2013) and Haigh et al (2016). Wilkes et al (1951) describe the EDSAC subroutine library in great detail, including what became known as the “Wheeler jump”, an innovative and influential coding technique for transferring control between the main routine and what were termed “closed subroutines”.

In Wilkes et al (1951), some library subroutines, such as those to carry our integration, call “auxiliary subroutines” which represent the function being integrated. The three-level terminology of master, sub-, and auxiliary routines suggests a rather stereotyped and limiting approach, though of course the use of subroutines in actual EDSAC programming practice may have been more flexible.

See Benington (1956). Background on the SAGE project can be found in Hughes (1998) and Benington (1983), which also reprints the text of the 1956 talk.

See Simon (1962). I thank one of the anonymous referees for drawing my attention to this paper.

GPS was first described in Newell et al (1958). The history of IPL is sketched in Newell and Tonge (1960).

See Gelernter et al. (1960, 88).

The following paragraphs draw on the account given in McCarthy (1981).

See Priestley (2011, 220–223) for more on this. In this connection, it is interesting to note the comment made by Turner (2012): “The theoretical model behind LISP was Kleene’s theory of first order recursive functions”. He added in a footnote: “McCarthy made these statements, or very similar ones, in a contribution from the floor at the 1982 ACM symposium on Lisp and functional programming in Pittsburgh. No written version of this exists, as far as [I] know”.

Rather than following Backus in seeing the von Neumann languages as reflections of the underlying computer, it might be more accurate to describe the “von Neumann architecture” as having been developed to support a particular way of structuring and expressing computations.

Backus, J. (1973). Programming language semantics and closed applicative languages. In Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on principles of programming languages (pp. 71–86).

Backus, J. (1978). Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Communications of the ACM, 21(8), 613–641.MathSciNetCrossRefMATH

Backus, J. (1981). The history of FORTRAN I, II, and III. In Wexelblat, 1981, 25–45.

Bartik, J. J. (2013). Pioneer programmer. Kirksville: Truman State University Press.

Benington, H. D. (1956). Production of large computer programs. In Symposium on advanced programming methods for digital computers, ONR Symposium Report ACR-15, 15–28. (Office of Naval Research, Washington, DC, June 28-9, 1956.)

Benington, H. D. (1983). Production of large computer programs. Annals of the History of Computing, 5(4), 350–361.CrossRef

Black, F. (1964). Styles of programming in LISP. In E. C. Berkeley & D. G. Bobrow (Eds.), The programming language LISP: Its operation and applications (pp. 96–107). Cambridge: MIT Press.

Boden, M. A. (2006). Mind as machine: A history of cognitive science (Vol. 2). Oxford: Oxford University Press.

Campbell-Kelly, M., Croarken, M., Flood, R., & Robson, E. (2003). The history of mathematical tables: From Sumer to spreadsheets. Oxford: Oxford University Press.CrossRefMATH

Church, A. (1941). The calculi of lambda-conversion. (Annals of Mathematics Series, Number 6, Princeton: Princeton University Press.)

Curry, H. B. (1949). On the composition of programs for automatic computing. (Naval Ordnance Laboratory Memorandum 9805, 26 January 1949).

Curry, H. B., & Wyatt, W. A. (1946). A study of inverse interpolation of the Eniac. (Ballistic Research Laboratory, Aberdeen Proving Ground, MD. Report No. 615. 19 August, 1946.)

Dinneen, G. P. (1955). Programming pattern recognition. In Proceedings of the Western Joint Computer Conference (pp. 94–100).

Feigenbaum, E. A., & Feldman, J. (Eds.). (1963). Computers and thought. New York: McGraw-Hill.MATH

Floyd, R. W. (1979). The paradigms of programming. Communications of the ACM, 22(8), 455–460.CrossRef

Gelernter, H., Hansen, J. R., & Gerberich, C. L. (1960). A Fortran-compiled list-processing language. Journal of the ACM, 7(2), 87–101.CrossRefMATH

Goldstine, H. H., von Neumann, J. (1947). Planning and coding of problems for an electronic computing instrument. Part II, Volume 1. (Institute of Advanced Study, NJ. 1 April, 1947.)

Grattan-Guinness, I. (1990). Work for the hairdressers: The production of de Prony’s logarithmic and trigonometric tables. Annals of the History of Computing, 12(3), 177–185.CrossRefMATH

Grier, D. A. (2005). When computers were human. Princeton: Princeton University Press.

Haigh, T., Priestley, M., & Rope, C. (2016). ENIAC in action: Making and remaking the modern computer. Cambridge: MIT Press.

Harvard. (1946). A manual of operation for the Automatic Sequence Controlled Calculator. Cambridge: Harvard University Press.

Hudak, P. (1989). Conception, evolution, and application of functional programming languages. ACM Computing Surveys, 21(3), 359–411.CrossRef

Hughes, T. P. (1998). Rescuing prometheus. New York: Pantheon.

IBM. (1956). The FORTRAN automatic coding system for the IBM 704 EDPM: Programmer’s reference manual. (Applied Science Division and Programming Research Dept., IBM: New York, NY, October 15, 1956.)

IBM. (1958). Reference manual: FORTRAN II for the IBM 704 data processing system. New York: IBM.

Kernighan, B., & Plauger, P. J. (1974). The elements of programming style. Reading: Addison-Wesley, Second edition: 1978.

Lubkin, S. (1947). Proposed programming for the EDVAC. (Moore School of Electrical Engineering, Office of the Director Records, 1931–1948, UPD 8.4, University of Pennsylvania Archives and Records, box 8.)

McCarthy, J. (1959). Letter to the editor. Communications of the ACM, 2(8), 2–3.CrossRefMATH

McCarthy, J. (1960). Recursive functions of symbolic expressions and their computation by machine: Part I. Communications of the ACM, 3(4), 184–195.CrossRefMATH

McCarthy, J. (1981). History of LISP. In Wexelblat, 1981, 173–194.

McCarthy, J., Minsky, M. L., Rochester, N., & Shannon C. E. (1955) A proposal for the Dartmouth summer research project on artificial intelligence. (Dartmouth College, 31 August, 1955.)

McCorduck, P. (2004). Machines who think. (A. K. Peters, Natick, MA.)

Merton, R. C., & Scholes, M. S. (1995). Fischer black. The Journal of Finance, 50(5), 1359–1370.CrossRef

Newell, A. (1954). The chess machine: An example of dealing with a complex task by adaptation. (RAND Corporation, report P-620, 28 December, 1954.)

Newell, A., & Shaw, J. C. (1957). Programming the logic theory machine. In Proceedings of the western joint computer conference: Techniques for reliability (pp. 230–240).

Newell, A., Shaw, J. C., & Simon, H. A. (1958). Report on a general problem-solving program. (RAND Corporation, report P-1584, 30 December, 1958. Revised 9 Feb 1959.)

Newell, A., & Simon, H. A. (1956a). Current developments in complex information processing. (RAND Corporation, report P-850, 1 May, 1956.)

Newell, A., & Simon, H. A. (1956b). The Logic Theory Machine: A complex information processing system. IRE Transactions on Information Theory, 2(3), 61–79.CrossRef

Newell, A., & Tonge, F. M. (1960). An introduction to Information Processing Language V. Communications of the ACM, 3(4), 205–211.MathSciNetCrossRefMATH

Priestley, M. (2008). Logic and the development of programming languages, 1930–1975. (PhD thesis, University of London).

Priestley, M. (2011). A science of operations: Machines, logic and the invention of programming. London: Springer.CrossRefMATH

Rosen, S. (1967). Programming systems and languages. New York: McGraw-Hill.MATH

Sakoda, J. M. (1974). Structured programming in FORTRAN. ACM SIGSOC Bulletin, 6(1), 12–16.CrossRef

Sammet, J. (1969). Programming languages: History and fundamentals. Upper Saddle River: Prentice-Hall.MATH

Sammet, J. (1971). Application of extensible languages to specialized application languages. ACM SIGPLAN Notices, 6(12), 141–143.CrossRef

Sammet, J (1972). An overview of programming languages for specialized application areas. In AFIPS ‘72 (Spring) Proceedings of the May 16–18, 1972, Spring joint computer conference (pp. 299–311).

Selfridge, O. G. (1955). Pattern recognition and modern computers. In Proceedings of the western joint computer conference (pp. 91–93).

Simon, H. A. (1962). The architecture of complexity. Proceedings of the American Philosophical Society, 106(6), 467–482.

Stoyan, H. (1984). Early LISP History (1956–1959). In Proceedings of the 1984 ACM symposium on LISP and functional programming (pp. 299–310).

Turner, D. A. (2012). Some history of functional programming languages. In 13th International symposium on trends in functional programming. (Paper available at https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf. Accessed February 28, 2017.)

Van Gelder, A. (1977). Structured programming in Cobol: An approach for application programmers. Communications of the ACM, 20(1), 2–12.CrossRefMATH

Van Roy, P. (2009). Programming paradigms for dummies: What every programmer should know. (Paper available at https://www.info.ucl.ac.be/~pvr/VanRoyChapter.pdf. Accessed February 28, 2017.)

Wexelblat, R. L. (Ed.). (1981). History of programming languages. New York: Academic Press.MATH

Wilkes, M. V., Wheeler, D. J., & Gill, S. (1951). The preparation of programs for an electronic digital computer. Reading: Addison-Wesley.MATH

Titel: AI and the Origins of the Functional Programming Language Style
verfasst von: Mark Priestley
Publikationsdatum: 02.05.2017
Verlag: Springer Netherlands
Erschienen in: Minds and Machines / Ausgabe 3/2017
Print ISSN: 0924-6495
Elektronische ISSN: 1572-8641
DOI: https://doi.org/10.1007/s11023-017-9432-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2017

Algorithmic Iteration for Computational Intelligence

The Logic of Design as a Conceptual Logic of Information

Artificial Intelligence, Cybercities and Technosocieties

Deterrence by Norms to Stop Interstate Cyber Attacks

Artificial Intelligence in a New Context: “Internal” and “External” Factors

From Intelligence to Rationality of Minds and Machines in Contemporary Society: The Sciences of Design and the Role of Information

Premium Partner