η-konwersja vs rozciągliwość w rozszerzeniach rachunku lambda

Często myli mnie związek między konwersją η a ekstensywnością.

Edytuj: Według komentarzy wydaje mi się, że jestem również zdezorientowany co do związku między równoważnością ekstensywną a równoważnością obserwacyjną. Ale przynajmniej w Agdzie z ekstensywną równością funkcji (jako postulat) i dla prostego rachunku lambda (który ma w pełni abstrakcyjną semantykę, jeśli się nie mylę), równoważność denotacyjna jest taka sama jak równoważność obserwacyjna. Popraw mnie w komentarzach lub odpowiedziach; Nigdy nie uzyskałem systematycznej edukacji w tych sprawach.

W niepisanym rachunku lambda reguła eta daje ten sam system dowodu co zasada ekstensywności, co udowodnił Barendregt (cytowany w odpowiedzi na to pytanie ). Rozumiem, że oznacza to, że system dowodowy z regułą eta jest kompletny dla równoważności obserwacyjnej (z innych odpowiedzi, które mogą wymagać reguły reguły ξ, to znaczy redukcji w segregatorach IIUC; nie mam też problemu z dodaniem tej reguły) .

Co się jednak stanie, jeśli przejdziemy na rachunek maszynowy i dodamy ten rachunek rozszerzający o dodatkowe typy bazowe i odpowiadające im formularze wprowadzenia i eliminacji? Czy nadal możemy napisać kompletny system dowodu równoważności obserwacyjnej? Opowiem o systemach dowodowych w postaci semantyki aksjomatycznej, zgodnie z Mitchell's Foundations of Programming Languages (FPL); system dowodowy / semantyka aksjomatyczna określa równoważność programu.

Pytanie 1 : czy twierdzenie Barendregta rozciąga się na STLC? Czy równoważność η jest równoważna ekstensywności w tym kontekście?

Ja przeglądając dyskusję FPL z PCF (ale nie dokończył jeszcze sekcję) i wydaje się, że po dodaniu par, ekstensjonalności wymaga dodatkowego regułę, mianowicie suriekcją parowanie: pair (Proj1 P, Proj2 P) = P. Co ciekawe, reguła ta dotyczy wprowadzania i eliminacji par dokładnie tak, jak reguła η dotyczy wprowadzania i eliminacji funkcji.

Pytanie 2 : Czy wystarczy dodać aksjomat parowania z przypuszczeniem, aby udowodnić ekstensywność prostego rachunku λ z parami? edytuj : Pytanie 2b : czy parowanie przez przymiotniki prawa η, jak wspomniane w tym artykule prawa η , z powodu podobieństwa strukturalnego, o którym wspomniałem?

Przejdźmy teraz do PCF. Opisy równości ekstensywnej, które widziałem, dowodzą, że ekstensywność implikuje regułę dowodową przez indukcję, ale nie mówią, czy to wystarczy. Ponieważ PCF jest kompletny w Turinga, równość ekstensywna jest nierozstrzygalna . Ale to nie oznacza, że nie ma pełnego systemu dowodów, ponieważ długość dowodów jest nieograniczona. Co ważniejsze, taki system dowodu może być sprzeczny z twierdzeniami Gödela o niekompletności. I ten argument może dotyczyć nawet PCF bez fix, a także System T. Gödla.

Pytanie 3 : Czy istnieje kompletny system dowodu równoważności obserwacyjnej w PCF? A co bez PCF fix?

Aktualizacja: pełna abstrakcja

Odpowiadam tutaj na komentarz dotyczący pełnej abstrakcji. Wydaje mi się, że PCF ma dwa różne rodzaje problemów: ma brak terminacji (via fix), co powoduje utratę pełnej abstrakcji, ale ma także liczby naturalne. Oba problemy sprawiają, że obserwowalną równoważność trudno jest leczyć, ale wierzę, że niezależnie od siebie.

Z jednej strony PCF traci pełną abstrakcję, ponieważ równolegle lub żyje w domenie semantycznej (Plotkin 1977), i wydaje się, że ma to związek z nieterminacją. Ralph Loader (2000, „Finitary PCF nie podlega rozstrzygnięciu”) pokazuje, że finational PCF (bez naturals, ale z nieterminacją) jest już niezdecydowany; stąd (jeśli poprawnie podsumuję) w pełni abstrakcyjny semantyczny nie może ograniczać się do domen z operacjami obliczalnymi.

