GLOSSARY¶

alpha

The name of the Greek letter $\alpha$ (lowercase) or $A$ (uppercase), corresponding to the letter "a".

binding occurrence

A binding occurrence is the place in a program where a variable is bound to its name (or identifier). In modern programming languages, a binding occurrence is the same as a declaration of the variable. In lambda calculus, a binding occurrence for, say, the variable $x$, is any sub-expression equal to $\lambda x.$

bnf grammar

A BNF grammar is...

bound

In a lambda expression, a variable occurrence is bound or occurs bound if it belongs to the scope of a binding occurrence of that variable.

free

In a lambda expression, a variable occurrence is free or occurs free if it is not bound in that expression.

function abstraction

In lambda calculus, a function abstraction (or lambda abstraction) is synonymous with a function definition that contains the name of the formal parameter and the body of the function.

lambda

The name of the Greek letter $\lambda$ (lowercase) or $\Lambda$ (uppercase), corresponding to the letter "L".

lambda abstraction

Synonym for function abstraction.

scope

Abbreviation for variable scope

variable capture

A free variable occurrence is captured when it becomes bound following the renaming of some other variable occurrence.

variable scope

The scope of a variable declaration (or binding occurrence) in a program is the collection of all parts of the program (that is, the lines of code) in which this variable is accessible via its name or identifier.