diff options
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch27/glossary.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch27/glossary.html | 433 |
1 files changed, 433 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch27/glossary.html b/js/games/nluqo.github.io/~bh/ssch27/glossary.html new file mode 100644 index 0000000..23fedfe --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch27/glossary.html @@ -0,0 +1,433 @@ +<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> |