Z drugiej strony weź System T Gödela, który nie ma nieterminacji. (Nie jestem pewien, czy ma w pełni abstrakcyjną semantykę, ale zgaduję, że tak, ponieważ problem jest wspomniany tylko w przypadku PCF; domena musi zawierać pierwotne funkcje rekurencyjne wyższego rzędu). Praktyczne podstawy Harpera dla języków programowania omawiają równoważność obserwacyjną dla tego języka; Sec. 47.4 zatytułowany jest „Niektóre prawa równości” i pokazuje pewne dopuszczalne reguły dowodowe dotyczące równoważności obserwacyjnej. Nigdzie nie jest powiedziane, czy system dowodowy jest kompletny, więc chyba nie jest, ale nigdzie też nie dyskutuje się, czy można go ukończyć. Moje najlepsze przypuszczenia wiążą się z twierdzeniem Gödela o niekompletności.

pl.programming-languages lambda-calculus

— Blaisorblade
źródło

Myślę, że mógłbym odpowiedzieć na niektóre z tych pytań, ale nie wiem, o co pytasz. Pytanie, o którym mówisz, nie dotyczy równoważności programu. Masz na myśli równoważność obserwacyjną? Dla jakiej semantyki operacyjnej? Zasadniczo, jeśli dokładnie wyjaśnisz, do czego odnosi się „dowód” w pytaniu 1, myślę, że mogę zgadnąć, co się dzieje. Moje najlepsze przypuszczenie: chciałbyś teorii teorii równań, która jest kompletna dla równoważności obserwacyjnej, i pytasz nas, czy

reguły są wystarczające. Czy to to?

η

$\eta$

— Andrej Bauer

@AndrejBauer: twoje przypuszczenia są prawidłowe, zacznę aktualizować pytanie.

— Blaisorblade,

Nie jestem pewien co do semantyki operacyjnej - czy to wpływa na oryginalne twierdzenia?

— Blaisorblade,

Próbowałem uściślić pytanie. Ale nadal uważam, że twoje najlepsze przypuszczenia są prawidłowe.

— Blaisorblade,

Jest tu mały problem: naprawdę nie jest jasne, czym jest

dla liczb naturalnych! Jeśli masz tylko typ funkcji i produktu, to jasne: terminy są równoważne obserwacyjnie, jeśli są równe

. Mówiąc bardziej ogólnie, myślę, że jest to związane z problemem pełnej abstrakcji .

η

$\eta$

β η

$\beta\eta$

— cody

Nie jestem pewien, czy potrafię w pełni odpowiedzieć na twoje pytanie, ale dam mu szansę i zadam kilka własnych pytań, które mogą zachęcić do dalszej dyskusji na ten temat.

Mój pierwszy punkt brzmi: dwa terminy w bez typu -calculus Mówi się zauważalnie równa wtw dla każdego terminu : Gdzie kończy oznacza „ma formularz -Normal” $t, t'$ $\lambda$ $M$

