Ist Eta-Äquivalenz für Funktionen mit Haskells seq-Operation kompatibel?

14

Lemma: Unter der Annahme einer Eta-Äquivalenz haben wir das (\x -> ⊥) = ⊥ :: A -> B.

Beweis: ⊥ = (\x -> ⊥ x)durch Eta-Äquivalenz und (\x -> ⊥ x) = (\x -> ⊥)durch Reduktion unter dem Lambda.

Der Haskell 2010-Bericht, Abschnitt 6.2, spezifiziert die seqFunktion durch zwei Gleichungen:

seq :: a -> b -> b
seq ⊥ b = ⊥
seq ab = b, wenn a ≠ ≠

Es wird dann behauptet "Folglich ist ⊥ nicht dasselbe wie \ x -> ⊥, da seq verwendet werden kann, um sie zu unterscheiden."

Meine Frage ist, ist das wirklich eine Folge der Definition von seq ?

Das implizite Argument scheint zu sein, dass seqwenn nicht berechenbar wäre seq (\x -> ⊥) b = ⊥. Ich konnte jedoch nicht beweisen, dass eine seqsolche nicht berechenbar wäre. Es scheint mir so einseq ob es sowohl monoton als auch kontinuierlich ist, was es in den Bereich der Berechenbarkeit bringt.

Ein Algorithmus, der für für einige zu suchen , indem er versucht, wie Seq funktionieren könnte implementieren , xwo f x ≠ ⊥durch die Domäne aufzuzählen , fbeginnend mit ⊥. Obwohl eine solche Implementierung, selbst wenn sie überhaupt möglich ist, ziemlich haarig wird, wenn wir sie seqpolymorph machen wollen .

Gibt es einen Beweis dafür , dass es keine berechenbaren ist , seqdie angibt , (\x -> ⊥)mit ⊥ :: A -> B? Alternativ gibt es einige Bau , seqdass sich identifizieren (\x -> ⊥)mit ⊥ :: A -> B?

Russell O'Connor
quelle

Antworten:

6

Lassen Sie uns zunächst erläutern, wie seqsich von λ x unterscheidet . :λx.

bottom :: a
bottom = bottom

eta :: a -> b
eta x = bottom

-- This terminates
fortytwo = seq eta 42

-- This does not terminate
infinity = seq bottom 42

Es ist daher eine experimentelle Tatsache, dass in Haskell und λ x . sind operativ unterscheidbar. Es ist auch eine Tatsache und eine ganz offensichtliche Tatsache, die berechenbar ist, weil Haskell sie berechnet. Soviel zu Haskell. Sie fragen nach der besonderen Formulierung der Haskell-Dokumentation. Ich habe es so gelesen, dass es die beiden gegebenen Gleichungen erfüllen soll, aber diese beiden Gleichungen reichen für die Definition von nicht aus . Hier ist der Grund: Ich kann Ihnen zwei Modelle des (einfach getippten) λ- Kalküls geben, in denen berechenbar ist und die angegebenen Gleichungen erfüllt, aber in einem der Modelle und λ x . λx.seqseqseqλseqλx. stimmen zu, während sie im anderen nicht.

In einem einfachen domänentheoretischen Modell, in dem Ausdrücke im Bereich stetiger Funktionen [ D E ] interpretiert werden, haben wir = λ x . offensichtlich. Nehmen Sie effektive Scott-Domains oder solche, um alles berechenbar zu machen. In einem solchen Modell ist es einfach zu definieren .λ[DE]=λx.seq

Wir können auch ein Modell von Kalkül , in dem unterscheidet und λ x . und dann kann natürlich die η- Regel nicht gelten. Zum Beispiel können wir dies tun, indem wir Funktionen in der Domäne [ D E ] ⊥ interpretieren , dh der Funktionsraumdomäne mit einem zusätzlichen Boden. Nun ist der Boden von [ D E ] , während λ x . ist das Element direkt darüber. Sie können nicht durch Anwendung unterschieden werden, weil sie beide zu auswertenλseqλx.η[DE][DE]λx. , egal auf was Sie sie anwenden (sie sind in ihrerAusdehnung gleich). Aber wir haben seqals Karte zwischen Domänen und es unterscheidet immer unten von allen anderen Elementen.

