# Director string

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.

## Motivation

In beta reduction, one defines the value of the expression on the left to be that on the right:

- [math]\displaystyle{ (\lambda x.E)y \equiv E[x:= y]\, }[/math] or [math]\displaystyle{ (\lambda x.E)y \equiv E[y/x] }[/math] (Replace all
*x*in*E*(body) by*y*)

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*. Such an algorithm is clearly *O*(*n*) in the length of the expression *E*. Thus, one is motivated to somehow track the occurrences of the free variables in the expression. 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.

## Definition

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

- [math]\displaystyle{ t ::= f(t_1,t_2,\dots,t_n) }[/math]

where *f* is a function, of arity *n*, with no free variables, and the [math]\displaystyle{ t_i }[/math] are terms that may or may not contain free variables. Let *V* denote the set of all free variables that may occur in the set of all terms. The director is then the map

- [math]\displaystyle{ \sigma_t: V\to P(\lbrace 1,2,\dots,n\rbrace) }[/math]

from the free variables to the power set [math]\displaystyle{ P(X) }[/math] of the set [math]\displaystyle{ X=\lbrace 1,2,\dots,n\rbrace }[/math]. The values taken by [math]\displaystyle{ \sigma_t }[/math] are simply a list of the indices of the [math]\displaystyle{ t_i }[/math] in which a given free variable occurs. Thus, for example, if a free variable [math]\displaystyle{ x\in V }[/math] occurs in [math]\displaystyle{ t_3 }[/math] and [math]\displaystyle{ t_5 }[/math] but in no other terms, then one has [math]\displaystyle{ \sigma_t(x) = \lbrace 3,5\rbrace }[/math].

Thus, for every term [math]\displaystyle{ t\in T }[/math] in the set of all terms *T*, one maintains a function [math]\displaystyle{ \sigma_t }[/math], and instead of working only with terms *t*, one works with pairs [math]\displaystyle{ (t,\sigma_t) }[/math]. 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.

## General case

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.

## See also

- Term rewrite system
- Explicit substitution
- Memoization

## References

- ↑ F.-R. Sinot, M. Fernández and I. Mackie. Efficient Reductions with Director Strings. In
*Proc. Rewriting Techniques and Applications*. Springer LNCS vol 2706, 2003

- F.-R. Sinot. "Director Strings Revisited: A Generic Approach to the Efficient Representation of Free Variables in Higher-order Rewriting."
*Journal of Logic and Computation***15**(2), pages 201-218, 2005.

Original source: https://en.wikipedia.org/wiki/ Director string.
Read more |