Glossary

Programming Languages Glossary

. :see cons.
: :1- has type.
: :2- infix cons (Haskell).
:: :1- see cons.
:: :2- has type (Haskell).
::= :rule definition in formal grammar.
:= :assignment operator, x:=e.
= :1- mathematical identity, definition.
= :2- equality test, t × t -> bool.
= :3- assignment operator in some languages.
λ :λ-abstraction; function defn, eg., successor=λn.n+1.
0 address :instruction or machine; stack-based, reverse Polish.
1 address :1 full memory address (and 1 implicit register (accumulator)).
1.5 address :1 register and 1 full memory address, e.g., Reg3+=b.
2 address :2 full memory addresses eg. a+=b.
3 address :3 full memory addresses eg. a:=b+c.
accumulator :1- special register, see 1-address.
accumulator :2- accumulating-parameter, esp' in FP.
activation :of a routine, instance of rtn called and not yet returned.
activation record :space allocated for local variables of an activation of a routine.
actual parameter :given when routine is called.
ad-hoc :esp' ad-hoc polymorphism, overloading etc..
Algol :ALGOrithmic Language, Algol-58, Algol-60, Algol-68, Algol-W.
algorithm :defn of process or steps to carry out a computation.
alias :when two variable names denote the same location.
APL :A Programming Language (also see J).
applicative :like functional but (usually) strict evaluation, not lazy.
ARB :activation record base (points to current act recd in stack).
assignment operator : ":=", "<-", or "=", in various programming languages.
atom :1- true fact without condition in pred' logic eg. red(dress).
atom :2- indivisible scalar object eg. an int or a char.
backtrack :to restore a previous state and try an alternative computation.
basic block :a maximal section of program, no internal jumps in or out.
BCPL :Basic CPL.
bind :to fix an attribute (eg. address, value, type, etc.) of something.
block structure: Language constructs for nested (recursive) routines.
BNF :Backus-Naur Form, meta language for expressing context free grammars.
bound :1- the limit of the index range of an array.
bound :2- see bind.
bound variable :in lambda calculus, given λx.e then x is bound (not free) in e.
by name :see name.
by need :see need.
by reference :see reference.
by value :see value.
C :an imperative language.
cast :explicitly force a type coercion eg. real(n div 2).
CFG :see Context-Free Grammar.
class :specifies constants and methods (operators, functions) for some "type" of value in an object-oriented language.
closure :a computation point; a proc, function or label value; <environment,address>.
Cobol :COmmon Business Oriented Language.
coercion :change type (& possibly value) eg. the 7->7.0 in 3.141593+7.
combinator :a function using parameters only, i.e. not using any non-local variables.
command :imperative instruction to do something.
compile-time :when the compiler is processing the program.
concurrent :two or more processes running at same time (possibly interleaved on a single processor).
conditional :if then else fi, or similar.
conjunction :and, eg. p and q.
cons :list constructor, also infix `:' (Haskell), `::' (SML), or `.' (LML).
context-free grammar :LHS of each production rule is just one NT.
context-sensitive grammar :LHS of each production rule contains one NT.
continuation :a computation or function to finish computation of program.
coroutine :kind of routine, resumes from its last exit not from its beginning.
CPL :Combined Programming Language (a particular one); see Barron et al, Comp.J. 6(2) 1963.
CPU :central processing unit.
curried : as in f x y = ... versus f(x, y) = ...
declarative :based on declarations of fact (equations or predicates).
denotational :semantics; method of giving semantics of a programming language.
denote :to stand for, eg. a numeral denotes a number.
dereference :to get contents of a location or follow a pointer.
descriptor :of an array = <base, length, (optional) scaling factor>.
deterministic :result uniquely determined by program.
disjunction :or, eg. p or q.
display :set of pointers to accessible activation records (especially non-local variables).
dyadic :binary, having 2 arguments eg. + in 2+3.
dynamic link :pointer to activation record of calling routine.
eager :strict evaluation, by value.
environment :collection of bindings at some point in a program.
equality operator : "=", or "==" in various programming languages.
expression :method for computing a value.
FIFO :First In First Out (queue).
fixed point :of function f, x s.t. f(x)=x, also see Y.
formal parameter :dummy name used in defn of proc or func to denote parameter.
Fortran :FORmula TRANslation, imperative programming language.
FP :1- Functional Programming languages based on λ-calculus.
FP :2- programming with (functional) combinators, J.Backus.
frame :activation record.
frame pointer :see ARB.
free list :list of free storage, e.g., for heap allocation.
free variable :e.g., λx.x+y then x is bound and y is free in x+y.
functional :expressions, functions, no := or side-effects, usually lazy.
G :giga, 1G = 2³⁰ = 1024³ ~ 10⁹.
garbage :storage that has become inaccessible to the program.
garbage-collector :system routine to recycle garbage, put it on the free list.
GIGO :Garbage In Garbage Out.
Gofer :functional language, near subset of Haskell.
grammar = <{terminals}, {non-terminals}, {production rules}, start-symbol>.
graph reduction :implementation technique for functional languages.
Haskell :functional language, c1990+ (named after Haskell B. Curry), also Haskell-98.
head :first element of a list.
heap :area of dynamically allocated store, often garbage collected.
hd :see head.
I :identity combinator defn: I x = x.
Icon :imperative programming language with very interesting control mechanisms.
imperative :an order! e.g., eat your vegetables!.
infix :eg. the + in a+b.
J :programming language by K. E. Iverson, descendant of APL.
Java :1- a strong coffee favoured by programmers.
Java :2- OO-language by Sun ~ 1996.
K :1- kilo, 1K = 2¹⁰ = 1024.
K :2- constant combinator defn: K x y = x.
L-value :an address; left value; from left hand side of assignment operator.
Lambda-calculus: Alonzo Church's λ-calculus is the ancestor of functional programming languages..
lazy :don't evaluate (esp' parameters) unless needed, see need, normal-order, λ-calculus.
leaf :extremity of a tree, has no subtree.
lex :generator of lexical analysers, also see yacc.
LIFO :Last In First Out (stack).
Lisp :1- LISt Processing language.
Lisp :2- Language of Insufferable Superfluous Parentheses:-).
list :list e = nil | cons e (list e).
LL(k) :Left to right parsing based on Left-most derivations with k symbols lookahead; can be parsed top-down with k-symbol limited lookahead.
LML :Lazy ML.
local :as in local variable, a routine's private variable, see non-local.
loop stop :see stop, loop.
LR(k) :Left to right parsing based on Right-most derivations; can be parsed bottom-up (also R~Reduction) with k-symbol lookahead.
M :mega, 1M = 2²⁰ = 1024² ~ 10⁶.
mark scan :a method of garbage collection; clear all marks, traverse accessible memory setting marks, reclaim unmarked memory.
memo :memo-function stores old results, does not recompute them.
method :OO-jargon for a routine of a class.
ML :Meta-Language, an applicative programming language.
mode :word for `type' in Algol-68.
module :construct for hiding information and/or separate compilation.
monad :a concept from category theory adopted by Haskell.
monadic :unary, having one argument eg. - is monadic in -(x+7).
mutual recursion :see recursion, mutual.
name parameter :actual parameter reevaluated on each use of formal parameter, formal parameter is bound to expression of actual parameter (thunk).
need :efficient implementation of call by name or lazy parameter in FP.
non-deterministic :1- (model) search all paths simultaneously, see backtrack.
non-deterministic :2- factors outside prog influence result, e.g., concurrent.
non-local :from an enclosing routine, e.g non-local variable.
non-terminal symbol :part of grammar; name for part of a sentence in a language.
normal-order :outermost, leftmost evaluation, see name, need, lazy.
object :instance of a class in an object-oriented language (an object often has a "state").
object-oriented :languages, usually imperative, with an emphasis on class and objects (e.g., C++, Java).
OO :object-oriented.
OOP :object-oriented programming.
overload :to give an operator ≥ 2 meanings eg. + addition & + set-union, say.
parallel :two or more processes run simultaneously, see concurrent.
parametric poly'm :see polymorphic.
partial-evaluation:to partially execute a program with some but not all inputs.
Pascal: imperative, block-structured language.
PL/1 :Programming Language 1.
polymorphic :many forms; type containing type variable eg. list *e.
postfix :post - after, eg. + as in a b +.
predicate :a truth function eg. `odd', `prime', >=, `part-of'.
prefix :pre - before, eg. + as in + a b.
production rule :in a grammar eg. <exp>::=<exp>+<term>.
Prolog :PROgramming in LOGic, a logic programming language.
R-value :right-value; a (storable) value; from right hand side of the assignment operator.
rank :number of dimensions of an array.
recursion :see recursion.
recursion, mutual :see mutual recursion.
reduction :a step in evaluation of expression, esp' in λ-calculus.
reference :address or pointer.
reference parameter :formal parameter is bound to the address of actual parameter (note, in OOP, object refs are typically passed by-value!).
regular grammar :has production rules of form NT::=T & NT::=T NT.
resolution :a rule of logic; (~p or q) & (p or r) => q or r.
resume :to restart a coroutine.
return address :address for routine to jump to on exit.
reverse Polish :postfix.
routine :function, procedure, subroutine and, less often, coroutine.
rule :see production rule.
run-time :when the program is running, executing.
S :S combinator defn: S x y z = (x z)(y z).
SB :Stack Base.
scope :of a declared name, var etc. - parts of program where name is accessible and has the binding given in the declaration.
semantics :meaning of a language or program.
Sentential form :Can be derived from the start symbol of a grammar; α:(N+T)^* s.t. S=>^*α.
sequencer :alters flow of control; goto, exit, break, continue, return.
SF :stack front, see TOS.
side-effect :to change the state in a hidden way (eg. in an expression).
slice :subsection of string, vector or array eg. a[3..7].
SML :Standard ML.
Snobol :Snowball's chance in Hell, a string processing language.
stack :LIFO; has operations empty, push, pop.
stack frame :activation record.
state :of a program; current values of variables and files.
statement :English- statement of truth. Programming- a command!.
static :at compile time or referring to the text of program.
static-link :pointer to activation record of textually enclosing routine.
stop, loop :see loop stop.
strict :f is strict (on x) if f(x) loops whenever x loops.
subroutine :procedure.
super-combinator :kind of combinator derived from a functional program.
synchronise :2 processes execute complementary actions at same moment.
syntax :rules to form structurally correct sentences of a language; see grammar.
tail :1- all but the first element of a list.
tail :2- the last element of list or vector in the language J.
tail recursion :if last action of routine is to call self (eg. fast reverse).
terminal symbol :a symbol appearing in sentences of language.
thunk :a closure, method of implementing a name parameter.
tl :see tail.
TOS :Top Of Stack.
type :e.g., Int, Real, (Int×Char), Tree(String), etc., properties that can be determined statically by a compiler and used to generate efficient code, a surprisingly slippery concept, sometimes overlaps with class.
unary :monadic, having one parameter.
uncurried : as in f(x,y) = ... versus f x y = ...
unification :to make the same, possibly substituting for variables.
value parameter :formal parameter is bound to actual parameter's (R-)value.
Y :fixed-point or paradoxical combinator Y F = F(Y F),. defn: Y = λG. (λg. G(g g)) (λg. G(g g)).
yacc :Yet Another Compiler Compiler ("only" a parser generator in fact).