ALGOrithmic Language, an obsolete (fl. 1960) high-level language which seems to have figured prominently in the minds of language designers in the 1970s.
(n) that where all elements of a form are first evaluated to determine their values before the operator is applied to the operands. This is how ordinary functions calls are evaluated in Scheme. See also strict. Contrast normal-order evaluation.
(n) the property of a language that it allows nested definitions. SICP-1.1:8
(n) a data structure that holds a single value, as a pointer, a reference, or (especially) a handle does in other languages. Although not standardized and for the most part unnecessary in Scheme, boxes are useful in algorithms where one would like to store (the location of) something in several places before one knows what the value is.
(v) at an implementation level, to represent a value in a way that includes information about its type. See boxing.
see FOLDOC:call-by-name, FOLDOC:call-by-need, or FOLDOC:call-by-value. See also normal-order evaluation, lazy evalution, or applicative-order evaluation, respectively.
(v) to redefine a variable; to bind a free variable. If done inadvertantly, this can be a bug. SICP-1.1:8
(n) a FOLDOC:Church integer. In the lambda calculus, everything is a function, even the numbers.
(n) an entity that can be called as a function, but that includes its surrounding environment; typically this surrounding environment is state that is modified by calling the closure. What lambda returns.
(n) a function with no free variables; one of the primitive functions on which the variant of lambda calculus known as combinatory logic is built. Note that, in the lambda calculus, functions take only one argument, so a combinator operates on exactly one piece of data.
(n) an expression evaluated entirely for its side effect.
(n) a function created by marking points in an arbitrary expression as the composable continuation's beginning (marked with shift) and end (with reset). (The operands go in at the beginning and the result is produced at the end.) Also called a delimited continuation or a partial continuation. See composable-continuations-tutorial.
(n) (1) the "rest of the program" that a called function will return its value to. (2) In Scheme, a value that captures the state of the rest of the program, can be assigned to a variable, and can be called as if it were a function of (usually) one argument (since generally functions are constrained to return one value). That is, evaluating a continuation is equivalent to returning from the function whose continuation it is. See reify, continuations.
(n) the use, usually as an intermediate step in compiliation, of a representation where every function takes (and is passed) its continuation (think "return address") explicitly.
(abbrv) continuation passing style.
(v) to convert a function of n arguments into a function which takes n - k (usually n - k is 1, because this is how functions are defined in the lambda calculus) argument(s) and returns a function which takes k arguments. The returned function will complete the calculation. (Or, again, the returned function itself will have been curried if necessary so that all functions take only one argument.) Thus, if (f x y) => z, then also ((f-curried x) y) => z.
(n) (presumably from the shift and reset delimiters which mark where computation begins and ends.) See composable continuation.
(adj) see WikiPedia:Datatype.
(n) the set of variable names and their values (or the locations of these values) in effect at a given point in the program. See SICP-1.1:2.
(adj) of a number, representable entirely with integers, such as 2, 11/10, 1+11/2i, and not the result of inexact operations or ingredients. Of an operation, capable of preserving the property of exactness, such as +, -, *, and hopefully /. See exactness.
(n) See y-combinator and Y combinator below. So-called because (f (Y f)) => (Y f) (? or so they say).
(n) in Scheme, stuff set off by parentheses, that is, (operator operand1 ...). Special forms are identified by their operator, such as "the set! form".
(n) in a function, neither a formal parameter nor a local variable; a variable defined (if anywhere) in the surrounding environment. See closure-vs-combinator.
(adj) of a number, not guaranteed to be exact; a floating point such as 2.0. Of an operation, not preserving exactness, such as (in all known implementations) sqrt.
(n) "one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate." -- SICP-1.2:1
(n) a formal system (a set of symbols and rules for manipulating them) that represents an extremely simple (yet Turing complete) programming language. (How does this apply to Scheme?) (A good introductionary paper)
(n) not evaluating an operand until its value is needed, but then only once. Has the advantages of normal-order evaluation without its inefficiencies. See also lazy evaluation, call by need.
(n) the property of a language that variables can get their values (bindings?) from definitions which enclose the procedure in which they are defined. See block structure. SICP-1.1:8
(n) ? the design and implementation of macro systems.
(n) ? the design and implementation of primitive language elements used in the construction of macro systems.
(v) to cache the value of an expression after evaluation (in particular, when a promise is forced) so that subsequent requests for evaluation do not require recomputing the value.
(n) see monadic-programming.
(n) an expression which uses only basic, primitive functions which cannot be further reduced.
(n) So-called because the expression is notionally reduced -- that is, re-expressed in terms of simpler operations -- to normal form -- that is, as far as possible -- before evaluation. Compare lazy evaluation, contrast applicative-order evaluation.
(n) A collection of things and their relationship between each other. Used for specifying knowledge for an AI.
(n) a thing on which an operator operates; an (unevaluated) expression that would evaluate to an argument; the second and subsequent elements of a form.
(n) (presumably in contrast to "full" continuations which contain the universe, partial continuations only go as far as the marked place -- the place marked with reset.) Also called a delimited continuation or composable continuation. See composable continuation.
(n) ? a high-level description of the effect of a procedure. (SICP-1.1:8)
(n) an expression that has been encapsulated without having been immediately evaluated. What delay returns and force applies to.
(adj) of a procedure, defined in terms of itself. (SICP-1.1:8)
(n) one that builds up a chain of deferred operations -- SICP-1.2:1, contrast iterative process.
(v) to re-express in terms of more primitive operations.
(v) ? the opposite of reify; to call a continuation.
(v) to make something (specifically, a continuation or partial continuation) assignable to variable. What call-with-current-continuation does.
of a name, "the set of expressions for which a binding defines [that] name." -- SICP-1.1:8
(n) a form that is not evaluated in the ordinary (applicative-order) way for function calls, e.g., one whose operator is set!, if, (or others,) or a macro.
(adj) see WikiPedia:Datatype.
(adj) of a form, evaluating all its arguments. All functions in Scheme are strict, but macros need not be. See also applicative-order evaluation.
(n) a macro that includes its syntactic environment, analogous to the way a closure includes its environment, thus avoiding (or more generally, controlling) the capture of syntax elements when it is used. See syntactic-closures.
(n) one that occurs as the last call in a procedure.
(n) avoiding use of the stack by replacing JSRs with JMPs where appropriate (so to speak). A fundamental property of Scheme that allows an iterative process to be expressed as a recursive procedure.
(adj) (1) of a language implementation, having the property that a procedure defined in terms of itself (recursive) can nevertheless describe a process requiring only constant space (an iterative process -- SICP-1.2:1), that is, one that performs tail call optimization. (2) Of a procedure, such a one, so called because the recursive call appears last in the procedure.
(abbrv) tail call optimization
(n) (explicit renaming transformer) the kind of macro that ?
(n) a function (a closure) that takes no arguments. (An expression e can be turned into a thunk by wrapping it in a lambda, as (lambda () e).)
(adj) of a programming language, capable of computing anything that can be computed (if run on a machine with enough memory), and thus equivalent to a Turing machine.
(n) the function that takes as its argument a nonrecursive function, say, f, that in turn takes a function as an argument -- call the function argument to f, g -- and returns (i.e., (Y f) returns) a function that is like f but calls itself where f would call g. A purely functional way to implement recursion. See y-combinator.
(interj) what pinheads say when they're excited. See understanding Zippy.