Die Bedeutung und Relevanz der Locution "keine terminierende Implementierung" in der Typentheorie

Question

Im Rahmen einer Diskussion über Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, Mir wurde gesagt, dass

Es gibt keine abschließende Implementierung für den polymorphen Typ $(e \ zu a) \ zu a$

und dass wir keine Funktion vom Typ haben könnten $((e \ zu a) \ zu a) \ zu e$ oder eine Funktion vom Typ $(r \ bis x) \ bis x$, denn diese wären nicht "umsetzbar".

Diese Typen sind im STLC gut geformt, in dem Sinne, dass wir sie nach den Regeln der Typbildung konstruieren können.Und ich verstehe nicht, warum wir keine Lambda-Terme dieser Form bilden können, wie zum Beispiel $\lambda c_{((a \bis t) \ bis t)}.\, b_a$, oder $\lambda p_{e \zu a}.\,b_a$.

Was ist also das Problem?Was ist im Einzelnen eine "terminierende Implementierung" im Kontext des STLC?Ich glaube, das hängt damit zusammen, dass $(e \ zu \bot) \ zu \bot$ ist konstruktiv nicht äquivalent zu $e$, aber ich würde mich freuen, wenn jemand das für mich buchstabieren könnte.

Answer 1

Sie können immer bewohnen Sie einen Typ mit einer freien Variablen:Art $ au$ wird von der freien Variablen bewohnt $x_ au$.Wenn Leute von "Implementierung" eines Typs sprechen, meinen sie a geschlossener Begriff, dh eine ohne freie Variablen.Die von Ihnen angegebenen Beispiele enthalten freie Variablen, nämlich $b_a$.

In rein einfach getippt $\Lambdasonde$-Kalkül Alle Begriffe sind "terminierend" in dem Sinne, dass sich der Kalkül stark normalisiert, sodass jede Reduktion, die Sie vornehmen, immer zur (eindeutigen) Normalform führt.

In $\Lambdasonde$-Kalkül erweitert mit rekursiven Definitionen (wie Haskell) können wir jeden Typ bewohnen $ au$ mit einem geschlossenen Begriff, zum Beispiel in Haskell der Typ t wird bewohnt von a definiert als

a :: t
a = a

Sobald wir rekursive Definitionen haben, ist es einfach, geschlossene Begriffe zu schreiben, die nicht enden (oder keine normale Form haben).