Welche Beziehung besteht zwischen Lambda-Kalkül und Programmiersprachen? [geschlossen]

13

Ich beginne nächstes Jahr mein erstes Studienjahr in Informatik und schreibe hauptsächlich in C (wenn das wichtig ist). Ich habe versucht zu suchen, aber das meiste, was ich finde, setzt Kenntnisse der Lambda-Rechnung voraus. Warum ist Lambda-Kalkül beim Programmieren so viel nützlicher als Einzelvariablen-Kalkül? Gibt es einen Zusammenhang zwischen Lambda-Ausdrücken und funktionalen Programmen? Hat die Arbeit der Alonzo-Kirche zur Lambda-Rechnung die Entwicklung der Programmiersprachen beeinflusst?

Alle außerhalb der Schule schwirren darüber und ich habe keine Ahnung, wovon sie sprechen werden, obwohl ich gespannt darauf bin, es zu lernen und zu sehen, wie es direkt mit meiner Programmierung und meinem Verständnis von Programmiersprachen zusammenhängt.

RonaldMunodawafa
quelle
2
Diese Frage wird unter cs.stackexchange.com besser beantwortet .
Davidk01
@ ChrisF. Vielleicht passt diese Frage besser zu einer der Informatikseiten. Wenn nicht, habe ich versucht, es einzugrenzen und mich zu fragen, ob es in seiner aktuellen Form wieder geöffnet werden kann.
Tom Au
Mathematica hat Lambda-Kalkül eingebrannt, aufgefallen, dass es niemand erwähnt hat.
William

Antworten:

26

Der Lambda-Kalkül ist interessant, elegant und erleichtert das Verständnis funktionaler Programmiersprachen. Sie werden jedoch in einem typischen CS-Bachelor-Kurs nicht auf den LC stoßen, so dass Sie ihn jetzt nicht lernen müssen - ich würde empfehlen, zuerst mit funktionalen Sprachen zu experimentieren, bevor Sie den Lambda-Kalkül überarbeiten. Ich glaube, OCaml ist ein guter Ausgangspunkt für die funktionale Programmierung eines C-Programmierers, und dieses Schema ist ein guter Ausgangspunkt, um in die Lambda-Rechnung einzutauchen.

Der Lambda-Kalkül ist nicht mit dem Kalkül verbunden (der stattdessen Analyse genannt werden sollte). Im Allgemeinen ist ein Kalkül ein „formales System“, dh ein Satz von Regeln, um etwas zu tun. Während die Differentialrechnung Regeln für die Änderung von Werten enthält, beschreiben die Regeln der Lambda-Rechnung die Berechnung selbst. Aus diesen Grundregeln können wir beliebige Berechnungen, Datendarstellungen wie Boolesche Werte, Ganzzahlen oder Listen erstellen und sogar Ablaufkonstruktionen wie Bedingungen oder Schleifen steuern. Der LC entspricht Turing Machines, aber beide Modelle haben unterschiedliche Stärken.

Lambda-Kalkül hatte einen immensen Einfluss auf die Programmiersprachen. Die zweite zu implementierende Hochsprache war Lisp, was als direkte Codierung des LC in eine Programmiersprache verstanden werden kann. Diese „funktionale Programmierung“ hat enorme Auswirkungen auf die Entwicklung der Programmiersprachen. Features wie anonyme Funktionen, Funktionszeiger, Closures (verschachtelte Funktionen), Garbage Collection, Variablenumfang, Metaprogrammierung, Fortschritte in Typsystemen, Typinferenz, interpretierte Sprachen, dynamisch typisierte Sprachen und objektorientierte Programmierung sind zu einem großen Teil zu verdanken in den funktionalen Programmierzweig der Programmiersprachen. Es gibt einen Witz, dass jede neue (nicht akademische) Programmiersprache nur Funktionen hinzufügt, die Lisp bereits seit Jahrzehnten hat.

