@@ -1,2263 +1,2263 @@ -\documentstyle[11pt,reduce]{article} -\title{The Standard Lisp Report} -\date{} -\author{Jed Marti \\ A. C. Hearn \\ M. L. Griss \\ C. Griss} - -%%% Function/method definition. -%%% de{fname}{arglist}{type}{text} For short arg lists. -%%% DE{fname}{arglist}{type}{text} For long arg lists. -\newlength{\argwidth} % Width of argument box. -\setlength{\argwidth}{4in} -\newlength{\dewidth} -\setlength{\dewidth}{4.5in} % Width of text box. - -\newcommand{\de}[4] -{\vspace{.25in} \noindent -\begin{minipage}[t]{\textwidth} \index{#1} {\f{#1}}{#2}\hfill{\em #3} \\ -\hspace*{.25in}\begin{minipage}[t]{\dewidth} #4 \end{minipage} -\end{minipage} } - -%%% Global/fluid variable description. -%%% variable{name}{initial value}{type}{text} -\newcommand{\variable}[4] -{\vspace{.25in} \noindent -\begin{minipage}[t]{\textwidth} \index{#1 (#3)} {\bf #1} = #2 \hfill {\em #3} - \\ -\hspace*{.25in} \ \begin{minipage}[t]{\dewidth} #4 \end{minipage} -\end{minipage}} - -%%% Command to display an error or warning message in teletype format. Also -%%% leaves blank vertical space around it. -\newcommand{\errormessage}[1] -{\vspace{.1in} \noindent {\tt #1} \\ \vspace{.1in}} - - -%%% \p is a parameter name (or argument). Just do this as bf. -\newcommand{\p}[1] {{\bf #1}} -%%% \ty is a type - do as italics. -\newcommand{\ty}[1] {{\em #1}} -\begin{document} -\maketitle - -\section{Introduction} -Although the programming language LISP was first formulated in -1960~\cite{LISP1.5}, a widely accepted standard has never appeared. As -a result, various dialects of LISP were -produced~\cite{CDC-LISP,LISP/360,MACLISP,Interlisp,LISPF1,LISP1.6} in -some cases several on the same machine! Consequently, a user often -faces considerable difficulty in moving programs from one system to -another. In addition, it is difficult to write and use programs which -depend on the structure of the source code such as translators, -editors and cross-reference programs. - -In 1969, a model for such a standard was produced~\cite{Hearn:69} as -part of a general effort to make a large LISP based algebraic -manipulation program, REDUCE~\cite{REDUCE3.3}, as portable as -possible. The goal of this work was to define a uniform subset of -LISP 1.5 and its variants so that programs written in this subset -could run on any reasonable LISP system. - -In the intervening years, two deficiencies in the approach taken in -Ref.~\cite{Hearn:69} have emerged. First in order to be as general as -possible, the specific semantics and values of several key functions -were left undefined. Consequently, programs built on this subset could -not make any assumptions about the form of the values of such -functions. The second deficiency related to the proposed method of -implementation of this language. The model considered in effect two -versions of LISP on any given machine, namely Standard LISP and the -LISP of the host machine (which we shall refer to as Target LISP). -This meant that if any definition was stored in interpretive form, it -would vary from implementation to implementation, and consequently one -could not write programs in Standard LISP which needed to assume any -knowledge about the structure of such forms. This deficiency became -apparent during recent work on the development of a portable compiler -for LISP~\cite{PLC}. Clearly a compiler has to know precisely the -structure of its source code; we concluded that the appropriate source -was Standard LISP and not Target LISP. - -With these thoughts in mind we decided to attempt again a definition -of Standard LISP. However, our approach this time is more aggressive. -In this document we define a standard for a reasonably large subset of -LISP with as precise as possible a statement about the semantics of -each function. Secondly, we now require that the target machine -interpreter be modified or written to support this standard, rather -than mapping Standard LISP onto Target LISP as previously. - -We have spent countless hours in discussion over many of the -definitions given in this report. We have also drawn on the help and -advice of a lot of friends whose names are given in the -Acknowledgements. Wherever possible, we have used the definition of a -function as given in the LISP 1.5 Programmer's Manual~\cite{LISP1.5} -and have only deviated where we felt it desirable in the light of LISP -programming experience since that time. In particular, we have given -considerable thought to the question of variable bindings and the -definition of the evaluator functions EVAL and APPLY. We have also -abandoned the previous definition of LISP arrays in favor of the more -accepted idea of a vector which most modern LISP systems support. -These are the places where we have strayed furthest from the -conventional definitions, but we feel that the consistency which -results from our approach is worth the redefinition. - -We have avoided entirely in this report problems which arise from -environment passing, such as those represented by the FUNARG problem. -We do not necessarily exclude these considerations from our standard, -but in this report have decided to avoid the controversy which they -create. The semantic differences between compiled and interpreted -functions is the topic of another paper~\cite{PLC}. Only functions -which affect the compiler in a general way make reference to it. - -This document is not intended as an introduction to LISP rather it is -assumed that the reader is already familiar with some version. The -document is thus intended as an arbiter of the syntax and semantics of -Standard LISP. However, since it is not intended as an implementation -description, we deliberately leave unspecified many of the details on -which an actual implementation depends. For example, while we assume -the existence of a symbol table for atoms (the "object list" in LISP -terminology), we do not specify its structure, since conventional LISP -programming does not require this information. Our ultimate goal, -however, is to remedy this by defining an interpreter for Standard -LISP which is sufficiently complete that its implementation on any -given computer will be straightforward and precise. At that time, we -shall produce an implementation level specification for Standard LISP -which will extend the description of the primitive functions defined -herein by introducing a new set of lower level primitive functions in -which the structure of the symbol table, heap and so on may be -defined. - -The plan of this chapter is as follows. In Section~\ref{dtypes} we -describe the various data types used in Standard LISP. In -Section~\ref{slfns}, a description of all Standard LISP functions is -presented, organized by type. These functions are defined in an RLISP -syntax which is easier to read than LISP S-expressions. -Section~\ref{slglobals} describes global variables which control the -operation of Standard LISP. - - -\section{Preliminaries} -\label{dtypes} -\subsection{Primitive Data Types} -\label{pdat} -\begin{description} -\item[integer] Integers are also called "fixed" numbers. The magnitude of -an integer is unrestricted. Integers in the LISP input stream are -\index{integer ! input} \index{integer ! magnitude} -recognized by the grammar: - -\begin{tabbing} -\s{digit} ::= 0$\mid$1$\mid$2$\mid$3$\mid$4$\mid$5$\mid$6$\mid$7$\mid$8$\mid$9 -\\ -\s{unsigned-integer} ::= \s{digit}$\mid$\s{unsigned-integer}\s{digit} \\ -\s{integer} ::= \= \s{unsigned-integer} $\mid$ \\ -\> +\s{unsigned-integer} $\mid$ \\ -\> ---\s{unsigned-integer} -\end{tabbing} - -\item[floating] - Any floating point number. The precision of floating point -\index{floating ! input} -numbers is determined solely by the implementation. In BNF floating -point numbers are recognized by the grammar: - -\begin{tabbing} -\s{base} ::= \= \s{unsigned-integer}.$\mid$.\s{unsigned-integer}$\mid$ \\ -\> \s{unsigned-integer}.\s{unsigned-integer} \\ -\> \s{unsigned-floating} ::= \s{base}$\mid$ \\ -\> \s{base}E\s{unsigned-integer}$\mid$ \\ -\> \s{base}E-\s{unsigned-integer}$\mid$ \\ -\> \s{base}E+\s{unsigned-integer} \\ -\s{floating} ::= \= \s{unsigned-floating}$\mid$ \\ -\> +\s{unsigned-floating}$\mid$-\s{unsigned-floating} -\end{tabbing} - -\item[id] An identifier is a string of characters which may have the -\index{id ! input} \index{identifier (see id)} -following items associated with it. - -\begin{description} -\item[print name] \index{print name} The characters of the identifier. - -\item[flags] An identifier may be tagged with a flag. Access is by the -FLAG, REMFLAG, and FLAGP functions defined in section~\ref{plist} on -page~\pageref{plist}. \index{FLAG} \index{REMFLAG} \index{FLAGP} - -\item[properties] \index{properties} An identifier may have an -indicator-value pair associated with it. Access is by the PUT, GET, -and REMPROP functions defined in section~\ref{plist} on -page~\pageref{plist}. -\index{PUT} \index{GET} \index{REMPROP} - -\item[values/functions] An identifier may have a value associated with -\index{values} \index{functions} it. Access to values is by SET and SETQ -defined in \index{SET} \index{SETQ} section~\ref{varsandbinds} on -page~\pageref{varsandbinds}. The method by which the value is attached -to the identifier is known as the binding type, being one of LOCAL, -GLOBAL, or FLUID. Access to the binding type is by the GLOBAL, -GLOBALP, FLUID, FLUIDP, and UNFLUID functions. -\index{GLOBAL} \index{GLOBALP} \index{FLUID} \index{FUIDP} \index{UNFLUID} - -An identifier may have a function or macro associated with it. Access -is by the PUTD, GETD, and REMD functions (see ``Function Definition'', -section~\ref{fdef}, on page~\pageref{fdef}). \index{PUTD} \index{GETD} -\index{REMD} An identifier may not have both a function and a value -associated with it. - -\item[OBLIST entry] \index{OBLIST entry} An identifier may be entered and -removed from a structure called the OBLIST. Its presence on the OBLIST -does not directly affect the other properties. Access to the OBLIST is -by the INTERN, REMOB, and READ functions. \index{INTERN} \index{REMOB} -\index{READ} -\end{description} - -The maximum length of a Standard LISP identifier is 24 characters -\index{id ! maximum length} -(excluding occurrences of the escape character !) but an -\index{id ! escape character} -implementation may allow more. Special characters (digits in the first -position and punctuation) must be prefixed with an escape character, -an ! in Standard LISP. In BNF identifiers are recognized by the -grammar: - - -\begin{tabbing} -\s{special-character} ::= !\s{any-character} \\ -\s{alphabetic} ::= \\ -\hspace*{.25in} \= A$\mid$B$\mid$C$\mid$D$\mid$E$\mid$F$\mid$G$\mid$H$ -\mid$I$\mid$J$\mid$K$\mid$L$\mid$M$\mid$N$\mid$O$\mid$P$\mid$Q$\mid$R$ -\mid$S$\mid$T$\mid$U$\mid$V$\mid$W$\mid$X$\mid$Y$\mid$Z$\mid$ \\ -\> a$\mid$b$\mid$c$\mid$d$\mid$e$\mid$f$\mid$g$\mid$h$\mid$i$\mid$j$ -\mid$k$\mid$l$\mid$m$\mid$n$\mid$o$\mid$p$\mid$q$\mid$r$\mid$s$\mid$t$ -\mid$u$\mid$v$\mid$w$\mid$x$\mid$y$\mid$z \\ -\s{lead-character} ::= \s{special-character}$\mid$\s{alphabetic} \\ -\s{regular-character} ::= \s{lead-character}$\mid$\s{digit} \\ -\s{last-part} ::= \= \s{regular-character} $\mid$ \\ -\> \s{last-part}\s{regular-character} \\ -\s{id} ::= \s{lead-character}$\mid$\s{lead-character}\s{last-part} -\end{tabbing} - -Note: Using lower case letters in identifiers may cause portability -problems. Lower case letters are automatically converted to upper case -when the !*RAISE flag is T. \index{*RAISE (global)} - - -\item[string] \index{string} A set of characters enclosed in double quotes as -in "THIS IS A STRING". A quote is included by doubling it as in "HE -SAID, ""LISP""". The maximum size of strings is 80 characters but an -implementation may allow more. Strings are not part of the OBLIST and -are considered constants like numbers, vectors, and function-pointers. - -\item[dotted-pair] A primitive structure which has a left and right part. -\index{dotted-pair} \index{dot-notation} -A notation called {\em dot-notation} is used for dotted pairs and -takes the form: - -\begin{tabbing} -(\s{left-part} . \s{right-part}) -\end{tabbing} - -The \s{left-part} is known as the CAR portion and the \s{right-part} -as the CDR portion. The left and right parts may be of any type. -Spaces are used to resolve ambiguity with floating point numbers. - - -\item[vector] \index{vector} A primitive uniform structure in which -an integer index is used to access random values in the structure. The -individual elements of a vector may be of any type. Access to vectors -is restricted to functions defined in ``Vectors'' -section~\ref{vectors} on page~\pageref{vectors}. A notation for -vectors, {\em vector-notation}, has the elements of a vector -surrounded -\index{vector-notation} -by square brackets\footnote{Vector elements are not separated by -commas as in the published version of this document.} - - -\begin{tabbing} -\s{elements} ::= \s{any}$\mid$\s{any} \s{elements} \\ -\s{vector} ::= [\s{elements}] -\end{tabbing} - -\item[function-pointer] \index{function-pointer} An implementation may have -functions which deal with specific data types other than those listed. -The use of these entities is to be avoided with the exception of a -restricted use of the function-pointer, an access method to compiled -EXPRs and FEXPRs. A particular function-pointer must remain valid -\index{EXPR} \index{FEXPR} -throughout execution. Systems which change the location of a function -must use either an indirect reference or change all occurrences of the -associated value. There are two classes of use of function-pointers, -those which are supported by Standard LISP but are not well defined, -and those which are well defined. - -\begin{description} -\item[Not well defined] Function pointers may be displayed by the print -functions or expanded by EXPLODE. \index{EXPLODE} The value appears in -the convention of the implementation site. The value is not defined in -Standard LISP. Function pointers may be created by COMPRESS -\index{COMPRESS} in the format used for printing but the value used is -not defined in Standard LISP. Function pointers may be created by -functions which deal with compiled function loading. Again, the values -created are not well defined in Standard LISP. - -\item[Well defined] The function pointer associated with an EXPR or -FEXPR may be retrieved by GETD \index{GETD} and is valid as long as -Standard LISP is in execution. Function pointers may be stored using -\index{PUTD} \index{PUT} \index{SETQ} PUTD, PUT, SETQ and the like or by -being bound to variables. Function pointers may be checked for -equivalence by EQ. \index{EQ ! of function-pointers} The value may be -checked for being a function pointer by the CODEP function. -\index{CODEP} -\end{description} -\end{description} - - -\subsection{Classes of Primitive Data Types} -\label{pclasses} -The classes of primitive types are a notational convenience for -describing the properties of functions. - - -\begin{description} -\item[boolean] \index{boolean} The set of global variables \{T,NIL\}, -or their respective values, \{T, NIL\}. \index{T (global)} \index{NIL -(global)} - -\item[extra-boolean] \index{extra-boolean} Any value in the system. -Anything that is not NIL \index{NIL (global)} has the boolean -interpretation T. \index{T (global)} - -\item[ftype] \index{ftype} The class of definable function types. The -set of ids \{EXPR, FEXPR, MACRO\}. \index{EXPR} \index{FEXPR} -\index{MACRO} - -\item[number] \index{number} The set of \{integer, floating\}. - -\item[constant] \index{constant} The set of \{integer, floating, -string, vector, function-pointer\}. Constants evaluate to themselves -(see the definition of EVAL in ``The Interpreter'', -section~\ref{interpreter} on page~\pageref{interpreter}). \index{EVAL -! of constants} - - -\item[any] \index{any} The set of \{integer, floating, string, id, -dotted-pair, vector, function-pointer\}. An S-expression is another -term for any. All Standard LISP entities have some value unless an -ERROR occurs during evaluation or the function causes transfer of -control (such as GO and RETURN). - - -\item[atom] \index{atom} The set \{any\}-\{dotted-pair\}. -\end{description} - -\subsection{Structures} -\index{data structures} \index{structures} -Structures are entities created out of the primitive types by the use -of dotted-pairs. Lists are structures very commonly required as actual -parameters to functions. Where a list of homogeneous entities is -required by a function this class will be denoted by -\s{{\bf xxx}-list} where {\bf \em xxx} is the name of a class of primitives -or structures. Thus a list of ids is an {\em id-list}, a list of -integers an {\em integer-list} and so on. \index{id-list} -\index{integer-list} -\index{-list} - -\begin{description} -\item[list] \index{list} A list is recursively defined as NIL or the -\index{list-notation} \index{NIL (global)} -dotted-pair (any~.~list). A special notation called {\em -list-notation} is used to represent lists. List-notation eliminates -extra parentheses and dots. The list (a . (b . (c . NIL))) in list -notation is (a b c). -\index{dot-notation} -List-notation and dot-notation may be mixed as in (a b . c) or (a (b . -c) d) which are (a . (b . c)) and (a . ((b . c) . (d . NIL))). In BNF -lists are recognized by the grammar: - -\begin{tabbing} -\s{left-part} ::= ( $\mid$ \s{left-part} \s{any} \\ -\s{list} ::= \s{left-part}) $\mid$ \s{left-part} . \s{any}) -\end{tabbing} - -Note: () is an alternate input representation of NIL. \index{()} - - -\item[alist] \index{alist} An association list; each element of the list -is a dotted-pair, the CAR part being a key associated with the value -in the CDR part. \index{association list} - - -\item[cond-form] \index{cond-form} A cond-form is a list of 2 element lists -of the form: - -(\p{ANTECEDENT}:{\em any} \p{CONSEQUENT}:{\em any}) - -The first element will henceforth be known as the antecedent and -\index{antecedent (cond-form)} \index{consequent (cond-form)} -the second as the consequent. The antecedent must have a value. The -consequent may have a value or an occurrence of GO or RETURN -\index{GO} \index{RETURN} -as described in the ``Program Feature Functions'', section~\ref{prog} -on page~\pageref{prog}. - - -\item[lambda] \index{LAMBDA} A LAMBDA expression which must have the form -(in list notation): (LAMBDA parameters body). ``parameters'' is a list -of formal parameters for ``body'' an S-expression to be evaluated. The -semantics of the evaluation are defined with the EVAL function (see -``The Interpreter'', section~\ref{interpreter} on \index{EVAL ! lambda -expressions} page~\pageref{interpreter}). \index{lambda expression} - -\item[function] \index{function} A LAMBDA expression or a function-pointer -to a function. A function is always evaluated as an EVAL, SPREAD form. -\index{EVAL ! function} -\end{description} - - -\subsection{Function Descriptions} - -Each function is provided with a prototypical header line. Each formal -parameter is given a name and suffixed with its allowed type. Lower -case, italic tokens are names of classes and upper case, bold face, -tokens are parameter names referred to in the definition. The type of -the value returned by the function (if any) is suffixed to the -parameter list. If it is not commonly used the parameter type may be -a specific set enclosed in brackets \{\ldots\}. \index{\{\ldots\} ! as -syntax} For example: - - -\vspace{.1in} -\noindent \f{PUTD}(\p{FNAME}:\ty{id}, \p{TYPE}:\ty{ftype}, -\p{BODY}:\{\ty{lambda, function-pointer}\}):\ty{id} -\vspace{.1in} - -PUTD is a function with three parameters. The parameter FNAME is an id -to be the name of the function being defined. TYPE is the type of the -function being defined and BODY is a lambda expression or a -function-pointer. PUTD returns the name of the function being defined. - - - -Functions which accept formal parameter lists of arbitrary length have -the type class and parameter enclosed in square brackets indicating -that zero or more occurrences of that argument are permitted. -\index{[\ldots] syntax} For example: - -\vspace{.1in} -\noindent \f{AND}([\p{U}:\ty{any}]):\ty{extra-boolean} -\vspace{.1in} - -AND is a function which accepts zero or more arguments which may be of -any type. - -\subsection{Function Types} - -EVAL type functions are those which are invoked with evaluated -\index{EVAL ! function type} -arguments. NOEVAL functions are invoked with unevaluated arguments. -\index{NOEVAL ! function type} -SPREAD type functions have their arguments passed in one-to-one -\index{SPREAD ! function type} -correspondence with their formal parameters. NOSPREAD functions -\index{NOSPREAD ! function type} -receive their arguments as a single list. EVAL, SPREAD functions are -\index{FEXPR} -associated with EXPRs and NO\-EVAL, NO\-SPREAD functions with FEXPRs. -EVAL, NO\-SPREAD and NOEVAL, SPREAD functions can be simulated using -NOEVAL, NO\-SPREAD functions or MACROs. \index{MACRO} - -EVAL, SPREAD type functions may have a maximum of 15 parameters. -\index{formal parameter limit} -There is no limit on the number of parameters a NOEVAL, NOSPREAD -function or MACRO may have. - -In the context of the description of an EVAL, SPREAD function, then we -speak of the formal parameters we mean their actual values. However, -in a NOEVAL, NOSPREAD function it is the unevaluated actual -parameters. - -A third function type, the MACRO, implements functions which -\index{MACRO} -create S-expressions based on actual parameters. When a macro -invocation is encountered, the body of the macro, a lambda expression, -is invoked as a NOEVAL, NOSPREAD function with the macro's invocation -bound as a list to the macros single formal parameter. When the macro -has been evaluated the resulting S-expression is reevaluated. The -description of the EVAL and EXPAND -\index{EVAL ! MACRO functions} -functions provide precise details. - - -\subsection{Error and Warning Messages} -\index{error messages} -Many functions detect errors. The description of such functions will -include these error conditions and suggested formats for display -\index{ERROR} -of the generated error messages. A call on the ERROR function is -implied but the error number is not specified by Standard LISP. In -some cases a warning message is sufficient. To distinguish between -\index{warning messages} \index{***** (error message)} -\index{*** (warning message)} -errors and warnings, errors are prefixed with five asterisks and -warnings with only three. - -Primitive functions check arguments that must be of a certain -primitive type for being of that type and display an error message if -the argument is not correct. The type mismatch error always takes the -form: -\index{error ! type mismatch error} - -\errormessage{***** PARAMETER not TYPE for FN} - -Here PARAMETER is the unacceptable actual parameter, TYPE is the type -that PARAMETER was supposed to be. FN is the name of the function that -detected the error. - -\subsection{Comments} - -\index{comments} \index{\%} -The character \% signals the start of a comment, text to be ignored -during parsing. A comment is terminated by the end of the line it -\index{READCH} \index{READ} -is on. The function READCH must be able to read a comment one -character at a time. Comments are transparent to the function READ. -\% may occur as a character in identifiers by preceding it with the -\index{escape character} -escape character !. - - -\section{Functions} -\label{slfns} - -\subsection{Elementary Predicates} -\label{elpreds} -\index{predicate !} -\index{T (global)} \index{NIL (global)} -Functions in this section return T when the condition defined is met -and NIL when it is not. Defined are type checking functions and -elementary comparisons. - - -\de{ATOM}{(\p{U}:\ty{any}):{\ty boolean}}{eval, spread} -{Returns T if U is not a pair. - -{\tt \begin{tabbing} EXPR PROCEDURE ATOM(U); \\ -\hspace*{1em} NULL PAIRP U; -\end{tabbing}}} - - -\de{CODEP}{(\p{U}:\f{any}):{\ty boolean}}{eval, spread} -{Returns T if U is a function-pointer.} - - -\de{CONSTANTP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a constant (a number, string, function-pointer, or -vector). - -{\tt \begin{tabbing} EXPR PROCEDURE CONSTANTP(U); \\ -\hspace*{1em} NULL OR(PAIRP U, IDP U); -\end{tabbing}} -} - - - -\de{EQ}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U points to the same object as V. EQ is \underline{not} -a reliable comparison between numeric arguments. } - - -\de{EQN}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U and V are EQ or if U and V are numbers and have the -same value and type. } - - -\de{EQUAL}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U and V are the same. Dotted-pairs are compared -recursively to the bottom levels of their trees. Vectors must have -identical dimensions and EQUAL values in all positions. Strings must -\index{EQ ! of function-pointers} \index{EQN} have identical characters. -Function pointers must have EQ values. Other atoms must be EQN equal. } - - -\de{FIXP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is an integer (a fixed number).} - - -\de{FLOATP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a floating point number. } - - -\de{IDP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is an id.} - - -\de{MINUSP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a number and less than 0. If U is not a number or -is a positive number, NIL is returned. - -{\tt \begin{tabbing} EXPR PROCEDURE MINUSP(U); \\ -\hspace*{1em} IF NUMBERP U THEN LESSP(U, 0) ELSE NIL; -\end{tabbing}}} - - -\de{NULL}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is NIL. - -{\tt \begin{tabbing} EXPR PROCEDURE NULL(U); \\ -\hspace*{1em} U EQ NIL; -\end{tabbing}}} - - -\de{NUMBERP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a number (integer or floating). - -{\tt \begin{tabbing} EXPR PROCEDURE NUMBERP(U); \\ -\hspace*{1em} IF OR(FIXP U, FLOATP U) THEN T ELSE NIL; -\end{tabbing}}} - - -\de{ONEP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread.} -{Returns T if U is a number and has the value 1 or 1.0. Returns NIL -otherwise. \footnote{The definition in the published report is -incorrect as it does not return T for \p{U} of 1.0.} - -{\tt \begin{tabbing} EXPR PROCEDURE ONEP(U); \\ -\hspace*{1em} OR(EQN(U, 1), EQN(U, 1.0)); -\end{tabbing}}} - - -\de{PAIRP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a dotted-pair. } - - -\de{STRINGP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a string. } - - -\de{VECTORP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a vector. } - - -\de{ZEROP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread.} -{Returns T if U is a number and has the value 0 or 0.0. Returns NIL -otherwise.\footnote{The definition in the published report is -incorrect as it does not return T for \p{U} of 0.0.} - -{\tt \begin{tabbing} EXPR PROCEDURE ZEROP(U); \\ -\hspace*{1em} OR(EQN(U, 0), EQN(U, 0.0)); -\end{tabbing}}} - - -\subsection{Functions on Dotted-Pairs} - -\index{dotted-pair} -The following are elementary functions on dotted-pairs. All functions -in this section which require dotted-pairs as parameters detect a type -mismatch error if the actual parameter is not a dotted-pair. - - - -\de{CAR}{(\p{U}:\ty{dotted-pair}):\ty{any}}{eval, spread} -{CAR(CONS(a, b)) $\rightarrow$ a. The left part of U is returned. The -type -\index{CONS} -mismatch error occurs if U is not a dotted-pair.} - - -\de{CDR}{(\p{U}:\ty{dotted-pair}):\ty{any}}{eval, spread} -{CDR(CONS(a, b)) $\rightarrow$ b. The right part of U is returned. The -type -\index{CONS} -mismatch error occurs if U is not a dotted-pair.} - - -The composites of CAR and CDR are supported up to 4 levels, namely: -\index{CAR ! composite forms} \index{CDR ! composite forms} - -\hspace*{1in}\begin{tabular}{l l l} -CAAAAR & CAAAR & CAAR \\ CAAADR & CAADR & CADR \\ CAADAR & CADAR & -CDAR \\ CAADDR & CADDR & CDDR \\ CADAAR & CDAAR & \\ CADADR & CDADR & -\\ CADDAR & CDDAR & \\ CADDDR & CDDDR & \\ CDAAAR & & \\ CDAADR & & \\ -CDADAR & & \\ CDADDR & & \\ CDDAAR & & \\ CDDADR & & \\ CDDDAR & & \\ -CDDDDR & & -\end{tabular} - -\de{CONS}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{dotted-pair}}{eval, spread} -{Returns a dotted-pair which is not EQ to anything and has U as its -\index{EQ ! of dotted-pairs} \index{dotted-pair} -CAR part and V as its CDR part.} - - -\de{LIST}{([\p{U}:\ty{any}]):\ty{list}}{noeval, nospread, or macro} -{A list of the evaluation of each element of U is returned. The order -of evaluation need not be first to last as the following definition -implies.\footnote{The published report's definition implies a specific -ordering.} - -{\tt \begin{tabbing} FEXPR PROCEDURE LIST(U); \\ -\hspace*{1em} EVLIS U; -\end{tabbing}}} - - -\de{RPLACA}{(\p{U}:\ty{dotted-pair}, -\p{V}:\ty{any}):\ty{dotted-pair}}{eval, spread} -{The CAR portion of the dotted-pair U is replaced by V. If dotted-pair -U is (a . b) then (V . b) is returned. The type mismatch error occurs -if U is not a dotted-pair. } - - -\de{RPLACD}{(\p{U}:\ty{dotted-pair}, -\p{V}:\ty{any}):\ty{dotted-pair}}{eval, spread} -{The CDR portion of the dotted-pair U is replaced by V. If dotted-pair -U is (a . b) then (a . V) is returned. The type mismatch error occurs -if U is not a dotted-pair.} - - -\subsection{Identifiers} -\label{identifiers} -The following functions deal with identifiers and the OBLIST, -\index{OBLIST} -the structure of which is not defined. The function of the OBLIST is -to provide a symbol table for identifiers created during input. -Identifiers created by READ which have the same characters will -\index{READ} \index{EQ ! of identifiers} -therefore refer to the same object (see the EQ function in -``Elementary Predicates'', section~\ref{elpreds} on -page~\pageref{elpreds}). - - - -\de{COMPRESS}{(\p{U}:\ty{id-list}):\{\ty{atom}-\ty{vector}\}}{eval, spread} -{U is a list of single character identifiers which is built into a -Standard LISP entity and returned. Recognized are numbers, strings, -and identifiers with the escape character prefixing special -characters. The formats of these items appear in ``Primitive Data -Types'' section~\ref{pdat} on page~\pageref{pdat}. Identifiers are not -interned on the OBLIST. Function pointers may be compressed but this -is an undefined use. If an entity cannot be parsed out of U or -characters are left over after parsing an error occurs: - -\errormessage{***** Poorly formed atom in COMPRESS} -} - - -\de{EXPLODE}{(\p{U}:\{\ty{atom}\}-\{\ty{vector}\}):\ty{id-list}}{eval, spread} -{Returned is a list of interned characters representing the characters -to print of the value of U. The primitive data types have these -formats: - -\begin{description} -\item[integer] \index{integer ! output} Leading zeroes are suppressed and -a minus sign prefixes the digits if the integer is negative. - -\item[floating] \index{floating ! output} The value appears in the format -[-]0.nn...nnE[-]mm if the magnitude of the number is too large or -small to display in [-]nnnn.nnnn format. The crossover point is -determined by the implementation. - -\item[id] \index{id ! output} The characters of the print name of the -identifier are produced with special characters prefixed with the -escape character. - -\item[string] \index{string ! output} The characters of the string are -produced surrounded by double quotes "\ldots". - -\item[function-pointer] \index{function-pointer ! output} The value of the -function-pointer is created as a list of characters conforming to the -conventions of the system site. -\end{description} - -The type mismatch error occurs if U is not a number, identifier, -string, or function-pointer. } - - -\de{GENSYM}{():\ty{identifier}}{eval, spread} -{Creates an identifier which is not interned on the OBLIST and -consequently not EQ to anything else. \index{OBLIST entry} \index{EQ ! -of GENSYMs}} - - -\de{INTERN}{(\p{U}:\{\ty{id,string}\}):\ty{id}}{eval, spread} -{INTERN searches the OBLIST for an identifier with the same print name -\index{OBLIST entry} -as U and returns the identifier on the OBLIST if a match is found. -Any properties and global values associated with U may be lost. If U -does not match any entry, a new one is created and returned. If U has -more than the maximum number of characters permitted by the -implementation (the minimum number is 24) an error occurs: -\index{id ! minimum size} - -\errormessage{***** Too many characters to INTERN} -} - - -\de{REMOB}{(\p{U}:\ty{id}):\ty{id}}{eval, spread} -{If U is present on the OBLIST it is removed. This does not affect U -\index{OBLIST entry} -having properties, flags, functions and the like. U is returned.} - - -\subsection{Property List Functions} -\label{plist} -\index{property list} -With each id in the system is a ``property list'', a set of entities -which are associated with the id for fast access. These entities are -called ``flags'' if their use gives the id a single valued -\index{flags} -property, and ``properties'' if the id is to have a multivalued -\index{properties} -attribute: an indicator with a property. - -Flags and indicators may clash, consequently care should be taken to -avoid this occurrence. Flagging X with an id which already is an -indicator for X may result in that indicator and associated property -being lost. Likewise, adding an indicator which is the same id as a -flag may result in the flag being destroyed. - - - -\de{FLAG}{(\p{U}:\ty{id-list}, \p{V}:\ty{id}):\ty{NIL}}{eval, spread} -{U is a list of ids which are flagged with V. The effect of FLAG is -that FLAGP will have the value T for those ids of U which were -flagged. Both V and all the elements of U must be identifiers or the -type mismatch error occurs.} - - -\de{FLAGP}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U has been previously flagged with V, else NIL. Returns -NIL if either U or V is not an id.} - - -\de{GET}{(\p{U}:\ty{any}, \p{IND}:\ty{any}):\ty{any}}{eval, spread} -{Returns the property associated with indicator IND from the property -list of U. If U does not have indicator IND, NIL is returned. GET -cannot be used to access functions (use GETD instead). -\index{GET ! not for functions}} - - -\de{PUT}{(\p{U}:\ty{id}, \p{IND}:\ty{id}, -\p{PROP}:\ty{any}):\ty{any}}{eval, spread} -{The indicator IND with the property PROP is placed on the property -list of the id U. If the action of PUT occurs, the value of PROP is -returned. If either of U and IND are not ids the type mismatch error -will occur and no property will be placed. PUT cannot be used to -define functions (use PUTD instead). -\index{PUT ! not for functions}} - - -\de{REMFLAG}{(\p{U}:\ty{any-list}, \p{V}:\ty{id}):\ty{NIL}}{eval, spread} -{Removes the flag V from the property list of each member of the list -U. Both V and all the elements of U must be ids or the type mismatch -error will occur.} - - -\de{REMPROP}{(\p{U}:\ty{any}, \p{IND}:\ty{any}):\ty{any}}{eval, spread} -{Removes the property with indicator IND from the property list of U. -Returns the removed property or NIL if there was no such indicator.} - - - -\subsection{Function Definition} -\label{fdef} -Functions in Standard LISP are global entities. To avoid -function-variable naming clashes no variable may have the same name as -a function. \index{function ! as GLOBAL} - - -\de{DE}{(\p{FNAME}:\ty{id}, \p{PARAMS}:\ty{id-list}, -\p{FN}:\ty{any}):\ty{id}}{noeval, nospread} -{The function FN with the formal parameter list PARAMS is added to the -set of defined functions with the name FNAME. Any previous definitions -of the function are lost. The function created is of type -\index{*COMP (fluid)} -EXPR. If the !*COMP variable is non-NIL, the EXPR is first -\index{EXPR} -compiled. The name of the defined function is returned. - -{\tt \begin{tabbing} FEXPR PROCEDURE DE(U); \\ -\hspace*{1em} PUTD(CAR U, 'EXPR, LIST('LAMBDA, CADR U, CADDR U)); -\end{tabbing}}} - - -\de{DF}{(\p{FNAME}:\ty{id}, \p{PARAM}:\ty{id-list}, -\p{FN}:\ty{any}):\ty{id}}{noeval, nospread} -{The function FN with formal parameter PARAM is added to the set of -defined functions with the name FNAME. Any previous definitions of the -function are lost. The function created is of type FEXPR. -\index{*COMP variable} \index{FEXPR} -If the !*COMP variable is T the FEXPR is first compiled. The name of -the defined function is returned. - -{\tt \begin{tabbing} FEXPR PROCEDURE DF(U); \\ -\hspace*{1em} PUTD(CAR U, 'FEXPR, LIST('LAMBDA, CADR U, CADDR U)); \\ -\end{tabbing} }} - - -\de{DM}{(\p{MNAME}:\ty{id}, \p{PARAM}:\ty{id-list}, -\p{FN}:\ty{any}):\ty{id}}{noeval, nospread} -{The macro FN with the formal parameter PARAM is added to the set of -defined functions with the name MNAME. Any previous definitions of the -function are overwritten. The function created is of type MACRO. -\index{MACRO} -The name of the macro is returned. - -{\tt \begin{tabbing} FEXPR PROCEDURE DM(U); \\ -\hspace*{1em} PUTD(CAR U, 'MACRO, LIST('LAMBDA, CADR U, CADDR U)); -\end{tabbing} } -} - - -\de{GETD}{(\p{FNAME}:\ty{any}):\{NIL, \ty{dotted-pair}\}}{eval, spread} -{If FNAME is not the name of a defined function, NIL is returned. If -FNAME is a defined function then the dotted-pair - -\vspace{.15in} -(\p{TYPE}:\ty{ftype} . \p{DEF}:\{\ty{function-pointer, lambda}\}) -\vspace{.15in} - -is returned.} - - -\de{PUTD}{(\p{FNAME}:\ty{id}, \p{TYPE}:\ty{ftype}, -\p{BODY}:\ty{function}):\ty{id}}{eval, spread} -{Creates a function with name FNAME and definition BODY of type TYPE. -If PUTD succeeds the name of the defined function is returned. The -effect of PUTD is that GETD will return a dotted-pair with the -functions type and definition. Likewise the GLOBALP predicate will -\index{GLOBALP} \index{function ! as global} -return T when queried with the function name. - -If the function FNAME has already been declared as a GLOBAL or FLUID -variable the error: - -\errormessage{***** FNAME is a non-local variable} - -occurs and the function will not be defined. If function FNAME already -exists a warning message will appear: - -\errormessage{*** FNAME redefined} - -The function defined by PUTD will be compiled before definition -\index{*COMP (fluid)} if the !*COMP global variable is non-NIL.} - - -\de{REMD}{(\p{FNAME}:\ty{id}):\{NIL, \ty{dotted-pair}\}}{eval, spread} -{Removes the function named FNAME from the set of defined functions. -Returns the (ftype . function) dotted-pair or NIL as does GETD. The -global/function attribute of FNAME is removed and the name may be used -subsequently as a variable.} - - - -\subsection{Variables and Bindings} -\label{varsandbinds} -\index{variable scope} \index{scope} -A variable is a place holder for a Standard LISP entity which is said -to be bound to the variable. The scope of a variable is the range over -which the variable has a defined value. There are three different -binding mechanisms in Standard LISP. - -\begin{description} -\item[Local Binding] \index{local binding} This type of binding occurs -\index{scope ! local} -only in compiled functions. Local variables occur as formal parameters -in lambda expressions and as PROG form variables. The binding occurs -when a lambda expression is evaluated or when a PROG form is executed. -The scope of a local variable is the body of the function in which it -is defined. - -\item[Global Binding] \index{global binding} Only one binding of a -\index{scope ! global} -global variable exists at any time allowing direct access to the value -bound to the variable. The scope of a global variable is universal. -Variables declared GLOBAL may not appear as parameters in lambda -expressions or as PROG form variables. A variable must be declared -GLOBAL prior to its use as a global variable since the default type -for undeclared variables is FLUID. - - -\item[Fluid Binding] \index{fluid binding} -\index{fluid binding ! as default} Fluid variables are global -in scope but may occur as \index{scope ! fluid} formal parameters or -PROG form variables. In interpreted functions all formal parameters -and PROG form variables are considered to have fluid binding until -changed to local binding by compilation. When fluid variables are -used as parameters they are rebound in such a way that the previous -binding may be restored. All references to fluid variables are to the -currently active binding. -\end{description} - - -\de{FLUID}{(\p{IDLIST}:\ty{id-list}):\p{NIL}}{eval, spread} -{The ids in IDLIST are declared as FLUID type variables (ids not -previously declared are initialized to NIL). Variables in IDLIST -already declared FLUID are ignored. Changing a variable's type from -GLOBAL to FLUID is not permissible and results in the error: - -\errormessage{***** ID cannot be changed to FLUID} -} - -\de{FLUIDP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{If U has been declared FLUID (by declaration only) T is returned, -otherwise NIL is returned.} - - -\de{GLOBAL}{(\p{IDLIST}:\ty{id-list}):\p{NIL}}{eval, spread} -{The ids of IDLIST are declared global type variables. If an id has -not been declared previously it is initialized to NIL. Variables -already declared GLOBAL are ignored. Changing a variables type from -FLUID to GLOBAL is not permissible and results in the error: - -\errormessage{***** ID cannot be changed to GLOBAL} -} - - -\de{GLOBALP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{If U has been declared GLOBAL or is the name of a defined function, T -is returned, else NIL is returned.} - - -\de{SET}{(\p{EXP}:\ty{id}, \p{VALUE}:\ty{any}):\ty{any}}{eval, spread} -{EXP must be an identifier or a type mismatch error occurs. The effect -of SET is replacement of the item bound to the identifier by VALUE. -If the identifier is not a local variable or has not been declared -GLOBAL it is automatically declared FLUID with the resulting warning -message: - -\errormessage{*** EXP declared FLUID} - -EXP must not evaluate to T or NIL or an error occurs: -\index{T ! cannot be changed} \index{NIL ! cannot be changed} - -\errormessage{***** Cannot change T or NIL} -} - -\de{SETQ}{(\p{VARIABLE}:\ty{id}, \p{VALUE}:\ty{any}):\ty{any}}{noeval, -nospread} -{If VARIABLE is not local or GLOBAL it is by default declared FLUID -and the warning message: - -\errormessage{*** VARIABLE declared FLUID} - -appears. The value of the current binding of VARIABLE is replaced by -the value of VALUE. VARIABLE must not be T or NIL or an error occurs: -\index{T ! cannot be changed} \index{NIL ! cannot be changed} - -\errormessage{***** Cannot change T or NIL} - -{\tt \begin{tabbing} MACRO PROCEDURE SETQ(X); \\ -\hspace*{1em} LIST('SET, LIST('QUOTE, CADR X), CADDR X); -\end{tabbing}} -} - -\de{UNFLUID}{(\p{IDLIST}:\ty{id-list}):\ty{NIL}}{eval, spread} -{The variables in IDLIST that have been declared as FLUID variables -are no longer considered as fluid variables. Others are ignored. This -affects only compiled functions as free variables in interpreted -functions are automatically considered fluid~\cite{PLC}. -\index{scope ! fluid and compiled}} - - -\subsection{Program Feature Functions} -\label{prog} -These functions provide for explicit control sequencing, and the -definition of blocks altering the scope of local variables. - - -\de{GO}{(\p{LABEL}:\ty{id})}{noeval, nospread} -{GO alters the normal flow of control within a PROG function. The next -statement of a PROG function to be evaluated is immediately preceded -by LABEL. A GO may only appear in the following situations: - - -\begin{enumerate} -\item At the top level of a PROG referencing a label which also -appears at the top level of the same PROG. - -\item As the consequent of a COND item of a COND appearing on the top -level of a PROG. -\index{GO ! in COND} -\index{RETURN ! in COND} -\item As the consequent of a COND item which appears as the -consequent of a COND item to any level. - -\item As the last statement of a PROGN which appears at the top level -of a PROG or in a PROGN appearing in the consequent of a COND to any -level subject to the restrictions of 2 and 3. - -\item As the last statement of a PROGN within a PROGN or as the -consequent of a COND in a PROGN to any level subject to the -restrictions of 2, 3 and 4. -\end{enumerate} - -If LABEL does not appear at the top level of the PROG in which the GO -appears, an error occurs: - -\errormessage{***** LABEL is not a known label} - -If the GO has been placed in a position not defined by rules 1-5, -another error is detected: - -\errormessage{***** Illegal use of GO to LABEL} -} - -\de{PROG}{(\p{VARS}:\ty{id-list}, -[\p{PROGRAM}:\{\ty{id, any}\}]):\ty{any}}{noeval, nospread} -{VARS is a list of ids which are considered fluid when the PROG is -interpreted and local when compiled (see ``Variables and Bindings'', -section~\ref{varsandbinds} on page~\pageref{varsandbinds}). The PROGs -variables are allocated space when the PROG form is invoked and are -deallocated when the PROG is exited. PROG variables are initialized to -\index{PROG ! variables} -NIL. The PROGRAM is a set of expressions to be evaluated in order of -their appearance in the PROG function. Identifiers appearing in the -top level of the PROGRAM are labels which can be referenced by GO. The -value returned by the PROG function is determined by a RETURN function -\index{PROG ! default value} -or NIL if the PROG ``falls through''.} - - -\de{PROGN}{([\p{U}:\ty{any}]):\ty{any}}{noeval, nospread} -{U is a set of expressions which are executed sequentially. The value -returned is the value of the last expression.} - - -\de{PROG2}{(A:any, B:any)\ty{any}}{eval, spread} -{Returns the value of B. - -{\tt \begin{tabbing} EXPR PROCEDURE PROG2(A, B);\\ -\hspace*{1em} B; -\end{tabbing}}} - - -\de{RETURN}{(\p{U}:\ty{any})}{eval, spread} -{Within a PROG, RETURN terminates the evaluation of a PROG and returns -U as the value of the PROG. The restrictions on the placement of -RETURN are exactly those of GO. Improper placement of RETURN results -in the error: - -\errormessage{***** Illegal use of RETURN} -} - - -\subsection{Error Handling} -\label{errors} - -\de{ERROR}{(\p{NUMBER}:\ty{integer}, \p{MESSAGE}:\ty{any})}{eval, spread} -{NUMBER and MESSAGE are passed back to a surrounding ERRORSET (the -Standard LISP reader has an ERRORSET). MESSAGE is placed in the -\index{EMSG* (global)} -global variable EMSG!* and the error number becomes the value of the -surrounding ERRORSET. FLUID variables and local bindings are unbound -\index{fluid ! unbinding by ERROR} -to return to the environment of the ERRORSET. Global variables are not -affected by the process.} - - -\de{ERRORSET}{(\p{U}:\ty{any}, \p{MSGP}:\ty{boolean}, -\p{TR}:\ty{boolean}):\ty{any}}{eval, spread} -{If an error occurs during the evaluation of U, the value of NUMBER -from the ERROR call is returned as the value of ERRORSET. In addition, -if the value of MSGP is non-NIL, the MESSAGE from the ERROR call is -displayed upon both the standard output device and the currently -selected output device unless the standard output device is not open. -The message appears prefixed with 5 asterisks. The MESSAGE -\index{***** (error message)} -list is displayed without top level parentheses. The MESSAGE from the -\index{EMSG* (global)} -ERROR call will be available in the global variable EMSG!*. The exact -format of error messages generated by Standard LISP functions -described in this document are not fixed and should not be relied upon -to be in any particular form. Likewise, error numbers generated by -Standard LISP functions are implementation dependent. - -If no error occurs during the evaluation of U, the value of (LIST -(EVAL U)) is returned. - -If an error has been signaled and the value of TR is non-NIL a -traceback sequence will be initiated on the selected output device. -The traceback will display information such as unbindings of FLUID -\index{fluid ! in traceback} -variables, argument lists and so on in an implementation dependent -format.} - - -\subsection{Vectors} -\label{vectors} -\index{vector} -Vectors are structured entities in which random elements may be -accessed with an integer index. A vector has a single dimension. Its -maximum size is determined by the implementation and available space. -A suggested input ``vector notation'' is defined in ``Classes of -Primitive Data Types'', section~\ref{pclasses} on -page~\pageref{pclasses} and output with EXPLODE, ``Identifiers'' -section~\ref{identifiers} on page~\pageref{identifiers}. -\index{EXPLODE} - - -\de{GETV}{(\p{V}:\ty{vector}, \p{INDEX}:\ty{integer}):\ty{any}}{eval, spread} -{Returns the value stored at position INDEX of the vector V. The type -mismatch error may occur. An error occurs if the INDEX does not lie -within 0\ldots UPBV(V) inclusive: - -\errormessage{***** INDEX subscript is out of range} -} - - -\de{MKVECT}{(\p{UPLIM}:\ty{integer}):\ty{vector}}{eval, spread} -{Defines and allocates space for a vector with UPLIM+1 elements -accessed as 0\ldots UPLIM. Each element is initialized to NIL. An -error will occur if UPLIM is $<$ 0 or there is not enough space for a -vector of this size: - -\errormessage{***** A vector of size UPLIM cannot be allocated} -} - - -\de{PUTV}{(\p{V}:\ty{vector}, \p{INDEX}:\ty{integer}, -\p{VALUE}:\ty{any}):\ty{any}}{eval, spread} -{Stores VALUE into the vector V at position INDEX. VALUE is returned. -The type mismatch error may occur. If INDEX does not lie in 0\ldots -UPBV(V) an error occurs: - -\errormessage{***** INDEX subscript is out of range} -} - - -\de{UPBV}{(\p{U}:\ty{any}):{NIL,\ty{integer}}}{eval, spread} -{Returns the upper limit of U if U is a vector, or NIL if it is not.} - - -\subsection{Boolean Functions and Conditionals} - - -\de{AND}{([\p{U}:\ty{any}]):\ty{extra-boolean}}{noeval, nospread} -{AND evaluates each U until a value of NIL is found or the end of the -list is encountered. If a non-NIL value is the last value it is -returned, or NIL is returned. - -{\tt \begin{tabbing} FEXPR PROCEDURE AND(U); \\ BEGIN \\ -\hspace*{1em} IF NULL U THEN RETURN NIL; \\ -LOOP: IF \= NULL CDR U THEN RETURN EVAL CAR U \\ -\> ELSE IF NULL EVAL CAR U THEN RETURN NIL; \\ -\hspace*{2em} \= U := CDR U; \\ -\> GO LOOP \\ -END; -\end{tabbing} }} - - -\de{COND}{([\p{U}:\ty{cond-form}]):\ty{any}}{noeval, nospread} -{The antecedents of all U's are evaluated in order of their appearance -until a non-NIL value is encountered. The consequent of the selected U -is evaluated and becomes the value of the COND. The consequent may -also contain the special functions GO and RETURN subject to the -restraints given for these functions in ``Program Feature Functions'', -section~\ref{prog} on page~\pageref{prog}. -\index{GO ! in COND} \index{RETUNR ! in CODE} In these cases COND does -not have a defined value, but rather an effect. If no antecedent is -non-NIL the value of COND is NIL. An error is detected if a U is -improperly formed: - -\errormessage{***** Improper cond-form as argument of COND} -} - - -\de{NOT}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{If U is NIL, return T else return NIL (same as function NULL). - -{\tt \begin{tabbing} EXPR PROCEDURE NOT(U); \\ -\hspace*{1em} U EQ NIL; -\end{tabbing}} -} - - -\de{OR}{([\p{U}:\ty{any}]):\ty{extra-boolean}}{noeval, nospread} -{U is any number of expressions which are evaluated in order of their -appearance. When one is found to be non-NIL it is returned as the -value of OR. If all are NIL, NIL is returned. - -{\tt \begin{tabbing} FEXPR PROCEDURE OR(U); \\ BEGIN SCALAR X; \\ -LOOP: IF \= NULL U THEN RETURN NIL \\ -\> ELSE IF (X := EVAL CAR U) THEN RETURN X; \\ -\hspace*{2em} \= U := CDR U; \\ -\> GO LOOP \\ -END; -\end{tabbing} }} - - -\subsection{Arithmetic Functions} - -Conversions between numeric types are provided explicitly by the -\index{FIX} \index{FLOAT} -FIX and FLOAT functions and implicitly by any multi-parameter -\index{mixed-mode arithmetic} -arithmetic function which receives mixed types of arguments. A -conversion from fixed to floating point numbers may result in a loss -of precision without a warning message being generated. Since -\index{integer ! magnitude} -integers may have a greater magnitude that that permitted for floating -numbers, an error may be signaled when the attempted conversion cannot -be done. Because the magnitude of integers is unlimited the conversion -of a floating point number to a fixed number is always possible, the -only loss of precision being the digits to the right of the decimal -point which are truncated. If a function receives mixed types of -arguments the general rule will have the fixed numbers converted to -floating before arithmetic operations are performed. In all cases an -error occurs if the parameter to an arithmetic function is not a -number: - -\errormessage{***** XXX parameter to FUNCTION is not a number} - -XXX is the value of the parameter at fault and FUNCTION is the name of -the function that detected the error. Exceptions to the rule are noted -where they occur. - - - - -\de{ABS}{(\p{U}:\ty{number}):\ty{number}}{eval, spread} -{Returns the absolute value of its argument. - -{\tt \begin{tabbing} EXPR PROCEDURE ABS(U); \\ -\hspace*{1em} IF LESSP(U, 0) THEN MINUS(U) ELSE U; -\end{tabbing}}} - -\de{ADD1}{(\p{U}:\ty{number}):\ty{number}}{eval, spread} -{Returns the value of U plus 1 of the same type as U (fixed or -floating). - -{\tt \begin{tabbing} EXPR PROCEDURE ADD1(U); \\ -% God knows why, but hspace* isn't accepted here. -\hspace{1em} PLUS2(U, 1); -\end{tabbing}} -} - -\de{DIFFERENCE}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, -spread} -{The value U - V is returned.} - - -\de{DIVIDE}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{dotted-pair}}{eval, -spread} -{The dotted-pair (quotient . remainder) is returned. The quotient part -is computed the same as by QUOTIENT and the remainder the same as by -REMAINDER. An error occurs if division by zero is attempted: -\index{division by zero} - -\errormessage{***** Attempt to divide by 0 in DIVIDE} - -{\tt \begin{tabbing} EXPR PROCEDURE DIVIDE(U, V); \\ -\hspace*{1em} (QUOTIENT(U, V) . REMAINDER(U, V)); -\end{tabbing}}} - - -\de{EXPT}{(\p{U}:\ty{number}, \p{V}:\ty{integer}):\ty{number}}{eval, spread} -{Returns U raised to the V power. A floating point U to an integer -power V does \underline{not} have V changed to a floating number -before exponentiation.} - - -\de{FIX}{(\p{U}:\ty{number}):\ty{integer}}{eval, spread} -{Returns an integer which corresponds to the truncated value of U. The -result of conversion must retain all significant portions of U. If U -is an integer it is returned unchanged. } - - -\de{FLOAT}{(\p{U}:\ty{number}):\ty{floating}}{eval, spread} -{The floating point number corresponding to the value of the argument -U is returned. Some of the least significant digits of an integer may -be lost do to the implementation of floating point numbers. FLOAT of a -floating point number returns the number unchanged. If U is too large -to represent in floating point an error occurs: - -\errormessage{***** Argument to FLOAT is too large} -} - -\de{GREATERP}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{boolean}}{eval, -spread} -{Returns T if U is strictly greater than V, otherwise returns NIL.} - - -\de{LESSP}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{boolean}}{eval, spread} -{Returns T if U is strictly less than V, otherwise returns NIL. } - - -\de{MAX}{([\p{U}:\ty{number}]):\ty{number}}{noeval, nospread, or macro} -{Returns the largest of the values in U. If two or more values are the -same the first is returned. - -{\tt \begin{tabbing} MACRO PROCEDURE MAX(U); \\ -\hspace*{1em} EXPAND(CDR U, 'MAX2); -\end{tabbing}}} - - -\de{MAX2}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} -{Returns the larger of U and V. If U and V are the same value U is -returned (U and V might be of different types). - -{\tt \begin{tabbing} EXPR PROCEDURE MAX2(U, V); \\ -\hspace*{1em} IF LESSP(U, V) THEN V ELSE U; -\end{tabbing}}} - - -\de{MIN}{([\p{U}:\ty{number}]):\ty{number}}{noeval, nospread, or macro} -{Returns the smallest of the values in U. If two or more values are -the same the first of these is returned. - -{\tt \begin{tabbing} MACRO PROCEDURE MIN(U); \\ -\hspace*{1em} EXPAND(CDR U, 'MIN2); -\end{tabbing}}} - - -\de{MIN2}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} -{Returns the smaller of its arguments. If U and V are the same value, -U is returned (U and V might be of different types). - -{\tt \begin{tabbing} EXPR PROCEDURE MIN2(U, V); \\ -\hspace*{1em} IF GREATERP(U, V) THEN V ELSE U; -\end{tabbing}}} - - -\de{MINUS}{(\p{U}:\ty{number}):\ty{number}}{eval, spread} -{Returns -U. - -{\tt \begin{tabbing} EXPR PROCEDURE MINUS(U); \\ -\hspace*{1em} DIFFERENCE(0, U); -\end{tabbing}}} - - -\de{PLUS}{([\p{U}:\ty{number}]):\ty{number}}{noeval, nospread, or macro} -{Forms the sum of all its arguments. - -{\tt \begin{tabbing} MACRO PROCEDURE PLUS(U); \\ -\hspace*{1em} EXPAND(CDR U, 'PLUS2); -\end{tabbing}}} - -\de{PLUS2}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} -{Returns the sum of U and V.} - - -\de{QUOTIENT}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} -{The quotient of U divided by V is returned. Division of two positive -or two negative integers is conventional. When both U and V are -integers and exactly one of them is negative the value returned is the -negative truncation of the absolute value of U divided by the absolute -value of V. An error occurs if division by zero is attempted: -\index{division by zero} - -\errormessage{***** Attempt to divide by 0 in QUOTIENT} -} - -\de{REMAINDER}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, -spread} -{If both U and V are integers the result is the integer remainder of U -divided by V. If either parameter is floating point, the result is the -difference between U and V*(U/V) all in floating point. If either -number is negative the remainder is negative. If both are positive or -both are negative the remainder is positive. An error occurs if V is -zero: \index{division by zero} - -\errormessage{***** Attempt to divide by 0 in REMAINDER} - -{\tt \begin{tabbing} EXPR PROCEDURE REMAINDER(U, V); \\ -\hspace*{1em} DIFFERENCE(U, TIMES2(QUOTIENT(U, V), V)); -\end{tabbing}}} - - -\de{SUB1}{(\p{U}:\ty{number}):\ty{number}}{eval, spread} -{Returns the value of U less 1. If U is a FLOAT type number, the -value returned is U less 1.0. - -{\tt \begin{tabbing} EXPR PROCEDURE SUB1(U); \\ -\hspace*{1em} DIFFERENCE(U, 1); -\end{tabbing}}} - - -\de{TIMES}{([\p{U}:\ty{number}]):\ty{number}}{noeval, nospread, or macro} -{Returns the product of all its arguments. - -{\tt \begin{tabbing} MACRO PROCEDURE TIMES(U); \\ -\hspace*{1em} EXPAND(CDR U, 'TIMES2); -\end{tabbing}}} - - -\de{TIMES2}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} -{Returns the product of U and V.} - - -\subsection{MAP Composite Functions} - - -\de{MAP}{(\p{X}:\ty{list}, F\p{N}:\ty{function}):\ty{any}}{eval, spread} -{Applies FN to successive CDR segments of X. NIL is returned. - -{\tt \begin{tabbing} EXPR PROCEDURE MAP(X, FN); \\ -\hspace*{1em} WHILE X DO $<<$ FN X; X := CDR X $>>$; -\end{tabbing}}} - - -\de{MAPC}{(X:list, FN:function):\ty{any}}{eval, spread} -{FN is applied to successive CAR segments of list X. NIL is returned. - -{\tt \begin{tabbing} EXPR PROCEDURE MAPC(X, FN); \\ -\hspace*{1em} WHILE X DO $<<$ FN CAR X; X := CDR X $>>$; -\end{tabbing}}} - - -\de{MAPCAN}{(X:list, FN:function):\ty{any}}{eval, spread} -{A concatenated list of FN applied to successive CAR elements of X is -returned. - -{\tt \begin{tabbing} EXPR PROCEDURE MAPCAN(X, FN); \\ -\hspace*{1em} IF\= NULL X THEN NIL \\ -\> ELSE NCONC(FN CAR X, MAPCAN(CDR X, FN)); -\end{tabbing}}} - - -\de{MAPCAR}{(X:list, FN:function):\ty{any}}{eval, spread} -{Returned is a constructed list of FN applied to each CAR of list X. - -{\tt \begin{tabbing} EXPR PROCEDURE MAPCAR(X, FN); \\ -\hspace*{1em} IF\= NULL X THEN NIL \\ -\> ELSE FN CAR X . MAPCAR(CDR X, FN); -\end{tabbing}}} - - -\de{MAPCON}{(X:list, FN:function):\ty{any}}{eval, spread} -{Returned is a concatenated list of FN applied to successive CDR -segments of X. - -{\tt \begin{tabbing} EXPR PROCEDURE MAPCON(X, FN); \\ -\hspace*{1em} IF\= NULL X THEN NIL \\ -\> ELSE NCONC(FN X, MAPCON(CDR X, FN)); -\end{tabbing}}} - - -\de{MAPLIST}{(X:list, FN:function):\ty{any}}{eval, spread} -{Returns a constructed list of FN applied to successive CDR segments -of X. - -{\tt \begin{tabbing} EXPR PROCEDURE MAPLIST(X, FN); \\ -\hspace*{1em} IF\= NULL X THEN NIL \\ -\> ELSE FN X . MAPLIST(CDR X, FN); -\end{tabbing}}} - - -\subsection{Composite Functions} - -\de{APPEND}{(\p{U}:\ty{list}, \p{V}:\ty{list}):\ty{list}}{eval, spread} -{Returns a constructed list in which the last element of U is followed -by the first element of V. The list U is copied, V is not. - -{\tt \begin{tabbing} EXPR PROCEDURE APPEND(U, V); \\ -\hspace*{1em} IF\= NULL U THEN V \\ -\> ELSE CAR U . APPEND(CDR U, V); -\end{tabbing}}} - -\de{ASSOC}{(\p{U}:\ty{any}, \p{V}:\ty{alist}):\{\ty{dotted-pair}, -NIL\}}{eval, spread} -{If U occurs as the CAR portion of an element of the alist V, the -dotted-pair in which U occurred is returned, else NIL is returned. -ASSOC might not detect a poorly formed alist so an invalid -\index{EQUAL ! in ASSOC} \index{alist ! in ASSOC} -construction may be detected by CAR or CDR. - -{\tt \begin{tabbing} EXPR PROCEDURE ASSOC(U, V); \\ -\hspace*{1em} IF \= NULL V THEN NIL \\ -\> ELSE \= IF ATOM CAR V THEN \\ -\> \> ERROR(000, LIST(V, "is a poorly formed alist")) \\ -\> ELSE IF U = CAAR V THEN CAR V \\ -\> ELSE ASSOC(U, CDR V); -\end{tabbing}} -} - -\de{DEFLIST}{(\p{U}:\ty{dlist}, \p{IND}:\ty{id}):\ty{list}}{eval, spread} -{A "dlist" is a list in which each element is a two element list: -\index{dlist} -(ID:id PROP:any). Each ID in U has the indicator IND with property -PROP placed on its property list by the PUT function. The value of -DEFLIST is a list of the first elements of each two element list. -Like PUT, DEFLIST may not be used to define functions. - -{\tt \begin{tabbing} EXPR PROCEDURE DEFLIST(U, IND); \\ -\hspace*{1em} IF NULL U THEN NIL \\ -\hspace*{2em} ELSE $<<$ \= PUT(CAAR U, IND, CADAR U); \\ -\> CAAR U $>>$ . DEFLIST(CDR U, IND); -\end{tabbing}} -} - -\de{DELETE}{(\p{U}:\ty{any}, \p{V}:\ty{list}):\ty{list}}{eval, spread} -{Returns V with the first top level occurrence of U removed from it. -\index{EQUAL ! in DELETE} - -{\tt \begin{tabbing} EXPR PROCEDURE DELETE(U, V); \\ -\hspace*{1em} IF NULL V THEN NIL \\ -\hspace*{2em} ELSE IF CAR V = U THEN CDR V \\ -\hspace*{2em} ELSE CAR V . DELETE(U, CDR V); -\end{tabbing}}} - -\de{DIGIT}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a digit, otherwise NIL. - -{\tt \begin{tabbing} EXPR PROCEDURE DIGIT(U); \\ -\hspace*{1em} IF MEMQ(U, '(!0 !1 !2 !3 !4 !5 !6 !7 !8 !9)) \\ -\hspace*{2em} THEN T ELSE NIL; -\end{tabbing}}} - -\de{LENGTH}{(\p{X}:\ty{any}):\ty{integer}}{eval, spread} -{The top level length of the list X is returned. - -{\tt \begin{tabbing} EXPR PROCEDURE LENGTH(X); \\ -\hspace*{1em} IF ATOM X THEN 0 \\ -\hspace*{2em} ELSE PLUS(1, LENGTH CDR X); -\end{tabbing}}} - -\de{LITER}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} -{Returns T if U is a character of the alphabet, NIL -otherwise.\footnote{The published report omits escape characters. -These are required for both upper and lower case as some systems -default to lower.} - -{\tt \begin{tabbing} EXPR PROCEDURE LITER(U); \\ -\hspace*{1em} IF \= MEMQ(U, '(\=!A !B !C !D !E !F !G !H !I !J !K !L !M \\ -\> \> !N !O !P !Q !R !S !T !U !V !W !X !Y !Z \\ -\> \> !a !b !c !d !e !f !g !h !i !j !k !l !m \\ -\> \> !n !o !p !q !r !s !t !u !v !w !x !y !z)) \\ -\> THEN T ELSE NIL; -\end{tabbing}}} - -\de{MEMBER}{(\p{A}:\ty{any}, \p{B}:\ty{list}):\ty{extra-boolean}}{eval, spread} -{Returns NIL if A is not a member of list B, returns the remainder of -B whose first element is A. \index{EQUAL ! in MEMBER} - -{\tt \begin{tabbing} EXPR PROCEDURE MEMBER(A, B); \\ -\hspace*{1em} IF NULL B THEN NIL \\ -\hspace*{2em} ELSE IF A = CAR B THEN B \\ -\hspace*{2em} ELSE MEMBER(A, CDR B); -\end{tabbing}}} - - -\de{MEMQ}{(\p{A}:\ty{any}, \p{B}:\ty{list}):\ty{extra-boolean}}{eval, spread} -{Same as MEMBER but an EQ check is used for comparison. \index{EQ ! in -MEMQ} - -{\tt \begin{tabbing} EXPR PROCEDURE MEMQ(A, B); \\ -\hspace*{1em} IF \= NULL B THEN NIL \\ -\> ELSE IF A EQ CAR B THEN B \\ -\> ELSE MEMQ(A, CDR B); -\end{tabbing}}} - -\de{NCONC}{(\p{U}:\ty{list}, \p{V}:\ty{list}):\ty{list}}{eval, spread} -{Concatenates V to U without copying U. The last CDR of U is modified -to point to V. - -{\tt \begin{tabbing} EXPR PROCEDURE NCONC(U, V); \\ BEGIN SCALAR W; \\ -\hspace*{2em} \= IF NULL U THEN RETURN V; \\ -\> W := U; \\ -\> WHILE CDR W DO W := CDR W; \\ -\> RPLACD(W, V); \\ -\> RETURN U \\ -END; -\end{tabbing}}} - -\de{PAIR}{(\p{U}:\ty{list}, \p{V}:\ty{list}):\ty{alist}}{eval, spread} -{U and V are lists which must have an identical number of elements. If -not, an error occurs (the 000 used in the ERROR call is arbitrary and -need not be adhered to). Returned is a list where each element is a -dotted-pair, the CAR of the pair being from U, and the CDR the -corresponding element from V. - -{\tt \begin{tabbing} EXPR PROCEDURE PAIR(U, V); \\ -\hspace*{1em} IF AND(U, V) THEN (CAR U . CAR V) . PAIR(CDR U, CDR V) \\ -\hspace*{2em} \= ELSE IF OR(U, V) THEN ERROR(000, \\ -\hspace*{4em} "Different length lists in PAIR") \\ -\> ELSE NIL; -\end{tabbing}}} - - -\de{REVERSE}{(\p{U}:\ty{list}):\ty{list}}{eval, spread} -{Returns a copy of the top level of U in reverse order. - -{\tt \begin{tabbing} EXPR PROCEDURE REVERSE(U); \\ BEGIN SCALAR W; \\ -\hspace*{2em} \= WHILE U DO $<<$ \= W := CAR U . W; \\ -\> \> U := CDR U $>>$; \\ -\> RETURN W \\ -END; -\end{tabbing}}} - -\de{SASSOC}{(\p{U}:\ty{any}, \p{V}:\ty{alist}, -\p{FN}:\ty{function}):\ty{any}}{eval, spread} -{Searches the alist V for an occurrence of U. If U is not in the alist -the evaluation of function FN is returned. \index{EQUAL ! in SASSOC} -\index{alist ! in SASSOC} - -{\tt \begin{tabbing} EXPR PROCEDURE SASSOC(U, V, FN); \\ -\hspace*{1em} IF NULL V THEN FN() \\ -\hspace*{2em} \= ELSE IF U = CAAR V THEN CAR V \\ -\> ELSE SASSOC(U, CDR V, FN); -\end{tabbing}}} - -\de{SUBLIS}{(\p{X}:\ty{alist}, \p{Y}:\ty{any}):\ty{any}}{eval, spread} -{The value returned is the result of substituting the CDR of each -element of the alist X for every occurrence of the CAR part of that -element in Y. \index{alist ! in SUBLIS} - -{\tt \begin{tabbing} EXPR PROCEDURE SUBLIS(X, Y); \\ -\hspace*{1em}IF NULL X THEN Y \\ -\hspace*{2em} ELSE BEGIN \= SCALAR U; \\ -\> U := ASSOC(Y, X); \\ -\> RETURN \= IF U THEN CDR U \\ -\> \> ELSE IF ATOM Y THEN Y \\ -\> \> ELSE \= SUBLIS(X, CAR Y) . \\ -\> \> \> SUBLIS(X, CDR Y) \\ -\> END; -\end{tabbing}}} - -\de{SUBST}{(\p{U}:\ty{any}, \p{V}:\ty{any}, \p{W}:\ty{any}):\ty{any}}{eval, -spread} -{The value returned is the result of substituting U for all -occurrences of V in W. \index{EQUAL ! in SUBST} - -{\tt \begin{tabbing} EXPR PROCEDURE SUBST(U, V, W); \\ -\hspace*{1em} IF NULL W THEN NIL \\ -\hspace*{2em} \= ELSE IF V = W THEN U \\ -\> ELSE IF ATOM W THEN W \\ -\> ELSE SUBST(U, V, CAR W) . SUBST(U, V, CDR W); -\end{tabbing}}} - - -\subsection{The Interpreter} -\label{interpreter} -\de{APPLY}{(\p{FN}:\{\ty{id,function}\}, -\p{ARGS}:\ty{any-list}):\ty{any}}{eval, spread} -{APPLY returns the value of FN with actual parameters ARGS. The actual -parameters in ARGS are already in the form required for binding to the -formal parameters of FN. Implementation specific portions described in -English are enclosed in boxes. - -{\tt \begin{tabbing} EXPR PROCEDURE APPLY(FN, ARGS); \\ BEGIN SCALAR -DEFN; \\ -\hspace*{2em}\= IF CODEP FN THEN RETURN \\ -\> \hspace{1em} \framebox[3.25in]{\parbox{3.25in}{Spread the actual -parameters in ARGS -following the conventions: for calling functions, transfer to the -entry point of the function, and return the value returned by the -function.}}; \\ -\> IF \= IDP FN THEN RETURN \\ -\> \> IF \= NULL(DEFN := GETD FN) THEN \\ -\> \> \> ERROR(000, LIST(FN, "is an undefined function")) \\ -\> \> ELSE IF CAR DEFN EQ 'EXPR THEN \\ -\> \> \> APPLY(CDR DEFN, ARGS) \\ -\> \> ELSE ERROR(000, \\ -\> \> \> LIST(FN, "cannot be evaluated by APPLY")); \\ -\> IF OR(ATOM FN, NOT(CAR FN EQ 'LAMBDA)) THEN \\ -\> \> ERROR(000, \\ -\> \> LIST(FN, "cannot be evaluated by APPLY")); \\ -\> RETURN \\ -\> \> \framebox[3.25in]{\parbox{3.25in}{Bind the actual parameters in ARGS to -the formal -parameters of the lambda expression. If the two lists are not of equal -length then ERROR(000, "Number of parameters do not match"); The value -returned is EVAL CADDR FN.}} \\ END; -\end{tabbing}}} - -\de{EVAL}{(\p{U}:\ty{any}):\ty{any}}{eval, spread} -{The value of the expression U is computed. Error numbers are -arbitrary. Portions of EVAL involving machine specific coding are -expressed in English enclosed in boxes. - -{\tt \begin{tabbing} EXPR PROCEDURE EVAL(U); \\ BEGIN SCALAR FN; \\ -\hspace*{2em} \= IF CONSTANTP U THEN RETURN U; \\ -\> IF IDP U THEN RETURN \\ -\> \hspace{1em} \framebox[3.25in]{\parbox{3.25in}{U is an id. Return the -value most currently -bound to U or if there is no such binding: ERROR(000, LIST("Unbound:", -U));}} \\ -\> IF \= PAIRP CAR U THEN RETURN \\ -\> \> IF CAAR U EQ 'LAMBDA THEN APPLY(CAR U, EVLIS CDR U) \\ -\> \> ELSE ERROR(\= 000, LIST(CAR U, \\ -\> \> \> "improperly formed LAMBDA expression")) \\ -\> \> ELSE IF CODEP CAR U THEN \\ -\> \> \> RETURN APPLY(CAR U, EVLIS CDR U); \\ -\> FN := GETD CAR U; \\ -\> IF NULL FN THEN \\ -\> \> ERROR(000, LIST(CAR U, "is an undefined function")) \\ -\> ELSE IF CAR FN EQ 'EXPR THEN \\ -\> \> RETURN APPLY(CDR FN, EVLIS CDR U) \\ -\> ELSE IF CAR FN EQ 'FEXPR THEN \\ -\> \> RETURN APPLY(CDR FN, LIST CDR U) \\ -\> ELSE IF CAR FN EQ 'MACRO THEN \\ -\> \> RETURN EVAL APPLY(CDR FN, LIST U) \\ -END; -\end{tabbing}}} - -\de{EVLIS}{(\p{U}:\ty{any-list}):\ty{any-list}}{eval, spread} -{EVLIS returns a list of the evaluation of each element of U. - -{\tt \begin{tabbing} EXPR PROCEDURE EVLIS(U); \\ -\hspace*{1em} IF NULL U THEN NIL \\ -\hspace*{2em} ELSE EVAL CAR U . EVLIS CDR U; -\end{tabbing}}} - -\de{EXPAND}{(\p{L}:\ty{list}, \p{FN}:\ty{function}):\ty{list}}{eval, spread} -{FN is a defined function of two arguments to be used in the expansion -of a MACRO. EXPAND returns a list in the form: - -\vspace{.15in} -(FN L$_0$ (FN L$_1$ \ldots (FN L$_{n-1}$ L$_n$) \ldots )) -\vspace{.15in} - -where $n$ is the number of elements in L, L$_i$ is the $i$th element -of L. - -{\tt \begin{tabbing} EXPR PROCEDURE EXPAND(L,FN); \\ -\hspace*{1em} IF NULL CDR L THEN CAR L \\ -\hspace*{2em} ELSE LIST(FN, CAR L, EXPAND(CDR L, FN)); -\end{tabbing}}} - -\de{FUNCTION}{(\p{FN}:\ty{function}):\ty{function}}{noeval, nospread} -{The function FN is to be passed to another function. If FN is to have -side effects its free variables must be fluid or global. FUNCTION is -like QUOTE but its argument may be affected by compilation. We do not -\index{FUNARGs not supported} -consider FUNARGs in this report.} - - -\de{QUOTE}{(U:any):\ty{any}}{noeval, nospread} -{Stops evaluation and returns U unevaluated. - -{\tt \begin{tabbing} FEXPR PROCEDURE QUOTE(U); \\ -\hspace*{2em}CAR U; -\end{tabbing}}} - -\subsection{Input and Output} -\label{IO} -The user normally communicates with Standard LISP through -\index{standard devices} -``standard devices''. The default devices are selected in accordance -with the conventions of the implementation site. Other input and -output devices or files may be selected for reading and writing using -the functions described herein. - - - -\de{CLOSE}{(\p{FILEHANDLE}:\ty{any}):\ty{any}}{eval, spread} -{Closes the file with the internal name FILEHANDLE writing any -necessary end of file marks and such. The value of FILEHANDLE is that -returned by the corresponding OPEN. \index{OPEN} The value returned is -the value of FILEHANDLE. An error occurs if the file can not be -\index{file handle} \index{files} -closed. - -\errormessage{ ***** FILEHANDLE could not be closed} -} - -\de{EJECT}{():NIL}{eval, spread} -{Skip to the top of the next output page. Automatic EJECTs are -executed by the print functions when the length set by the PAGELENGTH -\index{PAGELENGTH} function is exceeded.} - - -\de{LINELENGTH}{(\p{LEN}:\{\ty{integer}, NIL\}):\ty{integer}}{eval, spread} -{If LEN is an integer the maximum line length to be printed before the -print functions initiate an automatic TERPRI is set to the value LEN. -\index{TERPRI} -No initial Standard LISP line length is assumed. The previous line -length is returned except when LEN is NIL. This special case returns -the current line length and does not cause it to be reset. An error -occurs if the requested line length is too large for the currently -selected output file or LEN is negative or zero. - -\errormessage{ ***** LEN is an invalid line length} -} - - -\de{LPOSN}{():\ty{integer}}{eval, spread} -{Returns the number of lines printed on the current page. At the top -of a page, 0 is returned. } - - -\de{OPEN}{(\p{FILE}:\ty{any}, \p{HOW}:\ty{id}):\ty{any}}{eval, spread} -{Open the file with the system dependent name FILE for output if HOW -is EQ to OUTPUT, or input if HOW is EQ to INPUT. If the file is -\index{file handle} \index{files} \index{OUTPUT} \index{INPUT} -opened successfully, a value which is internally associated with the -file is returned. This value must be saved for use by RDS and WRS. An -error occurs if HOW is something other than INPUT or OUTPUT or the -file can't be opened. - -\errormessage{***** HOW is not option for OPEN} -\errormessage{***** FILE could not be opened} -} - - -\de{PAGELENGTH}{(\p{LEN}:\{\ty{integer}, NIL\}):\ty{integer}}{eval, spread} -{Sets the vertical length (in lines) of an output page. Automatic page -EJECTs are executed by the print functions when this length is -\index{EJECT} -reached. The initial vertical length is implementation specific. The -previous page length is returned. If LEN is 0, no automatic page -ejects will occur. } - - -\de{POSN}{():\ty{integer}}{eval, spread} -{Returns the number of characters in the output buffer. When the -buffer is empty, 0 is returned.} - - -\de{PRINC}{(\p{U}:\ty{id}):\ty{id}}{eval, spread} -{U must be a single character id such as produced by EXPLODE or read -by READCH or the value of !\$EOL!\$. The effect is the character U -\index{\$EOL\$ (global)} -displayed upon the currently selected output device. The value of -!\$EOL!\$ causes termination of the current line like a call to -TERPRI.} - - -\de{PRINT}{(\p{U}:\ty{any}):\ty{any}}{eval, spread} -{Displays U in READ readable format and terminates the print line. The -value of U is returned. - -{\tt \begin{tabbing} EXPR PROCEDURE PRINT(U); \\ -\hspace*{2em} $<<$ PRIN1 U; TERPRI(); U $>>$; -\end{tabbing}}} - - -\de{PRIN1}{(\p{U}:\ty{any}):\ty{any}}{eval, spread} -{U is displayed in a READ readable form. The format of display is the -result of EXPLODE expansion; special characters are prefixed with the -escape character !, and strings are enclosed in "\ldots ". Lists are -displayed in list-notation and vectors in vector-notation. } - - -\de{PRIN2}{(\p{U}:\ty{any}):\ty{any}}{eval, spread} -{U is displayed upon the currently selected print device but output is -not READ readable. The value of U is returned. Items are displayed as -described in the EXPLODE function with the exceptions that the escape -character does not prefix special characters and strings are not -enclosed in "\ldots ". Lists are displayed in list-notation and -vectors in vector-notation. The value of U is returned. } - - -\de{RDS}{(\p{FILEHANDLE}:\ty{any}):\ty{any}}{eval, spread} -{Input from the currently selected input file is suspended and further -input comes from the file named. FILEHANDLE is a system dependent -\index{file handle} -internal name which is a value returned by OPEN. If FILEHANDLE is NIL -the standard input device is selected. When end of file is reached on -a non-standard input device, the standard input device is reselected. -When end of file occurs on the standard input device the Standard LISP -reader terminates. RDS returns the internal name of the previously -selected input file. -\index{standard input} - -\errormessage{***** FILEHANDLE could not be selected for input} -} - - -\de{READ}{():\ty{any}}{} -{The next expression from the file currently selected for input. Valid -input forms are: vector-notation, dot-notation, list-notation, -numbers, function-pointers, strings, and identifiers with escape -characters. Identifiers are interned onW the OBLIST (see -\index{INTERN} \index{OBLIST entry} -the INTERN function in "Identifiers", section~\ref{identifiers} on -page~\pageref{identifiers}). READ returns the -\index{\$EOF\$ (global)} -value of !\$EOF!\$ when the end of the currently selected input file -is reached. } - - -\de{READCH}{():\ty{id}}{} -{Returns the next interned character from the file currently selected -for input. Two special cases occur. If all the characters in an input -\index{\$EOL\$ (global)} \index{\$EOF\$ (global)} record have been read, -the value of !\$EOL!\$ is returned. If the file selected for input has -all been read the value of !\$EOF!\$ is returned. Comments delimited -by \% and end-of-line are not transparent to READCH. \index{\% ! read -by READCH} } - - -\de{TERPRI}{():\p{NIL}}{} -{The current print line is terminated.} - - -\de{WRS}{(\p{FILEHANDLE}:\ty{any}):\ty{any}}{eval, spread} -{Output to the currently active output file is suspended and further -output is directed to the file named. FILEHANDLE is an internal name -which is returned by OPEN. The file named must have been opened for -output. If FILEHANDLE is NIL the standard output device is selected. -\index{file handle} \index{standard output} -WRS returns the internal name of the previously selected output file. - -\errormessage{***** FILEHANDLE could not be selected for output} -} - -\subsection{LISP Reader} - -An EVAL read loop has been chosen to drive a Standard LISP system to -provide a continuity in functional syntax. Choices of messages and the -amount of extra information displayed are decisions left to the -implementor. - -\index{STANDARD-LISP} -{\tt \begin{tabbing} EXPR PROCEDURE STANDARD!-LISP(); \\ BEGIN SCALAR -VALUE; \\ -\hspace*{2em} \= RDS NIL; WRS NIL; \\ -\> PRIN2 "Standard LISP"; TERPRI(); \\ -\> WHILE T DO \\ -\> \hspace*{1em} $<<$ \= PRIN2 "EVAL:"; TERPRI(); \\ -\> \> VALUE := ERRORSET(QUOTE EVAL READ(), T, T); \\ -\> \> IF NOT ATOM VALUE THEN PRINT CAR VALUE; \\ -\> \> TERPRI() $>>$; \\ -END; -\end{tabbing}} - -\de{QUIT}{()}{} -{Causes termination of the LISP reader and control to be transferred -to the operating system.} - -\section{System GLOBAL Variables} -\label{slglobals} - -These variables provide global control of the LISP system, or -implement values which are constant throughout execution.\footnote{The -published document does not specify that all these are GLOBAL.} - - -\variable{*COMP}{NIL}{global} -{The value of !*COMP controls whether or not PUTD compiles the -function defined in its arguments before defining it. If !*COMP is NIL -the function is defined as an xEXPR. If !*COMP is something else the -function is first compiled. Compilation will produce certain changes -in the semantics of functions particularly FLUID type access.} - - -\variable{EMSG*}{NIL}{global} -{Will contain the MESSAGE generated by the last ERROR call (see -\index{ERROR} -``Error Handling'' section~\ref{errors} on page~\pageref{errors}).} - - -\variable{\$EOF\$}{\s{an uninterned identifier}}{global} -{The value of !\$EOF!\$ is returned by all input functions when the -end -\index{end of file} -of the currently selected input file is reached.} - - -\variable{\$EOL\$}{\s{an uninterned identifier}}{global} -{The value of !\$EOL!\$ is returned by READCH when it reaches the end -of -\index{READCH} \index{end of line} \index{PRINC} -a logical input record. Likewise PRINC will terminate its current line -(like a call to TERPRI) when !\$EOL!\$ is its argument.} - -\variable{*GC}{NIL}{global} -{!*GC controls the printing of garbage collector messages. If NIL no -\index{garbage collector} -indication of garbage collection may occur. If non-NIL various system -dependent messages may be displayed.} - - -\variable{NIL}{NIL}{global} -{NIL is a special global variable. It is protected from being modified -by SET or SETQ. -\index{NIL ! cannot be changed}} - - -\variable{*RAISE}{NIL}{global} -{If !*RAISE is non-NIL all characters input through Standard LISP -input/output functions will be raised to upper case. If !*RAISE is NIL -characters will be input as is.} - - -\variable{T}{T}{global} -{T is a special global variable. It is protected from being modified -by SET or SETQ. \index{T ! cannot be changed}} - - -\section{The Extended Syntax} - -Whenever it is possible to define Standard LISP functions in LISP the -text of the function will appear in an extended syntax. These -definitions are supplied as an aid to understanding the behavior of -functions and not as a strict implementation guide. A formal scheme -for the translation of extended syntax to Standard LISP is presented -to eliminate misinterpretation of the definitions. - -\subsection{Definition} -The goal of the transformation scheme is to produce a PUTD invocation -which has the function translated from the extended syntax as its -actual parameter. A rule has a name in brackets -\s{\ldots} by which it is known and is defined by what follows the meta -symbol ::=. Each rule of the set consists of one or more -``alternatives'' separated by the $\mid$ meta symbol, being the -different ways in which the rule will be matched by source text. Each -alternative is composed of a ``recognizer'' and a ``generator'' -separated by the $\Longrightarrow$ meta symbol. The recognizer is a -concatenation of any of three different forms. 1) Terminals - Upper -case lexemes and punctuation which is not part of the meta syntax -represent items which must appear as is in the source text for the -rule to succeed. 2) Rules - Lower case lexemes enclosed in \s{\ldots} -are names of other rules. The source text is matched if the named -rule succeeds. 3) Primitives - Lower case singletons not in brackets -are names of primitives or primitive classes of Standard LISP. The -syntax and semantics of the primitives are given in Part I. - -The recognizer portion of the following rule matches an extended -syntax procedure: - - -\s{function} ::= ftype PROCEDURE id (\s{id list}); \\ -\hspace*{2em} \s{statement}; $\Longrightarrow$ - -A function is recognized as an ``ftype'' (one of the tokens EXPR, -FEXPR, etc.) followed by the keyword PROCEDURE, followed by an ``id'' -(the name of the function), followed by an \s{id list} (the formal -parameter names) enclosed in parentheses. A semicolon terminates the -title line. The body of the function is a -\s{statement} followed by a semicolon. For example: - -\begin{verbatim} -EXPR PROCEDURE NULL(X); EQ(X, NIL); -\end{verbatim} - -\noindent satisfies the recognizer, causes the generator to be activated and -the rule to be matched successfully. - -The generator is a template into which generated items are -substituted. The three syntactic entities have corresponding meanings -when they appear in the generator portion. 1) Terminals - These -lexemes are copied as is to the generated text. 2) Rules - If a rule -has succeeded in the recognizer section then the value of the rule is -the result of the generator portion of that rule. 3) Primitives - -When primitives are matched the primitive lexeme replaces its -occurrence in the generator. - -If more than one occurrence of an item would cause ambiguity in the -generator portion this entity appears with a bracketed subscript. -Thus: - -\begin{tabbing} -\s{conditional} ::= \\ -\hspace*{2em} IF \s{expression} \= THEN \s{statement$_1$} \\ -\> ELSE \s{statement$_2$} \ldots -\end{tabbing} - -\noindent has occurrences of two different \s{statement}s. The generator -portion uses the subscripted entities to reference the proper -generated value. - -The \s{function} rule appears in its entirety as: - -\begin{tabbing} -\s{function} ::= ftype PROCEDURE id (\s{id list});\s{statement}; -$\Longrightarrow$ \\ -\hspace*{2em} \=(PUTD \= (QUOTE id) \\ -\> \> (QUOTE ftype) \\ -\> \>(QUOTE (LAMBDA (\s{id list}) \s{statement}))) -\end{tabbing} - -If the recognizer succeeds (as it would in the case of the NULL -procedure example) the generator returns: - -\begin{verbatim} -(PUTD (QUOTE NULL) (QUOTE EXPR) (QUOTE (LAMBDA (X) (EQ X NIL)))) -\end{verbatim} - -The identifier in the template is replaced by the procedure name NULL, -\s{id list} by the single formal parameter X, the \s{statement} by (EQ -X NIL) which is the result of the \s{statement} generator. EXPR -replaces ftype, the type of the defined procedure. - - -\subsection{The Extended Syntax Rules} - -\begin{tabbing} -\s{function} ::= ftype \k{PROCEDURE} id (\s{id list}); \s{statement}; -$\Longrightarrow$ \\ -\hspace*{2em} \= (PUTD \= (QUOTE id) \\ -\> \> (QUOTE ftype) \\ -\> \> (QUOTE (LAMBDA (\s{id list}) \s{statement}))) \\ \\ - -\s{id list} ::= id $\Longrightarrow$ id $\mid$ \\ -\> id, \s{id list} $\Longrightarrow$ id \s{id list} $\mid$ \\ -\> $\Longrightarrow$ NIL \\ - -\s{statement} ::= \s{expression} $\Longrightarrow$ \s{expression} $\mid$ \\ -\> \s{proper statement} $\Longrightarrow$ \s{proper statement} \\ \\ - -\s{proper statement} ::= \\ -\> \s{assignment statement} $\Longrightarrow$ \s{assignment statement} -$\mid$ \\ -\> \s{conditional statement} $\Longrightarrow$ \s{conditional statement} -$\mid$ \\ -\> \s{while statement} $\Longrightarrow$ \s{while statement} $\mid$ \\ -\> \s{compound statement} $\Longrightarrow$ \s{compound statement} \\ \\ - -\s{assignment statement} ::= id := \s{expression} $\Longrightarrow$ \\ -\> \> (SETQ id \s{expression}) \\ \\ - -\s{conditional statement} ::= \\ -\> \k{IF} \s{expression} \k{THEN} \s{statement$_1$} \k{ELSE} -\s{statement$_2$} $\Longrightarrow$ \\ -\> \hspace{2em} \= (COND (\s{expression} \s{statement$_1$})(T -\s{statement$_2$})) $\mid$ \\ -\> \k{IF} \s{expression} \k{THEN} \s{statement} $\Longrightarrow$ \\ -\> \> (COND (\s{expression} \s{statement})) \\ \\ - -\s{while statement} ::= \k{WHILE} \s{expression} \k{DO} \s{statement} -$\Longrightarrow$ \\ -\> \> (PROG NIL \\ -\> \> LBL \= (COND ((NULL \s{expression}) (RETURN NIL))) \\ -\> \> \> \s{statement} \\ -\> \> \> (GO LBL)) \\ \\ - -\s{compound statement} ::= \\ -\> \k{BEGIN} \k{SCALAR} \s{id list}; \s{program list} \k{END} -$\Longrightarrow$ \\ -\> \> (PROG (\s{id list}) \s{program list}) $\mid$ \\ -\> \k{BEGIN} \s{program list} \k{END} $\Longrightarrow$ \\ -\> \> (PROG NIL \s{program list}) $\mid$ \\ -\> \k{$<<$} \s{statement list} \k{$>>$} $\Longrightarrow$ (PROGN -\s{statement list}) \\ \\ - -\s{program list} ::= \s{full statement} $\Longrightarrow$ \s{full statement} - $\mid$ \\ -\> \s{full statement} \s{program list} $\Longrightarrow$ \\ -\> \> \s{full statement} \s{program list} \\ \\ - -\s{full statement} ::= \s{statement} $\Longrightarrow$ \s{statement} $\mid$ -id: $\Longrightarrow$ id \\ \\ - -\s{statement list} ::= \s{statement} $\Longrightarrow$ \s{statement} $\mid$ \\ -\> \s{statement}; \s{statement list} $\Longrightarrow$ \\ -\> \> \s{statement} \s{statement list} \\ \\ - -\s{expression} ::= \\ -\> \s{expression$_1$} \k{.} \s{expression$_2$} $\Longrightarrow$ \\ -\> \> (CONS \s{expression$_1$} \s{expression$_2$} $\mid$ \\ -\> \s{expression$_1$} \k{=} \s{expression$_2$} $\Longrightarrow$ \\ -\> \> (EQUAL \s{expression$_1$} \s{expression$_2$}) $\mid$ \\ -\> \s{expression$_1$} \k{EQ} \s{expression$_2$} $\Longrightarrow$ \\ -\> \> (EQ \s{expression$_1$} \s{expression$_2$}) $\mid$ \\ -\> '\s{expression} $\Longrightarrow$ (QUOTE \s{expression}) $\mid$ \\ -\> function \s{expression} $\Longrightarrow$ (function \s{expression}) -$\mid$ \\ -\> function(\s{argument list}) $\Longrightarrow$ (function \s{argument list}) -$\mid$ \\ -\> number $\Longrightarrow$ number $\mid$ \\ -\> id $\Longrightarrow$ id \\ \\ - -\s{argument list} ::= () $\Longrightarrow$ $\mid$ \\ -\> \s{expression} $\Longrightarrow$ \s{expression} $\mid$ \\ -\> \s{expression}, \s{argument list} $\Longrightarrow$ \s{expression} -\s{argument list} -\end{tabbing} - -Notice the three infix operators . EQ and = which are translated into -calls on CONS, EQ, and EQUAL respectively. Note also that a call on a -function which has no formal parameters must have () as an argument -list. The QUOTE function is abbreviated by '. -\bibliography{sl} -\bibliographystyle{plain} -\end{document} +\documentstyle[11pt,reduce]{article} +\title{The Standard Lisp Report} +\date{} +\author{Jed Marti \\ A. C. Hearn \\ M. L. Griss \\ C. Griss} + +%%% Function/method definition. +%%% de{fname}{arglist}{type}{text} For short arg lists. +%%% DE{fname}{arglist}{type}{text} For long arg lists. +\newlength{\argwidth} % Width of argument box. +\setlength{\argwidth}{4in} +\newlength{\dewidth} +\setlength{\dewidth}{4.5in} % Width of text box. + +\newcommand{\de}[4] +{\vspace{.25in} \noindent +\begin{minipage}[t]{\textwidth} \index{#1} {\f{#1}}{#2}\hfill{\em #3} \\ +\hspace*{.25in}\begin{minipage}[t]{\dewidth} #4 \end{minipage} +\end{minipage} } + +%%% Global/fluid variable description. +%%% variable{name}{initial value}{type}{text} +\newcommand{\variable}[4] +{\vspace{.25in} \noindent +\begin{minipage}[t]{\textwidth} \index{#1 (#3)} {\bf #1} = #2 \hfill {\em #3} + \\ +\hspace*{.25in} \ \begin{minipage}[t]{\dewidth} #4 \end{minipage} +\end{minipage}} + +%%% Command to display an error or warning message in teletype format. Also +%%% leaves blank vertical space around it. +\newcommand{\errormessage}[1] +{\vspace{.1in} \noindent {\tt #1} \\ \vspace{.1in}} + + +%%% \p is a parameter name (or argument). Just do this as bf. +\newcommand{\p}[1] {{\bf #1}} +%%% \ty is a type - do as italics. +\newcommand{\ty}[1] {{\em #1}} +\begin{document} +\maketitle + +\section{Introduction} +Although the programming language LISP was first formulated in +1960~\cite{LISP1.5}, a widely accepted standard has never appeared. As +a result, various dialects of LISP were +produced~\cite{CDC-LISP,LISP/360,MACLISP,Interlisp,LISPF1,LISP1.6} in +some cases several on the same machine! Consequently, a user often +faces considerable difficulty in moving programs from one system to +another. In addition, it is difficult to write and use programs which +depend on the structure of the source code such as translators, +editors and cross-reference programs. + +In 1969, a model for such a standard was produced~\cite{Hearn:69} as +part of a general effort to make a large LISP based algebraic +manipulation program, REDUCE~\cite{REDUCE3.3}, as portable as +possible. The goal of this work was to define a uniform subset of +LISP 1.5 and its variants so that programs written in this subset +could run on any reasonable LISP system. + +In the intervening years, two deficiencies in the approach taken in +Ref.~\cite{Hearn:69} have emerged. First in order to be as general as +possible, the specific semantics and values of several key functions +were left undefined. Consequently, programs built on this subset could +not make any assumptions about the form of the values of such +functions. The second deficiency related to the proposed method of +implementation of this language. The model considered in effect two +versions of LISP on any given machine, namely Standard LISP and the +LISP of the host machine (which we shall refer to as Target LISP). +This meant that if any definition was stored in interpretive form, it +would vary from implementation to implementation, and consequently one +could not write programs in Standard LISP which needed to assume any +knowledge about the structure of such forms. This deficiency became +apparent during recent work on the development of a portable compiler +for LISP~\cite{PLC}. Clearly a compiler has to know precisely the +structure of its source code; we concluded that the appropriate source +was Standard LISP and not Target LISP. + +With these thoughts in mind we decided to attempt again a definition +of Standard LISP. However, our approach this time is more aggressive. +In this document we define a standard for a reasonably large subset of +LISP with as precise as possible a statement about the semantics of +each function. Secondly, we now require that the target machine +interpreter be modified or written to support this standard, rather +than mapping Standard LISP onto Target LISP as previously. + +We have spent countless hours in discussion over many of the +definitions given in this report. We have also drawn on the help and +advice of a lot of friends whose names are given in the +Acknowledgements. Wherever possible, we have used the definition of a +function as given in the LISP 1.5 Programmer's Manual~\cite{LISP1.5} +and have only deviated where we felt it desirable in the light of LISP +programming experience since that time. In particular, we have given +considerable thought to the question of variable bindings and the +definition of the evaluator functions EVAL and APPLY. We have also +abandoned the previous definition of LISP arrays in favor of the more +accepted idea of a vector which most modern LISP systems support. +These are the places where we have strayed furthest from the +conventional definitions, but we feel that the consistency which +results from our approach is worth the redefinition. + +We have avoided entirely in this report problems which arise from +environment passing, such as those represented by the FUNARG problem. +We do not necessarily exclude these considerations from our standard, +but in this report have decided to avoid the controversy which they +create. The semantic differences between compiled and interpreted +functions is the topic of another paper~\cite{PLC}. Only functions +which affect the compiler in a general way make reference to it. + +This document is not intended as an introduction to LISP rather it is +assumed that the reader is already familiar with some version. The +document is thus intended as an arbiter of the syntax and semantics of +Standard LISP. However, since it is not intended as an implementation +description, we deliberately leave unspecified many of the details on +which an actual implementation depends. For example, while we assume +the existence of a symbol table for atoms (the "object list" in LISP +terminology), we do not specify its structure, since conventional LISP +programming does not require this information. Our ultimate goal, +however, is to remedy this by defining an interpreter for Standard +LISP which is sufficiently complete that its implementation on any +given computer will be straightforward and precise. At that time, we +shall produce an implementation level specification for Standard LISP +which will extend the description of the primitive functions defined +herein by introducing a new set of lower level primitive functions in +which the structure of the symbol table, heap and so on may be +defined. + +The plan of this chapter is as follows. In Section~\ref{dtypes} we +describe the various data types used in Standard LISP. In +Section~\ref{slfns}, a description of all Standard LISP functions is +presented, organized by type. These functions are defined in an RLISP +syntax which is easier to read than LISP S-expressions. +Section~\ref{slglobals} describes global variables which control the +operation of Standard LISP. + + +\section{Preliminaries} +\label{dtypes} +\subsection{Primitive Data Types} +\label{pdat} +\begin{description} +\item[integer] Integers are also called "fixed" numbers. The magnitude of +an integer is unrestricted. Integers in the LISP input stream are +\index{integer ! input} \index{integer ! magnitude} +recognized by the grammar: + +\begin{tabbing} +\s{digit} ::= 0$\mid$1$\mid$2$\mid$3$\mid$4$\mid$5$\mid$6$\mid$7$\mid$8$\mid$9 +\\ +\s{unsigned-integer} ::= \s{digit}$\mid$\s{unsigned-integer}\s{digit} \\ +\s{integer} ::= \= \s{unsigned-integer} $\mid$ \\ +\> +\s{unsigned-integer} $\mid$ \\ +\> ---\s{unsigned-integer} +\end{tabbing} + +\item[floating] - Any floating point number. The precision of floating point +\index{floating ! input} +numbers is determined solely by the implementation. In BNF floating +point numbers are recognized by the grammar: + +\begin{tabbing} +\s{base} ::= \= \s{unsigned-integer}.$\mid$.\s{unsigned-integer}$\mid$ \\ +\> \s{unsigned-integer}.\s{unsigned-integer} \\ +\> \s{unsigned-floating} ::= \s{base}$\mid$ \\ +\> \s{base}E\s{unsigned-integer}$\mid$ \\ +\> \s{base}E-\s{unsigned-integer}$\mid$ \\ +\> \s{base}E+\s{unsigned-integer} \\ +\s{floating} ::= \= \s{unsigned-floating}$\mid$ \\ +\> +\s{unsigned-floating}$\mid$-\s{unsigned-floating} +\end{tabbing} + +\item[id] An identifier is a string of characters which may have the +\index{id ! input} \index{identifier (see id)} +following items associated with it. + +\begin{description} +\item[print name] \index{print name} The characters of the identifier. + +\item[flags] An identifier may be tagged with a flag. Access is by the +FLAG, REMFLAG, and FLAGP functions defined in section~\ref{plist} on +page~\pageref{plist}. \index{FLAG} \index{REMFLAG} \index{FLAGP} + +\item[properties] \index{properties} An identifier may have an +indicator-value pair associated with it. Access is by the PUT, GET, +and REMPROP functions defined in section~\ref{plist} on +page~\pageref{plist}. +\index{PUT} \index{GET} \index{REMPROP} + +\item[values/functions] An identifier may have a value associated with +\index{values} \index{functions} it. Access to values is by SET and SETQ +defined in \index{SET} \index{SETQ} section~\ref{varsandbinds} on +page~\pageref{varsandbinds}. The method by which the value is attached +to the identifier is known as the binding type, being one of LOCAL, +GLOBAL, or FLUID. Access to the binding type is by the GLOBAL, +GLOBALP, FLUID, FLUIDP, and UNFLUID functions. +\index{GLOBAL} \index{GLOBALP} \index{FLUID} \index{FUIDP} \index{UNFLUID} + +An identifier may have a function or macro associated with it. Access +is by the PUTD, GETD, and REMD functions (see ``Function Definition'', +section~\ref{fdef}, on page~\pageref{fdef}). \index{PUTD} \index{GETD} +\index{REMD} An identifier may not have both a function and a value +associated with it. + +\item[OBLIST entry] \index{OBLIST entry} An identifier may be entered and +removed from a structure called the OBLIST. Its presence on the OBLIST +does not directly affect the other properties. Access to the OBLIST is +by the INTERN, REMOB, and READ functions. \index{INTERN} \index{REMOB} +\index{READ} +\end{description} + +The maximum length of a Standard LISP identifier is 24 characters +\index{id ! maximum length} +(excluding occurrences of the escape character !) but an +\index{id ! escape character} +implementation may allow more. Special characters (digits in the first +position and punctuation) must be prefixed with an escape character, +an ! in Standard LISP. In BNF identifiers are recognized by the +grammar: + + +\begin{tabbing} +\s{special-character} ::= !\s{any-character} \\ +\s{alphabetic} ::= \\ +\hspace*{.25in} \= A$\mid$B$\mid$C$\mid$D$\mid$E$\mid$F$\mid$G$\mid$H$ +\mid$I$\mid$J$\mid$K$\mid$L$\mid$M$\mid$N$\mid$O$\mid$P$\mid$Q$\mid$R$ +\mid$S$\mid$T$\mid$U$\mid$V$\mid$W$\mid$X$\mid$Y$\mid$Z$\mid$ \\ +\> a$\mid$b$\mid$c$\mid$d$\mid$e$\mid$f$\mid$g$\mid$h$\mid$i$\mid$j$ +\mid$k$\mid$l$\mid$m$\mid$n$\mid$o$\mid$p$\mid$q$\mid$r$\mid$s$\mid$t$ +\mid$u$\mid$v$\mid$w$\mid$x$\mid$y$\mid$z \\ +\s{lead-character} ::= \s{special-character}$\mid$\s{alphabetic} \\ +\s{regular-character} ::= \s{lead-character}$\mid$\s{digit} \\ +\s{last-part} ::= \= \s{regular-character} $\mid$ \\ +\> \s{last-part}\s{regular-character} \\ +\s{id} ::= \s{lead-character}$\mid$\s{lead-character}\s{last-part} +\end{tabbing} + +Note: Using lower case letters in identifiers may cause portability +problems. Lower case letters are automatically converted to upper case +when the !*RAISE flag is T. \index{*RAISE (global)} + + +\item[string] \index{string} A set of characters enclosed in double quotes as +in "THIS IS A STRING". A quote is included by doubling it as in "HE +SAID, ""LISP""". The maximum size of strings is 80 characters but an +implementation may allow more. Strings are not part of the OBLIST and +are considered constants like numbers, vectors, and function-pointers. + +\item[dotted-pair] A primitive structure which has a left and right part. +\index{dotted-pair} \index{dot-notation} +A notation called {\em dot-notation} is used for dotted pairs and +takes the form: + +\begin{tabbing} +(\s{left-part} . \s{right-part}) +\end{tabbing} + +The \s{left-part} is known as the CAR portion and the \s{right-part} +as the CDR portion. The left and right parts may be of any type. +Spaces are used to resolve ambiguity with floating point numbers. + + +\item[vector] \index{vector} A primitive uniform structure in which +an integer index is used to access random values in the structure. The +individual elements of a vector may be of any type. Access to vectors +is restricted to functions defined in ``Vectors'' +section~\ref{vectors} on page~\pageref{vectors}. A notation for +vectors, {\em vector-notation}, has the elements of a vector +surrounded +\index{vector-notation} +by square brackets\footnote{Vector elements are not separated by +commas as in the published version of this document.} + + +\begin{tabbing} +\s{elements} ::= \s{any}$\mid$\s{any} \s{elements} \\ +\s{vector} ::= [\s{elements}] +\end{tabbing} + +\item[function-pointer] \index{function-pointer} An implementation may have +functions which deal with specific data types other than those listed. +The use of these entities is to be avoided with the exception of a +restricted use of the function-pointer, an access method to compiled +EXPRs and FEXPRs. A particular function-pointer must remain valid +\index{EXPR} \index{FEXPR} +throughout execution. Systems which change the location of a function +must use either an indirect reference or change all occurrences of the +associated value. There are two classes of use of function-pointers, +those which are supported by Standard LISP but are not well defined, +and those which are well defined. + +\begin{description} +\item[Not well defined] Function pointers may be displayed by the print +functions or expanded by EXPLODE. \index{EXPLODE} The value appears in +the convention of the implementation site. The value is not defined in +Standard LISP. Function pointers may be created by COMPRESS +\index{COMPRESS} in the format used for printing but the value used is +not defined in Standard LISP. Function pointers may be created by +functions which deal with compiled function loading. Again, the values +created are not well defined in Standard LISP. + +\item[Well defined] The function pointer associated with an EXPR or +FEXPR may be retrieved by GETD \index{GETD} and is valid as long as +Standard LISP is in execution. Function pointers may be stored using +\index{PUTD} \index{PUT} \index{SETQ} PUTD, PUT, SETQ and the like or by +being bound to variables. Function pointers may be checked for +equivalence by EQ. \index{EQ ! of function-pointers} The value may be +checked for being a function pointer by the CODEP function. +\index{CODEP} +\end{description} +\end{description} + + +\subsection{Classes of Primitive Data Types} +\label{pclasses} +The classes of primitive types are a notational convenience for +describing the properties of functions. + + +\begin{description} +\item[boolean] \index{boolean} The set of global variables \{T,NIL\}, +or their respective values, \{T, NIL\}. \index{T (global)} \index{NIL +(global)} + +\item[extra-boolean] \index{extra-boolean} Any value in the system. +Anything that is not NIL \index{NIL (global)} has the boolean +interpretation T. \index{T (global)} + +\item[ftype] \index{ftype} The class of definable function types. The +set of ids \{EXPR, FEXPR, MACRO\}. \index{EXPR} \index{FEXPR} +\index{MACRO} + +\item[number] \index{number} The set of \{integer, floating\}. + +\item[constant] \index{constant} The set of \{integer, floating, +string, vector, function-pointer\}. Constants evaluate to themselves +(see the definition of EVAL in ``The Interpreter'', +section~\ref{interpreter} on page~\pageref{interpreter}). \index{EVAL +! of constants} + + +\item[any] \index{any} The set of \{integer, floating, string, id, +dotted-pair, vector, function-pointer\}. An S-expression is another +term for any. All Standard LISP entities have some value unless an +ERROR occurs during evaluation or the function causes transfer of +control (such as GO and RETURN). + + +\item[atom] \index{atom} The set \{any\}-\{dotted-pair\}. +\end{description} + +\subsection{Structures} +\index{data structures} \index{structures} +Structures are entities created out of the primitive types by the use +of dotted-pairs. Lists are structures very commonly required as actual +parameters to functions. Where a list of homogeneous entities is +required by a function this class will be denoted by +\s{{\bf xxx}-list} where {\bf \em xxx} is the name of a class of primitives +or structures. Thus a list of ids is an {\em id-list}, a list of +integers an {\em integer-list} and so on. \index{id-list} +\index{integer-list} +\index{-list} + +\begin{description} +\item[list] \index{list} A list is recursively defined as NIL or the +\index{list-notation} \index{NIL (global)} +dotted-pair (any~.~list). A special notation called {\em +list-notation} is used to represent lists. List-notation eliminates +extra parentheses and dots. The list (a . (b . (c . NIL))) in list +notation is (a b c). +\index{dot-notation} +List-notation and dot-notation may be mixed as in (a b . c) or (a (b . +c) d) which are (a . (b . c)) and (a . ((b . c) . (d . NIL))). In BNF +lists are recognized by the grammar: + +\begin{tabbing} +\s{left-part} ::= ( $\mid$ \s{left-part} \s{any} \\ +\s{list} ::= \s{left-part}) $\mid$ \s{left-part} . \s{any}) +\end{tabbing} + +Note: () is an alternate input representation of NIL. \index{()} + + +\item[alist] \index{alist} An association list; each element of the list +is a dotted-pair, the CAR part being a key associated with the value +in the CDR part. \index{association list} + + +\item[cond-form] \index{cond-form} A cond-form is a list of 2 element lists +of the form: + +(\p{ANTECEDENT}:{\em any} \p{CONSEQUENT}:{\em any}) + +The first element will henceforth be known as the antecedent and +\index{antecedent (cond-form)} \index{consequent (cond-form)} +the second as the consequent. The antecedent must have a value. The +consequent may have a value or an occurrence of GO or RETURN +\index{GO} \index{RETURN} +as described in the ``Program Feature Functions'', section~\ref{prog} +on page~\pageref{prog}. + + +\item[lambda] \index{LAMBDA} A LAMBDA expression which must have the form +(in list notation): (LAMBDA parameters body). ``parameters'' is a list +of formal parameters for ``body'' an S-expression to be evaluated. The +semantics of the evaluation are defined with the EVAL function (see +``The Interpreter'', section~\ref{interpreter} on \index{EVAL ! lambda +expressions} page~\pageref{interpreter}). \index{lambda expression} + +\item[function] \index{function} A LAMBDA expression or a function-pointer +to a function. A function is always evaluated as an EVAL, SPREAD form. +\index{EVAL ! function} +\end{description} + + +\subsection{Function Descriptions} + +Each function is provided with a prototypical header line. Each formal +parameter is given a name and suffixed with its allowed type. Lower +case, italic tokens are names of classes and upper case, bold face, +tokens are parameter names referred to in the definition. The type of +the value returned by the function (if any) is suffixed to the +parameter list. If it is not commonly used the parameter type may be +a specific set enclosed in brackets \{\ldots\}. \index{\{\ldots\} ! as +syntax} For example: + + +\vspace{.1in} +\noindent \f{PUTD}(\p{FNAME}:\ty{id}, \p{TYPE}:\ty{ftype}, +\p{BODY}:\{\ty{lambda, function-pointer}\}):\ty{id} +\vspace{.1in} + +PUTD is a function with three parameters. The parameter FNAME is an id +to be the name of the function being defined. TYPE is the type of the +function being defined and BODY is a lambda expression or a +function-pointer. PUTD returns the name of the function being defined. + + + +Functions which accept formal parameter lists of arbitrary length have +the type class and parameter enclosed in square brackets indicating +that zero or more occurrences of that argument are permitted. +\index{[\ldots] syntax} For example: + +\vspace{.1in} +\noindent \f{AND}([\p{U}:\ty{any}]):\ty{extra-boolean} +\vspace{.1in} + +AND is a function which accepts zero or more arguments which may be of +any type. + +\subsection{Function Types} + +EVAL type functions are those which are invoked with evaluated +\index{EVAL ! function type} +arguments. NOEVAL functions are invoked with unevaluated arguments. +\index{NOEVAL ! function type} +SPREAD type functions have their arguments passed in one-to-one +\index{SPREAD ! function type} +correspondence with their formal parameters. NOSPREAD functions +\index{NOSPREAD ! function type} +receive their arguments as a single list. EVAL, SPREAD functions are +\index{FEXPR} +associated with EXPRs and NO\-EVAL, NO\-SPREAD functions with FEXPRs. +EVAL, NO\-SPREAD and NOEVAL, SPREAD functions can be simulated using +NOEVAL, NO\-SPREAD functions or MACROs. \index{MACRO} + +EVAL, SPREAD type functions may have a maximum of 15 parameters. +\index{formal parameter limit} +There is no limit on the number of parameters a NOEVAL, NOSPREAD +function or MACRO may have. + +In the context of the description of an EVAL, SPREAD function, then we +speak of the formal parameters we mean their actual values. However, +in a NOEVAL, NOSPREAD function it is the unevaluated actual +parameters. + +A third function type, the MACRO, implements functions which +\index{MACRO} +create S-expressions based on actual parameters. When a macro +invocation is encountered, the body of the macro, a lambda expression, +is invoked as a NOEVAL, NOSPREAD function with the macro's invocation +bound as a list to the macros single formal parameter. When the macro +has been evaluated the resulting S-expression is reevaluated. The +description of the EVAL and EXPAND +\index{EVAL ! MACRO functions} +functions provide precise details. + + +\subsection{Error and Warning Messages} +\index{error messages} +Many functions detect errors. The description of such functions will +include these error conditions and suggested formats for display +\index{ERROR} +of the generated error messages. A call on the ERROR function is +implied but the error number is not specified by Standard LISP. In +some cases a warning message is sufficient. To distinguish between +\index{warning messages} \index{***** (error message)} +\index{*** (warning message)} +errors and warnings, errors are prefixed with five asterisks and +warnings with only three. + +Primitive functions check arguments that must be of a certain +primitive type for being of that type and display an error message if +the argument is not correct. The type mismatch error always takes the +form: +\index{error ! type mismatch error} + +\errormessage{***** PARAMETER not TYPE for FN} + +Here PARAMETER is the unacceptable actual parameter, TYPE is the type +that PARAMETER was supposed to be. FN is the name of the function that +detected the error. + +\subsection{Comments} + +\index{comments} \index{\%} +The character \% signals the start of a comment, text to be ignored +during parsing. A comment is terminated by the end of the line it +\index{READCH} \index{READ} +is on. The function READCH must be able to read a comment one +character at a time. Comments are transparent to the function READ. +\% may occur as a character in identifiers by preceding it with the +\index{escape character} +escape character !. + + +\section{Functions} +\label{slfns} + +\subsection{Elementary Predicates} +\label{elpreds} +\index{predicate !} +\index{T (global)} \index{NIL (global)} +Functions in this section return T when the condition defined is met +and NIL when it is not. Defined are type checking functions and +elementary comparisons. + + +\de{ATOM}{(\p{U}:\ty{any}):{\ty boolean}}{eval, spread} +{Returns T if U is not a pair. + +{\tt \begin{tabbing} EXPR PROCEDURE ATOM(U); \\ +\hspace*{1em} NULL PAIRP U; +\end{tabbing}}} + + +\de{CODEP}{(\p{U}:\f{any}):{\ty boolean}}{eval, spread} +{Returns T if U is a function-pointer.} + + +\de{CONSTANTP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a constant (a number, string, function-pointer, or +vector). + +{\tt \begin{tabbing} EXPR PROCEDURE CONSTANTP(U); \\ +\hspace*{1em} NULL OR(PAIRP U, IDP U); +\end{tabbing}} +} + + + +\de{EQ}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U points to the same object as V. EQ is \underline{not} +a reliable comparison between numeric arguments. } + + +\de{EQN}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U and V are EQ or if U and V are numbers and have the +same value and type. } + + +\de{EQUAL}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U and V are the same. Dotted-pairs are compared +recursively to the bottom levels of their trees. Vectors must have +identical dimensions and EQUAL values in all positions. Strings must +\index{EQ ! of function-pointers} \index{EQN} have identical characters. +Function pointers must have EQ values. Other atoms must be EQN equal. } + + +\de{FIXP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is an integer (a fixed number).} + + +\de{FLOATP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a floating point number. } + + +\de{IDP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is an id.} + + +\de{MINUSP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a number and less than 0. If U is not a number or +is a positive number, NIL is returned. + +{\tt \begin{tabbing} EXPR PROCEDURE MINUSP(U); \\ +\hspace*{1em} IF NUMBERP U THEN LESSP(U, 0) ELSE NIL; +\end{tabbing}}} + + +\de{NULL}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is NIL. + +{\tt \begin{tabbing} EXPR PROCEDURE NULL(U); \\ +\hspace*{1em} U EQ NIL; +\end{tabbing}}} + + +\de{NUMBERP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a number (integer or floating). + +{\tt \begin{tabbing} EXPR PROCEDURE NUMBERP(U); \\ +\hspace*{1em} IF OR(FIXP U, FLOATP U) THEN T ELSE NIL; +\end{tabbing}}} + + +\de{ONEP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread.} +{Returns T if U is a number and has the value 1 or 1.0. Returns NIL +otherwise. \footnote{The definition in the published report is +incorrect as it does not return T for \p{U} of 1.0.} + +{\tt \begin{tabbing} EXPR PROCEDURE ONEP(U); \\ +\hspace*{1em} OR(EQN(U, 1), EQN(U, 1.0)); +\end{tabbing}}} + + +\de{PAIRP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a dotted-pair. } + + +\de{STRINGP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a string. } + + +\de{VECTORP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a vector. } + + +\de{ZEROP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread.} +{Returns T if U is a number and has the value 0 or 0.0. Returns NIL +otherwise.\footnote{The definition in the published report is +incorrect as it does not return T for \p{U} of 0.0.} + +{\tt \begin{tabbing} EXPR PROCEDURE ZEROP(U); \\ +\hspace*{1em} OR(EQN(U, 0), EQN(U, 0.0)); +\end{tabbing}}} + + +\subsection{Functions on Dotted-Pairs} + +\index{dotted-pair} +The following are elementary functions on dotted-pairs. All functions +in this section which require dotted-pairs as parameters detect a type +mismatch error if the actual parameter is not a dotted-pair. + + + +\de{CAR}{(\p{U}:\ty{dotted-pair}):\ty{any}}{eval, spread} +{CAR(CONS(a, b)) $\rightarrow$ a. The left part of U is returned. The +type +\index{CONS} +mismatch error occurs if U is not a dotted-pair.} + + +\de{CDR}{(\p{U}:\ty{dotted-pair}):\ty{any}}{eval, spread} +{CDR(CONS(a, b)) $\rightarrow$ b. The right part of U is returned. The +type +\index{CONS} +mismatch error occurs if U is not a dotted-pair.} + + +The composites of CAR and CDR are supported up to 4 levels, namely: +\index{CAR ! composite forms} \index{CDR ! composite forms} + +\hspace*{1in}\begin{tabular}{l l l} +CAAAAR & CAAAR & CAAR \\ CAAADR & CAADR & CADR \\ CAADAR & CADAR & +CDAR \\ CAADDR & CADDR & CDDR \\ CADAAR & CDAAR & \\ CADADR & CDADR & +\\ CADDAR & CDDAR & \\ CADDDR & CDDDR & \\ CDAAAR & & \\ CDAADR & & \\ +CDADAR & & \\ CDADDR & & \\ CDDAAR & & \\ CDDADR & & \\ CDDDAR & & \\ +CDDDDR & & +\end{tabular} + +\de{CONS}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{dotted-pair}}{eval, spread} +{Returns a dotted-pair which is not EQ to anything and has U as its +\index{EQ ! of dotted-pairs} \index{dotted-pair} +CAR part and V as its CDR part.} + + +\de{LIST}{([\p{U}:\ty{any}]):\ty{list}}{noeval, nospread, or macro} +{A list of the evaluation of each element of U is returned. The order +of evaluation need not be first to last as the following definition +implies.\footnote{The published report's definition implies a specific +ordering.} + +{\tt \begin{tabbing} FEXPR PROCEDURE LIST(U); \\ +\hspace*{1em} EVLIS U; +\end{tabbing}}} + + +\de{RPLACA}{(\p{U}:\ty{dotted-pair}, +\p{V}:\ty{any}):\ty{dotted-pair}}{eval, spread} +{The CAR portion of the dotted-pair U is replaced by V. If dotted-pair +U is (a . b) then (V . b) is returned. The type mismatch error occurs +if U is not a dotted-pair. } + + +\de{RPLACD}{(\p{U}:\ty{dotted-pair}, +\p{V}:\ty{any}):\ty{dotted-pair}}{eval, spread} +{The CDR portion of the dotted-pair U is replaced by V. If dotted-pair +U is (a . b) then (a . V) is returned. The type mismatch error occurs +if U is not a dotted-pair.} + + +\subsection{Identifiers} +\label{identifiers} +The following functions deal with identifiers and the OBLIST, +\index{OBLIST} +the structure of which is not defined. The function of the OBLIST is +to provide a symbol table for identifiers created during input. +Identifiers created by READ which have the same characters will +\index{READ} \index{EQ ! of identifiers} +therefore refer to the same object (see the EQ function in +``Elementary Predicates'', section~\ref{elpreds} on +page~\pageref{elpreds}). + + + +\de{COMPRESS}{(\p{U}:\ty{id-list}):\{\ty{atom}-\ty{vector}\}}{eval, spread} +{U is a list of single character identifiers which is built into a +Standard LISP entity and returned. Recognized are numbers, strings, +and identifiers with the escape character prefixing special +characters. The formats of these items appear in ``Primitive Data +Types'' section~\ref{pdat} on page~\pageref{pdat}. Identifiers are not +interned on the OBLIST. Function pointers may be compressed but this +is an undefined use. If an entity cannot be parsed out of U or +characters are left over after parsing an error occurs: + +\errormessage{***** Poorly formed atom in COMPRESS} +} + + +\de{EXPLODE}{(\p{U}:\{\ty{atom}\}-\{\ty{vector}\}):\ty{id-list}}{eval, spread} +{Returned is a list of interned characters representing the characters +to print of the value of U. The primitive data types have these +formats: + +\begin{description} +\item[integer] \index{integer ! output} Leading zeroes are suppressed and +a minus sign prefixes the digits if the integer is negative. + +\item[floating] \index{floating ! output} The value appears in the format +[-]0.nn...nnE[-]mm if the magnitude of the number is too large or +small to display in [-]nnnn.nnnn format. The crossover point is +determined by the implementation. + +\item[id] \index{id ! output} The characters of the print name of the +identifier are produced with special characters prefixed with the +escape character. + +\item[string] \index{string ! output} The characters of the string are +produced surrounded by double quotes "\ldots". + +\item[function-pointer] \index{function-pointer ! output} The value of the +function-pointer is created as a list of characters conforming to the +conventions of the system site. +\end{description} + +The type mismatch error occurs if U is not a number, identifier, +string, or function-pointer. } + + +\de{GENSYM}{():\ty{identifier}}{eval, spread} +{Creates an identifier which is not interned on the OBLIST and +consequently not EQ to anything else. \index{OBLIST entry} \index{EQ ! +of GENSYMs}} + + +\de{INTERN}{(\p{U}:\{\ty{id,string}\}):\ty{id}}{eval, spread} +{INTERN searches the OBLIST for an identifier with the same print name +\index{OBLIST entry} +as U and returns the identifier on the OBLIST if a match is found. +Any properties and global values associated with U may be lost. If U +does not match any entry, a new one is created and returned. If U has +more than the maximum number of characters permitted by the +implementation (the minimum number is 24) an error occurs: +\index{id ! minimum size} + +\errormessage{***** Too many characters to INTERN} +} + + +\de{REMOB}{(\p{U}:\ty{id}):\ty{id}}{eval, spread} +{If U is present on the OBLIST it is removed. This does not affect U +\index{OBLIST entry} +having properties, flags, functions and the like. U is returned.} + + +\subsection{Property List Functions} +\label{plist} +\index{property list} +With each id in the system is a ``property list'', a set of entities +which are associated with the id for fast access. These entities are +called ``flags'' if their use gives the id a single valued +\index{flags} +property, and ``properties'' if the id is to have a multivalued +\index{properties} +attribute: an indicator with a property. + +Flags and indicators may clash, consequently care should be taken to +avoid this occurrence. Flagging X with an id which already is an +indicator for X may result in that indicator and associated property +being lost. Likewise, adding an indicator which is the same id as a +flag may result in the flag being destroyed. + + + +\de{FLAG}{(\p{U}:\ty{id-list}, \p{V}:\ty{id}):\ty{NIL}}{eval, spread} +{U is a list of ids which are flagged with V. The effect of FLAG is +that FLAGP will have the value T for those ids of U which were +flagged. Both V and all the elements of U must be identifiers or the +type mismatch error occurs.} + + +\de{FLAGP}{(\p{U}:\ty{any}, \p{V}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U has been previously flagged with V, else NIL. Returns +NIL if either U or V is not an id.} + + +\de{GET}{(\p{U}:\ty{any}, \p{IND}:\ty{any}):\ty{any}}{eval, spread} +{Returns the property associated with indicator IND from the property +list of U. If U does not have indicator IND, NIL is returned. GET +cannot be used to access functions (use GETD instead). +\index{GET ! not for functions}} + + +\de{PUT}{(\p{U}:\ty{id}, \p{IND}:\ty{id}, +\p{PROP}:\ty{any}):\ty{any}}{eval, spread} +{The indicator IND with the property PROP is placed on the property +list of the id U. If the action of PUT occurs, the value of PROP is +returned. If either of U and IND are not ids the type mismatch error +will occur and no property will be placed. PUT cannot be used to +define functions (use PUTD instead). +\index{PUT ! not for functions}} + + +\de{REMFLAG}{(\p{U}:\ty{any-list}, \p{V}:\ty{id}):\ty{NIL}}{eval, spread} +{Removes the flag V from the property list of each member of the list +U. Both V and all the elements of U must be ids or the type mismatch +error will occur.} + + +\de{REMPROP}{(\p{U}:\ty{any}, \p{IND}:\ty{any}):\ty{any}}{eval, spread} +{Removes the property with indicator IND from the property list of U. +Returns the removed property or NIL if there was no such indicator.} + + + +\subsection{Function Definition} +\label{fdef} +Functions in Standard LISP are global entities. To avoid +function-variable naming clashes no variable may have the same name as +a function. \index{function ! as GLOBAL} + + +\de{DE}{(\p{FNAME}:\ty{id}, \p{PARAMS}:\ty{id-list}, +\p{FN}:\ty{any}):\ty{id}}{noeval, nospread} +{The function FN with the formal parameter list PARAMS is added to the +set of defined functions with the name FNAME. Any previous definitions +of the function are lost. The function created is of type +\index{*COMP (fluid)} +EXPR. If the !*COMP variable is non-NIL, the EXPR is first +\index{EXPR} +compiled. The name of the defined function is returned. + +{\tt \begin{tabbing} FEXPR PROCEDURE DE(U); \\ +\hspace*{1em} PUTD(CAR U, 'EXPR, LIST('LAMBDA, CADR U, CADDR U)); +\end{tabbing}}} + + +\de{DF}{(\p{FNAME}:\ty{id}, \p{PARAM}:\ty{id-list}, +\p{FN}:\ty{any}):\ty{id}}{noeval, nospread} +{The function FN with formal parameter PARAM is added to the set of +defined functions with the name FNAME. Any previous definitions of the +function are lost. The function created is of type FEXPR. +\index{*COMP variable} \index{FEXPR} +If the !*COMP variable is T the FEXPR is first compiled. The name of +the defined function is returned. + +{\tt \begin{tabbing} FEXPR PROCEDURE DF(U); \\ +\hspace*{1em} PUTD(CAR U, 'FEXPR, LIST('LAMBDA, CADR U, CADDR U)); \\ +\end{tabbing} }} + + +\de{DM}{(\p{MNAME}:\ty{id}, \p{PARAM}:\ty{id-list}, +\p{FN}:\ty{any}):\ty{id}}{noeval, nospread} +{The macro FN with the formal parameter PARAM is added to the set of +defined functions with the name MNAME. Any previous definitions of the +function are overwritten. The function created is of type MACRO. +\index{MACRO} +The name of the macro is returned. + +{\tt \begin{tabbing} FEXPR PROCEDURE DM(U); \\ +\hspace*{1em} PUTD(CAR U, 'MACRO, LIST('LAMBDA, CADR U, CADDR U)); +\end{tabbing} } +} + + +\de{GETD}{(\p{FNAME}:\ty{any}):\{NIL, \ty{dotted-pair}\}}{eval, spread} +{If FNAME is not the name of a defined function, NIL is returned. If +FNAME is a defined function then the dotted-pair + +\vspace{.15in} +(\p{TYPE}:\ty{ftype} . \p{DEF}:\{\ty{function-pointer, lambda}\}) +\vspace{.15in} + +is returned.} + + +\de{PUTD}{(\p{FNAME}:\ty{id}, \p{TYPE}:\ty{ftype}, +\p{BODY}:\ty{function}):\ty{id}}{eval, spread} +{Creates a function with name FNAME and definition BODY of type TYPE. +If PUTD succeeds the name of the defined function is returned. The +effect of PUTD is that GETD will return a dotted-pair with the +functions type and definition. Likewise the GLOBALP predicate will +\index{GLOBALP} \index{function ! as global} +return T when queried with the function name. + +If the function FNAME has already been declared as a GLOBAL or FLUID +variable the error: + +\errormessage{***** FNAME is a non-local variable} + +occurs and the function will not be defined. If function FNAME already +exists a warning message will appear: + +\errormessage{*** FNAME redefined} + +The function defined by PUTD will be compiled before definition +\index{*COMP (fluid)} if the !*COMP global variable is non-NIL.} + + +\de{REMD}{(\p{FNAME}:\ty{id}):\{NIL, \ty{dotted-pair}\}}{eval, spread} +{Removes the function named FNAME from the set of defined functions. +Returns the (ftype . function) dotted-pair or NIL as does GETD. The +global/function attribute of FNAME is removed and the name may be used +subsequently as a variable.} + + + +\subsection{Variables and Bindings} +\label{varsandbinds} +\index{variable scope} \index{scope} +A variable is a place holder for a Standard LISP entity which is said +to be bound to the variable. The scope of a variable is the range over +which the variable has a defined value. There are three different +binding mechanisms in Standard LISP. + +\begin{description} +\item[Local Binding] \index{local binding} This type of binding occurs +\index{scope ! local} +only in compiled functions. Local variables occur as formal parameters +in lambda expressions and as PROG form variables. The binding occurs +when a lambda expression is evaluated or when a PROG form is executed. +The scope of a local variable is the body of the function in which it +is defined. + +\item[Global Binding] \index{global binding} Only one binding of a +\index{scope ! global} +global variable exists at any time allowing direct access to the value +bound to the variable. The scope of a global variable is universal. +Variables declared GLOBAL may not appear as parameters in lambda +expressions or as PROG form variables. A variable must be declared +GLOBAL prior to its use as a global variable since the default type +for undeclared variables is FLUID. + + +\item[Fluid Binding] \index{fluid binding} +\index{fluid binding ! as default} Fluid variables are global +in scope but may occur as \index{scope ! fluid} formal parameters or +PROG form variables. In interpreted functions all formal parameters +and PROG form variables are considered to have fluid binding until +changed to local binding by compilation. When fluid variables are +used as parameters they are rebound in such a way that the previous +binding may be restored. All references to fluid variables are to the +currently active binding. +\end{description} + + +\de{FLUID}{(\p{IDLIST}:\ty{id-list}):\p{NIL}}{eval, spread} +{The ids in IDLIST are declared as FLUID type variables (ids not +previously declared are initialized to NIL). Variables in IDLIST +already declared FLUID are ignored. Changing a variable's type from +GLOBAL to FLUID is not permissible and results in the error: + +\errormessage{***** ID cannot be changed to FLUID} +} + +\de{FLUIDP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{If U has been declared FLUID (by declaration only) T is returned, +otherwise NIL is returned.} + + +\de{GLOBAL}{(\p{IDLIST}:\ty{id-list}):\p{NIL}}{eval, spread} +{The ids of IDLIST are declared global type variables. If an id has +not been declared previously it is initialized to NIL. Variables +already declared GLOBAL are ignored. Changing a variables type from +FLUID to GLOBAL is not permissible and results in the error: + +\errormessage{***** ID cannot be changed to GLOBAL} +} + + +\de{GLOBALP}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{If U has been declared GLOBAL or is the name of a defined function, T +is returned, else NIL is returned.} + + +\de{SET}{(\p{EXP}:\ty{id}, \p{VALUE}:\ty{any}):\ty{any}}{eval, spread} +{EXP must be an identifier or a type mismatch error occurs. The effect +of SET is replacement of the item bound to the identifier by VALUE. +If the identifier is not a local variable or has not been declared +GLOBAL it is automatically declared FLUID with the resulting warning +message: + +\errormessage{*** EXP declared FLUID} + +EXP must not evaluate to T or NIL or an error occurs: +\index{T ! cannot be changed} \index{NIL ! cannot be changed} + +\errormessage{***** Cannot change T or NIL} +} + +\de{SETQ}{(\p{VARIABLE}:\ty{id}, \p{VALUE}:\ty{any}):\ty{any}}{noeval, +nospread} +{If VARIABLE is not local or GLOBAL it is by default declared FLUID +and the warning message: + +\errormessage{*** VARIABLE declared FLUID} + +appears. The value of the current binding of VARIABLE is replaced by +the value of VALUE. VARIABLE must not be T or NIL or an error occurs: +\index{T ! cannot be changed} \index{NIL ! cannot be changed} + +\errormessage{***** Cannot change T or NIL} + +{\tt \begin{tabbing} MACRO PROCEDURE SETQ(X); \\ +\hspace*{1em} LIST('SET, LIST('QUOTE, CADR X), CADDR X); +\end{tabbing}} +} + +\de{UNFLUID}{(\p{IDLIST}:\ty{id-list}):\ty{NIL}}{eval, spread} +{The variables in IDLIST that have been declared as FLUID variables +are no longer considered as fluid variables. Others are ignored. This +affects only compiled functions as free variables in interpreted +functions are automatically considered fluid~\cite{PLC}. +\index{scope ! fluid and compiled}} + + +\subsection{Program Feature Functions} +\label{prog} +These functions provide for explicit control sequencing, and the +definition of blocks altering the scope of local variables. + + +\de{GO}{(\p{LABEL}:\ty{id})}{noeval, nospread} +{GO alters the normal flow of control within a PROG function. The next +statement of a PROG function to be evaluated is immediately preceded +by LABEL. A GO may only appear in the following situations: + + +\begin{enumerate} +\item At the top level of a PROG referencing a label which also +appears at the top level of the same PROG. + +\item As the consequent of a COND item of a COND appearing on the top +level of a PROG. +\index{GO ! in COND} +\index{RETURN ! in COND} +\item As the consequent of a COND item which appears as the +consequent of a COND item to any level. + +\item As the last statement of a PROGN which appears at the top level +of a PROG or in a PROGN appearing in the consequent of a COND to any +level subject to the restrictions of 2 and 3. + +\item As the last statement of a PROGN within a PROGN or as the +consequent of a COND in a PROGN to any level subject to the +restrictions of 2, 3 and 4. +\end{enumerate} + +If LABEL does not appear at the top level of the PROG in which the GO +appears, an error occurs: + +\errormessage{***** LABEL is not a known label} + +If the GO has been placed in a position not defined by rules 1-5, +another error is detected: + +\errormessage{***** Illegal use of GO to LABEL} +} + +\de{PROG}{(\p{VARS}:\ty{id-list}, +[\p{PROGRAM}:\{\ty{id, any}\}]):\ty{any}}{noeval, nospread} +{VARS is a list of ids which are considered fluid when the PROG is +interpreted and local when compiled (see ``Variables and Bindings'', +section~\ref{varsandbinds} on page~\pageref{varsandbinds}). The PROGs +variables are allocated space when the PROG form is invoked and are +deallocated when the PROG is exited. PROG variables are initialized to +\index{PROG ! variables} +NIL. The PROGRAM is a set of expressions to be evaluated in order of +their appearance in the PROG function. Identifiers appearing in the +top level of the PROGRAM are labels which can be referenced by GO. The +value returned by the PROG function is determined by a RETURN function +\index{PROG ! default value} +or NIL if the PROG ``falls through''.} + + +\de{PROGN}{([\p{U}:\ty{any}]):\ty{any}}{noeval, nospread} +{U is a set of expressions which are executed sequentially. The value +returned is the value of the last expression.} + + +\de{PROG2}{(A:any, B:any)\ty{any}}{eval, spread} +{Returns the value of B. + +{\tt \begin{tabbing} EXPR PROCEDURE PROG2(A, B);\\ +\hspace*{1em} B; +\end{tabbing}}} + + +\de{RETURN}{(\p{U}:\ty{any})}{eval, spread} +{Within a PROG, RETURN terminates the evaluation of a PROG and returns +U as the value of the PROG. The restrictions on the placement of +RETURN are exactly those of GO. Improper placement of RETURN results +in the error: + +\errormessage{***** Illegal use of RETURN} +} + + +\subsection{Error Handling} +\label{errors} + +\de{ERROR}{(\p{NUMBER}:\ty{integer}, \p{MESSAGE}:\ty{any})}{eval, spread} +{NUMBER and MESSAGE are passed back to a surrounding ERRORSET (the +Standard LISP reader has an ERRORSET). MESSAGE is placed in the +\index{EMSG* (global)} +global variable EMSG!* and the error number becomes the value of the +surrounding ERRORSET. FLUID variables and local bindings are unbound +\index{fluid ! unbinding by ERROR} +to return to the environment of the ERRORSET. Global variables are not +affected by the process.} + + +\de{ERRORSET}{(\p{U}:\ty{any}, \p{MSGP}:\ty{boolean}, +\p{TR}:\ty{boolean}):\ty{any}}{eval, spread} +{If an error occurs during the evaluation of U, the value of NUMBER +from the ERROR call is returned as the value of ERRORSET. In addition, +if the value of MSGP is non-NIL, the MESSAGE from the ERROR call is +displayed upon both the standard output device and the currently +selected output device unless the standard output device is not open. +The message appears prefixed with 5 asterisks. The MESSAGE +\index{***** (error message)} +list is displayed without top level parentheses. The MESSAGE from the +\index{EMSG* (global)} +ERROR call will be available in the global variable EMSG!*. The exact +format of error messages generated by Standard LISP functions +described in this document are not fixed and should not be relied upon +to be in any particular form. Likewise, error numbers generated by +Standard LISP functions are implementation dependent. + +If no error occurs during the evaluation of U, the value of (LIST +(EVAL U)) is returned. + +If an error has been signaled and the value of TR is non-NIL a +traceback sequence will be initiated on the selected output device. +The traceback will display information such as unbindings of FLUID +\index{fluid ! in traceback} +variables, argument lists and so on in an implementation dependent +format.} + + +\subsection{Vectors} +\label{vectors} +\index{vector} +Vectors are structured entities in which random elements may be +accessed with an integer index. A vector has a single dimension. Its +maximum size is determined by the implementation and available space. +A suggested input ``vector notation'' is defined in ``Classes of +Primitive Data Types'', section~\ref{pclasses} on +page~\pageref{pclasses} and output with EXPLODE, ``Identifiers'' +section~\ref{identifiers} on page~\pageref{identifiers}. +\index{EXPLODE} + + +\de{GETV}{(\p{V}:\ty{vector}, \p{INDEX}:\ty{integer}):\ty{any}}{eval, spread} +{Returns the value stored at position INDEX of the vector V. The type +mismatch error may occur. An error occurs if the INDEX does not lie +within 0\ldots UPBV(V) inclusive: + +\errormessage{***** INDEX subscript is out of range} +} + + +\de{MKVECT}{(\p{UPLIM}:\ty{integer}):\ty{vector}}{eval, spread} +{Defines and allocates space for a vector with UPLIM+1 elements +accessed as 0\ldots UPLIM. Each element is initialized to NIL. An +error will occur if UPLIM is $<$ 0 or there is not enough space for a +vector of this size: + +\errormessage{***** A vector of size UPLIM cannot be allocated} +} + + +\de{PUTV}{(\p{V}:\ty{vector}, \p{INDEX}:\ty{integer}, +\p{VALUE}:\ty{any}):\ty{any}}{eval, spread} +{Stores VALUE into the vector V at position INDEX. VALUE is returned. +The type mismatch error may occur. If INDEX does not lie in 0\ldots +UPBV(V) an error occurs: + +\errormessage{***** INDEX subscript is out of range} +} + + +\de{UPBV}{(\p{U}:\ty{any}):{NIL,\ty{integer}}}{eval, spread} +{Returns the upper limit of U if U is a vector, or NIL if it is not.} + + +\subsection{Boolean Functions and Conditionals} + + +\de{AND}{([\p{U}:\ty{any}]):\ty{extra-boolean}}{noeval, nospread} +{AND evaluates each U until a value of NIL is found or the end of the +list is encountered. If a non-NIL value is the last value it is +returned, or NIL is returned. + +{\tt \begin{tabbing} FEXPR PROCEDURE AND(U); \\ BEGIN \\ +\hspace*{1em} IF NULL U THEN RETURN NIL; \\ +LOOP: IF \= NULL CDR U THEN RETURN EVAL CAR U \\ +\> ELSE IF NULL EVAL CAR U THEN RETURN NIL; \\ +\hspace*{2em} \= U := CDR U; \\ +\> GO LOOP \\ +END; +\end{tabbing} }} + + +\de{COND}{([\p{U}:\ty{cond-form}]):\ty{any}}{noeval, nospread} +{The antecedents of all U's are evaluated in order of their appearance +until a non-NIL value is encountered. The consequent of the selected U +is evaluated and becomes the value of the COND. The consequent may +also contain the special functions GO and RETURN subject to the +restraints given for these functions in ``Program Feature Functions'', +section~\ref{prog} on page~\pageref{prog}. +\index{GO ! in COND} \index{RETUNR ! in CODE} In these cases COND does +not have a defined value, but rather an effect. If no antecedent is +non-NIL the value of COND is NIL. An error is detected if a U is +improperly formed: + +\errormessage{***** Improper cond-form as argument of COND} +} + + +\de{NOT}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{If U is NIL, return T else return NIL (same as function NULL). + +{\tt \begin{tabbing} EXPR PROCEDURE NOT(U); \\ +\hspace*{1em} U EQ NIL; +\end{tabbing}} +} + + +\de{OR}{([\p{U}:\ty{any}]):\ty{extra-boolean}}{noeval, nospread} +{U is any number of expressions which are evaluated in order of their +appearance. When one is found to be non-NIL it is returned as the +value of OR. If all are NIL, NIL is returned. + +{\tt \begin{tabbing} FEXPR PROCEDURE OR(U); \\ BEGIN SCALAR X; \\ +LOOP: IF \= NULL U THEN RETURN NIL \\ +\> ELSE IF (X := EVAL CAR U) THEN RETURN X; \\ +\hspace*{2em} \= U := CDR U; \\ +\> GO LOOP \\ +END; +\end{tabbing} }} + + +\subsection{Arithmetic Functions} + +Conversions between numeric types are provided explicitly by the +\index{FIX} \index{FLOAT} +FIX and FLOAT functions and implicitly by any multi-parameter +\index{mixed-mode arithmetic} +arithmetic function which receives mixed types of arguments. A +conversion from fixed to floating point numbers may result in a loss +of precision without a warning message being generated. Since +\index{integer ! magnitude} +integers may have a greater magnitude that that permitted for floating +numbers, an error may be signaled when the attempted conversion cannot +be done. Because the magnitude of integers is unlimited the conversion +of a floating point number to a fixed number is always possible, the +only loss of precision being the digits to the right of the decimal +point which are truncated. If a function receives mixed types of +arguments the general rule will have the fixed numbers converted to +floating before arithmetic operations are performed. In all cases an +error occurs if the parameter to an arithmetic function is not a +number: + +\errormessage{***** XXX parameter to FUNCTION is not a number} + +XXX is the value of the parameter at fault and FUNCTION is the name of +the function that detected the error. Exceptions to the rule are noted +where they occur. + + + + +\de{ABS}{(\p{U}:\ty{number}):\ty{number}}{eval, spread} +{Returns the absolute value of its argument. + +{\tt \begin{tabbing} EXPR PROCEDURE ABS(U); \\ +\hspace*{1em} IF LESSP(U, 0) THEN MINUS(U) ELSE U; +\end{tabbing}}} + +\de{ADD1}{(\p{U}:\ty{number}):\ty{number}}{eval, spread} +{Returns the value of U plus 1 of the same type as U (fixed or +floating). + +{\tt \begin{tabbing} EXPR PROCEDURE ADD1(U); \\ +% God knows why, but hspace* isn't accepted here. +\hspace{1em} PLUS2(U, 1); +\end{tabbing}} +} + +\de{DIFFERENCE}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, +spread} +{The value U - V is returned.} + + +\de{DIVIDE}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{dotted-pair}}{eval, +spread} +{The dotted-pair (quotient . remainder) is returned. The quotient part +is computed the same as by QUOTIENT and the remainder the same as by +REMAINDER. An error occurs if division by zero is attempted: +\index{division by zero} + +\errormessage{***** Attempt to divide by 0 in DIVIDE} + +{\tt \begin{tabbing} EXPR PROCEDURE DIVIDE(U, V); \\ +\hspace*{1em} (QUOTIENT(U, V) . REMAINDER(U, V)); +\end{tabbing}}} + + +\de{EXPT}{(\p{U}:\ty{number}, \p{V}:\ty{integer}):\ty{number}}{eval, spread} +{Returns U raised to the V power. A floating point U to an integer +power V does \underline{not} have V changed to a floating number +before exponentiation.} + + +\de{FIX}{(\p{U}:\ty{number}):\ty{integer}}{eval, spread} +{Returns an integer which corresponds to the truncated value of U. The +result of conversion must retain all significant portions of U. If U +is an integer it is returned unchanged. } + + +\de{FLOAT}{(\p{U}:\ty{number}):\ty{floating}}{eval, spread} +{The floating point number corresponding to the value of the argument +U is returned. Some of the least significant digits of an integer may +be lost do to the implementation of floating point numbers. FLOAT of a +floating point number returns the number unchanged. If U is too large +to represent in floating point an error occurs: + +\errormessage{***** Argument to FLOAT is too large} +} + +\de{GREATERP}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{boolean}}{eval, +spread} +{Returns T if U is strictly greater than V, otherwise returns NIL.} + + +\de{LESSP}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{boolean}}{eval, spread} +{Returns T if U is strictly less than V, otherwise returns NIL. } + + +\de{MAX}{([\p{U}:\ty{number}]):\ty{number}}{noeval, nospread, or macro} +{Returns the largest of the values in U. If two or more values are the +same the first is returned. + +{\tt \begin{tabbing} MACRO PROCEDURE MAX(U); \\ +\hspace*{1em} EXPAND(CDR U, 'MAX2); +\end{tabbing}}} + + +\de{MAX2}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} +{Returns the larger of U and V. If U and V are the same value U is +returned (U and V might be of different types). + +{\tt \begin{tabbing} EXPR PROCEDURE MAX2(U, V); \\ +\hspace*{1em} IF LESSP(U, V) THEN V ELSE U; +\end{tabbing}}} + + +\de{MIN}{([\p{U}:\ty{number}]):\ty{number}}{noeval, nospread, or macro} +{Returns the smallest of the values in U. If two or more values are +the same the first of these is returned. + +{\tt \begin{tabbing} MACRO PROCEDURE MIN(U); \\ +\hspace*{1em} EXPAND(CDR U, 'MIN2); +\end{tabbing}}} + + +\de{MIN2}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} +{Returns the smaller of its arguments. If U and V are the same value, +U is returned (U and V might be of different types). + +{\tt \begin{tabbing} EXPR PROCEDURE MIN2(U, V); \\ +\hspace*{1em} IF GREATERP(U, V) THEN V ELSE U; +\end{tabbing}}} + + +\de{MINUS}{(\p{U}:\ty{number}):\ty{number}}{eval, spread} +{Returns -U. + +{\tt \begin{tabbing} EXPR PROCEDURE MINUS(U); \\ +\hspace*{1em} DIFFERENCE(0, U); +\end{tabbing}}} + + +\de{PLUS}{([\p{U}:\ty{number}]):\ty{number}}{noeval, nospread, or macro} +{Forms the sum of all its arguments. + +{\tt \begin{tabbing} MACRO PROCEDURE PLUS(U); \\ +\hspace*{1em} EXPAND(CDR U, 'PLUS2); +\end{tabbing}}} + +\de{PLUS2}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} +{Returns the sum of U and V.} + + +\de{QUOTIENT}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} +{The quotient of U divided by V is returned. Division of two positive +or two negative integers is conventional. When both U and V are +integers and exactly one of them is negative the value returned is the +negative truncation of the absolute value of U divided by the absolute +value of V. An error occurs if division by zero is attempted: +\index{division by zero} + +\errormessage{***** Attempt to divide by 0 in QUOTIENT} +} + +\de{REMAINDER}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, +spread} +{If both U and V are integers the result is the integer remainder of U +divided by V. If either parameter is floating point, the result is the +difference between U and V*(U/V) all in floating point. If either +number is negative the remainder is negative. If both are positive or +both are negative the remainder is positive. An error occurs if V is +zero: \index{division by zero} + +\errormessage{***** Attempt to divide by 0 in REMAINDER} + +{\tt \begin{tabbing} EXPR PROCEDURE REMAINDER(U, V); \\ +\hspace*{1em} DIFFERENCE(U, TIMES2(QUOTIENT(U, V), V)); +\end{tabbing}}} + + +\de{SUB1}{(\p{U}:\ty{number}):\ty{number}}{eval, spread} +{Returns the value of U less 1. If U is a FLOAT type number, the +value returned is U less 1.0. + +{\tt \begin{tabbing} EXPR PROCEDURE SUB1(U); \\ +\hspace*{1em} DIFFERENCE(U, 1); +\end{tabbing}}} + + +\de{TIMES}{([\p{U}:\ty{number}]):\ty{number}}{noeval, nospread, or macro} +{Returns the product of all its arguments. + +{\tt \begin{tabbing} MACRO PROCEDURE TIMES(U); \\ +\hspace*{1em} EXPAND(CDR U, 'TIMES2); +\end{tabbing}}} + + +\de{TIMES2}{(\p{U}:\ty{number}, \p{V}:\ty{number}):\ty{number}}{eval, spread} +{Returns the product of U and V.} + + +\subsection{MAP Composite Functions} + + +\de{MAP}{(\p{X}:\ty{list}, F\p{N}:\ty{function}):\ty{any}}{eval, spread} +{Applies FN to successive CDR segments of X. NIL is returned. + +{\tt \begin{tabbing} EXPR PROCEDURE MAP(X, FN); \\ +\hspace*{1em} WHILE X DO $<<$ FN X; X := CDR X $>>$; +\end{tabbing}}} + + +\de{MAPC}{(X:list, FN:function):\ty{any}}{eval, spread} +{FN is applied to successive CAR segments of list X. NIL is returned. + +{\tt \begin{tabbing} EXPR PROCEDURE MAPC(X, FN); \\ +\hspace*{1em} WHILE X DO $<<$ FN CAR X; X := CDR X $>>$; +\end{tabbing}}} + + +\de{MAPCAN}{(X:list, FN:function):\ty{any}}{eval, spread} +{A concatenated list of FN applied to successive CAR elements of X is +returned. + +{\tt \begin{tabbing} EXPR PROCEDURE MAPCAN(X, FN); \\ +\hspace*{1em} IF\= NULL X THEN NIL \\ +\> ELSE NCONC(FN CAR X, MAPCAN(CDR X, FN)); +\end{tabbing}}} + + +\de{MAPCAR}{(X:list, FN:function):\ty{any}}{eval, spread} +{Returned is a constructed list of FN applied to each CAR of list X. + +{\tt \begin{tabbing} EXPR PROCEDURE MAPCAR(X, FN); \\ +\hspace*{1em} IF\= NULL X THEN NIL \\ +\> ELSE FN CAR X . MAPCAR(CDR X, FN); +\end{tabbing}}} + + +\de{MAPCON}{(X:list, FN:function):\ty{any}}{eval, spread} +{Returned is a concatenated list of FN applied to successive CDR +segments of X. + +{\tt \begin{tabbing} EXPR PROCEDURE MAPCON(X, FN); \\ +\hspace*{1em} IF\= NULL X THEN NIL \\ +\> ELSE NCONC(FN X, MAPCON(CDR X, FN)); +\end{tabbing}}} + + +\de{MAPLIST}{(X:list, FN:function):\ty{any}}{eval, spread} +{Returns a constructed list of FN applied to successive CDR segments +of X. + +{\tt \begin{tabbing} EXPR PROCEDURE MAPLIST(X, FN); \\ +\hspace*{1em} IF\= NULL X THEN NIL \\ +\> ELSE FN X . MAPLIST(CDR X, FN); +\end{tabbing}}} + + +\subsection{Composite Functions} + +\de{APPEND}{(\p{U}:\ty{list}, \p{V}:\ty{list}):\ty{list}}{eval, spread} +{Returns a constructed list in which the last element of U is followed +by the first element of V. The list U is copied, V is not. + +{\tt \begin{tabbing} EXPR PROCEDURE APPEND(U, V); \\ +\hspace*{1em} IF\= NULL U THEN V \\ +\> ELSE CAR U . APPEND(CDR U, V); +\end{tabbing}}} + +\de{ASSOC}{(\p{U}:\ty{any}, \p{V}:\ty{alist}):\{\ty{dotted-pair}, +NIL\}}{eval, spread} +{If U occurs as the CAR portion of an element of the alist V, the +dotted-pair in which U occurred is returned, else NIL is returned. +ASSOC might not detect a poorly formed alist so an invalid +\index{EQUAL ! in ASSOC} \index{alist ! in ASSOC} +construction may be detected by CAR or CDR. + +{\tt \begin{tabbing} EXPR PROCEDURE ASSOC(U, V); \\ +\hspace*{1em} IF \= NULL V THEN NIL \\ +\> ELSE \= IF ATOM CAR V THEN \\ +\> \> ERROR(000, LIST(V, "is a poorly formed alist")) \\ +\> ELSE IF U = CAAR V THEN CAR V \\ +\> ELSE ASSOC(U, CDR V); +\end{tabbing}} +} + +\de{DEFLIST}{(\p{U}:\ty{dlist}, \p{IND}:\ty{id}):\ty{list}}{eval, spread} +{A "dlist" is a list in which each element is a two element list: +\index{dlist} +(ID:id PROP:any). Each ID in U has the indicator IND with property +PROP placed on its property list by the PUT function. The value of +DEFLIST is a list of the first elements of each two element list. +Like PUT, DEFLIST may not be used to define functions. + +{\tt \begin{tabbing} EXPR PROCEDURE DEFLIST(U, IND); \\ +\hspace*{1em} IF NULL U THEN NIL \\ +\hspace*{2em} ELSE $<<$ \= PUT(CAAR U, IND, CADAR U); \\ +\> CAAR U $>>$ . DEFLIST(CDR U, IND); +\end{tabbing}} +} + +\de{DELETE}{(\p{U}:\ty{any}, \p{V}:\ty{list}):\ty{list}}{eval, spread} +{Returns V with the first top level occurrence of U removed from it. +\index{EQUAL ! in DELETE} + +{\tt \begin{tabbing} EXPR PROCEDURE DELETE(U, V); \\ +\hspace*{1em} IF NULL V THEN NIL \\ +\hspace*{2em} ELSE IF CAR V = U THEN CDR V \\ +\hspace*{2em} ELSE CAR V . DELETE(U, CDR V); +\end{tabbing}}} + +\de{DIGIT}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a digit, otherwise NIL. + +{\tt \begin{tabbing} EXPR PROCEDURE DIGIT(U); \\ +\hspace*{1em} IF MEMQ(U, '(!0 !1 !2 !3 !4 !5 !6 !7 !8 !9)) \\ +\hspace*{2em} THEN T ELSE NIL; +\end{tabbing}}} + +\de{LENGTH}{(\p{X}:\ty{any}):\ty{integer}}{eval, spread} +{The top level length of the list X is returned. + +{\tt \begin{tabbing} EXPR PROCEDURE LENGTH(X); \\ +\hspace*{1em} IF ATOM X THEN 0 \\ +\hspace*{2em} ELSE PLUS(1, LENGTH CDR X); +\end{tabbing}}} + +\de{LITER}{(\p{U}:\ty{any}):\ty{boolean}}{eval, spread} +{Returns T if U is a character of the alphabet, NIL +otherwise.\footnote{The published report omits escape characters. +These are required for both upper and lower case as some systems +default to lower.} + +{\tt \begin{tabbing} EXPR PROCEDURE LITER(U); \\ +\hspace*{1em} IF \= MEMQ(U, '(\=!A !B !C !D !E !F !G !H !I !J !K !L !M \\ +\> \> !N !O !P !Q !R !S !T !U !V !W !X !Y !Z \\ +\> \> !a !b !c !d !e !f !g !h !i !j !k !l !m \\ +\> \> !n !o !p !q !r !s !t !u !v !w !x !y !z)) \\ +\> THEN T ELSE NIL; +\end{tabbing}}} + +\de{MEMBER}{(\p{A}:\ty{any}, \p{B}:\ty{list}):\ty{extra-boolean}}{eval, spread} +{Returns NIL if A is not a member of list B, returns the remainder of +B whose first element is A. \index{EQUAL ! in MEMBER} + +{\tt \begin{tabbing} EXPR PROCEDURE MEMBER(A, B); \\ +\hspace*{1em} IF NULL B THEN NIL \\ +\hspace*{2em} ELSE IF A = CAR B THEN B \\ +\hspace*{2em} ELSE MEMBER(A, CDR B); +\end{tabbing}}} + + +\de{MEMQ}{(\p{A}:\ty{any}, \p{B}:\ty{list}):\ty{extra-boolean}}{eval, spread} +{Same as MEMBER but an EQ check is used for comparison. \index{EQ ! in +MEMQ} + +{\tt \begin{tabbing} EXPR PROCEDURE MEMQ(A, B); \\ +\hspace*{1em} IF \= NULL B THEN NIL \\ +\> ELSE IF A EQ CAR B THEN B \\ +\> ELSE MEMQ(A, CDR B); +\end{tabbing}}} + +\de{NCONC}{(\p{U}:\ty{list}, \p{V}:\ty{list}):\ty{list}}{eval, spread} +{Concatenates V to U without copying U. The last CDR of U is modified +to point to V. + +{\tt \begin{tabbing} EXPR PROCEDURE NCONC(U, V); \\ BEGIN SCALAR W; \\ +\hspace*{2em} \= IF NULL U THEN RETURN V; \\ +\> W := U; \\ +\> WHILE CDR W DO W := CDR W; \\ +\> RPLACD(W, V); \\ +\> RETURN U \\ +END; +\end{tabbing}}} + +\de{PAIR}{(\p{U}:\ty{list}, \p{V}:\ty{list}):\ty{alist}}{eval, spread} +{U and V are lists which must have an identical number of elements. If +not, an error occurs (the 000 used in the ERROR call is arbitrary and +need not be adhered to). Returned is a list where each element is a +dotted-pair, the CAR of the pair being from U, and the CDR the +corresponding element from V. + +{\tt \begin{tabbing} EXPR PROCEDURE PAIR(U, V); \\ +\hspace*{1em} IF AND(U, V) THEN (CAR U . CAR V) . PAIR(CDR U, CDR V) \\ +\hspace*{2em} \= ELSE IF OR(U, V) THEN ERROR(000, \\ +\hspace*{4em} "Different length lists in PAIR") \\ +\> ELSE NIL; +\end{tabbing}}} + + +\de{REVERSE}{(\p{U}:\ty{list}):\ty{list}}{eval, spread} +{Returns a copy of the top level of U in reverse order. + +{\tt \begin{tabbing} EXPR PROCEDURE REVERSE(U); \\ BEGIN SCALAR W; \\ +\hspace*{2em} \= WHILE U DO $<<$ \= W := CAR U . W; \\ +\> \> U := CDR U $>>$; \\ +\> RETURN W \\ +END; +\end{tabbing}}} + +\de{SASSOC}{(\p{U}:\ty{any}, \p{V}:\ty{alist}, +\p{FN}:\ty{function}):\ty{any}}{eval, spread} +{Searches the alist V for an occurrence of U. If U is not in the alist +the evaluation of function FN is returned. \index{EQUAL ! in SASSOC} +\index{alist ! in SASSOC} + +{\tt \begin{tabbing} EXPR PROCEDURE SASSOC(U, V, FN); \\ +\hspace*{1em} IF NULL V THEN FN() \\ +\hspace*{2em} \= ELSE IF U = CAAR V THEN CAR V \\ +\> ELSE SASSOC(U, CDR V, FN); +\end{tabbing}}} + +\de{SUBLIS}{(\p{X}:\ty{alist}, \p{Y}:\ty{any}):\ty{any}}{eval, spread} +{The value returned is the result of substituting the CDR of each +element of the alist X for every occurrence of the CAR part of that +element in Y. \index{alist ! in SUBLIS} + +{\tt \begin{tabbing} EXPR PROCEDURE SUBLIS(X, Y); \\ +\hspace*{1em}IF NULL X THEN Y \\ +\hspace*{2em} ELSE BEGIN \= SCALAR U; \\ +\> U := ASSOC(Y, X); \\ +\> RETURN \= IF U THEN CDR U \\ +\> \> ELSE IF ATOM Y THEN Y \\ +\> \> ELSE \= SUBLIS(X, CAR Y) . \\ +\> \> \> SUBLIS(X, CDR Y) \\ +\> END; +\end{tabbing}}} + +\de{SUBST}{(\p{U}:\ty{any}, \p{V}:\ty{any}, \p{W}:\ty{any}):\ty{any}}{eval, +spread} +{The value returned is the result of substituting U for all +occurrences of V in W. \index{EQUAL ! in SUBST} + +{\tt \begin{tabbing} EXPR PROCEDURE SUBST(U, V, W); \\ +\hspace*{1em} IF NULL W THEN NIL \\ +\hspace*{2em} \= ELSE IF V = W THEN U \\ +\> ELSE IF ATOM W THEN W \\ +\> ELSE SUBST(U, V, CAR W) . SUBST(U, V, CDR W); +\end{tabbing}}} + + +\subsection{The Interpreter} +\label{interpreter} +\de{APPLY}{(\p{FN}:\{\ty{id,function}\}, +\p{ARGS}:\ty{any-list}):\ty{any}}{eval, spread} +{APPLY returns the value of FN with actual parameters ARGS. The actual +parameters in ARGS are already in the form required for binding to the +formal parameters of FN. Implementation specific portions described in +English are enclosed in boxes. + +{\tt \begin{tabbing} EXPR PROCEDURE APPLY(FN, ARGS); \\ BEGIN SCALAR +DEFN; \\ +\hspace*{2em}\= IF CODEP FN THEN RETURN \\ +\> \hspace{1em} \framebox[3.25in]{\parbox{3.25in}{Spread the actual +parameters in ARGS +following the conventions: for calling functions, transfer to the +entry point of the function, and return the value returned by the +function.}}; \\ +\> IF \= IDP FN THEN RETURN \\ +\> \> IF \= NULL(DEFN := GETD FN) THEN \\ +\> \> \> ERROR(000, LIST(FN, "is an undefined function")) \\ +\> \> ELSE IF CAR DEFN EQ 'EXPR THEN \\ +\> \> \> APPLY(CDR DEFN, ARGS) \\ +\> \> ELSE ERROR(000, \\ +\> \> \> LIST(FN, "cannot be evaluated by APPLY")); \\ +\> IF OR(ATOM FN, NOT(CAR FN EQ 'LAMBDA)) THEN \\ +\> \> ERROR(000, \\ +\> \> LIST(FN, "cannot be evaluated by APPLY")); \\ +\> RETURN \\ +\> \> \framebox[3.25in]{\parbox{3.25in}{Bind the actual parameters in ARGS to +the formal +parameters of the lambda expression. If the two lists are not of equal +length then ERROR(000, "Number of parameters do not match"); The value +returned is EVAL CADDR FN.}} \\ END; +\end{tabbing}}} + +\de{EVAL}{(\p{U}:\ty{any}):\ty{any}}{eval, spread} +{The value of the expression U is computed. Error numbers are +arbitrary. Portions of EVAL involving machine specific coding are +expressed in English enclosed in boxes. + +{\tt \begin{tabbing} EXPR PROCEDURE EVAL(U); \\ BEGIN SCALAR FN; \\ +\hspace*{2em} \= IF CONSTANTP U THEN RETURN U; \\ +\> IF IDP U THEN RETURN \\ +\> \hspace{1em} \framebox[3.25in]{\parbox{3.25in}{U is an id. Return the +value most currently +bound to U or if there is no such binding: ERROR(000, LIST("Unbound:", +U));}} \\ +\> IF \= PAIRP CAR U THEN RETURN \\ +\> \> IF CAAR U EQ 'LAMBDA THEN APPLY(CAR U, EVLIS CDR U) \\ +\> \> ELSE ERROR(\= 000, LIST(CAR U, \\ +\> \> \> "improperly formed LAMBDA expression")) \\ +\> \> ELSE IF CODEP CAR U THEN \\ +\> \> \> RETURN APPLY(CAR U, EVLIS CDR U); \\ +\> FN := GETD CAR U; \\ +\> IF NULL FN THEN \\ +\> \> ERROR(000, LIST(CAR U, "is an undefined function")) \\ +\> ELSE IF CAR FN EQ 'EXPR THEN \\ +\> \> RETURN APPLY(CDR FN, EVLIS CDR U) \\ +\> ELSE IF CAR FN EQ 'FEXPR THEN \\ +\> \> RETURN APPLY(CDR FN, LIST CDR U) \\ +\> ELSE IF CAR FN EQ 'MACRO THEN \\ +\> \> RETURN EVAL APPLY(CDR FN, LIST U) \\ +END; +\end{tabbing}}} + +\de{EVLIS}{(\p{U}:\ty{any-list}):\ty{any-list}}{eval, spread} +{EVLIS returns a list of the evaluation of each element of U. + +{\tt \begin{tabbing} EXPR PROCEDURE EVLIS(U); \\ +\hspace*{1em} IF NULL U THEN NIL \\ +\hspace*{2em} ELSE EVAL CAR U . EVLIS CDR U; +\end{tabbing}}} + +\de{EXPAND}{(\p{L}:\ty{list}, \p{FN}:\ty{function}):\ty{list}}{eval, spread} +{FN is a defined function of two arguments to be used in the expansion +of a MACRO. EXPAND returns a list in the form: + +\vspace{.15in} +(FN L$_0$ (FN L$_1$ \ldots (FN L$_{n-1}$ L$_n$) \ldots )) +\vspace{.15in} + +where $n$ is the number of elements in L, L$_i$ is the $i$th element +of L. + +{\tt \begin{tabbing} EXPR PROCEDURE EXPAND(L,FN); \\ +\hspace*{1em} IF NULL CDR L THEN CAR L \\ +\hspace*{2em} ELSE LIST(FN, CAR L, EXPAND(CDR L, FN)); +\end{tabbing}}} + +\de{FUNCTION}{(\p{FN}:\ty{function}):\ty{function}}{noeval, nospread} +{The function FN is to be passed to another function. If FN is to have +side effects its free variables must be fluid or global. FUNCTION is +like QUOTE but its argument may be affected by compilation. We do not +\index{FUNARGs not supported} +consider FUNARGs in this report.} + + +\de{QUOTE}{(U:any):\ty{any}}{noeval, nospread} +{Stops evaluation and returns U unevaluated. + +{\tt \begin{tabbing} FEXPR PROCEDURE QUOTE(U); \\ +\hspace*{2em}CAR U; +\end{tabbing}}} + +\subsection{Input and Output} +\label{IO} +The user normally communicates with Standard LISP through +\index{standard devices} +``standard devices''. The default devices are selected in accordance +with the conventions of the implementation site. Other input and +output devices or files may be selected for reading and writing using +the functions described herein. + + + +\de{CLOSE}{(\p{FILEHANDLE}:\ty{any}):\ty{any}}{eval, spread} +{Closes the file with the internal name FILEHANDLE writing any +necessary end of file marks and such. The value of FILEHANDLE is that +returned by the corresponding OPEN. \index{OPEN} The value returned is +the value of FILEHANDLE. An error occurs if the file can not be +\index{file handle} \index{files} +closed. + +\errormessage{ ***** FILEHANDLE could not be closed} +} + +\de{EJECT}{():NIL}{eval, spread} +{Skip to the top of the next output page. Automatic EJECTs are +executed by the print functions when the length set by the PAGELENGTH +\index{PAGELENGTH} function is exceeded.} + + +\de{LINELENGTH}{(\p{LEN}:\{\ty{integer}, NIL\}):\ty{integer}}{eval, spread} +{If LEN is an integer the maximum line length to be printed before the +print functions initiate an automatic TERPRI is set to the value LEN. +\index{TERPRI} +No initial Standard LISP line length is assumed. The previous line +length is returned except when LEN is NIL. This special case returns +the current line length and does not cause it to be reset. An error +occurs if the requested line length is too large for the currently +selected output file or LEN is negative or zero. + +\errormessage{ ***** LEN is an invalid line length} +} + + +\de{LPOSN}{():\ty{integer}}{eval, spread} +{Returns the number of lines printed on the current page. At the top +of a page, 0 is returned. } + + +\de{OPEN}{(\p{FILE}:\ty{any}, \p{HOW}:\ty{id}):\ty{any}}{eval, spread} +{Open the file with the system dependent name FILE for output if HOW +is EQ to OUTPUT, or input if HOW is EQ to INPUT. If the file is +\index{file handle} \index{files} \index{OUTPUT} \index{INPUT} +opened successfully, a value which is internally associated with the +file is returned. This value must be saved for use by RDS and WRS. An +error occurs if HOW is something other than INPUT or OUTPUT or the +file can't be opened. + +\errormessage{***** HOW is not option for OPEN} +\errormessage{***** FILE could not be opened} +} + + +\de{PAGELENGTH}{(\p{LEN}:\{\ty{integer}, NIL\}):\ty{integer}}{eval, spread} +{Sets the vertical length (in lines) of an output page. Automatic page +EJECTs are executed by the print functions when this length is +\index{EJECT} +reached. The initial vertical length is implementation specific. The +previous page length is returned. If LEN is 0, no automatic page +ejects will occur. } + + +\de{POSN}{():\ty{integer}}{eval, spread} +{Returns the number of characters in the output buffer. When the +buffer is empty, 0 is returned.} + + +\de{PRINC}{(\p{U}:\ty{id}):\ty{id}}{eval, spread} +{U must be a single character id such as produced by EXPLODE or read +by READCH or the value of !\$EOL!\$. The effect is the character U +\index{\$EOL\$ (global)} +displayed upon the currently selected output device. The value of +!\$EOL!\$ causes termination of the current line like a call to +TERPRI.} + + +\de{PRINT}{(\p{U}:\ty{any}):\ty{any}}{eval, spread} +{Displays U in READ readable format and terminates the print line. The +value of U is returned. + +{\tt \begin{tabbing} EXPR PROCEDURE PRINT(U); \\ +\hspace*{2em} $<<$ PRIN1 U; TERPRI(); U $>>$; +\end{tabbing}}} + + +\de{PRIN1}{(\p{U}:\ty{any}):\ty{any}}{eval, spread} +{U is displayed in a READ readable form. The format of display is the +result of EXPLODE expansion; special characters are prefixed with the +escape character !, and strings are enclosed in "\ldots ". Lists are +displayed in list-notation and vectors in vector-notation. } + + +\de{PRIN2}{(\p{U}:\ty{any}):\ty{any}}{eval, spread} +{U is displayed upon the currently selected print device but output is +not READ readable. The value of U is returned. Items are displayed as +described in the EXPLODE function with the exceptions that the escape +character does not prefix special characters and strings are not +enclosed in "\ldots ". Lists are displayed in list-notation and +vectors in vector-notation. The value of U is returned. } + + +\de{RDS}{(\p{FILEHANDLE}:\ty{any}):\ty{any}}{eval, spread} +{Input from the currently selected input file is suspended and further +input comes from the file named. FILEHANDLE is a system dependent +\index{file handle} +internal name which is a value returned by OPEN. If FILEHANDLE is NIL +the standard input device is selected. When end of file is reached on +a non-standard input device, the standard input device is reselected. +When end of file occurs on the standard input device the Standard LISP +reader terminates. RDS returns the internal name of the previously +selected input file. +\index{standard input} + +\errormessage{***** FILEHANDLE could not be selected for input} +} + + +\de{READ}{():\ty{any}}{} +{The next expression from the file currently selected for input. Valid +input forms are: vector-notation, dot-notation, list-notation, +numbers, function-pointers, strings, and identifiers with escape +characters. Identifiers are interned onW the OBLIST (see +\index{INTERN} \index{OBLIST entry} +the INTERN function in "Identifiers", section~\ref{identifiers} on +page~\pageref{identifiers}). READ returns the +\index{\$EOF\$ (global)} +value of !\$EOF!\$ when the end of the currently selected input file +is reached. } + + +\de{READCH}{():\ty{id}}{} +{Returns the next interned character from the file currently selected +for input. Two special cases occur. If all the characters in an input +\index{\$EOL\$ (global)} \index{\$EOF\$ (global)} record have been read, +the value of !\$EOL!\$ is returned. If the file selected for input has +all been read the value of !\$EOF!\$ is returned. Comments delimited +by \% and end-of-line are not transparent to READCH. \index{\% ! read +by READCH} } + + +\de{TERPRI}{():\p{NIL}}{} +{The current print line is terminated.} + + +\de{WRS}{(\p{FILEHANDLE}:\ty{any}):\ty{any}}{eval, spread} +{Output to the currently active output file is suspended and further +output is directed to the file named. FILEHANDLE is an internal name +which is returned by OPEN. The file named must have been opened for +output. If FILEHANDLE is NIL the standard output device is selected. +\index{file handle} \index{standard output} +WRS returns the internal name of the previously selected output file. + +\errormessage{***** FILEHANDLE could not be selected for output} +} + +\subsection{LISP Reader} + +An EVAL read loop has been chosen to drive a Standard LISP system to +provide a continuity in functional syntax. Choices of messages and the +amount of extra information displayed are decisions left to the +implementor. + +\index{STANDARD-LISP} +{\tt \begin{tabbing} EXPR PROCEDURE STANDARD!-LISP(); \\ BEGIN SCALAR +VALUE; \\ +\hspace*{2em} \= RDS NIL; WRS NIL; \\ +\> PRIN2 "Standard LISP"; TERPRI(); \\ +\> WHILE T DO \\ +\> \hspace*{1em} $<<$ \= PRIN2 "EVAL:"; TERPRI(); \\ +\> \> VALUE := ERRORSET(QUOTE EVAL READ(), T, T); \\ +\> \> IF NOT ATOM VALUE THEN PRINT CAR VALUE; \\ +\> \> TERPRI() $>>$; \\ +END; +\end{tabbing}} + +\de{QUIT}{()}{} +{Causes termination of the LISP reader and control to be transferred +to the operating system.} + +\section{System GLOBAL Variables} +\label{slglobals} + +These variables provide global control of the LISP system, or +implement values which are constant throughout execution.\footnote{The +published document does not specify that all these are GLOBAL.} + + +\variable{*COMP}{NIL}{global} +{The value of !*COMP controls whether or not PUTD compiles the +function defined in its arguments before defining it. If !*COMP is NIL +the function is defined as an xEXPR. If !*COMP is something else the +function is first compiled. Compilation will produce certain changes +in the semantics of functions particularly FLUID type access.} + + +\variable{EMSG*}{NIL}{global} +{Will contain the MESSAGE generated by the last ERROR call (see +\index{ERROR} +``Error Handling'' section~\ref{errors} on page~\pageref{errors}).} + + +\variable{\$EOF\$}{\s{an uninterned identifier}}{global} +{The value of !\$EOF!\$ is returned by all input functions when the +end +\index{end of file} +of the currently selected input file is reached.} + + +\variable{\$EOL\$}{\s{an uninterned identifier}}{global} +{The value of !\$EOL!\$ is returned by READCH when it reaches the end +of +\index{READCH} \index{end of line} \index{PRINC} +a logical input record. Likewise PRINC will terminate its current line +(like a call to TERPRI) when !\$EOL!\$ is its argument.} + +\variable{*GC}{NIL}{global} +{!*GC controls the printing of garbage collector messages. If NIL no +\index{garbage collector} +indication of garbage collection may occur. If non-NIL various system +dependent messages may be displayed.} + + +\variable{NIL}{NIL}{global} +{NIL is a special global variable. It is protected from being modified +by SET or SETQ. +\index{NIL ! cannot be changed}} + + +\variable{*RAISE}{NIL}{global} +{If !*RAISE is non-NIL all characters input through Standard LISP +input/output functions will be raised to upper case. If !*RAISE is NIL +characters will be input as is.} + + +\variable{T}{T}{global} +{T is a special global variable. It is protected from being modified +by SET or SETQ. \index{T ! cannot be changed}} + + +\section{The Extended Syntax} + +Whenever it is possible to define Standard LISP functions in LISP the +text of the function will appear in an extended syntax. These +definitions are supplied as an aid to understanding the behavior of +functions and not as a strict implementation guide. A formal scheme +for the translation of extended syntax to Standard LISP is presented +to eliminate misinterpretation of the definitions. + +\subsection{Definition} +The goal of the transformation scheme is to produce a PUTD invocation +which has the function translated from the extended syntax as its +actual parameter. A rule has a name in brackets +\s{\ldots} by which it is known and is defined by what follows the meta +symbol ::=. Each rule of the set consists of one or more +``alternatives'' separated by the $\mid$ meta symbol, being the +different ways in which the rule will be matched by source text. Each +alternative is composed of a ``recognizer'' and a ``generator'' +separated by the $\Longrightarrow$ meta symbol. The recognizer is a +concatenation of any of three different forms. 1) Terminals - Upper +case lexemes and punctuation which is not part of the meta syntax +represent items which must appear as is in the source text for the +rule to succeed. 2) Rules - Lower case lexemes enclosed in \s{\ldots} +are names of other rules. The source text is matched if the named +rule succeeds. 3) Primitives - Lower case singletons not in brackets +are names of primitives or primitive classes of Standard LISP. The +syntax and semantics of the primitives are given in Part I. + +The recognizer portion of the following rule matches an extended +syntax procedure: + + +\s{function} ::= ftype PROCEDURE id (\s{id list}); \\ +\hspace*{2em} \s{statement}; $\Longrightarrow$ + +A function is recognized as an ``ftype'' (one of the tokens EXPR, +FEXPR, etc.) followed by the keyword PROCEDURE, followed by an ``id'' +(the name of the function), followed by an \s{id list} (the formal +parameter names) enclosed in parentheses. A semicolon terminates the +title line. The body of the function is a +\s{statement} followed by a semicolon. For example: + +\begin{verbatim} +EXPR PROCEDURE NULL(X); EQ(X, NIL); +\end{verbatim} + +\noindent satisfies the recognizer, causes the generator to be activated and +the rule to be matched successfully. + +The generator is a template into which generated items are +substituted. The three syntactic entities have corresponding meanings +when they appear in the generator portion. 1) Terminals - These +lexemes are copied as is to the generated text. 2) Rules - If a rule +has succeeded in the recognizer section then the value of the rule is +the result of the generator portion of that rule. 3) Primitives - +When primitives are matched the primitive lexeme replaces its +occurrence in the generator. + +If more than one occurrence of an item would cause ambiguity in the +generator portion this entity appears with a bracketed subscript. +Thus: + +\begin{tabbing} +\s{conditional} ::= \\ +\hspace*{2em} IF \s{expression} \= THEN \s{statement$_1$} \\ +\> ELSE \s{statement$_2$} \ldots +\end{tabbing} + +\noindent has occurrences of two different \s{statement}s. The generator +portion uses the subscripted entities to reference the proper +generated value. + +The \s{function} rule appears in its entirety as: + +\begin{tabbing} +\s{function} ::= ftype PROCEDURE id (\s{id list});\s{statement}; +$\Longrightarrow$ \\ +\hspace*{2em} \=(PUTD \= (QUOTE id) \\ +\> \> (QUOTE ftype) \\ +\> \>(QUOTE (LAMBDA (\s{id list}) \s{statement}))) +\end{tabbing} + +If the recognizer succeeds (as it would in the case of the NULL +procedure example) the generator returns: + +\begin{verbatim} +(PUTD (QUOTE NULL) (QUOTE EXPR) (QUOTE (LAMBDA (X) (EQ X NIL)))) +\end{verbatim} + +The identifier in the template is replaced by the procedure name NULL, +\s{id list} by the single formal parameter X, the \s{statement} by (EQ +X NIL) which is the result of the \s{statement} generator. EXPR +replaces ftype, the type of the defined procedure. + + +\subsection{The Extended Syntax Rules} + +\begin{tabbing} +\s{function} ::= ftype \k{PROCEDURE} id (\s{id list}); \s{statement}; +$\Longrightarrow$ \\ +\hspace*{2em} \= (PUTD \= (QUOTE id) \\ +\> \> (QUOTE ftype) \\ +\> \> (QUOTE (LAMBDA (\s{id list}) \s{statement}))) \\ \\ + +\s{id list} ::= id $\Longrightarrow$ id $\mid$ \\ +\> id, \s{id list} $\Longrightarrow$ id \s{id list} $\mid$ \\ +\> $\Longrightarrow$ NIL \\ + +\s{statement} ::= \s{expression} $\Longrightarrow$ \s{expression} $\mid$ \\ +\> \s{proper statement} $\Longrightarrow$ \s{proper statement} \\ \\ + +\s{proper statement} ::= \\ +\> \s{assignment statement} $\Longrightarrow$ \s{assignment statement} +$\mid$ \\ +\> \s{conditional statement} $\Longrightarrow$ \s{conditional statement} +$\mid$ \\ +\> \s{while statement} $\Longrightarrow$ \s{while statement} $\mid$ \\ +\> \s{compound statement} $\Longrightarrow$ \s{compound statement} \\ \\ + +\s{assignment statement} ::= id := \s{expression} $\Longrightarrow$ \\ +\> \> (SETQ id \s{expression}) \\ \\ + +\s{conditional statement} ::= \\ +\> \k{IF} \s{expression} \k{THEN} \s{statement$_1$} \k{ELSE} +\s{statement$_2$} $\Longrightarrow$ \\ +\> \hspace{2em} \= (COND (\s{expression} \s{statement$_1$})(T +\s{statement$_2$})) $\mid$ \\ +\> \k{IF} \s{expression} \k{THEN} \s{statement} $\Longrightarrow$ \\ +\> \> (COND (\s{expression} \s{statement})) \\ \\ + +\s{while statement} ::= \k{WHILE} \s{expression} \k{DO} \s{statement} +$\Longrightarrow$ \\ +\> \> (PROG NIL \\ +\> \> LBL \= (COND ((NULL \s{expression}) (RETURN NIL))) \\ +\> \> \> \s{statement} \\ +\> \> \> (GO LBL)) \\ \\ + +\s{compound statement} ::= \\ +\> \k{BEGIN} \k{SCALAR} \s{id list}; \s{program list} \k{END} +$\Longrightarrow$ \\ +\> \> (PROG (\s{id list}) \s{program list}) $\mid$ \\ +\> \k{BEGIN} \s{program list} \k{END} $\Longrightarrow$ \\ +\> \> (PROG NIL \s{program list}) $\mid$ \\ +\> \k{$<<$} \s{statement list} \k{$>>$} $\Longrightarrow$ (PROGN +\s{statement list}) \\ \\ + +\s{program list} ::= \s{full statement} $\Longrightarrow$ \s{full statement} + $\mid$ \\ +\> \s{full statement} \s{program list} $\Longrightarrow$ \\ +\> \> \s{full statement} \s{program list} \\ \\ + +\s{full statement} ::= \s{statement} $\Longrightarrow$ \s{statement} $\mid$ +id: $\Longrightarrow$ id \\ \\ + +\s{statement list} ::= \s{statement} $\Longrightarrow$ \s{statement} $\mid$ \\ +\> \s{statement}; \s{statement list} $\Longrightarrow$ \\ +\> \> \s{statement} \s{statement list} \\ \\ + +\s{expression} ::= \\ +\> \s{expression$_1$} \k{.} \s{expression$_2$} $\Longrightarrow$ \\ +\> \> (CONS \s{expression$_1$} \s{expression$_2$} $\mid$ \\ +\> \s{expression$_1$} \k{=} \s{expression$_2$} $\Longrightarrow$ \\ +\> \> (EQUAL \s{expression$_1$} \s{expression$_2$}) $\mid$ \\ +\> \s{expression$_1$} \k{EQ} \s{expression$_2$} $\Longrightarrow$ \\ +\> \> (EQ \s{expression$_1$} \s{expression$_2$}) $\mid$ \\ +\> '\s{expression} $\Longrightarrow$ (QUOTE \s{expression}) $\mid$ \\ +\> function \s{expression} $\Longrightarrow$ (function \s{expression}) +$\mid$ \\ +\> function(\s{argument list}) $\Longrightarrow$ (function \s{argument list}) +$\mid$ \\ +\> number $\Longrightarrow$ number $\mid$ \\ +\> id $\Longrightarrow$ id \\ \\ + +\s{argument list} ::= () $\Longrightarrow$ $\mid$ \\ +\> \s{expression} $\Longrightarrow$ \s{expression} $\mid$ \\ +\> \s{expression}, \s{argument list} $\Longrightarrow$ \s{expression} +\s{argument list} +\end{tabbing} + +Notice the three infix operators . EQ and = which are translated into +calls on CONS, EQ, and EQUAL respectively. Note also that a call on a +function which has no formal parameters must have () as an argument +list. The QUOTE function is abbreviated by '. +\bibliography{sl} +\bibliographystyle{plain} +\end{document}