Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?

Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B.

Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda.

Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań:

seq :: a -> b -> b
seq ⊥ b = ⊥
seq ab = b, jeśli a ≠ ⊥

Następnie twierdzi, że „W konsekwencji not nie jest tym samym, co \ x -> ⊥, ponieważ można je rozróżnić za pomocą seq.”

Moje pytanie brzmi, czy to naprawdę konsekwencja definicji seq?

Domniemany argument wydaje się być taki, seqże gdyby nie seq (\x -> ⊥) b = ⊥. Jednak nie byłem w stanie udowodnić, że takie seqbyłoby niemożliwe do obliczenia. Wydaje mi się, że taki seqjest zarówno monotoniczny, jak i ciągły, co stawia go w sferze obliczalności.

Algorytm że wdrożenie takich jak praca nast może próbując szukać dla niektórych xgdzie f x ≠ ⊥przez wyliczanie domenę fzaczynając ⊥. Chociaż taka implementacja, nawet jeśli jest to w ogóle możliwe, staje się dość owłosiona, gdy chcemy stworzyć seqpolimorfię.

Czy istnieje dowód, że nie ma obliczalnego seqidentyfikującego się (\x -> ⊥)z ⊥ :: A -> B? Alternatywnie, jest tam jakiś budowa seqktóre nie identyfikują (\x -> ⊥)się z ⊥ :: A -> B?

Po pierwsze, wyjaśnijmy, jak seqodróżnia się od λ x . ⊥ :$\bot$$\lambda x . \bot$

bottom :: a
bottom = bottom

eta :: a -> b
eta x = bottom

-- This terminates
fortytwo = seq eta 42

-- This does not terminate
infinity = seq bottom 42

Jest to zatem eksperymentalny fakt, że w Haskell i λ x . ⊥ są operacyjnie rozróżnialne. Jest to również fakt i dość oczywisty, który można obliczyć, ponieważ Haskell go oblicza. Tyle o Haskell. Pytasz o bardzo szczególne sformułowanie dokumentacji Haskell. Czytam to jako powiedzenie, które ma spełniać dwa podane równania, ale te dwa równania nie są wystarczające do zdefiniowania . Oto dlaczego: Mogę podać dwa modele (po prostu wpisanego) rachunku λ, w którym jest obliczalny i spełnia podane równania, ale w jednym z modeli ⊥ i λ x . $\bot$$\lambda x . \bot$seqseqseq$\lambda$seq$\bot$$\lambda x . \bot$ zgadzają się, podczas gdy w drugim nie.

W prostym modelu teoretycznym, w którym wyrażenia są interpretowane w dziedzinie funkcji ciągłych [ D → E ] , mamy ⊥ = λ x . ⊥ oczywiście. Weź skuteczne domeny Scotta lub inne, aby wszystko było obliczalne. W takim modelu łatwo jest zdefiniować .$\lambda$$[D \to E]$$\bot = \lambda x . \bot$seq

Możemy również mieć model rachunek, w którym rozróżnia się ⊥ i λ x . ⊥ , a następnie oczywiście η- reguła nie może utrzymać. Na przykład możemy to zrobić, interpretując funkcje w domenie [ D → E ] ⊥ , tj. Domena przestrzeni funkcji z dołączonym dodatkowym dnem. Teraz ⊥ jest, cóż, dolną częścią [ D → E ] ⊥ , podczas gdy λ x . ⊥ jest elementem tuż nad nim. Nie można ich rozróżnić według aplikacji, ponieważ oba oceniają$\lambda$seq$\bot$$\lambda x . \bot$$\eta$$[D \to E]_\bot$$\bot$$[D \to E]_\bot$$\lambda x . \bot$ , bez względu na to, do czego je zastosujesz (są onezasadniczo równe). Ale mamymapę między domenami, która zawsze odróżnia dno od wszystkich innych elementów.$\bot$seq

Zauważ, że specyfikacja, dla seqktórej zacytujesz, nie jest jej definicją. Cytując raport Haskella „Sekwencja funkcji jest zdefiniowana przez równania : [a następnie podane równania]”.

Sugerowanym argumentem wydaje się być to, że seq byłby nieobliczalny, gdyby seq (\ x -> ⊥) b = ⊥.

Takie zachowanie naruszałoby specyfikację seq.

Co ważne, ponieważ seqjest polimorficzny, seqnie można go zdefiniować w kategoriach dekonstruktorów (dopasowanie rzutów / wzorców itp.) Dla żadnego z dwóch parametrów.

Czy istnieje dowód, że nie ma obliczalnej sekwencji, która identyfikowałaby (\ x -> ⊥) za pomocą ⊥ :: A -> B?

