James Lindsay (actor)

James Lindsay (actor)

James Lindsay (1869-1928) was a British actor.

Selected filmography


  1. http://ftvdb.bfi.org.uk/sift/individual/13937

External links

Retrieved from : http://en.wikipedia.org/w/index.php?title=James_Lindsay_(actor)&oldid=458852251



Directed by Vamsi Paidipally
Produced by Dil Raju
Written by Vamsi Paidipally
Abburi Ravi
Screenplay by Vakkantham Vamsi
Story by Vamsi Paidipally
Starring Ram Charan Teja
Allu Arjun(guest)
Music by Devi Sri Prasad
Cinematography Chota K. Naidu
Studio Sri Venkateswara Creations
Distributed by Sri Venkateswara Creations
Release date(s) 2012
Country India
Language Telugu

Yevadu is an upcoming Telugu film written and directed by Vamsi. The film stars Ram Charan Teja and Samantha Ruth Prabhu in lead roles.Allu Arjun will be doing an important role in the movie. Music composed by Devi Sri Prasad. The movie launched on December 9.



The film is being produced by Dil Raju under Sri Venkateswara Creations Banner.


Retrieved from : http://en.wikipedia.org/w/index.php?title=Yevadu&oldid=465305036

Lucy Candler Heinz

Lucy Beall Candler Owens Heinz Leide

Lucy Beall Candler Owens Heinz Leide (1882-1962) was the only daughter of Coca-Cola co-founder Asa Griggs Candler.

In 1903, Lucy married her first husband William Davies Owens, who would become an assistant cashier (i.e. manager) at Central Bank and Trust, the bank that Asa Candler started in 1905. At first they lived together in her parents’ home, , at 61 Elizabeth Street in Inman Park. In 1910 they moved to a newly-built home in Druid Hills which would become known as "The Goose". It was located at what is now 1449 South Ponce de Leon Avenue. In 1968 the home would become the Mother Goose day care center, and later classroom space for The Paideia School until it burned down in 2009. William Owens died of influenza and a heart attack in the house in 1914.

Lucy then married Henry Heinz, capitalist, banker and president of Kiwanis International. Heinz was shot by a burglar at their home, Rainbow Terrace, in 1943. A black railroad worker confessed to the crime but rumours persisted that a relative murdered Heinz.

Lucy then married Enrico Leide (1887-1970), a concert cellist and orchestra conductor, conducting the first Atlanta Symphony Orchestra from 1920 to 1930. He was the brother of violinist and composer Manoah Leide-Tedesco.

Lucy died aboard the RMS Caronia in 1962.

External links


Retrieved from : http://en.wikipedia.org/w/index.php?title=Lucy_Beall_Candler_Owens_Heinz_Leide&oldid=458996595

Time in Nambia

Time in Namibia

Namibia observes daylight saving time, it uses UTC+01:00 in winter and UTC+02:00 in summer.


Until March 1903, at that time called German South-West Africa, it used UTC+01:30.

tz database

The tz database zone for Namibia is Africa/Windhoek.


States with limited
Dependencies and
other territories
  • / / / (Spain)
  • (Portugal)
  • / (France)
  • / / (United Kingdom)

Retrieved from : http://en.wikipedia.org/w/index.php?title=Time_in_Namibia&oldid=458665658

Timothy 1

First Epistle to Timothy

The First Epistle of Paul to Timothy, usually referred to simply as First Timothy and often written 1 Timothy, is one of three letters in the New Testament of the Bible often grouped together as the Pastoral Epistles, the others being Second Timothy and Titus. The letter, traditionally attributed to Saint Paul, consists mainly of counsels to his younger colleague and delegate Timothy regarding his ministry in Ephesus (1:3). These include instructions on the forms of worship and organization of the Church, the responsibilities resting on its several members, including episkopoi (overseers or bishops) and diakonoi ("deacons"); and secondly of exhortation to faithfulness in maintaining the truth amid surrounding errors (iv.iff), presented as a prophecy of erring teachers to come.


The author of First Timothy has been traditionally identified as the Apostle Paul. He is named as the author of the letter in the text (1:1). In modern times, scholars have become divided over the issue of authenticity, with many suggesting that First Timothy, along with Second Timothy and Titus, are not original to Paul, but rather an unknown Christian writing some time in the late-first-to-mid-2nd century. Despite the challenge to Pauline authorship, the traditional view is still held by many New Testament scholars.

