In mathematics, in the area of lambda calculus and computation, directors or director strings are a mechanism for keeping track of the free variables in a term.
Loosely speaking, they can be understood as a kind of memoization for free variables; that is, as an optimization technique for rapidly locating the free variables in a term algebra or in a lambda expression.
Director strings were introduced by Kennaway and Sleep in 1982 and further developed by Sinot, Fernández and Mackie[1] as a mechanism for understanding and controlling the computational complexity cost of beta reduction.
In beta reduction, one defines the value of the expression on the left to be that on the right: While this is a conceptually simple operation, the computational complexity of the step can be non-trivial: a naive algorithm would scan the expression E for all occurrences of the free variable x.
One may attempt to track the position of every free variable, wherever it may occur in the expression, but this can clearly become very costly in terms of storage; furthermore, it provides a level of detail that is not really needed.
Director strings suggest that the correct model is to track free variables in a hierarchical fashion, by tracking their use in component terms.
Consider, for simplicity, a term algebra, that is, a collection of free variables, constants, and operators which may be freely combined.
Assume that a term t takes the form where f is a function, of arity n, with no free variables, and the
The director is then the map from the free variables to the power set
in the set of all terms T, one maintains a function
Thus, the time complexity of finding the free variables in t is traded for the space complexity of maintaining a list of the terms in which a variable occurs.
Although the above definition is formulated in terms of a term algebra, the general concept applies more generally, and can be defined both for combinatory algebras and for lambda calculus proper, specifically, within the framework of explicit substitution.