Jeśli seq' (\x -> ⊥) bmożna by pomyśleć, że moglibyśmy zastosować pierwszy parametr (który jest funkcją) do pewnej wartości, a następnie uzyskać ⊥. Ale seqnigdy nie można zidentyfikować pierwszego parametru z wartością funkcji (nawet jeśli zdarza się, że jest to jeden do użytku seq) ze względu na jego parametryczny typ polimorficzny. Parametryzacja oznacza, że ​​nic nie wiemy o parametrach. Co więcej, seqnigdy nie można wyrazić i zdecydować „czy to jest?”. (por. problem Haltinga), seqmoże jedynie próbować go ocenić i sam się rozbiega na ⊥.

Co seqnie jest ocena pierwszy parametr (nie całkowicie, ale do „słabych główki normalnej postaci” [1], to znaczy do górnej skrajnej konstruktora), a następnie powrócić do drugiego parametru. Jeśli zdarzy się, że pierwszym parametrem jest ⊥(tj. Obliczenie nie kończące się), wówczas jego ocena powoduje, seqże nie jest on zakończony, a zatem seq ⊥ a = ⊥.

[1] Bezpłatne twierdzenia w obecności seq - Johann, Voigtlander http://www.iai.uni-bonn.de/~jv/p76-voigtlaender.pdf

$\lambda x.\, \bot$$\lambda x.\, \bot$

Samson Abramsky rozważał tę kwestię dawno temu i napisał artykuł zatytułowany „ The Lazy Lambda Calculus ”. Tak więc, jeśli chcesz formalne definicje, tutaj możesz poszukać.

Udowadniając, że λ x. Ω ‌ ≠ Ω jest jednym z celów wyznaczonych przez Abramsky'ego dla jego leniwej teorii rachunku lambda (strona 2 jego pracy , cytowanej już przez Udaya Reddy'ego), ponieważ oba są w normalnej formie słabej głowy. Od definicji 2.7 wyraźnie dyskutuje, że eta-redukcja λ x. M x → M nie jest ogólnie poprawny, ale jest możliwe, jeśli M kończy się w każdym środowisku. Nie oznacza to, że M musi być funkcją całkowitą - tylko to, że ocena M musi się zakończyć (na przykład poprzez redukcję do lambda).

Twoje pytanie wydaje się być motywowane względami praktycznymi (wydajność). Jednak, mimo że Raport Haskella może być mniej niż całkowicie jasny, wątpię, by zrównanie λ x. Ith „z” stworzyłoby przydatną implementację Haskella; kwestia, czy implementuje Haskell '98, czy nie, jest dyskusyjna, ale biorąc pod uwagę uwagę, jasne jest, że autorzy zamierzali, aby tak było.

Wreszcie, w jaki sposób seq generuje elementy dla dowolnego typu danych wejściowych? (Wiem, że QuickCheck definiuje w tym celu typ Arbitrary, ale nie możesz tutaj dodawać takich ograniczeń). Narusza to parametryczność.

Zaktualizowano : Nie udało mi się zakodować tego poprawnie (ponieważ nie jestem tak biegły w Haskel), a naprawienie tego wymaga zagnieżdżonych runSTregionów. Próbowałem użyć pojedynczej komórki referencyjnej (w monadzie ST), aby zapisać takie dowolne elementy, przeczytać je później i uczynić je powszechnie dostępnymi. Parametryzacja dowodzi, że break_parametricityponiżej nie można zdefiniować poniżej (z wyjątkiem zwracania wartości dolnej, np. Błędu), podczas gdy może odzyskać elementy, które wygenerowałaby proponowana sekwencja.

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

Muszę przyznać, że jestem nieco rozmyślny nad sformalizowaniem wymaganego tutaj dowodu parametrycznego, ale to nieformalne użycie parametryczności jest standardowe w Haskell; ale dowiedziałem się z pism Dereka Dreyera, że ​​potrzebna teoria jest szybko opracowywana w ostatnich latach.

EDYCJE:

• Nie jestem nawet pewien, czy potrzebujesz tych rozszerzeń, które są badane dla języków podobnych do ML, imperatywnych i bez typów, czy też klasyczne teorie parametryczne obejmują Haskella.
• Wspomniałem też o Dereku Dreyerze tylko dlatego, że dopiero później natknąłem się na twórczość Udaya Reddy'ego - dowiedziałem się o tym dopiero niedawno z „Esencji Reynoldsa”. (Naprawdę zacząłem czytać literaturę na temat parametryczności w ostatnim miesiącu).