Director string

<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, in the area of <a href="/facts/Lambda_calculus/DaD3RuQ4">lambda calculus</a> and <a href="/facts/Computation/qLsELosq">computation</a>, directors or director strings are a mechanism for keeping track of the <a href="/facts/Free_variable/ndWnXXYs">free variables</a> in a <a href="/facts/Expression_(mathematics)/MPrMlYbE">term</a>.  Loosely speaking, they can be understood as a kind of <a href="/facts/Memoization/u08VhUKm">memoization</a> for free variables; that is, as an <a href="/facts/Program_optimization/nXz6RpRM">optimization</a> technique for rapidly locating the free variables in a <a href="/facts/Term_algebra/kRGlTKMq">term algebra</a> or in a lambda expression. Director strings were introduced by Kennaway and Sleep in 1982 and further developed by Sinot, Fernández and Mackie as a mechanism for understanding and controlling the <a href="/facts/Analysis_of_algorithms/pStoBgBn">computational complexity</a> cost of <a href="/facts/Beta_reduction/DaD3RuQ4">beta reduction</a>.
</p>

Director string open-in-new

Director string