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