Was macht Lambda Calculus für das Studium relevant?

Question

Ich beginne im nächsten Herbst einen Bachelor-Informatikkurs, aber ich kann λ-Kalkulus im Kontext der funktionalen Programmierung nicht wirklich verstehen. Ich kann dies vollständig falsch interpretieren, aber basierend darauf Definition Aus der Stanford -Enzyklopädie der Philosophie ist es nur eine weitere Notation für Funktionen.

Wenn es ist Warum ist es vorteilhaft, λ-Kalkulus über reguläre Funktionsnotationen zu verwenden, um die Laufzeit von Algorithmus zu berechnen?

Answer 1

In der Informatik möchten wir den Quellcode mit mathematischer Strenge analysieren und verstehen. Dies ist der einzige Weg, um interessante Eigenschaften (z. B. Beendigung) mit absoluter Gewissheit zu beweisen. Dafür brauchen wir eine Sprache mit einer sehr genau definierten Bedeutung für jedes Konstrukt.

Theoretisch könnte dies jede Sprache mit einem guten sein formelle Semantik. Aber um die Dinge weniger kompliziert und weniger anfällig für Fehler zu machen, ist es am besten, eine Sprache zu verwenden, die so einfach wie möglich ist, aber immer noch in der Lage ist, ein Programm auszudrücken (dh IS ist Turing vollständig). Für die Argumentation über den imperativen Code gibt es Turing -Maschinen. Um jedoch über funktionale Programme zu argumentieren, gibt es den $ lambda $ -Calculus.

Das grundlegende $ lambda $ -Calculus ist wie eine funktionale Programmiersprache, aber mit viel "Gepäck" herausgenommen. Es ist nicht wichtig, dass dies eine nette Sprache ist, um tatsächlich Programme zu schreiben, oder dass es sich um eine effiziente Sprache handelt. Nur dass es einfach und ausdrucksstark ist. Zum Beispiel brauchen wir keine Schleifen, da wir sie mit Rekursion simulieren können. Und wir brauchen keine Funktionen mit mehreren Parametern, da wir sie mit simulieren können Currying.

Irgendwann möchten Sie möglicherweise Eigenschaften über Konstrukte beweisen, die nicht Teil des grundlegenden (untyped) $ lambda $ -Calculus sind. Deshalb haben Informatiker es im Laufe der Jahre in verschiedene Richtungen erweitert. Zum Beispiel gibt es eine Menge Variationen von Typen über Typ-Systeme tippt $ lambda $ -Calculi.

Answer 2

Seltsamerweise sprechen viele Bücher über $ lambda $ calculus ohne zu erwähnen Lispeln oder Planen, moderne Programmiersprachen, die darauf basieren und die Schüler leider mit der Idee lassen, dass es alt und abstrakt und meist theoretisch ist. Das Studium von Lisp oder Schema kann ein großer Winkel sein, um $ lambda $ calculus immens zu verstehen.

Wenn es ist Warum ist es vorteilhaft, λ-Kalkulus über reguläre Funktionsnotationen zu verwenden, um die Laufzeit von Algorithmus zu berechnen?

Die Verwendung von LISP- oder Funktionsprogrammierungen und Berechnung von Algorithmus -Laufzeit ist nur eine Möglichkeit (obwohl dies hilfreich wäre, wenn Sie einen Schiedsrichter dafür zitieren würden). Da es bereits in funktionaler Notation die Formeln für die Laufzeit durch Induktion oder Wiederholungsbeziehungen ermittelt, kann es eine stärkere oder offensichtliche 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. LISP ist also eine großartige Sprache, um die Theorie des Parsens zu studieren.

Ein weiterer Schlüsselaspekt ist die Analyse von Software mehr von a logisch oder mathematisch Linse/Ansicht und nicht eine "computerwissenschaftliche" Perspektive.

Wie die andere Antwort hervorhebt, dreht sich in LiSP alles um Rekursion anstelle von Iteration und Rekursion ist sehr im Herzen von CS.

Weitere Anwendung für ein "$ lambda $ -view" und ein Detail finden Sie in [1], einem kostenlosen Online- und Halb-Ref.

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