perm filename LISP70.MAN[L70,TES] blob sn#055281 filedate 1973-07-18 generic text, type T, neo UTF8

00100 The Lisp70 Manual. 00200 00300 How to do a few things in Lisp70, such as Factorial using 00400 recursion, iteration. Integer variables. 00500 00600 Inner product of two arrays. Inner product of two 00700 lists. 00800 00900 Generic function inner product. 01000 01100 Printing out an array of numbers. Printing out a list of numbers. 01200 Printing out a list of identifiers. Printing out a list of 01300 lists and various other things. 01400 01500 Printing on a disk file. Public variables. 01600 01700 Reading from the terminal. From a file. 01800 01900 Dictionary read-in using dot notation. 02000 02100 Alphabetized dictionary: use of a lexicon. 02200 02300 Long term memory. 02400 02500 Garbage collection. 02600 02700 Pattern matching (paper examples). 02800 02900 Generators -- show random number generator and lexicon-entry generator. 03000 03100 Coroutines. Streaming. 03200 03300 Decision points. Failures. Suspends. 03400 03500 Double arrow (backtrackable) rewrite rules. 03600 00100 LISP70 00200 00300 Lisp70 is a derivative of LISP, in the family line MLISP -> MLISP2 -> 00400 LISP70. 00500 In addition to the usual S-expression notation, like (PLUS A B), 00600 the programmer can write Algol-like notation, like A+B. 00700 There is also a pattern matching notation of particular clarity. 00800 To find the derivative of 2X with respect to X, 00900 one could call a function DERIVATIVE('(TIMES 2 X), 'X) where DERIVATIVE 01000 is defined by a collection of rules which include: 01100 (TIMES :A :V) :V -> :A 01200 The variable :A would match 2, the variable :V would match X, 01300 and the answer would be the value of :A, which is 2. 01400 01500 LISP70 is best learned by examples. We will start with the 01600 venerable recursive function FACTORIAL. 01700 01800 This won't work very well for anything but nonnegative integers. 01900 It is translated by the compiler to LISP as follows: 02000 02100 (DECLARE FACTORIAL FUNCTION (N) 02200 (COND ((EQUAL N 0) 1) 02300 (T (TIMES N (FACTORIAL (SUB1 N)))) ) 02400 02500 This in turn is translated to machine language and is stored away 02600 ready to invoke by a function call Note that all programs 02700 are compiled; there is no interpreter. Even when EVAL 02800 is called at run-time, the compiler is used to generate 02900 code that is executed and then discarded. 03000 This has the advantage that a program will 03100 run the same whether you are in debugging or in production. 03200 This is unlike other LISP systems, which all claim to have 03300 compatible interpreters and compilers, but don't when 03400 you read the fine print or actually try it. (SPECIAL 03500 GLOBALVAR∞ 03600 03700 Always compiling has the disadvantage that it takes longer to 03800 get a function started executing the first time it is called, 03900 because it has to be compiled first. To minimize these delays 04000 which are especially bothersome during debugging, LISP70 04100 only translates from the M-notation to the S-notation 04200 when a function is read in. The final translation to 04300 machine language is deferred until the first time the function is 04400 called. Thus, if there is an error in the first function you call, 04500 you won't have to wait for an entire compilation to find this 04600 out. 04700 04800 Another advantage of deferring final translation is that the 04900 compiler can generate much better code when it knows 05000 about the functions that are called from any given function. 05100 Variables can be typed to help the compiler generate better code: 05200 05300 INTEGER FUNCTION FACTORIAL (INTEGER N) = 05400 IF N=0 THEN 1 05500 ELSE N * FACTORIAL(N-1) ; 05600 05700 In this example, the variable N is declared to be type INTEGER. 05800 If someone calls FACTORIAL(NIL), the compiler will give an error 05900 message. If someone calls FACTORIAL(Y), and the compiler can't 06000 tell what the type of the value of Y will be at run time, it inserts 06100 a run-time check to report an error if FACTORIAL is called 06200 with a non-integer argument. 06300 The function itself is also declared integer. This means that 06400 its result must be an integer. Any caller can be confident that 06500 an integer will be returned. None of the horrible "boxing" and 06600 "interning" and "FIXNUMing" that happens to integers in LISP 06700 will happen to your integers if you declare your INTEGER 06800 variables and INTEGER functions to be type INTEGER. 06900 07000 07100 The code generated for the function FACTORIAL itself is 07200 better than in the first version, because the functions 07300 EQUAL (=), TIMES (*), and DIFFERENCE (-) don't have to check that 07400 their arguments are numbers; in fact, they compile integer 07500 arithmetic inline in the second version. Furthermore, the 07600 recursive call on FACTORIAL does not have to check to 07700 see that N-1 is an integer. 07800 07900 If FACTORIAL is passed a negative argument, it will go in an 08000 non-terminating loop. After a while, 08100 either a push-down stack will overflow or the TIMES function 08200 will generate a product that exceeds the machine precision. 08300 In either case, the program will pause and tell you one of the 08400 following things: 08500 DEEP RECURSION IN FACTORIAL(N= -7642). CONTINUEλY OR N) 08600 (-14 * -5872486) EXCEEDS MACHINE CAPACITY. TRUNCATEλY OR N) 08700 If you answer Y, the program will continue and you will not 08800 be asked again about the same difficulty. In the case of 08900 a deep recursion, the stacks are enlarged. If it needs to 09000 be enlarged again, you will be not be told, 09100 but if memory space is completely exhausted, you will be told 09200 about that instead. 09300 09400 If you would rather not receive such error messages, or would 09500 rather receive more of them, read the section on ERRORS AT RUNTIME. 09600 09700 If you answer N instead of Y to the above questions, you will be 09800 given an opportunity to debug your program. Right now, the debugger 09900 is not as powerful as some, but you can find out how you got 10000 where you are, interrogate variables, set breakpoints at the 10100 beginnings and ends of functions, and in fact evaluate any 10200 expression (in either M-notation or S-notation). 10300 10400 One way to avoid deep recursions is to use 10500 what is loosely known in computerese as iteration, i.e., loops. 10600 This won't prevent excessive products, but it will prevent stack 10700 overflows and sometimes speed up a program. LISP70 is full of 10800 iteration facilities; probably there are more than you need, but we 10900 will go to great lengths to avoid GO-TO's (which are 11000 illegal) and other confusions. 11100 11200 INTEGER FUNCTION FACTORIAL (INTEGER N) = 11300 BEGIN 11400 INTEGER FAC ← 1 ; 11500 FOR INTEGER I ← 1 TO N DO FAC ← FAC * I ; 11600 RETURN(FAC) ; 11700 END ; 11800 11810 BEGIN...END is like a LISP PROG or an Algol block. There can be 11820 declarations local to the block. These declarations can bind 11830 variables to initial values and type the variables. In the 11840 example, the variable FAC is declared local to the block, 11850 obscuring any meaning the name FAC had outside the 11860 block. The variable FAC is typed as an INTEGER, and initiallized to 1. 11870 If no initiallization were mentioned, it would have 11880 been initiallized to zero. 11890 11900 After the declaration of FAC 11910 comes a FOR statement as in Algol or MLISP. Notice that 11920 I is declared INTEGER; this makes it local to the FOR statement. 11930 If N=0, the loop is executed zero times. What happens if 11940 N is greater than zero should be obvious. 11950