Andrej Bauer
quelle
1
Es ist eine experimentelle Tatsache, dass in GHC und / oder Umarmungen ⊥ und λx.⊥. Glücklicherweise ist Haskell nicht durch eine Implementierung definiert. Meine Frage deutet darauf hin, dass Haskell in Bezug auf seq unterbestimmt ist.
Russell O'Connor
Können Sie einen Hinweis darauf geben, was Sie unter "effektiven Scott-Domains" verstehen? Auch der STLC ist nicht polymorph, aber Haskell ist. Normalerweise wird Haskell in System F oder einer seiner Ableitungen interpretiert. Wie wirkt sich das auf Ihre Argumentation aus?
Russell O'Connor
Abschnitt 1.1.4 meiner Promotion In der Dissertation andrej.com/thesis/thesis.pdf werden effektive Scott-Domains kurz definiert. Dies ist der erste Google-Hit, der frei verfügbar ist.
Andrej Bauer
2
Wenn Sie einen Beweis für mich schreiben, erhalten Sie eine Implementierung von Haskell 98, in der die eta-Regel gilt und ermöglicht, dass (foldr (\ ab -> fab) z xs) optimiert wird, um (foldr fz xs) eine asymptotische Leistungssteigerung von O zu verursachen (n ^ 2) bis O (n) (siehe ghc.haskell.org/trac/ghc/ticket/7436 ). Überzeugender ist, dass ein NewTypeWrapper in (NewTypeWrapper. F) optimiert werden kann, ohne dass f erweitert werden muss, und dass einige asymptotische Leistungseinbußen vermieden werden, die derzeit von newTypes in GHC verhängt werden (z. B. bei der Verwendung von foldr).
Russell O'Connor
1
Eigentlich müssten Sie sicherstellen, dass Ihr Compiler immer implementiert . wie . Das heißt, Sie könnten versucht sein, nicht immer zu kontrahieren und daher im Prinzip λ x . und wären "manchmal unterscheidbar", eine sehr gefährliche Situation. Um sicherzustellen, dass dies nicht der Fall ist, müssen Sie auf clevere Weise implementieren, indem Sie unendlich viele Prozesse erzeugen, die jeweils Ihre Funktion auf ein Grundelement anwenden. Wenn einer der Prozesse beendet wird, kann der Vorgang fortgesetzt werden. Es wäre interessant zu sehen, ob wir dies nacheinander tun können. Hmm. λx.λx.seqseq
Andrej Bauer
2

Beachten Sie, dass die von seqIhnen angegebene Spezifikation nicht deren Definition ist. So zitieren Sie den Haskell-Bericht: "Die Funktionsfolge wird durch die folgenden Gleichungen definiert : [und dann die von Ihnen angegebenen Gleichungen]".

Das vorgeschlagene Argument scheint zu sein, dass seq nicht berechenbar wäre, wenn seq (\ x -> ⊥) b = ⊥.

Ein solches Verhalten würde die Spezifikation von verletzen seq .

Wichtig ist, dass seqes polymorph seqist und nicht in Form von Dekonstruktoren (Projektionen / Mustervergleich usw.) für einen der beiden Parameter definiert werden kann.

Gibt es einen Beweis, dass es keine berechenbare Folge gibt, die (\ x -> ⊥) mit ⊥ :: A -> B identifiziert?

Wenn seq' (\x -> ⊥) b, könnte man meinen, wir könnten den ersten Parameter (der eine Funktion ist) auf einen bestimmten Wert anwenden und dann ⊥ ausgeben. Aber, seqkann niemals den ersten Parameter mit einem Funktionswert identifizieren (auch wenn es eine längeren Verwendung sein geschieht seq) wegen seines parametrischen polymorphen Typs. Parametrizität bedeutet, dass wir nichts über die Parameter wissen. Außerdem seqkann man niemals einen Ausdruck nehmen und entscheiden "ist das ⊥?" (vgl. das Halting-Problem), seqkann nur versuchen, es zu bewerten, und selbst divergieren zu ⊥.

