List Of Computer Programming Glossary Terms

LIST OF COMPUTER PROGRAMMING GLOSSARY TERMS accessor function A function such as STARSHIP-SPEED, defined automatically by DEFSTRUCT, that allows you to access a particular field of a structure. applicative operator A function that takes another function as input, and applies it to some data. Examples include MAPCAR and FIND-IF. applicative programming A style of programming in which functions are frequently passed as data to other functions, and explicit assignment is avoided. Repetitive operations are performed by passing functions to applicative operators APPLY The Lisp primitive that applies a function to a set of arguments. EVAL and APPLY are the two basic functions from which Lisp interpreters are constructed. Applicative operators are all constructed from APPLY (or from FUNCALL.) argument A piece of data serving as input to a function, or an expression which, when evaluated, will produce that piece of data. The term is also used to refer to the names a function uses for its inputs, as in ‘‘AVERAGE is a function of two arguments: X and Y.’’ argument list A list that specifies the names a function gives to each of its inputs, and how many inputs it requires. When defining a new function, the second input to DEFUN is the new function’s argument list. assignment-free style A style of programming that avoids explicit assignment to variables. Once a variable is given a value, such as by a function call or by LET, that value never changes. Assignment-free programs are considered very elegant and easy to read. augmentation The process of adding something on to a result to derive a new result. augmenting recursion A type of recursion in which the final result is built up bit by bit, by adding something to the result of each recursive call. backtrace A display of the execution stack showing the function currently being evaluated, the function that called it, the function that called that function, and so on. Backtraces are displayed by the debugger upon command. call To call or invoke a function means to pass it some inputs and ask it to produce an output or side effect. conditional A special function or macro function that makes decisions about which parts of its input to evaluate. Examples include IF, COND, AND, and OR. conditional augmentation A style of recursion in which the results of each recursive call are sometimes augmented and sometimes not, under the control of a conditional.

end-of-file error When READ tries to read an object beyond the last object in the file, an end-of-file error is signalled. This error can be disabled by supplying an optional argument to READ. EVAL The heart of Lisp: EVAL is a function that evaluates a Lisp expression according to a set of evaluation rules, and returns the result. EVAL notation A way to write Lisp expressions as lists. The first element of a list specifies a function, and the remaining elements specify arguments to be evaluated before the function is called. evaltrace diagram A graphical notation unique to this book. Evaltrace diagrams illustrate the evaluation of expressions, and are particularly useful for explaining lexical and dynamic scoping. evaluation The process of deriving a result from an expression. expression Expressions are the Lisp equivalent of sentences in English. Every Lisp object (number, symbol, list) is an expression. Lisp interpreters read expressions from the keyboard, evaluate them, and print the results. floating point number A number containing a decimal point, such as 5.0 or 3.14159 i/o Input/output. The process of transferring information between the computer and an external device, such as the keyboard, the display, or a disk file. indicator An atom (normally a symbol) that serves as the name of a property on a property list. input The inputs to a function are the pieces of data it receives. The term input also refers to the act of reading an object or character string from the keyboard, or from a file. invoke To invoke a function means to call it, in other words, to give it some inputs and ask it to produce an output. iteration To iterate means to repeat. Iteration in Lisp is accomplished by macros such as DO, DO*, DOTIMES, and DOLIST, which ultimately rely on the LOOP special function. key The item that names an entry in an association list or hash table. Entries can be retrieved (by ASSOC or GETHASH) given the associated key. keyword A special kind of symbol that is written with a preceding colon, such as :TEST. Keywords evaluate to themselves.

keyword argument An optional argument named by a keyword. For example, the MEMBER function takes an optional :TEST argument. macro function A special kind of function whose arguments are not evaluated. Macro functions must return Lisp expressions, which are then evaluated. macro expansion The act of invoking a macro on some inputs to obtain a Lisp expression. For example, the macro call (INCF A) may expand to the expression (SETQ A (+ A 1)). multiple recursion A style of recursion in which each call to a function results in several recursive calls, for example, to examine both the car and cdr halves of a tree. nested IF An IF appearing as the true-part or false-part of an enclosing IF. Nested IFs may be used to duplicate the multiple-clause capabilities of COND. nested list A list that contains other lists as elements nonterminal node A node of a tree with at least one descendant. output The output of a function is the result it returns. The term may also refer to a program’s outputting information to the display, or to a file. package Packages are the name spaces in which symbols are registered. The default package is called USER. Lisp functions and variables are named by symbols in package LISP. package name A character string giving the name of a package, such as "USER". APROPOS takes a package name as an optional second argument. pattern matcher A function that matches an input list against a pattern that may contain wildcards. For example, the input (B1 COLOR GREEN) matches the pattern (B1 COLOR ?) pointer A pointer to an object gives the address of that object in memory. Pointers are drawn as arrows in cons cell diagrams. predicate A function that answers a question by returning T (or some other non-NIL value) for true, or NIL for false. predicate expression An expression whose value is interpreted as true or false. Used with conditionals. primitive An elementary function that is built in to Lisp, not defined by the user. CONS and + are primitives

