 |
| Grant Snider |
Continuo da qui l'esplorazione dagli inizi del Lisp.
Un documento, tardivo, del '79 nel quale John McCarthy ripercorre la History of Lisp.
This paper concentrates on the development of the basic ideas and distinguishes two periods - Summer 1956 through Summer 1958 when most of the key ideas were developed (some of which were implemented in the FORTRAN based FLPL), and Fall 1958 through 1962 when the programming language was implemented and applied to problems of artificial intelligence.
After 1962, the development of LISP became multi-stranded, and different ideas were pursued in different places.
As a programming language, LISP is characterized by the following ideas: computing with symbolic expressions rather than numbers, representation of symbolic expressions and other information by list structure in the memory of a computer, representation of information in external media mostly by multi-level lists and sometimes by S-expressions, a small set of selector and constructor operations expressed as functions, composition of functions as a tool for forming more complex functions, the use of conditional expressions for getting branching into function definitions, the recursive use of conditional expressions as a sufficient tool for building computable functions, the use of λ-expressions for naming functions, the representation of LISP programs as LISP data, the conditional expression interpretation of Boolean connectives, the LISP function eval that serves both as a formal definition of the language and as an interpreter, and garbage collection as a means of handling the erasure problem. LISP statements are also used as a command language when LISP is used in a time-sharing environment.
Some of these ideas were taken from other languages, but most were new. Parecchie idee nuove che si sarebbero sviluppate successivamente, arrivando fino a noi.
Il problema (mio) è che copierei tutto, devo trattenermi.
La preistoria del Lisp, dice JMC va dall'estate del 1956 a quella del '58. Tutto inizia con IPL2 e JOHNNIAC (ehi! che nome, sì per via di lui, ovviamente).
Usare IPL o FORTRAN? E c'era l'IBM 704 disponibile e Marvin Minsky...
The first problem was how to do list structure in the IBM 704. This computer has a 36 bit word, and two 15 bit parts, called the address and decrement, were distinguished by special instructions for moving their contents to and from the 15 bit index registers. Da qui, storia un po' lunga, vengono fuori car e cdr (dovrei usare le maiuscole). E intanto [a]t some point a cons(a,d,p,t) was defined, but it was regarded as a subroutine and not as a function with a value. In connection with IBM’s plane geometry project, Nathaniel Rochester and Herbert Gelernter (on the advice of McCarthy) decided to implement a list processing language within FORTRAN, because this seemed to the the easiest way to get started, and, in those days, writing a compiler for a new language was believed to take many man-years. This work was undertaken by Herbert Gelernter and Carl Gerberich at IBM and led to FLPL, standing for FORTRAN List Processing Language. Gelernter and Gerberich noticed that cons should be a function, not just a subroutine, and that its value should be the location of the word that had been taken from the free storage list. This permitted new expressions to be constructed out of subsubexpressions by composing occurrences of cons.
While expressions could be handled easily in FLPL, and it was used successfully for the Geometry program, it had neither conditional expressions nor recursion, and erasing list structure was handled explicitly by the program.
I invented conditional expressions in connection with a set of chess legal move routines I wrote in FORTRAN for the IBM 704 at M.I.T. during 1957-58. This program did not use list processing. The IF statement provided in FORTRAN 1 and FORTRAN 2 was very awkward to use, and it was natural to invent a function XIF(M,N1,N2) whose value was N1 or N2 according to whether the expression M was zero or not. The function shortened many programs and made them easier to understand, but it had to be used sparingly, because all three arguments had to be evaluated before XIF was entered, since XIF was called as an ordinary FORTRAN function though written in machine language. This led to the invention of the true conditional expression which evaluates only one of N1 and N2 according to whether M is true or false and to a desire for a programming language that would allow its use. Nota (questa la so): le versioni iniziali di FORTRAN consideravano le funzioni il cui nome iniziava con X come intere; quirk che venne corretto solo in seguito; non s'incontra quasi mai, questa è un'eccezione. A paper defining conditional expressions and proposing their use in Algol was sent to the Communications of the ACM but was arbitrarily demoted to a letter to the editor, because it was very short.
I spent the summer of 1958 at the IBM Information Research Department e [i]t led to the following innovations beyond FLPL:
Writing recursive function definitions using conditional expressions;
- The maplist function that forms a list of applications of a functional argument to the elements of a list (The original form was what is now called mapcar);
- To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church. Church used higher order functionals instead of using conditional expressions. Conditional expressions are much more readily implemented on computers;
- The recursive definition of differentiation made no provision for erasure
- of abandoned list structure.
A questo punto l'implementazione del LISP. In the Fall of 1958, I became Assistant Professor of Communication Sciences (in the EE Department) at M.I.T., and Marvin Minsky (then an assistant professor in the Mathematics Department) and I started the M.I.T. Artificial Intelligence Project, supportato dall'esercito che però non s'intrometteva (troppo) e senza che fosse prodotto alcuna proposta scritta. Intanto occupatevi di sei dottorandi.
The implementation of LISP began in Fall 1958. The original idea was to produce a compiler, but this was considered a major undertaking, and we needed some experimenting in order to get good conventions for subroutine linking, stack handling and erasure. Therefore, we started by hand-compiling various functions into assembly language and writing subroutines to provide a LISP ”environment”. These included programs to read and print list structure. I can’t now remember whether the decision to use parenthesized list notation as the external form of LISP data was made then or whether it had already been used in discussing the paper differentiation program.
Non copio tutto ma questa devo citarla, tenendo presente che si usa il FORTRAN e una sintassi fortran-like (M-notation): [a]llowing recursive function definitions required no new notation from the function definitions allowed in FORTRAN I - only the removal of the restriction - as I recall, unstated in the FORTRAN manual - forbidding recursive definitions. Uh! in anticipo per il Fortran di più di 20 anni!
E, finora non l'avevo vista così chiara: [t]he M-notation also used brackets instead of parentheses to enclose the arguments of functions in order to reserve parentheses for list-structure constants. It was intended to compile from some approximation to the M-notation, but the M-notation was never fully defined, because representing LISP functions by LISP lists became the dominant programming language when the interpreter later became available. A machine readable M-notation would have required redefinition, because the pencil-and-paper M-notation used characters unavailable on the IBM 026 key punch.
The READ and PRINT programs induced a de facto standard external notation for symbolic information, e.g. representing x + 3y + z by (PLUS X (TIMES 3 Y) Z) and (∀x)(P (x) ∨ Q(x, y) by (ALL (X) (OR (P X) (Q X Y))). Any other notation necessarily requires special programming, because standard mathematical notations treat different operators in syntactically different ways. This notation later came to be called “Cambridge Polish”, because it resembled the prefix notation of Lukasiewicz, and because we noticed that Quine had also used a parenthesized prefix notation.
IPL era rozzo per liberare la memoria, ci sono soluzioni migliori ed ecco il garbage collection.
One mathematical consideration that influenced LISP was to express programs as applicative expressions built up from variables and constants using functions. I considered it important to make these expressions obey the usual mathematical laws allowing replacement of expressions by expressions giving the same value. The motive was to allow proofs of properties of programs using ordinary mathematical methods. This is only possible to the extent that side-effects can be avoided. Unfortunately, side-effects are often a great convenience when computational efficiency is important, and “functions” with side-effects are present in LISP. Fuori dal Lisp il problema dei side-effects quando ho iniziato io non era considerato, in Fortran si metteva tutto nei COMMON, variabili globali spesso con nomi che cambiavano, voi giovani non avete idea.
However, the so-called pure LISP is free of side-effects, and (Cartwright and McCarthy) show how to represent pure LISP programs by sentences and schemata in first order logic and prove their properties. This is an additional vindication of the striving for mathematical neatness, because it is now easier to prove that pure LISP programs meet their specifications than it is for any other programming language in extensive use. (Fans of other programming languages are challenged to write a program to concatenate lists and prove that the operation is associative) questo allora, oggi...
Adesso altro fondamentale: [a]nother way to show that LISP was neater than Turing machines was to write a universal LISP function and show that it is briefer and more comprehensible than the description of a universal Turing machine. This was the LISP function eval[e,a], which computes the value of a LISP expression e - the second argument a being a list of assignments of values to variables. (a is needed to make the recursion work). Writing eval required inventing a notation representing LISP functions as LISP data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express LISP programs in practice. Logical completeness required that the notation used to express functions used as functional arguments be extended to provide for recursive functions, and the LABEL notation was invented by Nathaniel Rochester for that purpose. D.M.R. Park pointed out that LABEL was logically unnecessary since the result could be achieved using only LAMBDA - by a construction analogous to Church’s Y-operator, albeit in a more complicated way.
Il mio eroe adesso: S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter. No, già messo troppe volte il link alla Wiki per Steve.
The unexpected appearance of an interpreter tended to freeze the form of the language, and some of the decisions made rather lightheartedly for the “Recursive functions ...” paper later proved unfortunate. These included the COND notation for conditional expressions which leads to an unnecessary depth of parentheses, and the use of the number zero to denote the empty list NIL and the truth value false. Besides encouraging pornographic programming, giving a special interpretation to the address 0 has caused difficulties in all subsequent implementations.
Another reason for the initial acceptance of awkwardnesses in the internal form of LISP is that we still expected to switch to writing programs as M-expressions. The project of defining M-expressions precisely and compiling them or at least translating them into S-expressions was neither finalized nor explicitly abandoned. It just receded into the indefinite future, and a new generation of programmers appeared who preferred internal notation to any FORTRAN-like or ALGOL-like notation that could be devised.
Pausa 🙂
🔴
Nessun commento:
Posta un commento