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
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
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
```