Historical views

The genuineness of Pauline authorship was accepted by Church orthodoxy as early as c. 180 AD, as evidenced by the surviving testimony of Irenaeus and the author of the Muratorian fragment. Possible allusions are found in the letters from Clement of Rome to the Corinthians (c. 95), Ignatius of Antioch to the Ephesians (c. 110) and Polycarp to the Philippians (c. 130), though it is difficult to determine the nature of any such literary relationships. Modern scholars who support Pauline authorship nevertheless stress their importance regarding the question of authenticity: I.H. Marshall and P.H. Towner wrote that 'the key witness is Polycarp, where there is a high probability that 1 and 2 Tim were known to him'. Similarly M.W. Holmes argued that it is 'virtually certain or highly probable' that Polycarp used 1 and 2 Timothy.

Late in the 2nd century there are a number of quotations from all three Pastoral Epistles in Irenaeus' work Against Heresies. The Muratorian Canon (c. 170-180) lists the books of the NT and ascribes all three Pastoral Epistles to Paul. Eusebius (c. 330) calls it, along with the other thirteen canonical Pauline Epistles, "undisputed", despite the fact that Eusebius wrote in the 4th century with little to no knowledge of the complex social structures which line the books of the New Testament. Exceptions to this positive witness include Tatian, a disciple of Justin Martyr turned heretic, as well as the Gnostic Basilides.

Marcion, an orthodox Bishop later excommunicated for heresy, formed a Gnostic canon of Scripture c. 140 around ten of the canonical Pauline epistles, excluding 1-2 Timothy, Titus and Hebrews. The reasons for these exclusions are unknown, and so speculation abounds, including the hypotheses that they were not written until after Marcion's time, or that he knew of them, but regarded them as inauthentic. Proponents of Pauline authorship argue that he had theological grounds for rejecting the Pastorals, namely their teaching about the goodness of creation (cf. 1 Tim 4:1 ff.). The question is indeed curious whether Marcion knew these three letters and rejected them as Tertullian says, since in 1 Timothy 6:20 "false opposing arguments" are referred to, with the word for "opposing arguments" being "antithesis", the name of Marcion's work, and so whether it is a subtle hint of Marcion's heresy. However, the structure of the Church presupposed which is less developed than the one Ignatius presupposes (who wrote c.110), as well as the fact that not only is "antithesis" itself a Greek word which simply means "opposing arguments" but as it has been noted, the attack on the heretics is not central to the three letters.

The challenge to Pauline authorship

