From j.oregan@cs.ucc.ie Thu Aug 19 18:50:39 1999 MIME-Version: 1.0 Content-type: TEXT/PLAIN; charset=US-ASCII X-Coding-System: undecided-unix Return-path: Envelope-to: dbh@doc.ic.ac.uk Delivery-date: Thu, 19 Aug 1999 18:50:39 +0100 X-Authentication-Warning: exile.ucc.ie: oregan owned process doing -bs Date: Thu, 19 Aug 1999 18:39:37 +0100 (IST) From: "John O'Regan" X-Sender: oregan@exile.ucc.ie To: Denis Howe Subject: musty old file MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear Denis, I was clearing out an old account and found the file included below. It dates from 1992. I thought you might like to see it in case you're in any way nostalgic, yours sincerely, John O'Regan. PS: FOLDOC is an excellent service. Keep up the good work! - - - - Programming Languages, Architectures and Domain Theory Glossary Updated 29-Oct-1992 Copyright (c) Denis Howe 1992 You may copy this file freely but you must not charge for it and you must not remove this notice. All corrections and additions gratefully accepted. Denis Howe Notation Where possible ASCII characters are used to represent mathematical symbols. Some LaTeX commands (beginning with "\") are used. They are described in the glossary in their alphabetic positions. \ A lower-case lambda. Used in lambda calculus to define functions. Used in this document to introduce LaTeX commands for certain symbols. Abstract interpretation A partial execution of a program which gains information about the control structure and flow of information without performing all the calculations. Algol Algorithmic Language. One of the first structured procedural languages, designed about 1960. Alice Parallel graph rewriting machine developed by Imperial College, Edinburgh University and ICL. Alpha conversion In lambda calculus, the renaming of a formal parameter in a lambda abstraction without changing the meaning of the abstraction. For example: \x. x+1 <--> \y . y+1 If the argument to a lambda abstraction contains instances of the formal parameter of the lambda abstraction then it is necessary to rename the parameter before applying the lambda abstraction. See also reduction. Amber A functional programming language which generalises ML's type system. Antisymmetric A relation R is antisymmetric if, for all x and y, x R y and y R x => x = y. APL A Programming Language. A procedural language based on composition of functions. Applicative language Synonym for "functional language". Often used loosely for any declarative language though logic programming languages are declarative but not applicative. Applicative order reduction Under this evaluation strategy, an expression is evaluated by repeated. ly evaluating its leftmost innermost redex. This means that a function's arguments are evaluated before the function is applied. This method will not terminate if a function is given a non-terminating expression as an argument even if the function is not strict in that argument. Also known as call by value since the values of arguments are passed rather than their names. This is the evaluation strategy used by ML, Scheme, Hope, and most procedural languages such as C and Pascal. See also Strict, Normal order reduction, Parallel reduction. Assignment Storing the value of an expression in a variable. Assignment is not allowed in functional languages, it is a side effect which could cause a function to return different results for the same arguments depending on the value of a variable. In a functional language assignment of different values to a variable would be replaced by a reference to a list of values. See also Single assignment, Zero assignment. Atomic An atomic data type is one which has a flat domain as its usual interpretation (all elements are equally defined). Integers and booleans are two examples. Backtracking Algorithm used by Prolog to find all possible ways of proving a goal. Backward chaining In backward chaining one attempts to prove a goal by recursively braking down a goal into sub-goals and trying to prove these until facts are reached. Facts are goals with no sub-goals which are therefore always true. See also Forward chaining, Prolog. BCPL A forerunner of C. Bernstein condition Processes cannot execute in parallel if one effects values used by the other. Nor can they execute in parallel if any subsequent process uses data effected by both, ie. whoses value might depend on the order of execution. Beta conversion In lambda calculus, the rule for beta conversion says that a lambda abstraction applied to an argument is equivalent to an instance of the body of the lambda abstraction with free occurrences . of the formal parameter in the body replaced by copies of the argument. For example: (\x . x+1) 4 --> 4+1 This is an example of beta reduction. The other kind of beta conversion is the reverse of this and is called beta abstraction. An example of beta abstraction would be: 4+1 <- (\x . + 4 1) 4 See also Reduction. \big Prefix of several LaTeX commands implying a larger symbol. See the command without "big". Often used to convert a dyadic operator into a function which operates on a set. Eg. \sqcup, \bigsqcup. Bijection A function is bijective or a bijection or a one-to-one correspondence if it is both injective (no two values map to the same value) and surjective (for every element of the codomain there is some element of the domain which maps to it). Only bijective functions have inverses f' where f(f'(x)) = f'(f(x)) = x. See also Injection, Surjection. Bipartite See complete graph. Bottom The least defined element in a given domain. Usually written as an inverted T. Bound variable A bound variable in a function definition represents a dummy argument which will be replaced by the actual argument when the function is called. In logic a bound variable is a quantified variable. See also Free variable, Quantifier, Scope. Bracket abstraction The result of using bracket abstraction on term T with respect to variable v, written as [v]T, is a term containing no occurences of v and denoting a function f such that f v = T. This defines the function (\v . T). Using bracket abstraction and currying we can define a language without bound variables in which the only operation is monadic function application. Call by name An evaluation strategy where the address of an argument variable is passed to a function or procedure rather than the value of that variable. Execution of the function or procedure may have side effects on the actual argument as seen by the caller. See also Call by value, Call by need. Call by nee. d See Lazy evaluation. Call by value An evaluation strategy where arguments are evaluated before the function or procedure is entered. Only the values of the arguments are passed and changes to the arguments within the called procedure have no effect on the arguments as seen by the caller. See Applicative order reduction, Strict evaluation. Cambridge Lisp A flavour of Lisp using BCPL. Sources owned by Fitznorman partners. Church-Rosser Theorem This property of a reduction system states that if an expression can be reduced by zero or more reduction steps to either expression M or expression N then there exists some other expression to which both M and N can be reduced. This implies that there is a unique normal form for any expression since M and N cannot be different normal forms because the threorem says they can be reduced to some other expression and normal forms are irreducible by definition. It does not imply that a normal form is reachable, only that if reduction terminates it will reach a unique normal form. Clean A lazy higher-order functional programming language based on functional graph rewriting systems. Closure In reduction systems, a closure is a data structure that holds an expression and an environment of variable bindings in which that expression is to be evaluated. The variables may be local or global. Closures are used in implementing lazy evaluation to represent unevaluated expressions. In a real implementation, both expression and environment are represented by pointers. In domain theory, given a poset D and a subset X \subseteq D, the upward closure of X in D, written \uparrow_{D} X, is the union over all x in X of the sets of all d in D such that x \sqsubseteq d. The downward closure is similar but with d \sqsubseteq x. Thus the upward (downward) closure of X contains all of X plus any greater (lesser) element of D. Codomain A set containing the values of a function applied to elements of its . domain (qv). Combination In the theory of combinators a combination denotes an expression in which function application is the only operation. Combinator A function with no free variables. A system for reducing the operational notation of logic, mathematics or a functional language to a sequence of modifications to the input data structure. First introduced by Curry and Feys in 1958. A term is either a constant or variable or of the form A B denoting the application of term A (a monadic function) to term B. Juxtaposition associates to the left in the absence of parentheses. All combinators can be defined from two basic combinators - S and K. These two and a third, I are defined thus: S f g x = f x (g x) K x y = x I x = x Other combinators were added by David Turner in 1979 when he used combinators to implement SASL: B f g x = f (g (x) C f g x = f x g S' c f g x = c (f x) (g x) B* c f g x = c (f (g x)) C' c f g x = c (f x) g See Supercombinators, Curried function. Common Lisp A dialect of Lisp defined by a consortium of companies brought together by the Defence Advanced Research Projects Agency (DARPA). Companies included Symbolics, Lisp Machines Inc., Digital Equipment Corp., Bell Labs., Xerox, Hewlett-Packard, Lawrence Livermore Labs., Carnegie-Mellon Univ., Stanford Univ., Yale, MIT and UC Berkeley. Based on ZetaLisp, it is lexically scoped but can be dynamically scoped. According to Martin Evans it is big and clumsy, not very efficient and there is no DIY kit available. Complete graph A graph which has a link between every pair of nodes. A complete bipartite graph can be partitioned into two subsets of nodes such that each node is joined to every node in the other subset. Complete lattice A lattice in which all subsets have a meet and a join. A lattice is a poset in which all finite subsets have a meet and a join whereas a complete lattice also has meets and joins for infinite subsets. Note that e. very finite lattice is complete. Complete partial ordering (CPO) A CPO or Domain is a partial ordering which includes a least element, bottom (\perp) and in which any increasing sequence has a least upper bound. Connected graph A set of nodes (eg. processors) connected by links such that there is a path between any pair of nodes. Connective An operator used in logic to combine two logical formulas. See First order logic. Conservative evaluation Under this parallel evaluation strategy, no evaluation is started unless it is known to be needed. Opposite of speculative evaluation. Constant folding A compiler optimisation technique where constant subexpressions are evaluated at compile time. This is usually only applied to built-in numerical and boolean operators whereas partial evaluation is more general in that expressions involving user-defined functions may also be evaluated at compile time. Continental drift In 1980 Professor David Turner remarked that KRC ran "at the speed of the continental drift". Continuation A function which is passed as an argument to some other function, f say. When f would normally return a result instead, it calls the continuation with the result as an argument. Some examples: normal --> continuation passing square x = x * x square x k = k (x*x) g (square 23) square 23 g (square 3) + 1 square 3 ( \s . s+1 ) CPS Continuation passing style. The style of programming where every function takes a continuation as an argument. See continuation. C-Prolog See Prolog. Critical section A non-reentrant piece of code that can only be executed by one process at a time. It will usually terminate in finite time and a process will only have to wait a finite time to enter it. CSP Communicating Sequential Processes. Hoare's precursor to OCCAM. Curried function A function of several arguments can be transformed into a function of one argument which returns another function of one argument. . Eg. in Haskell we can define: average :: num -> (num -> num) (The parentheses are optional). A partial application of average, average 4 returns a function which averages its argument with 4. Named after the logician Haskell B Curry but first refered to in M Schoenfinkel, "Uber die Bausteine der mathematischen Logik", Mathematische Annalen. Vol 92 (1924). Currying See Curried function. DACTL Declarative Alvey Compiler Target Language. Intermediate language used in the Flagship project. Based on a form of graph rewriting which can be used to implement functional, logic and imperative languauges. Data abstraction Implementation of a data type in such a way that operations on it can be defined in terms of lower level operations without knowing the details of how it is stored or how the low level operations are implemented. Data driven A data driven architecture/language performs computations in an order dictated by data dependencies. Two kinds of data driven computation are data flow and demand driven. Data flow A data flow architecture/language performs a computation when all the operands are available. Eg. MIT's VAL machine. See also Demand driven. Data flow analysis The order of execution in a data-flow language is determined solely by dependencies between different data. Data-flow analysis is the analysis needed to determine those dependencies. For example, given 1. X = A + B 2. B = 2 + 2 3. A = 3 + 4 a data-flow analysis would find that 2 and 3 must be evaluated before 1. Since there are no data dependencies between 2 and 3, they may be evaluated in parallel. Declarative language A general term for relational languages and functional languages, as opposed to imperative languages. Imperative languages specify procedures for solving problems, while in declarative languages you specify what kind of solution you are seeking. For example, to find the cube of 7 in an imperative language, you might perform the. following CUBE = 1 CUBE = CUBE * 7 CUBE = CUBE * 7 CUBE = CUBE * 7 In a declarative language you would define what cube means and then ask what the cube of 7 is. Deductive tableau A theorem proof system consisting of a table whose rows contain assertions or goals. Variables in assertions are implicitly universally quantified and variables in goals are implicitly existentially quantified. The declarative meaning of a tableau is that if every instance of every assertion is true then some instance of at least one of the goals is true. Definite clause See Horn clause. Definite sentence A collection of definite clauses. Degree (or valency) of a node in a network is the number of links joined to it. Delta conversion In lambda calculus, delta reduction replaces a mathematical function applied to the required number of argument expressions by its result. Eg. plus 2 3 --> 5. See Reduction. Demand driven A demand driven architecture/language performs computations when the result is required by some other computation. Eg. Imperial College's ALICE running HOPE. See also Data flow, Lazy evaluation, Reduction. Diameter of a graph is the maximum value of the minimum distance between any two nodes. Directed graph (or digraph) A graph with one-way links. Display A data structure used in Algol implementations containing pointers to variables which are kept on the stack. Distributive lattice A lattice for which the meet and join operators distribute over one another so that a join (b meet c) == (a meet c) join (a meet b) and similarly with meet and join interchanged. Domain In the theory of functions, the set of argument values for which a function is defined. Downward closure See Closure. Dynamic programming Dynamic scoping If the definition of procedure 'P' contains a variable 'v' then procedure 'Q' called by P can refer to v by name without it being declared as an argument. Opposite of lexical scoping. A common implem. entation of dynamic scoping is shallow binding. Eager evaluation Under an eager evaluation strategy, evaluation of some function arguments is started before their value is required. Opposite of Lazy evaluation. See also Speculative evaluation, Conservative evaluation, Strict evaluation. Elephant Large, grey, four-legged mammal. EQLOG Equality, types and generic modules for logic programming. A language using Horn clauses. Goguen J.A., Meseguer J. Eta conversion In lambda calculus, the eta conversion rule states \x . f x <--> f provided x does not occur free in f and f is a function. See also Reduction. Evaluator Geoff Burn defines evaluators E0, E1, E2 and E3 which when applied to an expression, reduce it to varying degrees. E0 does no evaluation, E1 evaluates to weak head normal form (WHNF), E2 evaluates the structure of a list, ie. it evaluates it either to NIL or evaluates it to a CONS and then applies E2 to the second argumant of the CONS. E3 evaluates the structure of a list and evaluates each element of the list to WHNF. Extensional equality Functions, f and g are extensionally equal if and only if f x = g x for all x. Two functions may be extensionally equal but not interconvertible. Eg. \x . x+x <-/-> \x . 2*x. Extensionality See Extensional equality. FGL Function Graph Language (or possibly Flow-Graph Lisp). First order logic The language describing the truth of mathematical formulas. Formulas describe properties of terms and have a truth value. The following are atomic formulas: True False p(t1,..tn) where t1,..,tn are terms and p is a predicate. If F1, F2 and F3 are formulas and v is a variable then the following are compound formulas: F1 ^ F2 conjunction - true if both F1 and F2 are true, F1 V F2 disjunction - true if either or both are true, F1 => F2 implication - true if F1 is false or F2 is true, F1 is the antecedant, F2 is the consequent (sometimes written with a thin arrow), F1 . <= F2 true if F1 is true or F2 is false, F1 == F2 true if F1 and F2 are both true or both false (normally written with a three line equivalence symbol) ~F1 negation - true if f1 is false (normally written with a not symbol). (Av)F universal quantification - true if F is true for all values of v (normally written with an inverted A). (Ev)F existential quentification - true if there exists some value of v for which F is true. (Normally written with a reversed E). The operators ^ V => <= == ~ are called connectives. A and E are quantifiers whose scope is F. A term is a mathematical expression involving numbers, operators, functions and variables. Fixed point The fixed point of a function, f is any value, x for which f(x) = x. A recursive function can be expressed as the fixed point of a higher order function, eg. FAC = \n . (... FAC ...) = (\f . (\n . (... f ...))) FAC = H FAC where H = \f . (\n . (... f ...)) FAC is a fixed point of H. A function may have more than one fixed point. See least fixed point. Fixed point combinator (Y) Y is a function which takes a function and returns the fixed point of that function. It has the property that Y H = H (Y H) Y can be defined as a non-recursive lambda abstraction: Y = (\h . (\x . h (x x)) (\x . h (x x))) Fixpoint Fixed point. Flat A flat domain is one where all elements except bottom are incomparable (equally well defined). Eg. the integers. Formal methods Referentially transparent languages are amenable to symbolic manipulation allowing program transformation (eg. clear inefficient specification -> obscure efficient program) and proof of correctness. Formula In logic, a sequence of symbols representing terms, predicates, connectives and quantifiers which is either true or false. Forth Interpreted stack-based language where programs are built from "words" (procedures) which are defined in terms of other words, down to a small se. t of predefined words. Forward chaining A data-driven technique used in constructing goals or reaching inferences derived from a set of data. See also Backward chaining. FP Functional programming. Also a functional language which stresses functional level reasoning. FP2 Functional Parallel Programming. A language combining functional and parallel programming through a unified approach. Every object is a term and every computation is done by rewriting. Free variable 1. In a function, a variable which is not an argument of the function. 2. In logic, a variable which is not quantified. See also Bound variable, Quantifier, Scope. Franz Lisp A dialect of Lisp developed by DEC, (source in C) often distributed with Berkley UNIX. Full laziness An optimisation of lambda lifting where maximal free expressions are shared in an attempt to minimise the amount of recalculation. Function If D and C are sets (the domain and codomain (qv)) then a function f : D -> C is a subset of D x C such that 1. for each d in D there exists c in C such that (d,c) in f. 2. for each d in D, c1 and c2 in C, if both (d,c1) in f and (d,c2) in f then c1 = c2. This says that the function is uniquely defined for every element of D. Functional A higher order function. Function Graph Language (FGL) Used as the machine language for the AMPS (Applicative Multi-Processing System) proposed by Robert Keller, Gary Lindstrom and Suhas Patil at the University of Utah. Functional language A functional language consists of, reasonably enough, functions and arguments to those functions that uniquely identify the program output. For example, plus(4,5) returns 9 and only 9. This implies that there are no side-effects to function calls. The order of evaluation is irrelevant in a functional language. Hope and FP are examples of functional languages. Garbage collection The process by which no longer used storage is reclaimed during the evaluation of an expression in a ce. ll and pointer based memory system. In a system like Lisp which uses dynamic storage allocation and where expressions are represented as graphs containing pointers to cells or similar data structures it is necessary to reclaim space used by subexpressions but which is no longer referenced or pointed to by anything. The three main methods are: 1. Mark-sweep Each cell has a bit reserved for marking which is clear initially. During garbage collection all active cells are traced from the root and marked. Then all cells are examined. Unmarked cells are freed. 2. Reference count Each cell contains a count of the number of other cells which point to it. If this count reaches zero the cell is freed and its pointers to other cells are deleted. 3. Copying Memory is divided into two spaces. Garbage collection involves copying active cells from one space to the other and leaving behind an invisible pointer from the old position to the new copy. Once all active cells have been copied in one direction, the spaces are swapped and the process repeated in the opposite direction. GHC Guarded horn clauses. Graph A collection of nodes and links. See also connected graph, degree, directed graph, Moore bound, regular graph. Graph reduction An expression is represented as an inverted tree. Each node represents a function call and its subtrees represent the arguments to that function. Subtrees are replaced by the expansion or value of the function they represent. This is repeated until the tree has been reduced to a value with no more function calls. Graph reduction has the advantage that common subexpressions are represented as pointers to a single instance of the expression which is only reduced once. See Lazy evaluation, String reduction. Graph rewriting system An extension of a term rewriting system where terms are replaced by directed graphs to avoid duplication of work by sharing expressions. Greatest lower bound (GLB) Th. e dual to Least upper bound. The greatest lower bound or meet of two elements, a and b, written a \sqcap b, is an element c such that c \sqsubseteq a and c \sqsubseteq b and if there is any other lower bound c' then c' \sqsubseteq c. The greatest lower bound of a set S, written \bigsqcap S, is the greatest element b such that for all s \in S, b \sqsubseteq s. Also known as the meet. GRIP Graph Reduction In Parallel. Simon Peyton Jones's GRIP machine built at UCL, now at Glasgow. Many processors (68020 or other) on Futurebus with intelligent memory units. Guard In functional programming, a boolean expression appended to a function definition specifying when (for what arguments) that definition is appropriate. In (parallel) logic programming, a boolean expression which is used to select a clause from several alternative clauses. See Guarded Horn Clauses. Guarded horn clauses A parallel dialect of Prolog in which each clause has a guard. When several clauses match a goal, their guards are evaluated in parallel and the first clause whose guard is found to be true is used and others are rejected. Head normal form In graph reduction, an expression is in head normal form if its top level is either a variable, a data item or a function with insuffucuent arguments, ie. the top level is irreducible. See also Normal form, Weak head normal form. Help (Help Est un Lisp Paresseux - Help Is a Lazy Lisp). A lazy version of Scheme with strictness annotations by Thomas Schiex Higher order function A function that can take one or more functions as argument or return a function as its value. Eg. map in map f l which returns the list of values returned when function f is applied to each of the elements of list l. See also Curried function. Hope A functional programming language designed by Burstall, MacQuenn and Sannella at Edinburgh. A large language supporting user defined prefix, infix or disfix operators. Hope . has polymorphic typing and allows overloading of operators which requires explicit type declarations. Hope+ An extension of Hope implemented in the Flagship project. Hope+ has vectors, real numbers, best fit pattern matching and lazy data constructors. It has an I/O system which is both referentially transparent and capable of handling all common I/O tasks such as terminal and file I/O, signal handling, interprocess communications. Horn clause Also known as a definite clause. A set of atomic literals with one positive literal. Usually written L <- L1, ..., Ln where n>=0. If L is false the clause is regarded as a goal. Horn clauses can express a subset of statements of first order logic. ID Irvine Dataflow language. IDEAL Ideal DEductive Applicative Language A language by Pier Bosco and Elio Giovannetti combining Miranda and Prolog. Function definitions can have a guard condition (introduced by ":-") which is a conjunction of equalities between arbitrary terms, including functions. These guards are solved by normal Prolog resolution and unification. At present (Nov '86) it is compiled into C-Prolog but eventually will be compiled to K-leaf. Image The image (or range) of a function is the set of values of that function applied to all elements of its domain. So, if f : D -> C then the set f(D) = { f(d) | d in D } is the image of D under f. The image is a subset of C, the codomain (qv). \in A lower case epsilon. In set theory, the "is an element of" relation. Injection A function, f : A -> B, is injective or one-one, or is an injection, if for all a,b in A, f(a) = f(b) => a = b. This means that no two elements of A map to the same element of B (contrast many-to-one). Sometimes called an embedding. Only injective functions have left inverses f' where f'(f(x)) = x or f'. f = i, the identity function since, if f were not an injection, there would be elements of B for which the value of f' was not unique. See also Bijection, . Surjection. InterLisp A dialect of Lisp developed in 1967 by Bolt, Beranek and Newman (Cambridge, MA) emphasising user interfaces. Currently supported by Xerox PARC. J A functional programming language by Kenneth Iverson. Referred to as "an exciting advance in programming languages" in a posting to comp.lang.functional from Eugene E McDonnell 19 Septemper 1992. Join See Least upper bound. KRC A functional programming language designed by Professor David Turner. Lambda calculus The basis of Lisp and functional programming languages. A branch of mathematical logic dealing with the application of functions to their arguments. The pure lambda calculus contains no constants - neither numbers nor mathematical functions such as plus and is untyped. Constants and types are commonly added to make the calculus more useful for describing functional programs. See Lambda expression, Reduction. Lambda expression An expression in the lambda calculus denoting an unnamed function, a variable or (optionally) a constant. A function begins with a lower-case lambda (represented as "\" in this document), followed by a variable name, a full stop and a lambda expression (the body). The body is taken to extend as far to the right as possible so, for example an expression, \x . \y . x+y is read as \x . (\y . x+y). Application is represented by juxtaposition so (\x . x) 42 represents the identity function applied to the constant 42. Lambda expressions in Haskell are written with "->" instead of "." eg. \x -> x Last call optimisation Normally when procedure A calls procedures B, C, .., Z, the environment of procedure A is only discarded when procedure Z returns and procedure A itself terminates. Using last call optimisation, A's environment is discarded as Z is called. This allows arbitrarily deep nesting of procedure calls without consuming memory to store useless environments. A special case of this is tail. recursion optimisation where the last procedure called is the calling procedure itself. Lattice In domain theory, a poset in which all finite subsets have a meet and a join. See also Complete lattice Lazy evaluation An evaluation strategy where an expression is evaluated only when some other expression needs its value (Normal order evaluation). Shared expressions are only evaluated once and the result is reused. This is often implemented by graph reduction. Lazy evaluation is one evaluation strategy which is used to implement non-strict functions. It allows functions to be defined which return an infinite list of results which are evaluated one at a time as needed. Opposite of Eager evaluation. See Full laziness. Lazy list A list whose elements are lazily evaluated. Ie. the list is only defined for those elements whose values are needed by the program, the tail is represented as a closure. LCF Least fixed point The least defined fixed point of a function. There can be many fixed points of a function but there is only one least fixed point. Least upper bound (LUB) The dual to greatest lower bound. The least upper bound of two elements a and b, written a \sqcup b, is an element c such that a \sqsubseteq c and b \sqsubseteq c and if there is any other upper bound c' then c \sqsubseteq c'. The least upper bound of a set S, written \bigsqcup S, is the least element b such that for all s \in S, s \sqsubseteq b. Also known as the join. Lenient evaluation Under a lenient evaluation strategy, [Traub, FPCA 89], all redexes are evaluated in parallel except inside the arms of conditionals and inside lambdas. Lexical scoping Variable names in a procedure, P are independent from names of free variables in procedures called by P. Opposite of Dynamic scoping. Lisp List processing. A language based on lambda calculus. Data objects in Lisp are lists and atoms. Lists may contain lists and atoms. Atoms are either numbers or symbol. s. Programs in Lisp are themselves lists of symbols which can be treated as data. Most implementations of Lisp allow functions with side-effects but there is a core of Lisp which is purely functional. See also Common Lisp, Franz Lisp, MacLisp, Portable Standard Lisp, InterLisp. Lispkit A functional programming language designed by Peter Henderson with Lisp syntax. Designed for portability. The Lispkit implementation is an extension to Landin's SECD machine that supports lazy evaluation. See also Stack environment control dump machine. List comprehension An expression in a functional language denoting the results of some operation on (selected) members of one or more lists. An example in Haskell: [ (x,y) | x <- [1 .. 6], y <- [1 .. x], x+y < 10] This returns all pairs of numbers (x,y) where x and y are elements of the list 1, 2, ..., 10, y <= x and their sum is less than 10. A list comprehension is simply "syntactic sugar" for a combination of applications of the higher order functions, concat, map and filter. For instance the above example could be written: filter p (concat (map f [1 .. 6])) where p (x,y) = x+y < 10 f x = map g [1 .. x] where g y = (x,y) According to a note by Rishiyur Nikhil , August 1992: The term itself seems to have been coined by Phil Wadler circa 1983-1985, although the programming construct itself goes back much further (most likely Jack Schwartz and the SETL language). The term "list comprehension" appears in the following: "The OL Manual" Philip Wadler, Quentin Miller and Martin Raskovsky Probably 1983-1985 (my copy is undated) and "How to Replace Failure by a List of Successes" FPCA September 1985, Nancy, France, pp 113-146 The earliest reference to the notation is in Rod Burstall and John Darlington's description of their language, NPL. David Turner subsequently adopted this notation in his languages SASL, KRC and Miranda, where he has ca. lled them "ZF expressions", set-abstractions and list-abstractions (in his 1985 FPCA paper [Miranda: A Non-Strict Functional Language with Polymorphic Types]). LML Lazy ML. ML with lazy semantics. A compiler, LMLC, based on the G-Machine was written at the Chalmers University of Technology by Thomas Johnsson and Lennart Augustsson. Locality (1). In sequential architectures programs tend to access data that has been accessed recently (temporal locality) or that is at an address near recently referenced data (spatial locality). This is the basis for the speed-up obtained with a cache memory. (2). In a multi-processor architecture with distributed memory it takes longer to access the memory attached to a different processor. This overhead increases with the number of communicating processors. Thus to efficiently employ many processors on a problem we must increase the proportion of references which are to local memory. Logic Programming See Prolog. LOGLisp A version of Prolog implemented by Robinson in Lisp which allows Prolog programs to call Lisp and vice versa. MacLisp A dialect of Lisp developed at MIT in 1966, known for its efficiency and programming facilities. MALI A memory for logic programming with real time garbage collection. Meet See Greatest lower bound. MIMD Multiple Instruction Multiple Data The class of parallel processor where many functional units perform different operations on different data. The term was invented by Flynn. See SIMD. Miranda A functional programming language and interpreter designed and sold by Professor David Turner's company, Research Software, Ltd.. It combines the main features of KRC and SASL with a strong type discipline similar to that of ML. The type of an expression is inferred from the source by the compiler but explicit type declarations are also allowed. Implemented for UNIX by Allan Grimeley, Computer Lab., UKC. ML Originally designed as part of the Edinburgh LCF . project. It was the first language to include polymorphic typing. It is now being significantly redesigned to produce Standard ML. See also Lazy ML. Monotonic In domain theory, a function f : D -> C is monotonic if for all x,y in D, x \sqsubseteq y => f(x) \sqsubseteq f(y). Moore bound An upper limit on the number of nodes in a regular graph of degree d>2 and diameter k: k N(d,k) <= d(d-1) - 2 ---------- d-2 Moore graph A graph which achieves the Moore bound. These are complete graphs, polygon graphs (regular, degree 2 graphs) and three others: (nodes, degree, diameter) = (10,3,2), (50,7,2) and the possible but undiscovered (3250,57,2). Most general unifier If U is the most general unifier of a set of expressions then any other unifier, V, can be expressed as V = UW, where W is another substitutiion. See Unification, Unifier. MultiLisp An extension of the Lisp dialect Scheme with additional operators and semantics for parallelism. Narrowing Negation by failure An extralogical feature of Prolog in which failure of unification is treated as establishing the negation of a relation. For example, if Ronald Reagan is not in our database and we asked if he was an american, Prolog would answer "no". Nondeterminism Normal form In reduction systems, a graph is in normal form when it contains no reducible expressions. See also Head normal form, Weak head normal form. Normal order reduction. Under this evaluation strategy an expression is evaluated by reducing the leftmost outermost redex first. This method will terminate for any expression for which termination is possible, whereas applicative order reduction may not. This method is equivalent to passing arguments unevaluated because arguments are initially to the right of functions applied to them. See Applicative order reduction. NPL A functional language designed by Rod Burstall and John Darlington. The language allowed certain sets and logic constructs . to appear on the right hand side of definitions, Eg. setofeven(X) <= <:x: x in X & even(x) :> The NPL interpreter evaluates the list of generators from left to right so conditions can mention any bound variables that occur to their left. The language is described in John Darlington, "Program Transformation and Synthesis: Present Capabilities", Research Report No. 77/43, Dept. of Computing and Control, Imperial College of Science and Technology, London September 1977. See also: List comprehension. Occam A language based on C A R Hoare's CSP. Named after William of Occam who propounded Occam's Razor - that entities should not be multiplied more than necessary. The Occam language was designed by David May to easily describe concurrent processes which communicate via one-way channels. It was developed to run on INMOS Transputer but compilers are available for Vax, Sun and Intel MDS, inter alia. The basic entity in Occam is the process of which there are four fundamental types, assignment, input, output, and wait. More complex processes are constructed from these using SEQ to specify sequential execution, PAR to specify parallel execution and ALT where each process is associated with an input from a channel. The process whose channel inputs first is executed. The fourth constructor is IF with a list of conditions and associated processes. The process executed is the one with the first true condition in textual order. OPS5 A production system used for knowledge representation. See production system. Order-embedding A function f : D -> C is order-embedding iff for all x,y in D, f(x) \sqsubseteq f(y) <=> x \sqsubseteq y. A function which is order-embedding is monotonic and one-to-one and an injection. Ordering A relation. See Partial ordering, Pre-order, Total ordering. Orwell A functional language. Overloading of operators Use of a single symbol to represent operators with different arguments, eg.. '-', used either, as a monadic operator to negate an expression, or as a dyadic operator to return the difference between two expressions. Another example is '+' used to add either integers or floating point numbers. Parallel reduction A form of applicative order reduction in which all redexes in an expression are reduced simultaneously. Variants include parallel outermost reduction and lenient reduction. See Normal order reduction. Paramodulation Partial evaluation An optimisation technique where the compiler evaluates some subexpressions at compile time. Eg. pow x 0 = 1 pow x n = if even n then pxn2 * pxn2 else x * pow x (n-1) where pxn2 = pow x (n/2) f x = pow x 5 Since n is known we can unfold the definition of pow at compile time giving: f x = x * x2 where x2 = x * x It is important that the partial evaluation algorithm should terminate. This is not guaranteed in the presence of recursive function definitions. For example, if partial evaluation were applied to the right hand side of the second clause for pow above, it would never terminate because the value of n is not known. A more subtle point is that partial evaluation might change the termination properties of the program. For example, if the expression (x * 0) was reduced to 0 it would terminate even if x (and thus x * 0) did not. Constant folding is a limited form of partial evaluation. Partial function A function which is not defined for all values of its arguments. Eg. f(x) = 1/x if x <> 0. Partial ordering A relation R is a partial ordering if it is reflexive, antisymmetric and transitive. See also Pre-order, Total ordering. In domain theory, if D is a set of values plus the undefined value (\perp) then we can define a relation \sqsubseteq on D by x \sqsubseteq y if x = \perp or x = y. The constructed set D x D contains the very undefined element, (\perp, \perp) and the not so undefined elements, (x, \perp) and (\perp, x). Th. e partial ordering on D x D is then (x1,y1) \sqsubseteq (x2,y2) if x1 \sqsubseteq x2 and y1 \sqsubseteq y2. The partial ordering on D -> D is defined by f \sqsubseteq g if f(x) \sqsubseteq g(x) for all x in D. Ie. f is not more defined than g if no application of f is more defined than the application of g to the same argument. Pattern matching A function is defined to take arguments of a particular type, form or value. When applying the function to its actual arguments it is necessary to match the type, form or value of the actual arguments against the formal arguments in some definition. \perp An inverted T. Used in domain theory to represent the least defined (undefined) element of a domain. Read as "bottom". Ping-pong An phenomenon which can occur in a multi-processor system with private caches where two processors are alternately caching a shared location. Each time one writes to it it invalidates the other's copy. Polymorphic typing Concept developed by Hindley and Milner allowing types such as list of anything. Eg. in Haskell: length :: [*] -> num a function which operates on a list of objects of any type. Thus we can have type checking as well as generic functions. Ponder A functional programming language designed by Fairbairn with an interesting generalisation of ML's type system. Portable Standard Lisp A dialect of Lisp from Utah University. Available as a kit for 68000. Runs on VAX. Compiles Lisp to C-code virtual machine language. Poset Partially ordered set. See Partial ordering. Pre-order In domain theory, a relation is a pre-order if it is reflexive and transitive. See also Partial ordering, Total ordering. Production system A production system consists of a collection of productions (rules). A rule becomes eligable to fire when its conditions match some set of elements currently in working memory. A confict resolution strategy determines which of several eligable rules fir. es next. A condition is a list of symbols which represent constants, which must be matched exactly; variables which bind to the thing they match and "<> symbol" which matches a field not equal to symbol. Projection In domain theory, a function, f, which is (a) idempotent, ie. f(f(x))=x and (b) whose result is no more defined than its argument. E.g. F(x)=bottom or F(x)=x. In reduction systems, a function which returns part of its argument. In a graph reduction system the function can just return a pointer to part of its argument and does not need to build any new graph. Eg. head, tail, \(x,y) . x. Prolog Programming in Logic. A relational language based on first order logic. The basic operation of Prolog is goal proving by backward chaining. The program is written as a database of facts and rules. A fact is something that is always true whereas a rule specifies that a proposition or goal is true if certain sub-goals are all true. Facts and rules may contain variables which take on any value necessary to make the fact or rule succeed. Prolog will try all possible combinations of values for variables to satisfy a goal. If a goal fails then Prolog backtracks to try alternative solutions of goals further up the tree. The user supplies the first goal and Prolog attempts to prove it by searching the database for any fact or rule that matches the goal (it attempts to "unify" the goal with a clause in the database). If the goal unifies with the head of a rule Prolog then attempts to prove the sub-goals of the rule in the same (recursive) way as for the first goal. The user is informed of the success or failure of his first goal and if it succeeds and contains variables he is told what values of those variables caused it to succeed. He can also ask for alternative solutions. See also Backtracking, First order logic, Unification, Negation by failure. Proof theory The branch of logic describing procedures for combining logical stateme. nts to show, by a series of truth-preserving transformations, that one statement is a consequence of some other statement or group of statements. PSL Portable Standard Lisp. Pure Lisp A subset of Lisp with no side-effects. A functional language. Quantifier An operator in logic specifying for which values of a variable a formula is true. Universally quantified means "for all values" (written with an inverted A) and existentially quantified means "there exists some value" (written with a reversed E). If a variable is not quantified then it is free. See also Bound variable, First order logic, Free variable, Scope. QLOG A version of Prolog implemented in Lisp which allows Prolog programs to call Lisp and vice versa. Range See Image. Rational tree Recipe See Suspension. Redex Reducible Expression. An expression matching the left hand side of a rule or defintion. See Reduction. Reduction The process of transforming an expression according to certain reduction rules. The most important forms are beta reduction (application of a lambda abstraction to one or more argument expressions) and delta reduction (application of a mathematical function to the required number of arguments). There are many different stratgies for choosing which part of an expression (which redex) to reduce first. See Graph reduction, Reduction strategy, String reduction, Normal order reduction, Applicative order reduction, Parallel reduction Alpha conversion, Beta conversion, Delta conversion, Eta conversion. Reduction strategy An algorithm for deciding which redex(es) to reduce next. Different strategies have different termination properties in the presence of recursive functions or values. See String reduction, Normal order reduction, Applicative order reduction, Parallel reduction Referential transparency A program is referentially transparent if it prohibits assigning different values to the same named variable during the same run. This means that . a function and its value are interchangeable. Referentially transparent programs are amenable to formal methods. Functional languages achieve this by using only named constants whose values are passed as data at run time. Relational languages permit the use of variables but require the program to be, in effect, rerun for each different value returned. Reflexive A relation R is reflexive if, for all x, x R x. Regular graph A graph with all nodes of the same degree. Relational language Relational languages specify output in terms of some property and some arguments. For example, if Tom has two brothers, Dick and Harry, a relational language will respond to the query "Who is Tom's brother ?" with either Dick or Harry. Notice that unlike functional languages, relational languages do not require a unique output for each predicate/argument pair. Prolog is the best known relational language. Resolution A mechanical method for proving statements of first order logic, introduced by J A Robinson in 1965. Resolution is applied to two clauses in a sentence. It eliminates, by unification, a literal that occurs positive in one and negative in the other to produce a new clause, the resolvent, which is added to the sentence. Resolution with backtracking is the basic control mechanism of Prolog. See also SLD Resolution. SASL Single ASsignment Language. A functional programming language designed by Professor David Turner. Example syntax: def fac n = n = 0 -> 1 ; n x fac(n-1) Scheme A dialect of Lisp from MIT. Scope The scope of a variable is that region of a program source within which it represents one thing. Within its scope a variable can be replaced by any other variable without altering its meaning (barring name clashes). See also Lexical scoping, Dynamic scoping. SECD machine Stack Environment Control Dump machine. One of the first abstract machines for graph reduction. Described by Landin. Sentence In logic, a collect. ion of clauses. SETL A language by Jack Schwartz. Possibly the first use of list comprehension notation. Shallow binding A method of storing variable bindings where the current vaule of a variable can be found at at a known location rather than by searching an environment or association list. When a new binding is made, the old value is copied into the environment. Skolemization A means of removing quantifiers from first order logic formulas. Side effect Statements that modify the current state of the system rather than simply adding more to what was already there are said to have side effects. Side-effects include assignment and I/O. SIMD Single Instruction Multiple Data The class of parallel processor where many functional units perform the same operations on different data. The term was invented by Flynn. See MIMD. Single assignment If a variable is only assigned a value once then an instance of that variable is equivalent to the value and can be considered as a function which returns that value. Thus a single assignment language is a functional language. See zero assignment. SISAL A functional programming language originating from data-flow languages, targeted at numerical computation. Developed (around 1985) by Manchester University, MIT, DEC and Lawrence Livermore National Lab. One major objective was the efficient handling of arrays. Not to be confused with SASL. S-K reduction machine An abstract machine defined by Professor David Turner to evaluate combinator expressions represented as binary graphs. Named after the two basic combinators, S and K. SLD resolution Linear resolution with a selection function for definite sentences. A definite sentence has exactly one positive literal in each clause and this literal is selected to be resolved upon, ie. replaced in the goal clause by the conjunction of negative literals which form the body of the clause. SML Standard ML. A descendent of ML. SML of New Jersey (SM. L-NJ) is a popular version. Speculative evaluation Under speculative evaluation some evaluation may be started before it is known whether it is needed (Eager evaluation). This may result in some wasted processing and may introduce unnecessary non-terminating processes but it can reduce the overall run-time by making some needed results available earlier than they would be otherwise. Opposite of Conservative evaluation. Spice Lisp A flavour of Lisp the sources of which (in Lisp) are available from CMU. \sqcup A square U. Used for the Least upper bound. \sqsubseteq Like a capital E with its middle line moved below its bottom. In domain theory, x \sqsubseteq y if x is no more defined that y. STAB A decendent of BCPL Stack environment control dump machine (SECD machine) The first abstract machine for reducing lambda calculus expressions invented by P.J.Landin. The machine has four registers holding pointers to linked lists operated as push-down stacks which hold the information required for the evaluation of an expression. The registers point to (1) Stack which holds the arguments of partially evaluated expressions and results of completely evaluated ones, (2) Environment where the current expression being evaluated is stored, (3) Control which holds the machine instructions that manipulate the contents of the four registers that represent the expression being evaluated, (4) Dump on which the state of the machine is temporarily saved during the evaluation of expressions. See also Lispkit. Strength reduction A compiler optimisation. Strict A function is strict in an argument if the result of the function application is bottom whenever that argument is bottom. In other words, the result depends on the argument. See also Strict evaluation. Strict evaluation Call by value evaluation order is sometimes called ``strict evaluation'' because, in a sequential system, it makes functions behave as though they were strict, in the sen. se that evaluation of a function application cannot terminate before evaluation of the argument. Similarly, languages are called strict if they use call by value. See Eager evaluation, Lazy evaluation. String reduction An expression is represented as a string of function names and constants. It is reduced by substituting values for parts of the string into the string or a copy of it. See Graph reduction. Structured language A language where the program may be broken down into blocks or procedures which can be written without detailed knowledge of the inner workings of other blocks, thus allowing a top-down-design approach. \subseteq Like a U on its right side with a line under it. For sets x and y, x \subseteq y if all elements of x are also elements of y. Supercombinators Combinators with coarser granularity than those proposed by Turner. A functional program is translated to a set of functions without free variables. The members of the set are selected to be optimal for that program. Supercombinators were proposed by John Hughes at Edinburgh University. Surjection A function f : A -> B is surjective or onto or a surjection if f(A) = B. This means that its image is its codomain. Only surjective functions have right inverses, f' where f(f'(x)) = x or f . f' = i, the identity function since if f were not a surjection there would be elements of the codomain for which f' was not defined. See also Bijection, Injection. Suspension In lazy evaluation, a suspension (or in Henderson's terminology, a recipe) is a closure with a flag indicating whether the expression has been evaluated or not. When the expression is evaluated the first time, this flag is set. Subsequent requests for the value of the expression will not attempt to re-evaluate it. Symmetric A relation R is symmetric if, for all x and y, a R b => b R a. TABLOG A programming language based on first order predicate logic with equality that combines realtional and. functional programming. It has functional notation and unification as its binding mechanism. TABLOG supports a more general subset of standard first order logic than Prolog. It employs the Manna-Waldinger 'deductive-tableau' proof system as an interpreter instead of resolution. T Lisp A dialect of Lisp from Yale. Used as the basis for the Yale Haskell system. Tail recursion optimisation (TRO) When the last thing a procedure does is to call itself, it is not necessary to retain the calling invocation's environment. This is important when a procedure calls itself recursively many times for, without tail recursion optimisation, the environments of earlier invocations would fill up the memory only to be discarded when (if) the last call terminated. Tail recursion optimisation is a special case of last call optimisation but it allows the further optimisation that some arguments may be passed in situ, possibly in registers. TEMPLOG Extension of Prolog to handle temporal logic proposed by M Abadi and Z Manna of Stanford University. Temporal logic Temporal logic is an extension of predicate calculus which includes notation for arguing about when statements are true. Time is discrete, linear and extends indefinately into the future. Three prefix operators, represented by a circle, square and diamond mean "is true at the next time instant", "is true from now on" and "is eventually true". x U y means x is true until y is true. x P y means x precedes y. Term rewriting system A computational paradigm consisting of a collection of rewrite rules to transform terms (expressions, strings in some formal language) into equivalent terms. See reduction. Threaded code An instruction/op-code represents the address of some (lower level) code to perform the required operation. Used by Forth. Total ordering A relation R on a set A is a total ordering if the relation is reflexive, transitive, antisymmetric and for any two elements x and y . in A, either x R y or y R x. Transformation The systematic development of efficient programs from high-level specifications by meaning-preserving program manipulations. Transitive A relation R is transitive if x R y and y R z => x R z. Transitive closure The transitive closure R* of a relation R is defined by x R y => x R* y x R y and y R* z => x R* z Ie. elements are related by R* if they are related by R directly or through some sequence of intermediate related elements. Eg. in graph theory, if R is the relation on nodes "has an edge leading to" then the transitive closure of R is the relation "has a path of zero or more edges to". Tree A graph containing no cycles. ie. there is only one route between any pair of nodes. Unification The generalisation of pattern matching that is the logic programming equivalent of instantiation in logic. When two terms are to be unified, they are compared. If they are both constants then the result of unification is success if they are equal else failure. If one is a variable then it is bound to the other, which may be a variable, constant or structure and the unification succeeds. If both terms are structures then each pair of sub-terms is unified recursively and the unification succeeds if all the sub-terms unifiy. The result of unification is either failure or success with a set of variable bindings. See Unifier. Unifier The unifier of a set of expressions is a set of substitutions of terms for variables such that the expressions are all equal. See Most general unifier, Unification. \uparrow An upward pointing arrow. See Closure. Upward closure See Closure. VAL Value Algorithmic Language. A dataflow language. Valency See degree. WHNF Weak head normal form Weak head normal form A term coined by Simon Peyton-Jones to make explicit the difference between head normal form (HNF) and what graph reducers produce in practice. A lambda expression is in weak head normal form . (but not HNF) even if its top level is a lamdba abstraction with a reducible body. Hence, the expression \x . ((\y . y+x) 2) is in WHNF but not HNF. To Reduce this expression to HNF would require reduction of the inner application (\y . y+x) 2 --> 2+x Conversion to WHNF avoids the need for alpha conversion of an inner lambda abstraction and so is prefered in practical graph rediction systems. Y See Fixed-point combinator. Zeta Lisp A dialect of Lisp originally derived from MacLisp and currently supported by Lisp Machines Inc. and Symbolics. Zero assignment A zero assignment language is a language where there are no variables but only functions. See single assignment. ZAPP Zero Assignment Parallel Processor. A virtual tree machine architecture in which a process tree is dynamically mapped onto a fixed, strongly connected network of processors communicating by message passing. The basic operation of each node is to apply a divide and conquor function which takes four arguments: (1) a function 'primitive' which takes a problem description (PD) and returns true if it can be solved without division, (2) a function 'solve' which takes a primitive PD and returns its solution, (3) a function 'divide' which takes a PD and returns a list of PDs of smaller problems and (4) a function 'combine' which returns the solution to a problem by combining a list of solutions of subproblems. Each node has a copy of the code and one is given the initial problem description. Task distribution is by process stealing in which a process constructs a descriptor for each subtask and idle (lightly loaded) processors can steal a descriptor from a physically connected neighbour. ZF expression See list comprehension.