Ist Lambda Calculus rein syntaktisch?

29

Ich habe ein paar Wochen lang über den Lambda-Kalkül gelesen, aber ich habe noch nichts gesehen, das sich materiell von vorhandenen mathematischen Funktionen unterscheidet, und ich möchte wissen, ob es sich nur um eine Notationssache handelt oder ob es irgendwelche neuen gibt Eigenschaften oder Regeln, die von den Axiomen der Lambda-Rechnung erstellt wurden und nicht für jede mathematische Funktion gelten. So habe ich zum Beispiel gelesen, dass:

"Es kann anonyme Funktionen geben" : Lambda-Funktionen sind nicht anonym, sondern werden nur Lambda genannt. In der mathematischen Notation ist es zulässig, dieselbe Variable für verschiedene Funktionen zu verwenden, wenn der Name nicht wichtig ist. Beispielsweise werden die beiden Funktionen in einer Galois-Verbindung häufig als * bezeichnet.

"Funktionen können Funktionen als Eingaben akzeptieren" : Nicht neu können Sie dies mit normalen Funktionen tun.

"Funktionen sind Black Boxes" : Nur Ein- und Ausgänge sind auch gültige Beschreibungen mathematischer Funktionen ...

Dies mag wie eine Diskussion oder eine mit einer Meinung versehene Frage erscheinen, aber ich glaube, dass es eine "richtige" Antwort auf diese Frage geben sollte. Ich möchte wissen, ob die Lambda-Rechnung nur eine Schreibweise oder eine syntaktische Konvention für die Arbeit mit mathematischen Funktionen ist oder ob es wesentliche oder semantische Unterschiede zwischen Lambdas und gewöhnlichen Funktionen gibt.

Neil
quelle
2
Ich möchte keine vollständige Antwort daraus machen, aber Funktionen können keine Funktionen als Eingaben akzeptieren. Ich kann f (g (0)) schreiben, aber ich kann f (g, 0) nicht schreiben. Letzteres wird als "funktional" bezeichnet und erfordert unterschiedliche Regeln.
Cort Ammon - Setzen Sie Monica
@ CortAmmon-Funktionen sind Funktionen. Eine Funktion ist nur eine Menge von Paaren (obwohl es genau genommen ein Tripel (D, R, G) ist, wobei D die Domäne ist, R der Bereich ist und G der Graph (eine Menge von Paaren), ein weiteres kleines Problem, das ich habe mit der akzeptierten Antwort, aber das ist weder hier noch da). Wenn also D eine Menge von Funktionen ist und Sie Paare nehmen, bei denen das erste Element eine Funktion in D ist, dann haben Sie eine Funktion. Überprüfen Sie Wikipedia: "Eine Funktion ist eine Zuordnung [Funktion] ..."
Neil
Dh alle Funktionen sind Funktionen, nicht alle Funktionen sind Funktionen. Aber alle Regeln, die für Funktionen gelten, gelten für Funktionale
Neil

Antworten:

63

Ironischerweise ist der Titel auf den Punkt gebracht, aber nicht so, wie Sie es zu meinen scheinen: "Ist der Lambda-Kalkül nur eine Notationskonvention?", Was nicht korrekt ist.

Lambda-Terme sind keine Funktionen 1 . Sie sind Syntaxelemente, dh Symbolsammlungen auf einer Seite. Wir haben Regeln für die Manipulation dieser Symbolsammlungen, insbesondere für die Beta-Reduzierung. Sie können mehrere verschiedene Lambda-Terme haben, die der gleichen Funktion entsprechen. 2

Ich werde Ihre Punkte direkt ansprechen.

Erstens ist Lambda kein Name, der wiederverwendet wird. Dies wäre nicht nur äußerst verwirrend, sondern wir schreiben auch nicht λ(x) (oder (λ x) ), was wir tun würden, wenn λ ein Name für eine Funktion wäre, genau wie wir f(x) schreiben . In f(x) konnten wir ersetzen f mit dem Lambda - Term Herstellung von so etwas wie (wenn es von einem Lambda - Ausdruck definiert wurde) (λy.y)(x) bedeutet (λy.y) ist ein Ausdruck, der eine Funktion darstellen kann, keine Deklaration, die eine Funktion deklariert (mit dem Namenλ oder etwas anderem). Wenn wir die Terminologie / Notation überladen, geschieht dies jedenfalls (so hofft man) auf eine Art und Weise, bei der eine eindeutige Zuordnung über den Kontext möglich ist, was bei Lambda-Begriffen sicherlich nicht der Fall ist.