The modern challenge to Pauline authorship began with the work of German theologians F.D.E. Schleiermacher in 1807 and J.G Eichorn in 1812. (Eichorn extended Schleirmacher's critique of 1 Timothy to all three Pastoral letters.) This was argued in further detail by F.C. Baur in 1835. Following these arguments, a large number of modern scholars continue to reject Pauline authorship, citing various and serious problems in associating it therewith. For example, Norman Perrin analyzed the Greek used by the author or authors of the Pastoral Epistles, finding that over 1/3 of their vocabulary is not used anywhere else in the Pauline epistles; more than 1/5 is not used anywhere else in the New Testament, while 2/3 of the non-Pauline vocabulary are used by 2nd century Christian writers. Richard Heard, in 1950, had this to say: "The evidence of teaching as of style and vocabulary is strongly against Paul’s authorship, nor are these arguments seriously weakened by any supposition that the epistles were written late in Paul’s lifetime and to meet a new type of situation. The three epistles show such a unity of thought and expression that they must be the work of one man, but for the author we must look rather to one of Paul’s admirers than to Paul himself." Robert Grant noted the afore-mentioned parallels to Polycarp's Epistles and suggested he might be the author.


The dating of 1 Timothy depends very much on the question of authorship. Those who accept the epistle's authenticity believe it was most likely written toward the end of Paul's ministry, c.62-67 CE. Other historians generally place its composition some time in the late 1st century or first half of the 2nd century CE, with a wide margin of uncertainty. The text seems to be contending against nascent Gnosticism(1 Tim 1:4, 1 Tim 4:3)(see Encratism), which would suggest a later date due to Gnosticism developing primarily in the latter 1st century. The term Gnosis("knowledge") itself occurs in 1 Timothy 6:20. If the parallels between 1 Timothy and Polycarp's epistle are understood as a literary dependence by the latter on the former, as is generally accepted, this would constitute a terminus ante quem of 130-155 CE. However, Irenaeus (writing c. 180 CE) is the earliest author to clearly and unequivocally describe the Pastorals.


This historical relationship between Paul and Timothy is one of mentorship. Timothy is first mentioned in Acts 16:1. His mother Eunice, and his grandmother, Lois, are mentioned in 2 Tim. 1:5. All that we know of his father is that he was a Greek not a Jew (Acts 16:1).

Paul's second visit to Lystra is when Timothy first connected with Paul (1 Timothy 1:2; 2 Timothy 3:11). Paul not only brought Timothy into the faith but he was Timothy’s main mentor in Christian leadership (Acts 16:3), having done church planting and missionary journeys together. Timothy would have received his authority to preach in churches directly from Paul who of course was the greater known and accepted of the two and an apostle. Timothy’s official position in the church was one of an evangelist (1 Timothy 4:14) and he worked with Paul in Phrygia, Galatia, and Mysia, Troa, Philippi and Berea (Acts 17:14) and continued on to do even more work in Athens, and Thessalonica for the church (Acts 17:15; 1 Thessalonians 3:2) not to mention his work in Corinth, Macedonia, Ephesus and greater Asia. Timothy was also noted for coming to Paul’s aid when Paul fell into prison (Philippians 1:1, 2 Timothy 4:13). It is noteworthy that despite not being required due the ruling of the Jerusalem council; Timothy took circumcision himself to be a better witness among the Jews. According to church tradition he was loyal to Paul’s wishes and stayed and worked in Ephesus until he finally suffered the Martyr's death himself.

If, however, "… the pastorals are best understood against the background of the second century, the evidence in the letters relative to church order ... clearly reflect a time when apostle and prophet have been succeeded by bishop (and archbishop?) and/or elder in a stabilized church organization fully committed to an authorized succession of ordained ministers. The local churches are no longer lay churches, nor are their needs now taken care of simply by itinerant missionaries. There is obviously hierarchical organization both in the local and ecumenical church. The chief function of the bishop (or archbishop?) is to transmit and maintain the true faith" TIB 1955 XI p. 346


Regardless of whether this epistle is seen as a 4th missionary journey not recorded in Acts or as being written at some other point of Paul’s life, its intent seems clear that Paul is writing to encourage Timothy on his own ministry. Timothy is now pastoring in the Ephesus Church and Paul writes him to tell him to stay there and continue his good work there. Paul had planted the Ephesus church himself putting over 3 years of his blood and tears in to the effort (Acts 19:10; 20:31) and he is well pleased his former student is currently taking the post there. This is most likely a letter written in Paul’s late life and can be seen as being among his departing advice to his former student who has risen up in the ranks of church leadership himself. As Paul becomes more aware of his impending end, soon to be at the hands of Nero, he is setting things in order for the next generation.

If, however, I Timothy is post Paul, then Timothy represents all the "Timothies" of the church whom the writer is exhorting to preserve Pauline Christianity against incipient heresies.

Key themes and words

The themes in this book circulate around church structure more than any other issue in the letter. Paul gives an example warning to Timothy not to let false doctrine such as Encratism take hold.

The structure for the role of women in the Church at Ephesus is laid out as well as a detailed list of qualifications for who can and cannot serve as Elders and Deacons in the church. It is a notably a hotly debated issue in the church as to what Paul meant in this book in regard to the women’s role in the church. What provoked this reversion from Paul’s revelation, in Galatians, that in Christ Jesus there is no male or female, to this banal legalism? Had the women, having been led to expect an imminent end of the world, begun to abandon their “wifely duties”? "Some feel he clearly teaches that women are not to have authority over men in the church structure (1 Timothy 2:12) and that this is why he clearly excludes them from the roles of Elder/Bishop and Deacon in chapter three. People who hold to this stance point out that Paul’s use of the phrase “Husband of one wife” is gender specific and excludes women from that role. They would point out that in the Greek text it literally reads "Man of one woman". "μιασ γυναικοσ ανδρα"(1 Timothy 3:2) However, more liberal scholars debate this, arguing that this is a product of the time in which Paul lived and it is a cultural reference not meant to be eternally binding on the church. Many churches have now embraced the ordination of women based on this modern outlook. The treatment of this issue has also been pointed to as evidence that I Timothy is not Pauline, noting "the freedom granted [women] in the aspostolic age to exercise the gifts of the Spirit, [and] Paul's insistence that in Christ there is neither male nor female, [which] had brought them into quick and widespread public activity." TIB 1955 XI p. 349. TNJBC also points out that the reasoning in I Timothy (the fall was Eve's fault) is non-Pauline: “Paul himself prefers to assign blame to Adam (as a counterpart to Christ – see Rom [Romans] 5:12-21; I Cor [Corinthians] 15: 45-49…)” TNJBC 1990 p. 897

