perm filename LISP70.MAN[L70,TES] blob sn#055281
filedate 1973-07-18 generic text, type T, neo UTF8
00100 The Lisp70 Manual.
00300 How to do a few things in Lisp70, such as Factorial using
00400 recursion, iteration. Integer variables.
00600 Inner product of two arrays. Inner product of two
00900 Generic function inner product.
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.
01500 Printing on a disk file. Public variables.
01700 Reading from the terminal. From a file.
01900 Dictionary read-in using dot notation.
02100 Alphabetized dictionary: use of a lexicon.
02300 Long term memory.
02500 Garbage collection.
02700 Pattern matching (paper examples).
02900 Generators -- show random number generator and lexicon-entry generator.
03100 Coroutines. Streaming.
03300 Decision points. Failures. Suspends.
03500 Double arrow (backtrackable) rewrite rules.
00300 Lisp70 is a derivative of LISP, in the family line MLISP -> MLISP2 ->
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.
01500 LISP70 is best learned by examples. We will start with the
01600 venerable recursive function FACTORIAL.
01800 This won't work very well for anything but nonnegative integers.
01900 It is translated by the compiler to LISP as follows:
02100 (DECLARE FACTORIAL FUNCTION (N)
02200 (COND ((EQUAL N 0) 1)
02300 (T (TIMES N (FACTORIAL (SUB1 N)))) )
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
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
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:
05300 INTEGER FUNCTION FACTORIAL (INTEGER N) =
05400 IF N=0 THEN 1
05500 ELSE N * FACTORIAL(N-1) ;
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.
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.
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.
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.
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).
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.
11200 INTEGER FUNCTION FACTORIAL (INTEGER N) =
11400 INTEGER FAC ← 1 ;
11500 FOR INTEGER I ← 1 TO N DO FAC ← FAC * I ;
11600 RETURN(FAC) ;
11700 END ;
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.
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.