Director string

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. 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.

Contents

Motivation

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

(\lambda x.E)y \equiv E[x:= 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

t ::= f(t_1,t_2,\dots,t_n)

where f is a function, of arity n, with no free variables, and the ti 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

\sigma_t: V\to P(\lbrace 1,2,\dots,n\rbrace)

from the free variables to the power set P(X) of the set X=\lbrace 1,2,\dots,n\rbrace. The values taken by σt are simply a list of the indices of the ti in which a given free variable occurs. Thus, for example, if a free variable x\in V occurs in t3 and t5 but in no other terms, then one has σt(x) = {3,5}.

Thus, for every term t\in T in the set of all terms T, one maintains a function σt, and instead of working only with terms t, one works with pairs (tt). 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

References

  1. ^ 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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Director — may refer to: Contents 1 Arts 2 Business 3 Works 4 Othe …   Wikipedia

  • String Quartets 1–3 — Infobox Album Name = String Quartets 1 3 Type = studio Longtype = Artist = Michael Nyman and Balanescu Quartet Cover size = 200 Caption = art by Paul Richards clockwise from top left: Balanescu, Musker, Hinnigan, Carney Released = June 14, 1991… …   Wikipedia

  • String Quartets 2, 3 & 4/If & Why — Infobox Album Name = String Quartets 2, 3 4/If Why Type = studio Longtype = Artist = Michael Nyman Cover size = 200 Caption = Released = September 24, 2002 Recorded = Genre = Contemporary classical, Chamber music, minimalism, art song Length =… …   Wikipedia

  • Director telephone system — The Director System was a system which made it possible to call subscribers at other telephone exchanges without operator intervention in large multi exchange cities, and to have a mixture of automatic and manual exchanges within these cities. It …   Wikipedia

  • String Quartet No. 1 (Dvořák) — Antonín Dvořák finished the composition of his String Quartet No. 1 in A major, Op. 2, (B. 8), in March, 1862. It was one of his early chamber works. Background Dvořák s fourteen string quartets covers the substantial part of his composing career …   Wikipedia

  • String Quartet No. 8 (Simpson) — The String Quartet No. 8 by Robert Simpson was composed in 1979 in response to a commission by the Brunel Philharmonic Society with funds made available from the Greater London Arts Association. The work is dedicated to Professor Gillett, who was …   Wikipedia

  • New England String Ensemble — was founded in 1993 by violinist Peter Stickel and cellist John Bumstead to champion strings in performance and education and is one of the country’s leading professional string orchestras.[citation needed] The ensemble consists of 26… …   Wikipedia

  • Duke University String School — Established January 1967 Director Dorothy Kitchen Students approx. 250 Location Durham, North Carolina …   Wikipedia

  • Life on a String (film) — Infobox Film name = Life on a String image size = caption = Kino International edition DVD cover director = Chen Kaige producer = Karl Baumgartner, Cai Rubin Donald Ranvaud writer = Chen Kaige Shi Tiesheng (novel) starring = Liu Zhongyuan Huang… …   Wikipedia

  • The Carlos Chavez String Quartet — is a Mexican based string quartet (previously known as The Russian American String Quartet ) founded by cellist Alain Durbecq in 1994. The quartet currently resides in Mexico City and performs a broad spectrum of mainstream classical music… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”