Darüber hinaus sind der Lambda-Kalkül und andere verwandte Kalküle unverzichtbare Werkzeuge in der Programmiersprachtheorie und in bestimmten Compiler-Konstruktionstechniken.

Jede Sprache, die anonyme Funktionen hat, die sich wie Abschlüsse verhalten und frei herumgereicht werden können, enthält sofort eine Kodierung des Lambda-Kalküls. Anonyme Funktionen entsprechen einem Lambda-Ausdruck, nur dass in den LC-Funktionen immer genau ein Argument steht. Jede Turing-complete-Sprache entspricht jedoch dem LC, sodass der LC immer über solchen Sprachen implementiert werden kann. Dies geschieht in der Regel in Regel-Matching-Systemen oder in übermäßig intelligenten Konfigurationsformaten, was (meistens im Scherz) zu „Greenspuns zehnter Regel“ führt: „ Jedes ausreichend komplizierte C- oder Fortran-Programm enthält ein ad-hoc, informell spezifiziertes, fehlerbehaftetes Programm , langsame Implementierung der Hälfte von Common Lisp. "

amon
quelle
Dies ist eine bessere Antwort als die, die ich zuvor ausgewählt hatte. Ihre Antwort trifft wirklich zu Hause. Genau das habe ich gesucht!
RonaldMunodawafa
"... außer dass in den LC-Funktionen immer genau ein Argument steht": Heißt dieses Feature currying oder hängt es zumindest damit zusammen?
Giorgio
@Giorgio Currying ist anders, aber verwandt. LC hat keine Funktionen mit mehreren Argumenten, aber diese können einfach als verschachtelte Funktionen codiert werden, die jeweils ein Argument enthalten. Beispiel mit ML-Notation: x = fn (a, b, c) => a + b + c(Typ int * int * int -> int, Aufruf fn (1, 2, 3)) kann in x = fn a => fn b => fn c => a + b + c(Typ int -> int -> int -> int, Aufruf ((x 1) 2) 3- Parens optional in ML) umgewandelt werden. Anstatt nun alle drei Argumente zu liefern, können wir auch nur zwei liefern: plus3 = x 1 2das hat Typ int -> int. Dies ist eine teilweise Anwendung / Currying.
amon
Ich dachte, dass das Currying bedeutet, dass alle Funktionen nur ein Argument enthalten (wie in LC).
Giorgio
8

Die Lambda-Rechnung hat nichts mit der Differential- / Integralrechnung zu tun. Kalkül im allgemeinsten Sinne des Wortes bedeutet nur ein Rechensystem.

Auf einer sehr hohen Ebene ist die Lambda-Berechnung ein Berechnungsmodell, genau wie eine Turing-Maschine ein Berechnungsmodell ist. Der Grund, warum Programmiersprachenforscher Lambda-Kalkül studieren, liegt darin, dass es als Modell starke Verbindungen zu formalen Methoden in der Mathematik wie Logik und Kategorietheorie aufweist. Daher können Methoden aus diesen Bereichen angewendet werden, um verschiedene Aspekte und Erweiterungen der Lambda-Rechnung zu untersuchen, was wiederum dazu beiträgt, bessere Programmiersprachen mit bestimmten Eigenschaften zu entwerfen.

Der direkteste Einfluss der Lambda-Rechnung in Programmiersprachen tritt normalerweise in Form erstklassiger Funktionen und Abschlüsse auf. C unterstützt keine Closures, daher müssen Sie das Konzept in einer höheren Sprache wie Lisp, Python, Ruby, JavaScript usw. untersuchen. Historisch gesehen wird Lisp als die erste konkrete Implementierung von Lambda-Kalkül als Programmiersprache angesehen .

davidk01
quelle
1
Vielleicht möchten Sie bestimmte Sprachen erwähnen, die der Lambda-Rechnung sehr nahe kommen, z. B. Lisp.
Giorgio
1
Ich lerne noch Scheme mit SICP und hoffe, dass ich mehr über diesen Bereich erfahren werde. Vielen Dank für Ihre ausführliche Antwort und Anregung.
RonaldMunodawafa