M. t kończy się \Leftrightarrow M. t^{'} kończy się

$M\ t \mbox{ terminates } \Leftrightarrow M\ t' \mbox{ terminates }$

β

$\beta$

Uważam za bardziej naturalne rozważanie terminów z „dziurami” lub kontekstami zamiast po prostu terminów i pisania zamiast . Oba widoki są z pewnością równoważne (jeśli zmienne nie są powiązane kontekstem), ponieważ abstrakcja pozwala zamienić kontekst na termin . $E[\_]$ $M$ $E[t]$ $M\ t$ $E[\_]$ $\lambda x.E[x]$

Teraz faktem jest, że równość obserwacyjna w rachunku różnym bez typu nie jest ujmowana przez -equality! Rzeczywiście istnieje cała klasa terminów, które oba nie kończą się i nie mają normalnych form głowy, a zatem wszystkie są zauważalnie równe. Są one czasami nazywane warunkami wieczystymi lub nierozwiązywalnymi , a oto dwa takie terminy: i $\beta\eta$

(λ x . x x) (λ x . x x)

$(\lambda x. x\ x)(\lambda x. x\ x)$

Łatwo jest wykazać, że te terminy nie są

-equal.

(λ x . x x x) (λ x . x x x)

$(\lambda x. x\ x\ x)(\lambda x. x\ x\ x)$

β η

$\beta\eta$

Jeśli zostaną zidentyfikowane wszystkie warunki wieczyste, wówczas równość obserwacyjna zostanie całkowicie uchwycona przez klasyczny wynik (patrz twierdzenie Barendregta 16.2.7).

Teraz dla wpisanych rachunków. Rozważmy najpierw prosty rachunek bez liczb naturalnych. Powyższa definicja równości obserwacyjnej staje się banalna, ponieważ każdy termin normalizuje się! Potrzebujemy dokładniejszego rozróżnienia. Użyjemy równości wartości do zamkniętych warunkach, określonych przez indukcję od typu i . Dodajmy najpierw dla każdego typu nieskończoną liczbę stałych . Wybierzemy stałą $\lambda$ $t_1\downarrow t_2$ $t_1$ $t_2$ $A$ $c_A, c_A', c''_A,\ldots$ $c_x$ odpowiedniego typu, który odpowiada każdej zmiennej . $x$

Przy typie podstawowym , iff głowica normalna forma to a dla jest i oraz w odpowiednich typach. $B$ $t_1\downarrow t_2$ $\beta$ $t_1$ $c\ u_1\ldots u_n$ $t_2$ $d\ v_1\ldots v_n$ $c=d$ $u_1\downarrow v_1,\ldots, u_n\downarrow v_n$
Przy typie strzałki strzałka w dół obydwu terminach redukuje do -abstrakcji. $t_1\downarrow t_2$ $\beta$ $\lambda$

Zauważ, że używam tylko konwersji w tej definicji. $\beta$

Teraz definiuję konteksty jako: z kontekstem głowy, zastosowaniem, abstrakcją i podstawieniem (wyrażeniami zamkniętymi).

[_] ∣ E [_] u ∣ t E [_] ∣ λ x . E [_] ∣ E [_] θ

$[\_]\mid E[\_]\ u\mid t\ E[\_]\mid \lambda x.\ E[\_]\mid E[\_]\theta$

Możemy wtedy zdefiniować i , dobrze typowane typu aby być obserwacyjnie równoważne, jeśli i tylko wtedy, gdy dla każdego kontekstu takie, że są dobrze wpisane i zamknięte . napiszemy w tym przypadku $t$ $t'$ $T$ $E[\_]$ $E[t],E[t']$

