Lambda-Kalkül Ausdruck

Question

Für einen Lambda-Ausdruck (x (λx y. x y) z h), ich verstand nicht, wie freie Variablen x (outer x), z und h können in C-Code umgewandelt werden?

Viele Grüße, darkie

Answer 1

Freie Variablen sind ein Sonderfall in der Lambda-Kalkül - sie kann nicht „umgewandelt“ zu allem, so in der Regel sind sie nur als Symbole genommen. In Ihrem Beispiel und einige fiktive Konstrukteuren für Lambda-Ausdrücke gegeben, würden Sie es auf die folgende übersetzen C-ähnlichen Ausdruck (die mit dem impliziten currying beinhaltet den Umgang):

mk_app(mk_app(mk_app(mk_sym("x"),
                     mk_lam("x",
                            mk_lam("y",
                                   mk_app(mk_var("x"),
                                          mk_var("y"))))),
              mk_sym("z")),
       mk_sym("h"));

Natürlich können Sie mk_var() für diese Symbole verwenden zu, aber das wäre irreführend, da sie nicht wirklich Variablen sind, da sie nicht gebunden sind. Mit anderen Worten, wenn Sie eine Alpha-Konvertierung auf dem Ausdruck zu tun, müssen sie gleich bleiben.

(BTW, der relevante Teil hier ist Barendregt des freie Variable Annahme.)

Answer 2

Konvertieren von Lambda-Kalkül in C-Code ist nicht trivial. Normalerweise werden Sie einen Dolmetscher schreiben, der Schritt-für-Schritt auswertet. Das heißt, wiederum die Expression in einen Baum, und findet die Knoten am nächsten an die Wurzel, die eine Anwendung mit der linken Seite ist, um ein-lambda ist. ersetzt nun in der rechten Seite. Wiederholen Sie, bis Sie nicht mehr anwenden können, und Sie haben das Ergebnis aus.

Beachten Sie, dass es hier auf die freien Variablen keine direkte Entsprechung ist; wir verwenden sie nur zu wissen, wo die Dinge zu ersetzen.

Beachten Sie, dass die Gleichwertigkeit Turing nicht erforderlich genau Äquivalenz zwischen irgendwelchen Konzepten in zwei Turing-complete Sprachen. Es erfordert lediglich, dass Sie kehrt emulieren eine mit dem anderen und umge können.