Continuo da quì l'esplorazione dgli inizi del Lisp
Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I è il paper che introduce il Lisp, ci racconta tutto quello che serve per iniziare. Siccome c'è tutto Part II non ci sarà. Il PDF non è perfetto, forse meglio usare la versione HTML.
A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artificial Intelligence group at M.I.T. The system was designed to facilitate experiments with a proposed system called the Advice Taker, whereby a machine could be instructed to handle declarative as well as imperative sentences and could exhibit "common sense" in carrying out its instructions. The original proposal for the Advice Taker was made in November 1958. The main requirement was a programming system for manipulating expressions representing formalized declarative and imperative sentences so that the Advice Taker system could make deductions.
In the course of its development the Lisp system went through several stages of simplification and eventually came to be based on a scheme for representing the partial recursive functions of a certain class of symbolic expressions. This representation is independent of the IBM 704 computer, or of any other electronic computer, and it now seems expedient to expound the system by starting with the class of expressions called S-expressions and the functions called S-functions.
Qui (e siamo appena nel secondo paragrafo ci sono due grosse notizie, il Lisp non sarà legato al computer attualmente disponibile e usato per lo sviluppo e sarà basato su funzioni ricorsive. Ecco siamo ai tempi in cui domina il Fortran (ancora in non standardizzato, roba interna IBM e Academia, anche se c'è già Algol, tentativamente).
Una cosa che il Fortran vieta espressamente è la ricorsività, sia diretta che indiretta. Se ricordo bene la ragione era dovuta alla scarsità di memoria disponibile, ma niente panico, trasformi la serie di chiamate ricorsive in un ciclo (non so se è sempre possibile, dovrei pensarci su o fare un salto a quell'epoca con la macchina del tempo).
In this article, we first describe a formalism for defining functions recursively. We believe this formalism has advantages both as a programming language and as vehicle for developing a theory of computation. Next, we describe S-expressions and S-functions, give some examples, and then describe the universal S-function apply which plays the theoretical role of a universal Turing machine and the practical role of an interpreter.
L'informatica, al tempo, è giovane e si devono definire tante cose, funzioni parziali che possono essere indeterminate per certi argomenti, i predicati (funzioni che ritornano un valore booleano T o F), and e or, le espressioni condizionali (COND, non IF). La ricorsività viene definita come [b]y using conditional expressions we can, without circularity, define functions by formulas in which the defined function occurs, seguono esempi, è una novità. E attenzione che [t]here is no guarantee that the computation determined by a recursive definition will ever terminate and, for example, an attempt to compute n! from our definition will only succeed if n is a non-negative integer. If the computation does not terminate, the function must be regarded as undefined for the given argument.
Sempre tra le cose nuove la distinzione tra Functions and Forms. It is usual in mathematics --outside of mathematical logic-- to use the word 'function' imprecisely and to apply it to forms such as y^2 + x. Because we shall later compute with expressions for functions, we need a distinction between functions and forms and a notation for expressing this distinction. This distinction and a notation for describing it, from which we deviate trivially, is given by Church. Salto ma si arriva a λ, per l'esempio trattato λ((x,y), y^2 +x) che risolve l'ambiguità di f(3,4) essendo ovviamente λ((x,y),y^2+x)(3,4)=19. OK, c'è di più, le variabili sono dummy, possono essere cambiate, cose che adesso si da per scontato ma allora era tutto un mondo nuovo.
Con le funzioni ricorsive lambda diventa inadeguata, vedi l'esempio di sqrt. Qui la proposta non è quella che avrebbe vinto alla lunga, dipende dalla prassi del Fortran, anzi dal codice macchina, si introduce label. Personalmente sono contento di non aver lispato all'epoca, ma le stesse cose le ho fatte, parecchie volte in Fortran (e Basic).
Uh, ancora lungo il paper; pausa 🙂
🔴
Nessun commento:
Posta un commento