Ihr nächster Punkt ist in Ordnung, aber etwas irrelevant. Dies ist kein Wettbewerb, bei dem es Team Lambda Terms und Team Functions gibt, und nur einer kann gewinnen. Eine Hauptanwendung von Lambda-Begriffen ist das Studieren und Verstehen bestimmter Arten von Funktionen. Ein Polynom ist keine Funktion, obwohl wir sie oft schlampig identifizieren. Das Studieren von Polynomen bedeutet nicht, dass man glaubt, dass alle Funktionen Polynome sein sollten, und es ist auch nicht so, dass Polynome etwas "Neues" tun müssen, um es wert zu sein, studiert zu werden.

Mengen-theoretische Funktionen sind keine Black Boxes, obwohl sie vollständig durch ihre Eingabe-Ausgabe-Beziehung definiert sind. (Sie buchstäblich sind ihre Input-Output - Relation.) Lambda Begriffe sind auch nicht schwarz - Boxen , und sie sind nicht durch ihr Input-Output - Verhältnis definiert. Wie ich bereits erwähnt habe, können Sie verschiedene Lambda-Terme verwenden, die die gleiche Eingabe-Ausgabe-Beziehung ergeben. Dies unterstreicht auch die Tatsache, dass Lambda-Terme keine Funktionen sein können, obwohl sie Funktionen auslösen können. 2

Tatsächlich ist die Analogie zwischen Polynomen und Lambda-Termen sehr ähnlich, und ich vermute, dass Sie die Unterscheidung zwischen einem Polynom und der Funktion, die es darstellt, nicht richtig einschätzen, weshalb ich etwas näher darauf eingehen werde. 3 Wenn Polynome eingeführt werden, normalerweise mit reellen Koeffizienten, werden sie typischerweise als reelle Funktionen eines bestimmten Typs behandelt. Betrachten Sie nun die Theorie der Linear-Feedback-Schieberegister (LFSRs). Es ist größtenteils die Theorie von (univariaten) Polynomen über F2 , aber wenn wir das als Funktion F2F2 , dann gibt es höchstens 4 solcher Funktionen. Es gibt jedoch unendlich viele Polynome über F2 . 4Eine Möglichkeit, dies zu sehen, besteht darin, dass wir diese Polynome als etwas anderes alsF2F2 -Funktioneninterpretieren können, was in der Tat jedeF2 -Algebra tun wird. Für LFSR interpretieren wir die Polynome gewöhnlich als Operationen auf Bitströmen, die, wenn wir wollten, als Funktionen2N2N könnten, obwohl die überwiegende Mehrheit dieser Funktionen nicht im Bild der Interpretation eines LFSR wäre.

Dies gilt auch für Lambda-Terme. Wir können beide als andere Dinge als Funktionen interpretieren. Sie sind auch beide viel leichter zu handhabende Objekte als die normalerweise unzähligen unendlichen Mengen von Funktionen. Sie sind beide viel rechenintensiver als beliebige Funktionen. Ich kann ein Programm schreiben, um Polynome (mit Koeffizienten, die zumindest berechenbar sind) und Lambda-Terme zu manipulieren. In der Tat sind untypisierte Lambda-Terme eines der ursprünglichen Modelle berechenbarer Funktionen. Diese symbolischere / syntaktischere, berechnendere / rechnendere Perspektive wird normalerweise stärker betont, insbesondere für den untypisierten Lambda-Kalkül, als für die semantischeren Interpretationen des Lambda-Kalküls. GetipptLambda-Terme sind weitaus handlichere Dinge und können normalerweise (aber nicht immer) leicht als Mengenfunktionen interpretiert werden, können aber auch normalerweise in eine noch breitere Klasse von Dingen interpretiert werden als der untypisierte Lambda-Kalkül. Sie haben auch eine reiche eigene syntaktische Theorie und eine sehr tiefe Verbindung zur Logik .

1 Es ist möglich, dass das Problem in die andere Richtung geht. Vielleicht haben Sie ein Missverständnis darüber, was eine Funktion ist.

DDDDDDund für die Kategorie der Mengen gibt es keine nicht trivialen reflexiven Objekte. Die Geschichte ist für typisierte Lambda-Begriffe etwas anders , kann aber dennoch nicht trivial sein.

