Was macht Lambda-Kalkül für das Studium relevant?

Ich beginne im nächsten Herbst einen Bachelor-Informatikkurs, kann aber λ-Kalkül im Kontext der funktionalen Programmierung nicht wirklich verstehen. Ich kann dies völlig falsch interpretieren, aber basierend auf dieser Definition aus der Stanford Encyclopedia of Philosophy ist es nur eine weitere Notation für Funktionen.

Wenn es nur so ist , warum ist es vorteilhaft, λ-Kalkül gegenüber regulären Funktionsnotationen zu verwenden, um die Laufzeit des Algorithmus zu berechnen?

programming-languages lambda-calculus Jules
quelle

Es ist nicht "nur eine andere Notation für Funktionen", sondern "die erste Notation für Funktionen".

Andrej Bauer

Danke für den Vorschlag, @Kaveh. Ich werde es für zukünftige Posts berücksichtigen, aber die Antwort von mhelvens ist ausgezeichnet, so dass kein Crosspost erforderlich ist.

Es ist ein formal definierter Körper von Objekten. Ich verstehe nicht, was genau Ihr Problem ist.

Raphael

Ich habe die Terminologie oder die Gründe, warum Dinge in der funktionalen Programmierung gemacht wurden, nicht wirklich verstanden, bis ich etwas über Lambda-Kalkül gelernt habe. Dadurch wirken Software-Konstrukte weit weniger willkürlich.

Dansalmo

Antworten:

In der Informatik wollen wir den Quellcode mit mathematischer Genauigkeit analysieren und verstehen. Nur so können interessante Eigenschaften (z. B. Terminierung) mit absoluter Sicherheit nachgewiesen werden. Dafür brauchen wir für jedes Konstrukt eine Sprache mit einer sehr genau definierten Bedeutung.

$\lambda$

$\lambda$ $\lambda$

mhelvens
quelle

Imo, in einigen Informatikbereichen geht es vielleicht darum, den Quellcode zu verstehen, aber zu sagen, dass dies im Allgemeinen zutrifft, klingt so, als würde man sagen, dass es in der Physik darum geht, Raketen mit mathematischer Genauigkeit zu verstehen. In der Informatik geht es um Berechnung. Eine verwandte Beschwerde ist , dass die Effizienz der Sprache tut ganz gleich , ob Sie studieren Effizienz wollen und nicht wohlgeformt Quellcode. In diesem Sinne ist es wahrscheinlich besser, über TMs nachzudenken, um über Effizienz nachzudenken, als über ein Modell zwingender Sprachen (und für beide Zwecke ist das Wort RAM möglicherweise die bessere Wahl)

Sasho Nikolov,

Übrigens bedeutet das, was ich oben geschrieben habe, nicht, dass ich Ihre Antwort nicht mag :)

Sasho Nikolov

Einverstanden. ;-) Fest.

Mhelvens

Turing - Maschinen Argumentation über Imperativ Code scheußlich sind, ist es viel einfacher , ein Spielzeug Sprache wie ein einfach zu bedienen , während Typ Sprache. stackoverflow.com/questions/507310/the-while-language . Turingmaschinen bleiben sehr nützlich für Einblicke in die Komplexitätstheorie.

Cody

$\lambda$ $\lambda$

Wenn es nur so ist , warum ist es vorteilhaft, λ-Kalkül gegenüber regulären Funktionsnotationen zu verwenden, um die Laufzeit des Algorithmus zu berechnen?

Die Verwendung von Lisp oder der funktionalen Programmierung bietet viele Vorteile, und die Berechnung der Laufzeit des Algorithmus ist nur eine Möglichkeit (obwohl es hilfreich wäre, wenn Sie dafür einen Verweis zitieren würden). da es bereits in funktionaler Notation ist, kann das Bestimmen der Formeln für die Laufzeit über Induktions- oder Wiederholungsbeziehungen manchmal eine stärkere oder offensichtlichere Beziehung zum ursprünglichen Code haben. Andere Arten der Analyse des Algorithmus werden ebenfalls vereinfacht.

Ein weiterer Hauptvorteil ist die syntaktische Einfachheit. Parser für andere Sprachen sind sehr komplex, aber die Lisp-Parser sind sehr einfach. Daher ist Lisp eine großartige Sprache, um die Theorie des Parsens zu studieren.

Ein weiterer wichtiger Aspekt ist die Analyse von Software eher aus einer logischen oder mathematischen Perspektive als aus einer "computerwissenschaftlichen" Perspektive.

Wie die andere Antwort zeigt, dreht sich bei Lisp alles um Rekursion statt um Iteration, und Rekursion ist das Herzstück von CS.

$\lambda$

[1] Struktur und Interpretation von Computerprogrammen von Abelson & Sussman

vzn
quelle