perm filename MICRO.S78[206,LSP]1 blob sn#344582 filedate 1978-03-31 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00002 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .s(MICRO, A MICRO-MANUAL FOR LISP - MOSTLY TRUTHFUL) C00013 ENDMK C⊗; .s(MICRO, A MICRO-MANUAL FOR LISP - MOSTLY TRUTHFUL) .BEGIN "MICRO" .at "z1" ⊂"%41%*"⊃ .at "zn" ⊂"%4n%*"⊃ .ITEM←0 .ss Basic notions. LISP data are symbolic expressions that can be either %2atoms%1 or %2lists%1. %2Atoms%1 are strings of letters and digits and other characters not otherwise used in LISP. A ⊗list consists of a left parenthesis followed by zero or more atoms or lists separated by spaces and ending with a right parenthesis. Examples: $$A, ONION, (), (A), (A ONION A), (PLUS A (TIMES B ONION) 1)$. The LISP programming language is defined by rules for %2evaluating%1 certain LISP expressions to yield other LISP expressions as their values. The function ⊗value used in giving these rules is not part of the LISP language but rather part of the informal language in which LISP is being defined. Likewise, the italic letters ⊗e and ⊗a (sometimes with subscripts) denote LISP expressions, the letter ⊗v (usually subscripted) denotes an atom serving as a variable, and the letter ⊗f stands for a LISP expression serving as a function name. #. ⊗⊗value ($QUOTE e) = e⊗. For example, the value of $$(QUOTE A)$ is $$A$. #. ⊗⊗value ($CAR e)⊗, where ⊗⊗value e⊗ is a non-empty list, is the first element of ⊗⊗value_e⊗. Thus ⊗⊗value_$$(CAR_(QUOTE_(A_B_C)))$_=_$$A$. #. ⊗⊗value ($CDR e)⊗, where ⊗⊗value e⊗ is a non-empty list, is the the list that remains when the first element of ⊗⊗value_e⊗ is deleted. Thus ⊗⊗value_$$(CDR (QUOTE (A B C)))$ = $$(B C)$.⊗ #. ⊗⊗value ($CONS e1 e2)⊗, is the list that results from prefixing ⊗⊗value_e1⊗ onto the list ⊗⊗value_e2⊗. Thus ⊗⊗value_$$(CONS (QUOTE A) (QUOTE (B C)))$ = $$(A B C)$.⊗ #. ⊗⊗value ($EQUAL e1 e2)⊗ is qT if ⊗⊗value e1 = value e2⊗. Otherwise, its value is qNIL. Thus ⊗⊗value_$$(EQUAL_(CAR_(QUOTE_(A_B)))_(QUOTE_A))$_=_qT⊗. #. ⊗⊗value ($ATOM e) = qT⊗ if ⊗⊗value e⊗ is an atom; otherwise its value is qNIL. #. ⊗⊗value ($COND (pz1 ez1) ... (pzn ezn)) = value e%4i%*⊗, where ⊗⊗p%4i%*⊗ is the the first of the ⊗⊗p⊗'s whose value is not qNIL. Thus ⊗⊗value_$$(COND_((ATOM_(QUOTE_A))_(QUOTE_B))_((QUOTE_T)_(QUOTE_C)))$_=_$$B$⊗. #. An atom ⊗v, regarded as a variable, may have a value. #. ⊗⊗value (($LAMBDA (vz1 ... vzn) e) ez1 ... ezn)⊗ is the same as ⊗⊗value_e⊗ but in an environment in which the variables ⊗⊗vz1_..._vzn⊗ take the values of the expressions ⊗⊗ez1_..._ezn⊗ in the original environment. Thus ⊗⊗value_$$((LAMBDA_(X_Y)_(CONS_(CAR_X)_Y))_(QUOTE_(A_B))_(CDR_(QUOTE_(C_D))))$_=_$$(A_D)$⊗. #. Here's the hard one. ⊗⊗value (($LABEL f ($LAMBDA (vz1 ... vzn) e)) ez1 ... ezn)⊗ is the same as ⊗⊗value_(($LAMBDA (vz1_..._vzn)_e)_ez1_..._ezn)⊗, but whenever ⊗⊗(f_az1 ..._azn)⊗ must be evaluated, ⊗f is replaced by ⊗⊗($LABEL f_($LAMBDA (vz1_..._vzn)_e))⊗. Lists beginning with $LABEL define functions recursively. This is the core of LISP, and here are more examples: ⊗⊗⊗value $$(CAR X)$ = $$(A B)$⊗ if ⊗⊗value $$X$ = $$((A B) C)$⊗, and ⊗⊗⊗value$$((LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X)))))) (QUOTE ((A B) C)))$ = $$A$.⊗ Thus $$((LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X))))))$, is the LISP name of a function ⊗ff such that ⊗⊗ff_e⊗ is the first atom in the written form of ⊗e. Note that the list ⊗ff is substituted for the atom $FF twice in the course of evaluating the above expression. Difficult mathematical type exercise: Find a list ⊗e such that ⊗⊗value e = e⊗. You may now program in LISP. Call LISP system on a time-sharing computer, type in a list, and LISP will type back its value. .ss Some Useful Abbreviations. The above LISP needs some abbreviations for practical use. .item←0 #. So as not to describe a LISP function each time it is used, we define it permanently by typing ⊗⊗($DEFUN f_(vz1_..._vzn)_e)⊗. Thereafter ⊗⊗(f_ez1_..._ezn)⊗ is evaluated by evaluating ⊗e with the variables ⊗⊗vz1,_..._,vzn⊗ taking the values ⊗⊗value_ez1,_..._,value_ezn⊗ respectively. Thus, after we define $$(DEFUN_FF_(X)_(COND_((ATOM_X)_X)_((QUOTE_T)_(FF_(CAR_X)))))$, typing $$(FF_(QUOTE_((A_B)_C)))$, gets $$A$ from LISP. #. The variables $$T$ and $$NIL$ are permanently assigned the values $$T$ and $$NIL$, and $$NIL$ is the name of the null list (). Therefore, the above definition can be written $$(DEFUN_FF_(X)_(COND_((ATOM_X)_X)_(T_(FF_(CAR_X)))))$. #. We have the permanent function definitions $$(DEFUN NULL (X) (EQUAL X NIL))$ and $$(DEFUN CADR (X) (CAR (CDR X)))$, and similarly for arbitrary combinations of $$A$ and $$D$. #. ⊗⊗($LIST ez1 ... ezn)⊗ is defined for each ⊗n to be ⊗⊗($CONS ez1_($CONS ..._($CONS ezn_qNIL)))⊗. #. ⊗⊗($AND p q)⊗ abbreviates ⊗⊗($COND (p_q)_(qT_qNIL))⊗. $$AND$s with more terms are defined similarly, and the propositional connectives $$OR$ and $$NOT$ abbreviate similar conditional expressions. Now we can give some further examples of LISP function definitions: $$(DEFUN ALT (X) (COND ((OR (NULL X) (NULL (CDR X))) X) (T (CONS (CAR X) (ALT (CDDR X))))))$ defines a function that gives alternate elements of a list starting with the first element. Thus $$(ALT_(QUOTE_(A_B_C_D_E)))$_=_$$(A_C_E)$. .NOFILL $$(DEFUN SUBST (X Y Z) (COND ((ATOM Z) (COND ((EQUAL Z Y) X) (T Z)))$ $$(T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z))))))$ .FILL gives the result of substituting $$X$ for $$Y$ in $$Z$. Thus $$(SUBST (QUOTE (PLUS X Y)) (QUOTE V) (QUOTE (TIMES X V)))$ = $$(TIMES X (PLUS X Y))$. .END "MICRO"