3 Wenn Sie sich über diese Unterscheidung klar sind, sollte die Analogie ziemlich informativ sein.

4 Dieses Problem tritt bei Feldern des Merkmals 0 wie komplexen Zahlen, Real, Rationalen oder Ganzzahlen nicht auf, sodass die Unterscheidung nicht so scharf ist, obwohl sie noch vorhanden ist.

Derek Elkins
quelle
8
Dies ist eine erstaunliche Antwort, die ich nur zu sagen habe. Klärt wirklich einige lange Missverständnisse für mich. Vielen Dank!
am
4
Ich wünschte, ich könnte detailliert darauf antworten! Viele Dinge, die ich gerne weiterverfolgen würde. Insgesamt war dies für mich und anscheinend auch für einige andere sehr nützlich. Vielen Dank für die gründliche und bedachte Antwort.
Neil
1
Es gibt nur einen Punkt, mit dem ich mich auseinandersetzen möchte, nämlich Ihre Behauptung, dass Polynome nichts "Neues" tun müssen, um studienwürdig zu sein. Natürlich tun sie das! Natürlich kann "neu" abhängig von Ihrem Fachgebiet unterschiedliche Bedeutungen haben (Ein reiner Mathematiker wird also nicht zwischen Spaltenvektoren und Zeilenvektoren unterscheiden, weil sie isomorph sind, aber ein Statistiker kann die Unterscheidung als nützlich für Berechnungszwecke ansehen). Jeder neue Formalismus muss sich rechtfertigen.
Neil
2
@Neil: Insbesondere Fußnote 2 liefert einige sehr klare Beweise dafür, dass der Lambda-Kalkül "etwas Neues macht", was "reguläre" Funktionen "nicht können". Ein konkreteres Beispiel für einen nicht fundierten Lambda-Ausdruck finden Sie unter Festkomma-Kombinatoren . Die Kirche Ziffern auch für eine faszinierende Lektüre, vor allem der Vorgänger - Funktion.
Kevin
1
Ich würde hinzufügen, dass Lambdas als Funktionen nichts Sinnvolles tun. Das einzige, was Sie mit einem Lambda tun können, ist, es als Lambda zu übergeben, und es gibt ein Lambda zurück. Sie können nicht testen, was das resultierende Lambda bewirkt. Sie können nur ein weiteres Lambda übergeben, um im Gegenzug ein weiteres Lambda zu erhalten. Als Funktionen verhält sich die Menge der "Lambda-Funktionen" genau wie eine Singleton-Menge, die nur die Identitätsfunktion enthält. Nur wenn Sie die Eingabe und Ausgabe eines Lambdas als Ausdrücke betrachten, können Sie die Lambdas unterscheiden.
Florian F
0

Denken Sie über das Konzept der Variablen nach. In alten Sprachen wie Basic hatten Sie keine dynamische Zuordnung und benötigten einen Namen für jede Variable. (Dies ist nicht genau, da Sie Arrays hatten, aber die Idee ist, dass ...) In vielen Fällen müssen Sie in der Lage sein, so viele Variablen zuzuweisen, wie Sie möchten, ohne durch die Anzahl der von Ihrem Programm definierten Namen beschränkt zu sein.

Mit Lambda-Funktionen können Sie die gleiche Einschränkung bei Funktionsnamen aufheben, sodass Ihr Programm so viele Funktionen definieren kann, wie es benötigt, und diese in den gleichen komplexen Datenstrukturen wie andere Variablen "speichern" kann. Mit herkömmlichen benannten Funktionen ist dies nicht möglich.

Camion
quelle
Warum kann ich das nicht mit herkömmlichen benannten Funktionen machen? Wenn ich schreibe f(x)=let g(y)=x+y in g, weiß jeder Mathematiker sofort, was gemeint ist und ist sich einig, dass dies ein vernünftiges mathematisches Objekt ist (vielleicht bis zu einigen Uneinigkeiten darüber, inwieweit klar ist, in welchem ​​Bereich es sich befindet f). Sie werden sich auch sehr freuen, wenn ich dann die Menge aufschreibe {f(n) | n ∈ ℕ}, die unendlich viele Funktionen enthält und insbesondere nicht durch eine endliche Anzahl von zu verwendenden Namen eingeschränkt ist.
Daniel Wagner,
Die Frage ist über Lambda-Kalkül. Das ist zwar verwandt, aber nicht dasselbe wie Lambda-Funktionen in Programmiersprachen.
Andy Dent