The treatment of widows, elders, masters, youth, and church members are spelled out; as well as a healthy warning against greed being given to the rich.

Key words and phrases in this book include; “fight the good fight”, “This is a faithful saying”,” let no one despise your youth”, doctrine, elder/bishop, deacon, fables, guard.


I. Salutation (1:1-2)

II. Negative Instructions: Stop the False Teachers (1:3-20)

A. Warning against False Teachers (1:3-11)
1. The Charge to Timothy Stated (1:3)
2. Their Wrong Use of the Law (1:4-7)
3. The Right Use of the Law (1:8-11)
B. Paul’s Experience of Grace (1:12-17)
C. The Charge to Timothy Repeated (1:18-20)

III. Positive Instructions: Repair the Church (2:1–6:10)

A. Restoring the Conduct of the Church (2:1–3:16)
1. Instructions on Public Worship (2:1-15)
a. Concerning Prayer (2:1-7)
b. Concerning the Role of Men and Women (2:8-15)
1) Men: Pray in a Holy Manner (2:8)
2) Women: Quiet Conduct (2:9-15)
2. Instructions on Church Leadership (3:1-13)
a. Qualifications of Overseers (3:1-7)
b. Qualifications of Deacons (3:8-13)
3. Summary (3:14-16)
a. Conduct of the Church (3:14-15)
b. Hymn to Christ (3:16)
B. Guarding the Truth in the Church (4:1-16)
1. In the Face of Apostasy (4:1-5)
2. Timothy’s Personal Responsibilities (4:6-16)
3. Spiritual Exercises (4:7-9)
C. Dealing with Groups in the Church (5:1–6:10)
1. Men and Women, Young and Old (5:1-2)
2. Widows (5:3-16)
a. Older Widows (5:3-10)
b. Younger Widows (5:11-16)
3. Elders (5:17-25)
a. The Reward of Elders (5:17-18)
b. The Reputation of Elders (5:19-20)
1) The Reputation of Elders Protected (5:19)
2) The Sins of Elders Publicly Rebuked (5:20)
c. The Recognition of Prospective Elders (5:21-25)
4. Slaves (6:1-2)
5. False Teachers (6:3-10)

IV. Personal Instructions: Pursue Godliness (6:11-21)

A. Fight the Good Fight (6:11-16)
B. A Final Word to the Wealthy (6:17-19)
C. Guard What has been Entrusted (6:20-21)

See also


External links

Subdivisions Development Manuscripts See also

Retrieved from : http://en.wikipedia.org/w/index.php?title=First_Epistle_to_Timothy&oldid=460929685

Castra of Bădeni

Castra of Bădeni

Porolissum-porta-praetoria-icon.png Castra of Bădeni

See also

External links


Retrieved from : http://en.wikipedia.org/w/index.php?title=Castra_of_B%C4%83deni&oldid=458839030

Preston Field House

Prestonfield House

Prestonfield House
Prestonfield House Hotel - geograph.org.uk - 1599950.jpg
Location Prestfield Road, Edinburgh
Opening date 1960s
Suites 23
Restaurants 1
Website www.prestonfield.com

Prestonfield House is a five-star boutique hotel located in Prestonfield, Edinburgh. It was originally built in 1687 by architect Sir William Bruce, and was once a wealthy rural estate, but in recent decades has come to serve as a hotel. Though it is but a small establishment, having only 23 rooms, Prestonfield House is well renowned by critics.

Situated on extensive grounds at the foot of Arthur's Seat, Prestonfield House also owns a large roundhouse, which was previously used for keeping horses. The now-converted stables are used to host large functions, one example being the Taste of Scotland festival. Otherwise, the Hotel maintains a small dedicated restaurant named 'Rhubarb', which serves gourmet food.