property list A list composed of alternating property indicators and values, such as (SIBLINGS (GEORGE WANDA) AGE 23 SEX MALE). Every symbol contain a plist cell that points to its associated property list. Properties can be retrieved using the GET function. pushdown stack A data structure where new elements are pushed on or popped off only at one end, usually called the ‘‘top’’ of the stack. Named after spring loaded stacks of dishes in cafeterias. Also called a LIFO (Last In, First Out) stack. Stacks are implemented as lists or vectors in Lisp. read-eval-print loop The part of a Lisp interpreter that reads expressions from the keyboard, evaluates them, and prints the result. rebinding Rebinding a special variable means creating a new dynamic variable with the same name, such as with LET. The name is then dynamically associated with the new variable when it appears anywhere in the program, and the old variable is inaccessible until the form that bound the new variable returns recursion A thing is recursive if it contains a reference to itself in its definition. Recursive functions call themselves recursion template A fill-in-the-blanks description of a class of recursive functions. For example, CAR/CDR recursion describes a class of functions for searching binary trees result The output of (or value returned by) a function or expression. return When a function ‘‘returns a value,’’ it is outputting a piece of data. scope The scope of an object is the region of the program in which the object can be referenced. For example, if a variable names the input to some function, the scope of the variable is limited to the body of that function. See also lexical scoping and dynamic scoping sequence A linear collection of elements. Sequences in Lisp include lists and vectors, and hence strings, which are a type of vector. Many functions that worked only lists in previous Lisp dialects work on all types of sequences in Common Lisp. Examples include LENGTH and REVERSE set An unordered collection of elements, each of which appears only once in the set. In Lisp, sets are implemented as lists. set difference The set difference (or set subtraction) of sets x and y is the set of elements that appear in x and do not appear in y. set exclusive or The exclusive or of two sets is the set of elements that appear in one set but not the other.

side effect Any action a function takes other than returning a value. Assignment to variables, and input/output operations are examples of side effects. single-test recursion A style of recursive function in which there is only one end test. Single-test recursion is used when the function is guaranteed to eventually find what it’s looking for, so there is no need to check for failure. An example would be the recursive definition of FACT, where the end test is ZEROP. special function A built-in function that does not evaluate its arguments. Special functions provide the primitive constructs, such as assignment, block structure, looping, and variable binding, from which the rest of Lisp is built. They do not return Lisp expressions to be evaluated, as macros do. Lisp programmers can create new macros, but they cannot create new special functions. special variable A dynamically scoped variable. When a name is declared special, all variables with that name will be dynamically scoped. stream object A Lisp object describing a connection to a file. Lisp programs read and write files by supplying an appropriate stream object as optional input to READ or FORMAT. string A sequence of characters enclosed in double quotes, such as the string "Foo Bar". Strings are vectors of character objects. structure A user-defined datatype composed of named slots. An example is the STARSHIP structure, whose slots are NAME, CAPTAIN, SPEED, SHIELDS, and CONDITION. Subroutines

One approach he suggested was to build on top of FORTRAN, by creating a set of special subroutines for list manipulation. tail recursive A function is tail recursive if it does all its work before making the recursive call. Tail recursive functions return the result of the recursive call without augmenting (modifying) it, or doing any other additional work. Clever Lisp compilers turn tail recursive calls into jump instructions, eliminating the need for a call stack. terminal call A call to a function that results in no further recursive calls. The function simply returns a value. terminal node A node of a tree with no descendants, in other words, a bottommost node. Terminal nodes are also called leaves. top-level prompt A prompt character such as ‘‘>’’ or ‘‘*’’ that indicates to the user that he or she is typing to the top-level read-eval-print loop. TRACE A tool for displaying function entries and exits.

tree A structure composed of nodes and links, where each node has zero or more children and exactly one parent. An exception is the topmost node, or root, which has no parent. Trees may be represented as lists in Lisp. truth function A function whose inputs and output are truth values, that is, true or false. type predicate A predicate such as NUMBERP or CONSP that returns true if its input is a particular type of data. type system The set of datatypes a language offers, and their organization. unassigned variable A variable that has no value. unbound variable ‘‘Unbound’’ is an archaic term for ‘‘unassigned,’’. See unassigned variable union The union of two sets contains all the elements of each set. Each element appears only once in the union. See also intersection. variable A place where a value is stored ( temporarily) to help in some computation. Ordinary variables are named by symbols. Generalized variables are named by place descriptions.