E [t] ↓ E [t^{'}]

$E[t]\downarrow E[t']$

t =_{o b s} t^{'}

$t=_{\mathrm{obs}}t'$

Teraz łatwo zauważyć, że jeśli to . Drugi kierunek jest mniej trywialny, ale także utrzymuje: w rzeczy samej , jeśli , to możemy wykazać, że warunki są dla indukcyjne na typ: $t=_{\beta\eta}t'$ $t=_{\mathrm{obs}}t'$ $t=_{\mathrm{obs}}t'$ $\beta\eta$

W typie podstawowym po prostu weź na , z podstawieniem, które wysyła do . Mamy i . Mamy i $E[\_]$ $[\_]\theta$ $\theta$ $x$ $c_x$ $E[t]=t\theta$ $E[t']=t'\theta$ $t\theta\rightarrow_\beta c_x\ u_1\theta\ldots u_n\theta$ . Mamy wtedy a więc . Teraz nie możemy od razu stwierdzić, że . Rzeczywiście, jeśli i są -abstractions, to trywialnie ! Sztuką jest wysłanie $t'\theta\rightarrow_\beta c_{x'}\ v_1\theta\ldots v_n\theta$ $c_x=c_{x'}$ $x=x'$ $u_i\theta=_{\beta\eta}v_i\theta$ $u_i$ $v_i$ $\lambda$ $u_i\theta\downarrow v_i\theta$ $x$ na i powtarzaj to tyle razy, ile to konieczne. Jestem trochę rozmyślny w szczegółach tutaj, ale idea jest podobna do twierdzenia Böhm ( Barendregt ponownie 10.4.2).
$λ \vec{y} . \tilde{c_{x}} (y_{1} \vec{c_{1}}) \dots (y_{n} \vec{c_{n}})$ $\lambda \vec{y}.\tilde{c_x}\ (y_1\vec{c_1})\ldots (y_n\vec{c_n})$
Przy typie strzałki weź na , tj. Zastosuj do z i nie w lub . Zgodnie z hipotezą indukcyjną mamy: a więc co daje $E[\_]$ $[\_]\ c_y$ $c_y$ $c_y$ $y$ $t$ $t'$
$t c_{y} =_{β η} t^{'} c_{y}$ $t\ c_y \ =_{\beta\eta}\ t'\ c_y$ $t y =_{β η} t^{'} y$ $t\ y \ =_{\beta\eta}\ t'\ y$ i wreszcie przez-equality: $\lambda y.t\ y\ =_{\beta\eta}\ \lambda.t'\ y$ $\eta$ $t =_{β η} t^{'}$ $t\ =_{\beta\eta}\ t'$

To było trudniejsze niż się spodziewałem!

Dobrze niech rozwiązania systemu T. Dodajmy typu z mieszanki konstruktory i , i recursor dla każdego typu , z " -rules" $\mathbb{N}$ $0$ $S$ $\mathrm{rec_T}$ $T$ $\beta$

r mi {do}_{T.} u v 0 \to_{β} u

$\mathrm{rec_T}\ u\ v\ 0\rightarrow_{\beta} u$

r mi {do}_{T.} u v (S. n) \to_{β} v n (r mi {do}_{T.} u v n)

$\mathrm{rec_T}\ u\ v\ (S\ n)\rightarrow_{\beta} v\ n\ (\mathrm{rec_T}\ u\ v\ n)$

Chcemy udowodnić to samo twierdzenie co powyżej. Kuszące jest dodanie „ rules”, aby udowodnić równoważności takie jak: gdzie terminem po prawej jest „głupia tożsamość”, która odrywa następców tylko po to, aby dodać je ponownie. $\eta$

λ x . x =_{β η} r mi {do}_{N.} 0 (λ k m . S. m)

$\lambda x.x\ =_{\beta\eta}\ \mathrm{rec_{\mathbb{N}}}\ 0\ (\lambda k\ m.S\ m)$

m

$m$

Na przykład dodajmy tę regułę:

\frac{fa (S. x) =_{β η} h x (fa x)}{fa t =_{β η} r mi {do}_{T.} (fa 0) h t}

$\frac{f\ (S\ x)\ =_{\beta\eta}\ h\ x\ (f\ x)}{f\ t\ =_{\beta\eta}\mathrm{rec_T}\ (f\ 0)\ h\ t}$

x

$x$

η

$\eta$

h

$h$

${\cal M}$ $t_{\cal M}$ $T$ $t_{\cal M}\ (S\ldots\ S\ 0)$ $n$ $S$ $1$ ${\cal M}$ $n$ $0$

${\cal M}$

t_{M} = λ x .0

$t_{\cal M}\ = \lambda x.0$

β η

$\beta\eta$

M

${\cal M}$

0 =_{β η} S 0

$0\ =_{\beta\eta}\ S\ 0$

T

$T$

t_{M} = λ x .0

$t_{\cal M}=\lambda x.0$

— cody
źródło

Dziękuję za odpowiedź! Moje pierwsze pytanie brzmi: czy zwykle w kontekście stosuje się podstawienia za równoważność obserwacyjną? Przynajmniej praca LCF Plotkina (1997) tego nie robi (chociaż mogę sobie wyobrazić, że coś takiego miałoby sens w rachunku różniczkowym, w którym coś takiego jak podstawienia jest częścią składni). Ale z łatwością widzę dla każdego kontekstu „podstawienia” można zdefiniować bardziej (jak dla mnie) „standardowy” kontekst, który wykorzystuje po prostu abstrakcję lambda i aplikację, powiedzmy (λx. []) C_x; więc myślę, że powyższa równoważność obserwacyjna jest równoważna definicji, do której jestem przyzwyczajony.

— Blaisorblade,

t = λ x .0

$t = \lambda x.0$

0 =_{β η} S 0

$0 =_{\beta\eta} S 0$

M

${\cal M}$

0 =_{β η} S 0

$0 =_{\beta\eta} S 0$

0 \neq_{β η} S 0

$0 \not=_{\beta\eta} S\ 0$

M

${\cal M}$

t = λ x . 0

$t = \lambda x . 0$

P A

$\mathrm{PA}$

0 \neq 1

$0\neq 1$

P A ⊬ 0 = 1

$\mathrm{PA}\not\vdash 0=1$

T

$T$

\frac{f 0 = g 0 f (S 0) = g (S 0) \dots}{f = g}

$\frac{f\ 0=g\ 0\quad f\ (S\ 0)=g\ (S\ 0)\ldots}{f=g}$

Zgadza się! Chociaż czasem sensowne jest rozważenie takich „nieskończonych” systemów do celów dowodowych (np. Analiza porządkowa).

— cody