Originally known as Priestfield, the site was once a wealthy monastery, founded in 1150 by Henry, Earl of Northumbria. Over the subsequent centuries, the estate changed hands many times, until when newly in the possession of the Catholic Dick family, the monastery was in the 1670s burned down by Protestant students. The Family quickly enlisted William Bruce to design a replacement building, which was renamed Prestonfield. The new estate remained in the family's possession for many generations, who played host to many great thinkers of their times, including David Hume, Benjamin Franklin, Dr Samuel Johnson, and Allan Ramsay. The Dick family continued to modify and improve the estate, adding paintings, a grand new staircase with reception rooms, and a porte-cochère. Most notably, the stable house was built in the 19th century, as designed by James Gillespie Graham. As later generations of the family spent less and less time at the estate, no further remodelling took place, preserving the decor to the modern day.

The estate was converted for use as hotel in the 1960s, and has since played host to Sandie Shaw, Winston Churchill, Margaret Thatcher, Sean Connery, Elton John, Catherine Zeta Jones, and Oliver Reed. In 2003, the hotel was bought by restaurateur James Thomson, who also maintains the acclaimed The Witchery by the Castle.


External Links

Coordinates: 55°56′11″N 3°09′27″W / 55.936426°N 3.157475°W

Retrieved from : http://en.wikipedia.org/w/index.php?title=Prestonfield_House&oldid=459968085

Y Combinator

Fixed-point combinator

In computer science, a fixed-point combinator (or fixpoint combinator ) is a higher-order function that computes a fixed point of other functions. A fixed point of a function f is a value x such that x = f(x). For example, 0 and 1 are fixed points of the function f(x) = x, because 0 = 0 and 1 = 1. Whereas a fixed-point of a first-order function (a function on "simple" values such as integers) is a first-order value, a fixed point of a higher-order function f is another function p such that p = f(p). A fixed-point combinator, then, is a function g which produces such a fixed point p for any function f:

g( f) = p, where p = f( p)

or, alternatively:

g( f) = f( g( f)).

Because fixed-point combinators are higher-order functions, their history is intimately related to the development of lambda calculus. One well-known fixed-point combinator in the untyped lambda calculus is Haskell Curry's Y = λf·(λx·f (x x)) (λx·f (x x)). The name of this combinator is sometimes incorrectly used to refer to any fixed-point combinator. The untyped lambda calculus however, contains an infinitude of fixed-point combinators. Fixed-point combinators do not necessarily exist in more restrictive models of computation. For instance, they do not exist in simply typed lambda calculus.

In programming languages that support anonymous functions, fixed-point combinators allow the definition and use of anonymous recursive functions, i.e. without having to bind such functions to identifiers. In this setting, the use of fixed-point combinators is sometimes called anonymous recursion.

How it works

Ignoring for now the question whether fixed-point combinators even exist (to be addressed in the next section), we illustrate how a function satisfying the fixed-point combinator equation works. To easily trace the computation steps, we choose untyped lambda calculus as our programming language. The (computational) equality from the equation that defines a fixed-point combinator corresponds to beta reduction in lambda calculus.

As a concrete example of a fixed-point combinator applied to a function, we use the standard recursive mathematical equation that defines the factorial function

fact( n) = if n = 0 then 1 else n * fact( n − 1)

We can express a single step of this recursion in lambda calculus as the lambda abstraction

 F = λf. λn. IFTHENELSE (ISZERO n) 1 (MULT n (f (PRED n))) 

using the usual encoding for booleans, and Church encoding for numerals. The functions in CAPITALS above can all be defined as lambda abstractions with their intuitive meaning; see lambda calculus for their precise definitions. Intuitively, f in F is a place-holder argument for the factorial function itself.

We now investigate what happens when a fixed-point combinator FIX is applied to F and the resulting abstraction, which we hope would be the factorial function, is in turn applied to a (Church-encoded) numeral.

 (FIX F) n = (F (FIX F)) n --- expanded the defining equation of FIX = (λx. IFTHENELSE (ISZERO x) 1 (MULT x ((FIX F) (PRED x)))) n --- expanded the first F = IFTHENELSE (ISZERO n) 1 (MULT n ((FIX F) (PRED n))) --- applied abstraction to n. 

If we now abbreviate FIX F as FACT, we recognize that any application of the abstraction FACT to a Church numeral calculates its factorial


