Lambda račun

U matematičkoj logici i računarstvu, lambda račun, odnosno λ-račun, je formalni sistem dizajniran za ispitivanje definicije funkcije, aplikaciju funkcije, te rekurziju. Lambda račun se može koristiti za precizno definiranje izračunljive funkcije. Pitanje jesu li dva lambda izraza istovjetna ne može biti riješeno općenitim algoritmom. Ovo je bilo prvo pitanje, čak i prije problema zaustavljanja, za kojeg je mogla biti dokazana neodlučivost. Lambda račun je jako utjecao na funkcionalno programske jezike, kao što su Lisp, ML i Haskell.

Lambda račun se slobodno može nazvati najmanjim univerzalnim programskim jezikom. Sastoji se od jednog transformacijskog pravila (supstitucija varijable) i jednog načina definicije funkcije. Lambda račun je univerzalan na način da bilo koja izračunljiva funkcija može biti izražena i evaluirana koristeći njegov formalizam. Ovo je stoga istovjetno formalizmu Turingove mašine. Medutim, lambda račun naglašava transformacijska pravila i ne zamara se stvarnom mašinom koja ih ostvaruje i u tom smislu predstavlja pristup srodniji programskoj podršci nego hardveru.

Ovaj se članak bavi "netipovanim lambda računom" za razliku od u međuvremenu razvijenih tipovanih lambda računa.

 Historija 
Lambda račun je uveo Alonzo Church 1930-ih u sklopu istrage o temeljima matematike.A. Church, "A set of postulates for the foundation of logic", Annals of Mathematics, Druga serija, 33:346–366 (1932).Za čitavu historiju pogledajte Cardoneov i Hindley-ov "History of Lambda-calculus and Combinatory Logic" (2006). Za izvorni sistem je se pokazalo da je logički nedosljedan 1935-e kad su Stephen Kleene i J. B. Rosser razvili Kleene–Rosserov paradoks. Zatim, u 1936-oj, Church je izolovao i publicirao samo dio ovoga što je bilo relevantno za izračunavanje. Ovo sada predstavlja netipovani lambda račun.A. Church, "An unsolvable problem of elementary number theory", American Journal of Mathematics, Volume 58, No. 2. (Apr., 1936), str. 345-363. 1940-e godine, Church je također uveo sistem koji je bio računalno slabiji ali logički dosljedan što je sada poznat kao jednostavno tipovani lambda račun.A. Church, "A Formulation of the Simple Theory of Types", Journal of Symbolic Logic, Volume 5 (1940).

 Neformalni opis 

 Formalna definicija 

 Također pogledajte 
 Anonimna rekurzija
 Curry-Howard izomorfizam
 Knights of the Lambda Calculus
 Lambda kocka
 Prepisivanje
 SKI kombinatorni račun
 Sistem F
 Račun konstrukcija
 Tipovani lambda račun
 Unlambda

 Literatura 
 Abelson, Harold & Gerald Jay Sussman.  Structure and Interpretation of Computer Programs.  The MIT Press.  .
 Hendrik Pieter Barendregt, Introduction to Lambda Calculus.
 Hendrik Pieter Barendregt, The Type Free Lambda Calculus, str.1091–1132 u Handbook of Mathematical Logic, North-Holland (1977) .
 Henk Barendregt, The Impact of the Lambda Calculus in Logic and Computer Science. The Bulletin of Symbolic Logic, Volume 3, Number 2, June 1997.
 Cardone i Hindley, 2006. History of Lambda-calculus and Combinatory Logic. Gabbay i Woods, Handbook of the History of Logic, vol. 5.  Elsevier.
 Church, Alonzo, An unsolvable problem of elementary number theory, American Journal of Mathematics, 58 (1936), str. 345–363. Ova istraga sadrži dokaz da ekvivalencija lamdba računa općenito nije odlučiva.
 Kleene, Stephen, A theory of positive integers in formal logic, American Journal of Mathematics, 57 (1935), str. 153–173 i 219–244. Sadrži definicije lambda računa od različitih poznatih funkcija.
 Landin, Peter, A Correspondence Between ALGOL 60 and Church's Lambda-Notation, Communications of the ACM, vol. 8, broj 2 (1965), str. 89–101. Dostupno na ACM sajt u. Klasična istraga koja ističe značajnost lambda računa kao temelj programskih jezika.
 Larson, Jim, An Introduction to Lambda Calculus and Scheme . Jednostavni uvod za programere.
 Schalk, A. and Simmons, H. (2005) An introduction to λ-calculi and arithmetic with a decent selection of exercises . Bilježci za predmet Matematičke Logike (MSc) na Manchester Univerzitetu.
 de Queiroz, Ruy J.G.B. (2008) On Reduction Rules, Meaning-as-Use and Proof-Theoretic Semantics. Studia Logica, 90(2):211-247.

Monografije/udžbenici za postdiplomce:
 Morten Heine Sørensen, Pawel Urzyczyn, Lectures on the Curry-Howard isomorphism, Elsevier, 2006, .
 .

 Vanjski linkovi 
 Achim Jung, A Short Introduction to the Lambda Calculus-(PDF)
 David C. Keenan, To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction Raúl Rojas, A Tutorial Introduction to the Lambda Calculus-(PDF)
 Peter Selinger, Lecture Notes on the Lambda Calculus-(PDF)
 L. Allison, Neki λ-računski primjeri  Georg P. Loczewski, The Lambda Calculus and A++
 Bret Victor, Alligator Eggs: A Puzzle Game Based on Lambda Calculus Lambda Calculus '' na Safalra sajtu 
 Lambda Calculus na PlanetMath sajtu.
 LCI Lambda Interpreter. Jednostavni i jednako moćni računski interpreter.
 Lambda Calculus link on Lambda-the-Ultimate
 Mike Thyer, Lambda Animator . Grafički Java applet koji pokazuje alternativne strategije redukcije.
 An Introduction to Lambda Calculus and Scheme , Jim Larson.

 Reference 

Kategorija:Lambda račun
Kategorija:Računski modeli
Kategorija:Teorijsko računarstvo