<P> <P> <HTML> <HEAD> <TITLE>Simply Scheme: Glossary</TITLE> </HEAD> <BODY> <CITE>Simply Scheme</CITE>: <CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT <H1>Glossary</H1> <TABLE width="100%"><TR><TD> <IMG SRC="../simply.jpg" ALT="cover photo"> <TD><TABLE> <TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian Harvey</A><BR>University of California, Berkeley</CITE> <TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew Wright</A><BR>University of California, Santa Barbara</CITE> <TR><TD align="right"><BR> <TR><TD align="right"><A HREF="../pdf/ssch27.pdf">Download PDF version</A> <TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A> <TR><TD align="right"><A HREF="appendix-funlist.html"><STRONG>BACK</STRONG></A> chapter thread <A HREF="appuindex.html"><STRONG>NEXT</STRONG></A> <TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT Press web page for <CITE>Simply Scheme</CITE></A> </TABLE></TABLE> <HR> <P> <STRONG>ADT: </STRONG> See <EM>abstract data type.</EM> <P><STRONG>a-list: </STRONG> Synonym for <EM>association list.</EM> <P><STRONG>abstract data type: </STRONG> A <EM>type</EM> that isn't provided automatically by Scheme, but that the programmer invents. In order to create an abstract data type, a programmer must define <EM>selectors</EM> and <EM>constructors</EM> for that type, and possibly also <EM>mutators.</EM> <P><STRONG>abstraction: </STRONG> An approach to complex problems in which the solution is built in layers. The structures needed to solve the problem (algorithms and data structures) are implemented using lower-level capabilities and given names that can then be used as if they were primitive facilities. <P><STRONG>actual argument expression: </STRONG> An expression that produces an actual argument value. In <CODE>(+ 2 (* 3 5))</CODE>, the subexpression <CODE>(* 3 5)</CODE> is an actual argument expression, since it provides an argument for the invocation of <CODE>+</CODE>. <P><STRONG>actual argument value: </STRONG> A value used as an argument to a procedure. For example, in the expression <CODE>(+ 2 (* 3 5))</CODE>, the number <CODE>15</CODE> is an actual argument value. <P><STRONG>aggregate: </STRONG> An object that consists of a number of other objects. For example, a sentence is an aggregate whose elements are words. Lists and vectors are also aggregates. A word can be thought of, for some purposes, as an aggregate whose elements are one-letter words. <P><STRONG>algorithm: </STRONG> A method for solving a problem. A computer program is the expression of an algorithm in a particular programming language; the same algorithm might also be expressed in a different language. <P><STRONG>apply: </STRONG> To <EM>invoke</EM> a procedure with arguments. For example, "Apply the procedure <CODE>+</CODE> to the arguments <CODE>3</CODE> and <CODE>4</CODE>." <P><STRONG>argument: </STRONG> A datum provided to a procedure. For example, in <CODE>(square 13)</CODE>, <CODE>13</CODE> is the argument to <CODE>square</CODE>. <P><STRONG>association list: </STRONG> A list in which each element contains a <EM>name</EM> and a corresponding <EM>value.</EM> The list is used to look up a value, given a name. <P><STRONG>atomic expression: </STRONG> An expression that isn't composed of smaller pieces. <P><STRONG>backtracking: </STRONG> A programming technique in which the program tries one possible solution to a problem, but tries a different solution if the first isn't successful. <P><STRONG>base case: </STRONG> In a recursive procedure, the part that solves the smallest possible version of the problem without needing a recursive invocation. <P><STRONG>body: </STRONG> An expression, part of the definition of a procedure, that is evaluated when that procedure is invoked. For example, in <P><PRE>(define (square x) (* x x)) </PRE> <P>the expression <CODE>(* x x)</CODE> is the body of the <CODE>square</CODE> procedure. <P><STRONG>Boolean: </STRONG> The value <CODE>#t</CODE>, meaning "true," or <CODE>#f</CODE>, meaning "false." <P><STRONG>branch node: </STRONG> A <EM>tree node</EM> with <EM>children.</EM> The opposite of a <EM>leaf node.</EM> <P><STRONG>bug: </STRONG> An error in a program. This word did <EM>not</EM> originate with Grace Hopper finding an actual insect inside a malfunctioning computer; she may have done so, but the terminology predates computers by centuries. <P><STRONG>call: </STRONG> Synonym for <EM>invoke.</EM> <P><STRONG>cell: </STRONG> One location in a <EM>spreadsheet.</EM> <P><STRONG>children: </STRONG> The <EM>nodes</EM> directly under this one, in a <EM>tree.</EM> (See also <EM>siblings</EM> and <EM>parent.</EM>) <P><STRONG>composition of functions: </STRONG> Using the value returned by a function as an argument to another. In the expression <CODE>(+ 2 (* 3 5))</CODE>, the value returned by the <CODE>*</CODE> function is used as an argument to the <CODE>+</CODE> function. <P><STRONG>compound expression: </STRONG> An expression that contains subexpressions. Opposite of <EM>atomic expression.</EM> <P><STRONG>compound procedure: </STRONG> A procedure that a programmer defines. This is the opposite of a <EM>primitive</EM> procedure. <P><STRONG>constructor: </STRONG> A procedure that returns a new object of a certain type. For example, the <CODE>word</CODE> procedure is a constructor that takes words as arguments and returns a new word. See also <EM>selector</EM>, <EM>mutator</EM>, and <EM>abstract data type.</EM> <P><STRONG>data abstraction: </STRONG> The invention of <EM>abstract data types.</EM> <P><STRONG>data structure: </STRONG> A mechanism through which several pieces of information are combined into one larger unit. The most appropriate mechanism will depend on the ways in which the small pieces are used in the program, for example, sequentially or in arbitrary order. <P><STRONG>database program: </STRONG> A program that maintains an organized collection of data, with facilities to modify or delete old entries, add new entries, and select certain entries for display. <P><STRONG>datum: </STRONG> The piece of information stored in each node of a tree. <P><STRONG>debugging: </STRONG> The process by which a programmer finds and corrects mistakes in a program. No interesting program works the first time; debugging is a skill to develop, not something to be ashamed of. <P><STRONG>destructive: </STRONG> A destructive procedure is one that modifies its arguments. Since the only data type in this book that can be modified is the vector, all destructive procedures call <CODE>vector-set!</CODE>. <P><STRONG>domain: </STRONG> The set of all legal arguments to a function. For example, the domain of the <CODE>count</CODE> function is the set of all sentences and all words. <P><STRONG>effect: </STRONG> Something a procedure does other than return a value. For example, a procedure might create a file on disk, or print something to the screen, or change the contents of a vector. <P><STRONG>empty sentence: </STRONG> The sentence <CODE>()</CODE>, which has no words in it. <P><STRONG>empty word: </STRONG> The word <CODE>""</CODE>, which has no letters in it. <P><STRONG>end-of-file object: </STRONG> What the file-reading procedures return if asked to read a file with no more unread data. <P><STRONG>expression: </STRONG> The representation in Scheme notation of a request to perform a computation. An expression is either an <EM>atomic expression,</EM> such as <CODE>345</CODE> or <CODE>x</CODE>, or a <EM>compound expression</EM> consisting of one or more subexpressions enclosed in parentheses, such as <CODE>(+ 3 4)</CODE>. <P><STRONG>field: </STRONG> A single component of a database <EM>record.</EM> For example, "title" is a field in our example database of albums. <P><STRONG>first-class data: </STRONG> Data with the following four properties: <TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">It can be the argument to a procedure. </TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">It can be the return value from a procedure. </TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">It can be given a name. </TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">It can be part of a data aggregate. </TABLE> In Scheme, words, lists, sentences, trees, vectors, ports, end-of-file objects, Booleans, and procedures are all first-class. <P><STRONG>forest: </STRONG> A list of <EM>trees.</EM> <P><STRONG>formal parameter: </STRONG> In a procedure definition, the name given to refer to an argument. In <P><PRE>(define (square x) (* x x))</PRE><CODE>x</CODE> is the formal parameter. (Note that this is not the same thing as an actual argument! When we invoke <CODE>square</CODE> later, the argument will be a number, such as 5. The parameter is the <EM>name</EM> for that number, not the number itself.) <STRONG>function: </STRONG> A transformation of information that associates a <EM>return value</EM> with some number of <EM>argument values.</EM> There may be many different <EM>algorithms</EM> that compute the same function; the function itself is the relationship between argument values and return value, no matter how it may be implemented. <P><STRONG>functional programming: </STRONG> A style of programming in which programs are expressed as compositions of functions, emphasizing their arguments and return values. Compare to <EM>sequential programming.</EM> <P><STRONG>global variable: </STRONG> A variable created with <CODE>define</CODE>, which has meaning everywhere in the program. The opposite of a <EM>local variable.</EM> <P><STRONG>helper procedure: </STRONG> A procedure that exists to help another procedure do its work. Normally, a user does not invoke a helper procedure directly. Instead, the user invokes a top-level procedure, which invokes the helper procedure to assist it in coming up with the answer. <P><STRONG>higher-order procedure: </STRONG> A procedure whose domain or range includes other procedures. <P><STRONG>index: </STRONG> A number used to select one of the elements of a vector. <P><STRONG>initialization procedure: </STRONG> A procedure that doesn't do any work except to invoke a <EM>helper procedure</EM> with appropriate argument values. <P><STRONG>interactive: </STRONG> An interactive program or programming language does its work in response to messages typed by the user at a keyboard (or perhaps indicated with a pointing device like a mouse). Each message from the user causes the program to respond in some way. By contrast, a non-interactive program works with input data that have been prepared in advance. <P><STRONG>invoke: </STRONG> To ask a procedure to do its work and come up with a return value. For example, "Invoke the <CODE>+</CODE> procedure," or "Invoke the <CODE>+</CODE> procedure with the arguments <CODE>3</CODE> and <CODE>4</CODE>." <P><STRONG>keyword: </STRONG> The name of a <EM>special form.</EM> <P><STRONG>kludge: </STRONG> A method that gets the job done but isn't very elegant. Usually the result is a program that can't be extended the next time a new feature is needed. <P><STRONG>leaf node: </STRONG> A <EM>tree node</EM> with no <EM>children.</EM> The opposite of a <EM>branch node.</EM> <P><STRONG>leap of faith: </STRONG> A method for understanding recursion in which you say to yourself, "I'm going to assume that the recursive call always returns the right answer," and then use the answer from the recursive call to produce the answer to the entire problem. <P><STRONG>list: </STRONG> A data aggregate containing elements that may be of any type. <P><STRONG>local variable: </STRONG> A variable that associates a formal parameter name with an actual argument value. It's "local" because the variable exists only within one procedure invocation. (This includes variables created by <CODE>let</CODE>.) This is the opposite of a <EM>global variable.</EM> <P> <P><STRONG>mutable: </STRONG> A data structure is mutable if its contents can change. <P><STRONG>mutator: </STRONG> A procedure that changes the value of a data object. In this book, the only mutable data objects we use are vectors, so every mutator is implemented using <CODE>vector-set!</CODE>. See also <EM>selector,</EM> <EM>constructor,</EM> and <EM>abstract data type.</EM> <P><STRONG>mutual recursion: </STRONG> The program structure in which one procedure invokes another, and the second invokes the first. <P><STRONG>node: </STRONG> An element of a <EM>tree.</EM> A node has a <EM>datum</EM> and zero or more <EM>children.</EM> <P><STRONG>parent: </STRONG> The node above this one, in a <EM>tree.</EM> (See also <EM>children</EM> and <EM>siblings.</EM>) <P><STRONG>pattern matcher: </STRONG> A program that takes a pattern and a piece of data as inputs and says whether or not that piece of data is one that the pattern describes. We present a pattern matcher in Chapter 16. <P><STRONG>plumbing diagram: </STRONG> A pictorial representation of the composition of functions, with the return value from one procedure connected to an argument intake of another. <P><STRONG>port: </STRONG> An object that Scheme uses to keep track of a file that is currently open for reading or writing. <P><STRONG>portable: </STRONG> A portable program is one that can be run in more than one version of Scheme or on more than one computer. <P><STRONG>potsticker: </STRONG> A Chinese dumpling stuffed with meat and vegetables, first steamed and then pan-fried, or sometimes first pan-fried and then simmered in water added to the pan. <P><STRONG>predicate: </STRONG> A procedure that always returns a <EM>Boolean</EM> value. By convention, Scheme predicates have names like "<CODE>equal?</CODE>" that end in a question mark. <P><STRONG>primitive procedure: </STRONG> A procedure that is already defined when a Scheme session begins. By contrast, a <EM>compound</EM> procedure is one that the programmer defines in Scheme. <P><STRONG>procedure: </STRONG> The expression of an algorithm in Scheme notation. <P><STRONG>prompt: </STRONG> A character or characters that an interactive program prints to tell the user that it's ready for the user to type something. In many versions of Scheme, the prompt is a <CODE>></CODE> character. <P><STRONG>random access: </STRONG> A data structure allows random access if the time required to locate an element of the structure is independent of its position within the structure. <P><STRONG>range: </STRONG> The set of all possible return values from a function. For example, the range of the <CODE>count</CODE> function is the set of non-negative integers. <P><STRONG>read-eval-print loop: </STRONG> The overall structure of a Scheme interpreter. It <EM>reads</EM> an expression from the keyboard, <EM>evaluates</EM> the expression by invoking procedures, etc., and <EM>prints</EM> the resulting value. The same process repeats forever. <P><STRONG>record: </STRONG> One complete entry in a database. For example, one album in our database of albums. A record contains several <EM>fields.</EM> <P><STRONG>recursion: </STRONG> Solving a big problem by reducing it to smaller problems of the same kind. If something is defined recursively, then it's defined in terms of itself. See <EM>recursion.</EM> <P><STRONG>recursive case: </STRONG> In a recursive procedure, the part that requires a recursive invocation. The opposite of the <EM>base case.</EM> <P><STRONG>rest parameter: </STRONG> A parameter that represents a variable number of arguments. In the formal parameter list <CODE>(a b . x)</CODE>, <CODE>x</CODE> is a rest parameter. <P><STRONG>result replacement: </STRONG> A technique people can use to figure out the value of a complicated Scheme expression by rewriting the expression repeatedly, each time replacing some small subexpression with a simpler expression that has the same value, until all that's left is a single quoted or self-evaluating value. <P><STRONG>robust: </STRONG> Able to function despite user errors. Robust programs check for likely errors and recover from them gracefully. <P><STRONG>root node: </STRONG> The <EM>node</EM> at the very top of a <EM>tree.</EM> <P><STRONG>selector: </STRONG> A procedure that takes an object as its argument and returns some part of that object. For example, the selector <CODE>first</CODE> takes a word or sentence as argument and returns the first letter of the word or first word of the sentence. See also <EM>constructor,</EM> <EM>mutator,</EM> and <EM>abstract data type.</EM> <P><STRONG>self-evaluating: </STRONG> An expression is self-evaluating if, when evaluated, it has as its value the expression itself. Numbers, Booleans, and strings are the only self-evaluating objects we use in this book. <P><STRONG>semipredicate: </STRONG> A procedure that answers a yes-no question by returning <CODE>#f</CODE> for "no," but instead of returning <CODE>#t</CODE> for "yes," it returns some additional piece of information. The primitive <CODE>member</CODE> procedure is a good example of a semipredicate. ("Semipredicate" isn't a common term; we made it up for this book.) <P><STRONG>sequencing: </STRONG> Evaluating two or more expressions one after the other, for the sake of their <EM>effects.</EM> <P><STRONG>sequential programming: </STRONG> A style of programming in which programs say, "First do this, then do that, then do that other thing." (Compare to <EM>functional programming.</EM>) <P><STRONG>siblings: </STRONG> Two <EM>nodes</EM> of a <EM>tree</EM> that are the children of the same node. (See also <EM>children</EM> and <EM>parent.</EM>) <P><STRONG>side effect: </STRONG> See <EM>effect.</EM> <P><STRONG>special form: </STRONG> A Scheme expression that begins with a <EM>keyword</EM> and is evaluated using a special rule. In particular, some of the subexpressions might not be evaluated. The keywords used in this book are <CODE>and</CODE>, <CODE>begin</CODE>, <CODE>cond</CODE>, <CODE>define</CODE>, <CODE>if</CODE>, <CODE>lambda</CODE>, <CODE>let</CODE>, <CODE>or</CODE>, and <CODE>quote</CODE>. (The keyword itself is also sometimes called a special form.) <P><STRONG>spreadsheet program: </STRONG> A program that maintains a two-dimensional display of data can compute some elements automatically, based on the values of other elements. <P><STRONG>state: </STRONG> A program's memory of what has happened in the past. <P><STRONG>string: </STRONG> A <EM>word</EM> delimited by double-quote marks, such as <CODE>"A Hard Day's Night"</CODE> or <CODE>"000123"</CODE>. <P><STRONG>structured list: </STRONG> A list with <EM>sublists.</EM> <P><STRONG>subexpression: </STRONG> An element of a <EM>compound expression.</EM> For example, the expression <CODE>(+ (* 2 3) 4)</CODE> has three subexpressions: <CODE>+</CODE>, <CODE>(* 2 3)</CODE>, and <CODE>4</CODE>. <P><STRONG>sublist: </STRONG> An element of a list that is itself a smaller list. For example, <CODE>(c d)</CODE> is a sublist of the list <CODE>(a b (c d) e)</CODE>. <P><STRONG>substitution model: </STRONG> The way we've explained how Scheme evaluates function invocations. According to the substitution model, when a compound procedure is invoked, Scheme goes through the body of that procedure and replaces every copy of a formal parameter with the corresponding actual argument value. Then Scheme evaluates the resulting expression. <P><STRONG>subtree: </STRONG> A tree that is part of a larger tree. <P><STRONG>symbol: </STRONG> A word that isn't a number or a string. <P><STRONG>symbolic computing: </STRONG> Computing that is about words, sentences, and ideas instead of just numbers. <P> <P><STRONG>tree: </STRONG> A two-dimensional data structure used to represent hierarchical information. <P><STRONG>tree recursion: </STRONG> A form of recursion in which a procedure calls itself recursively more than one time in each level of the recursion. <P><STRONG>type: </STRONG> A category of data. For example, words, sentences, Booleans, and procedures are types. Some types overlap: All numbers are also words, for example. <P> <P><STRONG>variable: </STRONG> A connection between a name and a value. Variables can be <EM>global</EM> or <EM>local.</EM> <P><STRONG>vector: </STRONG> A primitive data structure that is mutable and allows random access. <P><STRONG>word: </STRONG> A sequence of characters, including letters, digits, or punctuation. Numbers are a special case of words. <P> <HR> <P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> <A HREF="appendix-funlist.html"><STRONG>BACK</STRONG></A> chapter thread <A HREF="appuindex.html"><STRONG>NEXT</STRONG></A> <P> <ADDRESS> <A HREF="../index.html">Brian Harvey</A>, <CODE>bh@cs.berkeley.edu</CODE> </ADDRESS> </BODY> </HTML>