Recall that in lambda calculus all abstractions are anonymous, and that the names we give to some of them are only syntactic sugar. Therefore, it's meaningless in this context to contrast FACT as a recursive function with F as somehow being "not recursive". What fixed point operators really buy us here is the ability to solve recursive equations. That is, we can ask the question in reverse: does there exist a lambda abstraction that satisfies the equation of FACT? The answer is yes, and we have a "mechanical" procedure for producing such an abstraction: simply define F as above, and then use any fixed point combinator FIX to obtain FACT as FIX F.

In the practice of programming, substituting FACT at a call site by the expression FIX F is sometimes called anonymous recursion. In the lambda abstraction F, FACT is represented by the bound variable f, which corresponds to an argument in a programming language, therefore F need not be bound to an identifier. F however is a higher-order function because the argument f is itself called as a function, so the programming language must allow passing functions as arguments. It must also allow function literals because FIX F is an expression rather than an identifier. In practice, there are further limitations imposed on FIX, depending on the evaluation strategy employed by the programming environment and the type checker. These are described in the implementation section.

Existence of fixed-point combinators

In certain mathematical formalizations of computation, such as the untyped lambda calculus and combinatory logic, every expression can be considered a higher-order function. In these formalizations, the existence of a fixed-point combinator means that every function has at least one fixed point; a function may have more than one distinct fixed point.

In some other systems, for example in the simply typed lambda calculus, a well-typed fixed-point combinator cannot be written. In those systems any support for recursion must be explicitly added to the language. In still others, such as the simply-typed lambda calculus extended with recursive types, fixed-point operators can be written, but the type of a "useful" fixed-point operator (one whose application always returns) may be restricted. In polymorphic lambda calculus (System F) a polymorphic fixed-point combinator has type ∀a.(a→a)→a, where a is a type variable.

Y combinator

One well-known (and perhaps the simplest) fixed-point combinator in the untyped lambda calculus is called the Y combinator. It was discovered by Haskell B. Curry, and is defined as:

Y = λf.(λx.f (x x)) (λx.f (x x))

We can see that this function acts as a fixed-point combinator by applying it to an example function g and rewriting:

Y g = (λf . (λx . f (x x)) (λx . f (x x))) g (by definition of Y)
= (λx . g (x x)) (λx . g (x x)) (β-reduction of λf: applied main function to g)
= (λy . g (y y)) (λx . g (x x)) (α-conversion: renamed bound variable)
= g ((λx . g (x x)) (λx . g (x x))) (β-reduction of λy: applied left function to right function)
= g (Y g) (by second equality)

In programming practice, the Y combinator is useful only in those languages that provide a call-by-name evaluation strategy, since (Y g) diverges (for any g) in call-by-value settings.

Example in Scheme

 (define Y (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg))))))) 

Factorial definition using Y Combinator

 (define fact (Y (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1)))))))) 

Example in Common Lisp

 (defun y (func) ((lambda (x) (funcall x x)) (lambda (y) (funcall func (lambda (&rest args) (apply (funcall y y) args)))))) 

Factorial program using the Y combinator

 (funcall (y (lambda (f) (lambda (x) (if (<= x 1) 1 (* x (funcall f (1- x))))))) 5) => 120 

Other fixed-point combinators

In untyped lambda calculus fixed-point combinators are not especially rare. In fact there are infinitely many of them. In 2005 Mayer Goldberg showed that the set of fixed-point combinators of untyped lambda calculus is recursively enumerable.

A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:

Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

Here is an example of this in Python:

 >>> Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args))) >>> fact = lambda f: lambda x: 1 if x == 0 else x * f(x-1) >>> Z(fact)(5) 120 

The Y combinator can be expressed in the SKI-calculus as

Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
Y' = S S K (S (K (S S (S (S S K)))) K)

which corresponds to the lambda expression

Y' = (λx. λy. x y x) (λy. λx. y (x y x))

This fixed-point combinator is simpler than the Y combinator, and β-reduces into the Y combinator; it is sometimes cited as the Y combinator itself:

X = λf.(λx.x x) (λx.f (x x))

Another common fixed point combinator is the Turing fixed-point combinator (named after its discoverer, Alan Turing):

Θ = (λx. λy. (y (x x y))) (λx. λy. (y (x x y)))

It also has a simple call-by-value form:

Θ v = (λx. λy. (y (λz. x x y z))) (λx. λy. (y (λz. x x y z)))

Some fixed point combinators, such as this one (constructed by Jan Willem Klop) are useful chiefly for amusement:

Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)


L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

Strictly non-standard fixed-point combinators

