Lambda Kalkül

knivil schrieb:

Fuer dich habe ich es aber noch kurz hineineditiert.

Das finde ich nett.

Ishildur

@knivil & µngbd
Hei ihr beiden, ich habe da noch eine Frage zum Lambda Kalkül, die ich nicht verstehe:

λx.(λx.xx)

1. Welches x innerhalb des Funktionskörpers der rechten Funktion ist denn nun an den Parameter der linken Funktion gebunden?

2. Was bedeutet überhaupt xx?
Ich meine, es ist weder ein Symbol, noch eine Applikation? Müsste es nicht vielmehr x x heissen oder ist xx OK?

Vielen Danke für eure Geduld

Christoph

Ishildur schrieb:

λx.(λx.xx)

1. Welches x innerhalb des Funktionskörpers der rechten Funktion ist denn nun an den Parameter der linken Funktion gebunden?

Es zählt immer die innerste lambda-Abstraktion. Deswegen ist "λx.(λx.xx)" das gleiche wie "λy.(λx.xx)".

Ishildur schrieb:

2. Was bedeutet überhaupt xx?
Ich meine, es ist weder ein Symbol, noch eine Applikation? Müsste es nicht vielmehr x x heissen oder ist xx OK?

Variablen bestehen in der Mathematik per Konvention immer aus einem Buchstaben (fast immer). Deswegen ist "xx" zu lesen als "x x", die Anwendungs der Funktion "x" auf den Parameter "x".

Ishildur

"λx.(λx.xx)" das gleiche wie "λy.(λx.xx)".

Bist du dir da ganz sicher? Sollte das y nicht auch in der rechten Funktion vorkommen?

Ishildur schrieb:

Sollte das y nicht auch in der rechten Funktion vorkommen?

Schwer zu sagen, oft schon. Man kann aber natürlich auch Argumente ignorieren, und muss das afaik auch manchmal tun.

Wenn xx eine Variable sein soll, wäre sie frei, und müsste irgendwo im Kontext zu finden sein (oder sie ist absichtlich frei, damit sie in irgendeinem Kontext passend festgelegt wird).

Christophs Interpretation halte ich für wahrscheinlicher, das könnte man durchaus maschinell interpretieren, Scheme: (lambda (x) (x x)) , in CL braucht man wahrscheinlich noch ein funcall . Das könnte man sicher sinnvoll verwenden, zB für den Y-Kombinator.

Ishildur

Ich stelle die Frage mal anders:
λxy.xy <=> [λx.(λy.yx) od. λx.(λy.xy)]

Ishildur schrieb:

Ich stelle die Frage mal anders:
λxy.xy <=> [λx.(λy.yx) od. λx.(λy.xy)]

Sowas wie λxy.xy ist (wie erwähnt) eine Erweiterung auf mehrere Parameter. Man kann das immer auch durch Currying machen (Schönfinkeln klingt besser), in dem die innere Funktion ein Argument nimmt und eine Funktion zurückgibt, die noch ein Argument nimmt und dann die Arbeit erledigt.

Unter diesem Siegel ist λxy.(...) das gleiche wie λx.(λy.(...)), das gilt auch für deine Frage.

Ich empfehle, neben Stift und Papier auch einen Computer zu verwenden. In Sprachen wie Haskell geht Currying von Haus aus, in den üblichen Lisp-Varianten könnte man die zusätzlichen Klammern mit einem Makro entfernen. Common Lisp ist btw nicht die beste Wahl wenn's um den Lambda-Kalkül geht, weil es verschiedene Namensräume für Funktionen und Variablen hat (und sonst auch noch einige).

Weiterführend ist auch lustig:
http://www.madore.org/~david/programs/unlambda/

Ishildur

Ja das habe ich schon verstanden, aber welches Symbol ist denn nun an welchen Parameter gebunden?

Achso. y ist üblicherweise der zweite, x der erste. Aber das ist reine Konvention, man kann es auch umgekehrt machen.

knivil

Mich wuerde mal interessieren, wo du diese Beispiele her hast.

Prof84

Hier mal eine humorvolle Darstellung, die mir gut geholfen hatte:
http://www.soton.ac.uk/~doctom/teaching/lambda/lambda.pdf