glossary


Michael-Micek

This is probably redundant... or impossible/useless The idea is of course to give concise but clear definitions in not-too-technical language of terms mentioned in #scheme-on-freenode. Redundant because this whole site is basically about this task and impossible because it seems so to convey these ideas to a person new to them in a sentence, however simple they seem once they are understood. The Free On-Line Dictionary Of Computing has longer definitions for many of these, but their examples are generally in Haskell. Wikipedia - Computer Science is another source.

Note: I use the term "function" here frequently but do not define it. Schemers would generally use the more general term "procedure", but I feel "function" is more intuitive, which is why I don't define it.

If you feel you have a more intuitive definition, or a technical correction please put it in a quote after the definition. Replace a definition only if you know that you have a more correct definition that is as intuitive.

But edit-hint feel free to add definitions or fill in empty definitions, with the understanding that I will feel free to edit them.

At the moment I'm trying to follow a form where I give a general definition first and then where it comes up in scheme, and then other references. I expect the reader to mentally insert, if the term is a (n)oun, "A [term] is"; if a (v)erb, "To [term] is"; if an (adj)ective, "[term] means, when used as a description". I recognize that this may not be the most intuitive form, but I think it follows the usage in dictionaries. Please follow the form for now unless you are willing to commit to maintaining the entire glossary.

And now I shall quote Polonius: Brevity is the soul of wit.


Algol

ALGOrithmic Language, an obsolete (fl. 1960) high-level language which seems to have figured prominently in the minds of language designers in the 1970s.

applicative-order evaluation

(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.

block structure

(n) the property of a language that it allows nested definitions. SICP-1.1:8

bound variable

(n) SICP-1.1:8

box

(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.

box

(v) at an implementation level, to represent a value in a way that includes information about its type. See boxing.

call by

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.

capture

(v) to redefine a variable; to bind a free variable. If done inadvertantly, this can be a bug. SICP-1.1:8

church numeral

(n) a FOLDOC:Church integer. In the lambda calculus, everything is a function, even the numbers.

closure

(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.

docl

A closure is something that can be called as a function. However, it includes the surrounding set of variables as data, in addition to any arguments passed to it. These variables are a sort of state, and that state is modified when the closure is called as a function. When you evaluate a lambda expression, you are creating a closure.

Note that calling the closure does not necessarily modify its state.



combinator

(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.

docl

A combinator is a type of function that does not use any of the free variables available, but only uses those passed to it as arguments. This makes it a simple approximation of the lambda calculus.

A combinator isn't a simple approximation of the lambda calculus, combinatory logic is a variant of the lambda calculus that starts with only a few combinators rather than the rule called abstraction.

Also, free variables aren't said to be "available"... a free variable is used in a function with the assumption it will be defined elsewhere.

Hm.

a function that refers only to its argument(s), ... hm



command

(n) an expression evaluated entirely for its side effect.

composable continuation

(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.

continuation

(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.

docl

When you execute a function, you have to keep track of where you called it from. This is kept in a sort of a variable, called the continuation. To call the continuation is to return from the function.

The distinction needs to be made between the fact that every called procedure has a continuation and that you can capture (reify) this continuation and assign it to a variable... I've tried to do that above, now.

Although it is true that calling a continuation has the effect of returning from the function whose continuation it is, it is not true that "you" have to keep track of it, unless "you" are the interpreter, and even then, a continuation is not just a return address, but the entire state of the program.



continuation passing style

(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.

CPS

(abbrv) continuation passing style.

curry

(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.

delimited continuation

(n) (presumably from the shift and reset delimiters which mark where computation begins and ends.) See composable continuation.

denotation

(n)

dynamically typed

(adj) see WikiPedia:Datatype.

environment

(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.

exact

(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.

fixed point combinator

(n) See y-combinator and Y combinator below. So-called because (f (Y f)) => (Y f) (? or so they say).

form

(n) in Scheme, stuff set off by parentheses, that is, (operator operand1 ...). Special forms are identified by their operator, such as "the set! form".

free variable

(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.

inexact

(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.

iterative process

(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

lambda calculus

(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)

late-binding

(adj)

lazy evaluation

(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.

lexical scoping

(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

macrology

(n) ? the design and implementation of macro systems.

macrology, low-level

(n) ? the design and implementation of primitive language elements used in the construction of macro systems.

memoize

(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.

monad

(n) see monadic-programming.

normal form

(n) an expression which uses only basic, primitive functions which cannot be further reduced.

normal-order evaluation

(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.

ontology

(n) A collection of things and their relationship between each other. Used for specifying knowledge for an AI.

operand

(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.

partial continuation

(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.

procedural abstraction

(n) ? a high-level description of the effect of a procedure. (SICP-1.1:8)

promise

(n) an expression that has been encapsulated without having been immediately evaluated. What delay returns and force applies to.

recursive

(adj) of a procedure, defined in terms of itself. (SICP-1.1:8)

recursive process

(n) one that builds up a chain of deferred operations -- SICP-1.2:1, contrast iterative process.

reduce

(v) to re-express in terms of more primitive operations.

reflect

(v) ? the opposite of reify; to call a continuation.

reify

(v) to make something (specifically, a continuation or partial continuation) assignable to variable. What call-with-current-continuation does.

scope

of a name, "the set of expressions for which a binding defines [that] name." -- SICP-1.1:8

special form

(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.

statically typed

(adj) see WikiPedia:Datatype.

strict

(adj) of a form, evaluating all its arguments. All functions in Scheme are strict, but macros need not be. See also applicative-order evaluation.

syntactic closure

(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.

tail call

(n) one that occurs as the last call in a procedure.

tail call optimization

(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.

tail recursive

(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.

TCO

(abbrv) tail call optimization

transformer, ER

(n) (explicit renaming transformer) the kind of macro that ?

thunk

(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).)

Turing complete

(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.

Y combinator

(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.

yow

(interj) what pinheads say when they're excited. See understanding Zippy.


category-learning-scheme