In untyped lambda calculus there are terms that have the same Böhm tree as a fixed-point combinator, that is they have the same infinite extension λx.x(x(x ... )). These are called non-standard fixed-point combinators. Evidently, any fixed-point combinator is also a non-standard one, but not all non-standard fixed-point combinators are fixed-point combinators because some of them fail to satisfy the equation that defines the "standard" ones. These strange combinators are called strictly non-standard fixed-point combinators; an example is the following combinator N = BM(B(BM)B), where B = λxyz.x(yz) and M = λx.xx. The set of non-standard fixed-point combinators is not recursively enumerable.

Implementing fixed-point combinators

In a language that supports lazy evaluation, like in Haskell, it is possible to define a fixed-point combinator using the defining equation of the fixed-point combinator. A programming language of this kind effectively solves the fixed-point combinator equation by means of its own (lazy) recursion mechanism. This implementation of a fixed-point combinator in Haskell is sometimes referred to as defining the Y combinator in Haskell. This is incorrect because the actual Y combinator is rejected by the Haskell type checker (but see the following section for a small modification of Y using a recursive type which works). The listing below shows the implementation of a fixed-point combinator in Haskell that exploits Haskell's ability to solve the fixed-point combinator equation. This fixed-point combinator is traditionally called fix in Haskell. Observe that fix is a polymorphic fixed-point combinator (c.f. the discussion in previous section on System F); its type is only shown for clarity—it can be inferred in Haskell. The definition is followed by some usage examples.

 fix :: (a -> a) -> a fix f = f (fix f) fix (const 9) -- const is a function that returns its first parameter and ignores the second; -- this evaluates to 9 factabs fact 0 = 1 -- factabs is F from our lambda calculus example factabs fact x = x * fact (x-1) (fix factabs) 5 -- evaluates to 120 

In the example above, the application of fix does not loop infinitely, because of lazy evaluation; e.g., in the expansion of fix (const 9) as (const 9)(fix f) , the subexpression fix f is not evaluated. In contrast, the definition of fix from Haskell loops forever when applied in a strict programming language, because the argument to f is expanded beforehand, yielding an infinite call sequence f (f ... (fix f) ... )) , which causes a stack overflow in most implementations.

In a strict language like OCaml, we can avoid the infinite recursion problem by forcing the use of a closure. The strict version of fix shall have the type ∀a.∀b.((a→b)→(a→b))→(a→b). In other words, it works only on a function which itself takes and returns a function. For example, the following OCaml code implements a strict version of fix :

 let rec fix f x = f (fix f) x (* note the extra x *) let factabs fact = function (* factabs now has extra level of lambda abstraction *) 0 -> 1 | x -> x * fact (x-1) let _ = (fix factabs) 5 (* evaluates to "120" *) 

The same idea can be used to implement a (monomorphic) fixed combinator in strict languages that support inner classes inside methods (called local inner classes in Java), which are used as 'poor man's closures' in this case. Even when such classes may be anonymous, as in the case of Java, the syntax is still cumbersome. Java code. Function objects, e.g. in C++, simplify the calling syntax, but they still have to be generated, preferably using a helper function such as boost::bind. C++ code.

Example of encoding via recursive types

In programming languages that support recursive types (see System Fω), it is possible to type the Y combinator by appropriately accounting for the recursion at the type level. The need to self-apply the variable x can be managed using a type (Rec a), which is defined so as to be isomorphic to (Rec a -> a).

For example, in the following Haskell code, we have In and out being the names of the two directions of the isomorphism, with types:

 In :: (Rec a -> a) -> Rec a out :: Rec a -> (Rec a -> a) 

which lets us write:

 newtype Rec a = In { out :: Rec a -> a } y :: (a -> a) -> a y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x))) 

Or equivalently in OCaml:

 type 'a recc = In of ('a recc -> 'a) let out (In x) = x let y f = (fun x a -> f (out x x) a) (In (fun x a -> f (out x x) a)) 

Anonymous recursion by other means

Although fixed point combinators are the standard solution for allowing a function not bound to an identifier to call itself, some languages like JavaScript provide a syntactical construct which allows anonymous functions to refer to themselves. For example, in Javascript one can write the following, although it has been removed in the strict mode of the latest standard edition.

 function(x) { return x === 0 ? 1 : x * arguments.callee(x-1); } 

See also




External links

Retrieved from : http://en.wikipedia.org/w/index.php?title=Fixed-point_combinator&oldid=465380705