Czy istnieją pośrednie teorie eta dla rachunku lambda?

15

Istnieją dwie główne, zbadane teorie rachunku lambda, teorii beta i jej rozwinięcia post-zupełnego, teorii beta-eta.

Czy te dwie teorie mają pośrednią, rodzaj pośredniej reguły eta, która daje spójną teorię przepisywania? Czy istnieje jakieś interesujące pojęcie częściowej ekstensywności, któremu ono odpowiada?

Jest to drugie pytanie, które zadałem w ramach pośredniej eta, przy czym poprzednie było rozszerzeniem beta-teorii rachunku lambda , co doprowadziło do pytania o ortogonalne pojęcie rozszerzenia, charakteryzujące niewidzialne równoważności poprzez zbieżne reguły przepisywania , które miały na celu wyjaśnienie odpowiedz na to wcześniejsze pytanie.

lo.logic lambda-calculus extensionality

— Charles Stewart
źródło

10

W przypadku kalkulatorów maszynowych, jeśli weźmiesz pod uwagę typy ujemne ( , , ), możesz włączać i wyłączać reguły eta praktycznie w dowolnym momencie, bez wpływu na zbieżność. $1$ $\times$ $\to$

W przypadku typów dodatnich (sum i par z eliminacją dopasowania do wzorca) sytuacja jest znacznie bardziej chaotyczna. Zasadniczo pytanie brzmi, czy termin ma formę eliminacji o zamkniętym zakresie, która pozwala kontekstom na interakcję w skomplikowany sposób z rozszerzeniem eta. Na przykład, jeśli ma typ , to jego eta-ekspansja jest $e$ $A \times B$ . Ale aby uzyskać teorię równań, której oczekiwałby teoretyk kategorii, należy wziąć pod uwagę konteksty i uogólnić równanie na $\mathsf{let}\;(a,b) = e \;\mathsf{in}\; (a,b)$ $\mathbb{C}[-]$ (z oczekiwanymi ograniczeniami zakresu). $\mathbb{C}[e] \equiv \mathsf{let}\;(a,b) = e\;\mathsf{in}\;\mathbb{C}[(a,b)]$

Myślę, że nadal możesz udowodnić wynik zbiegu, jeśli nie zezwolisz na konwersję dojazdów do pracy. Ale to jest pogłoska - sam nigdy tego nie próbowałem ani nie przeglądałem dokumentów dokumentujących to.

Ale tak naprawdę nie wiem nic o nietypowym rachunku lambda.

EDYCJA: Charles pyta o eta-redukcje. Jest to obiecujące dla tego rodzaju przykładu, którego szuka, ponieważ myślę, że ogólnie nie będą one wystarczająco silne, aby modelować pełną teorię równości, którą zilustruję prostym przykładem obejmującym booleany. Ekspansja eta dla booleanów to . (Redukcja eta jest oczywiście w innym kierunku). $\mathbb{C}[e] \mapsto \mathsf{if}(e, \mathbb{C}[\mathsf{true}], \mathbb{C}[\mathsf{false}])$

Teraz rozważmy termin . Wskazując, że termin ten jest równoważny z $\mathsf{if}(e, f, g)\;\mathsf{if}(e, x, y)$ musi przejść przez eta spieniania, ponieważ trzeba wymienić w jednym z jeżeli-to-elses połączeniu z and w celu doprowadzenia do -redukcja. $\mathsf{if}(e, f\;x, g\;y)$ $e$ $\mathsf{true}$ $\mathsf{false}$ $\beta$

— Neel Krishnaswami
źródło

Powinienem był wyjaśnić, że chodziło o niepisany rachunek lambda: logika na bok może to uczynić niejasnym. W typowym przypadku spodziewam się, że kompletność postów jest zgodna z teorią 〈→, ×〉, ale nie jestem wcale pewien innych typów. konteksty współdziałają w skomplikowany sposób z rozszerzeniami eta - to jest powód do rozważenia zmniejszenia eta, prawda, ponieważ nie trzeba ograniczać przepisywania?

— Charles Stewart,

4

Według Johna C. Mitchella w Foundations of Programming Languages, zarówno w STLC, jak i w niepisanym rachunku lambda, reguła redukcji pair (proj₁ P, proj₂ P) → Pprzerywa konfluencję w połączeniu z fixredukcją (lub, jak przypuszczam, patrząc na dowód), bez takich warunków dla nietypowego przypadku. To jest twierdzenie 4.4.19 (strona 272).

— Blaisorblade
źródło

2

Myślę, że to obszerny komentarz do odpowiedzi Neela. Klop i De Vrijer (1989) badają teorię niepoprawnego rachunku lambda za pomocą parowania z impulsem: przypadek z redukcją eta jest wprawdzie niekonfluentny, ale teoria jest spójna (ma model w konstrukcji Scotta D_inf) i dają wyniki sugerując, że można podać zbieżną, konserwatywną teorię przepisywania dla par przymiotników (wciąż problem otwarty, AFAIK).

— Charles Stewart