Co sprawia, że ​​rachunek lambda jest istotny w badaniu?

10

Jesienią rozpoczynam licencjat z informatyki, ale tak naprawdę nie rozumiem rachunku λ w kontekście programowania funkcjonalnego. Być może całkowicie błędnie to interpretuję, ale w oparciu o tę definicję z Encyklopedii Filozoficznej Stanforda jest to kolejna notacja funkcji.

Jeśli to jest właśnie to, dlaczego jest korzystne stosowanie λ nazębnego nad regularnych zapisów funkcyjnych algorytm do obliczania czasu pracy?

programming-languages lambda-calculus Jules
źródło
5
To nie jest „kolejna notacja funkcji”, ale „pierwsza notacja funkcji”.
Andrej Bauer,
Dzięki za sugestię, @Kaveh. Będę o tym pamiętać w przypadku przyszłych postów, jednak odpowiedź mhelvensa jest doskonała, więc nie ma potrzeby stosowania poprzeczki.
To formalnie zdefiniowana bryła obiektów. Nie rozumiem, jaki jest twój dokładny problem.
Raphael
Tak naprawdę nie rozumiałem terminologii ani tego, dlaczego tak się dzieje. Robi się to w programowaniu funkcjonalnym, dopóki nie dowiedziałem się o rachunku lambda. Sprawia, że ​​konstrukcje oprogramowania wydają się znacznie mniej arbitralne.
dansalmo

Odpowiedzi:

13

W informatyce chcemy analizować i rozumieć kod źródłowy z matematyczną dyscypliną. To jedyny sposób na udowodnienie interesujących właściwości (takich jak zakończenie) z absolutną pewnością. W tym celu potrzebujemy języka o bardzo dobrze zdefiniowanym znaczeniu dla każdej konstrukcji.

λ

λ

λλ

mhelvens
źródło
3
imo, niektóre informatyki mogą dotyczyć zrozumienia kodu źródłowego, ale stwierdzenie, że to prawda, brzmi jak powiedzenie, że fizyka polega na zrozumieniu rakiet z matematyczną dyscypliną. informatyka dotyczy obliczeń. Powiązaną skargą jest to, że wydajność języka ma znaczenie, jeśli chcesz przestudiować wydajność i źle sformułowany kod źródłowy. W tym sensie prawdopodobnie lepiej jest myśleć o TM jako o sposobie myślenia o wydajności niż o modelu imperatywnych języków (i dla obu celów słowo-RAM może być lepszym wyborem)
Sasho Nikolov
btw to, co napisałem powyżej, nie oznacza, że ​​nie podoba mi się twoja odpowiedź :)
Sasho Nikolov
Zgoda. ;-) Naprawiony.
mhelvens,
1
Maszyny Turinga są okropne w rozumowanie o kodzie imperatywu, to o wiele łatwiejsze w użyciu języka zabawki jak proste while typu języka. stackoverflow.com/questions/507310/the-while-language . Maszyny Turinga pozostają bardzo przydatne do wglądu w teorię złożoności.
cody
1

λλ

Jeśli to jest właśnie to, dlaczego jest korzystne stosowanie λ nazębnego nad regularnych zapisów funkcyjnych algorytm do obliczania czasu pracy?

istnieje wiele zalet korzystania z Lisp lub programowania funkcjonalnego, a obliczanie czasu działania algorytmu jest tylko jedną z możliwości (chociaż byłoby pomocne, gdyby zacytowano za to referencję). ponieważ jest już w notacji funkcjonalnej, czasami określając formuły dla czasu wykonywania za pomocą relacji indukcyjnych lub rekurencyjnych, może mieć silniejszy lub bardziej oczywisty związek z pierwotnym kodem. inne rodzaje analizy algorytmu są również uproszczone.

kolejną główną zaletą jest prostota syntaktyczna. parsery dla innych języków są bardzo złożone, ale parsery Lisp są bardzo proste. więc Lisp jest świetnym językiem do nauki teorii parsowania.

innym kluczowym aspektem jest bardziej analiza oprogramowania z logicznego lub matematycznego obiektywu / widoku niż z perspektywy „komputerowo-naukowej”.

jak wskazuje druga odpowiedź, Lisp polega na rekurencji zamiast iteracji, a rekurencja jest w centrum CS.

λ

[1] Struktura i interpretacja programów komputerowych, autor: Abelson i Sussman

vzn
źródło