Was seqbedeutet, ist, den ersten Parameter auszuwerten (nicht vollständig, sondern auf "schwache Kopfnormalform" [1], dh auf den obersten Konstruktor) und dann den zweiten Parameter zurückzugeben. Wenn es sich bei dem ersten Parameter zufällig um eine nicht abschließende Berechnung handelt (dh um eine nicht abschließende Berechnung), führt die Auswertung dazu, dass die Berechnung seqnicht abgeschlossen wird, und somit seq ⊥ a = ⊥.

[1] Freie Theoreme in Gegenwart von seq - Johann, Voigtländer http://www.iai.uni-bonn.de/~jv/p76-voigtlaender.pdf

Dorchard
quelle
Die Spezifikation, die ich für seq gebe, ist die Definition von seq, weil genau das im Haskell 2010-Bericht in Abschnitt 6.2 steht. Ihre Operationsdefinition von seq wird vom Haskell 2010-Bericht nicht unterstützt: Die Wörter "head normal form" kommen nur einmal im Bericht in einem völlig anderen Kontext vor. Es widerspricht auch meinem Verständnis, dass GHC das zweite Argument häufig vor dem ersten Argument auf seq reduziert, oder das erste Argument überhaupt nicht reduziert wird, weil der Strenge-Analysator bewiesen hat, dass es statisch nicht ganz unten liegt.
Russell O'Connor
Die Parametrizität besagt nicht direkt, dass wir keine Dekonstruktoren anwenden können, und sie besagt auch nicht, dass wir den ersten Parameter niemals mit einem Funktionswert identifizieren können. Alle Parameter, die für den polymorphen Lambda-Kalkül mit Fixpunkten besagen, sind, dass seq strenge Funktionen absorbieren kann, oder allgemeiner bestimmte strenge Beziehungen, die für Terme gelten, die seq enthalten. Ich gebe zu, es ist plausibel, dass Parametrizität verwendet werden könnte, um (\ x -> ⊥) & ne; ⊥, aber ich würde gerne einen strengen Beweis sehen.
Russell O'Connor
Im Fall einer Funktion f : forall a . a -> T(bei der Tes sich um einen anderen Typ handelt) fkönnen keine Dekonstruktoren auf das erste Argument angewendet werden, da nicht bekannt ist, welche Dekonstruktoren angewendet werden sollen. Wir können keinen "Fall" für Typen machen. Ich habe versucht, die obige Antwort zu verbessern (einschließlich des Zitierens von Informationen zur seqBewertung in normaler Kopfform).
Dorchard
Ich kann später versuchen, den strengen Beweis zu erbringen, wenn ich Zeit finde (Beziehungen im Stil von Reynolds sind möglicherweise ein guter Ansatz).
Dorchard
@ RussellO'Connor: Die Beschreibung von seq ist nicht "inkonsistent" mit diesen Verhaltensweisen, sie ist nur eine Betriebsspezifikation (und Verhaltensweisen sind Optimierungen, die das Endergebnis nicht ändern).
Blaisorblade
2

λx.λx.

Samson Abramsky hat sich vor langer Zeit mit diesem Thema befasst und einen Artikel mit dem Titel " The Lazy Lambda Calculus " geschrieben. Wenn Sie also formale Definitionen wünschen, sollten Sie hier nachsehen.

Uday Reddy
quelle
1
Anscheinend werden diese Details nur durch Desugaring in den "Haskell-Kernel" definiert. Wo ist es definiert, ist es? Der Bericht sagt, in Sec. 1.2 : "Obwohl der Kernel formal nicht spezifiziert ist, handelt es sich im Wesentlichen um eine leicht gezuckerte Variante des Lambda-Kalküls mit einer einfachen Denotationssemantik. Die Übersetzung jeder syntaktischen Struktur in den Kernel wird angegeben, wenn die Syntax eingeführt wird."
Blaisorblade
Der Haskell 2010-Bericht sagt das erstaunlicherweise auch.
Blaisorblade
Danke für den Hinweis auf Abramsky! Ich überflog es, um zu sehen, wie es die Frage beantwortet, und fand die folgende Antwort: cstheory.stackexchange.com/a/21732/989
Blaisorblade
2

