Programming Languages Glossary

LA home
Computing
Prog.Langs
 Glossary

also see
maths
  • .   :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 = 230 = 10243 ~ 109.
  • 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 = 210 = 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 = 220 = 10242 ~ 106.
  • 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).
© L.A., 1984, 1986, 1996.
www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Tuesday, 19-Sep-2017 14:49:52 EDT.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.