Beweis, dass λ x. Ω ‌ ≠ Ω in ist eines der Ziele, die Abramsky sich für seine Theorie der faulen Lambda-Rechnung setzt (Seite 2 seiner Arbeit) , die bereits von Uday Reddy zitiert wurde) setzt, weil beide in normaler Schwachkopfform vorliegen. Ab Definition 2.7 diskutiert er explizit die eta-Reduktion λ x. M x → M ist nicht allgemein gültig, aber es ist möglich, wenn M in jeder Umgebung endet. Dies bedeutet nicht, dass M eine Gesamtfunktion sein muss - nur, dass die Auswertung von M enden muss (z. B. durch Reduzieren auf ein Lambda).

Ihre Frage scheint von praktischen Bedenken (Leistung) motiviert zu sein. Obwohl der Haskell-Bericht möglicherweise nicht ganz klar ist, bezweifle ich, dass λ x gleichgesetzt wird. ⊥ ‌mit ⊥ würde eine nützliche Implementierung von Haskell ergeben; ob es Haskell '98 implementiert oder nicht, ist umstritten, aber angesichts der Bemerkung ist klar, dass die Autoren beabsichtigten, dass dies der Fall ist.

Schließlich, wie ist es, Elemente für einen beliebigen Eingabetyp zu generieren? (Ich weiß, dass QuickCheck die Arbitrary-Typenklasse dafür definiert, aber Sie dürfen hier keine solchen Einschränkungen hinzufügen.) Dies verletzt die Parametrizität.

Aktualisiert : Ich habe es nicht geschafft, dieses Recht zu codieren (weil ich nicht so fließend in Haskel bin), und um dies zu beheben, sind anscheinend verschachtelte runSTRegionen erforderlich . Ich habe versucht, mit einer einzelnen Referenzzelle (in der ST-Monade) solche beliebigen Elemente zu speichern, sie später zu lesen und universell verfügbar zu machen. Die Parametrizität beweist, dass das break_parametricityFolgende nicht definiert werden kann (außer durch Zurückgeben von bottom, z. B. eines Fehlers), während die Elemente wiederhergestellt werden könnten, die die vorgeschlagene Folge erzeugen würde.

import Control.Monad.ST
import Data.STRef
import Data.Maybe

produce_maybe_a :: Maybe a
produce_maybe_a = runST $ do { cell <- newSTRef Nothing; (\x -> writeSTRef cell (Just x) >> return x) `seq` (readSTRef cell) }

break_parametricity :: a
break_parametricity = fromJust produce_maybe_a

Ich muss zugeben, dass ich die Formalisierung des hier benötigten Parametrizitätsnachweises ein wenig unklar finde, aber diese informelle Verwendung von Parametrizität ist in Haskell Standard. aber ich habe aus Derek Dreyers Schriften gelernt, dass die nötige Theorie in den letzten Jahren schnell ausgearbeitet wird.

EDITs:

  • Ich bin mir nicht einmal sicher, ob Sie diese Erweiterungen benötigen, die für ML-artige, imperative und untypisierte Sprachen studiert wurden, oder ob die klassischen Theorien der Parametrizität Haskell abdecken.
  • Außerdem habe ich Derek Dreyer erwähnt, weil ich erst später auf Uday Reddys Werk gestoßen bin - das habe ich erst kürzlich aus "The essence of Reynolds" erfahren. (Ich habe erst im letzten Monat angefangen, Literatur über Parametrizität zu lesen).
Blaisorblade
quelle
Das Auswerten (\x -> writeSTRef cell (Just x) >> return x)von zufälligen Eingaben führt kein Schreiben in die Zelle aus. Es werden immer nur die ST-Befehle ausgeführt, die es in die übergebene Sequenz schaffen runST. Ebenso wird beim Ausführen main = (putStrLn "Hello") `seq` (return ())nichts auf dem Display gedruckt.
Russell O'Connor
@ RussellO'Connor, natürlich hast du recht - Testen ist schwierig, da seq nicht das Verhalten hat, das wir diskutieren. Aber ich denke immer noch, dass das Erzeugen von Elementen die Parametrizität an sich bricht. Ich werde versuchen, die Antwort zu korrigieren, um das zu veranschaulichen.
Blaisorblade
Hm, die offensichtliche Lösung für die Antwort erfordert das Verschachteln von runST-Regionen und die Verwendung der Zelle aus der äußeren Region in der inneren, aber das ist nicht erlaubt.
Blaisorblade