Rachunek konstrukcji: skompresuj wyrażenie do jego najmniejszej postaci

Wiem, że Rachunek Konstrukcji jest silnie normalizujący, co oznacza, że ​​każde wyrażenie ma normalną wartość, która nie może być beta, a jeszcze bardziej zmniejszona eta. W rzeczywistości jest to najbardziej wydajne wyrażenie, które oblicza tę samą wartość, co oryginalne wyrażenie.

Ale w niektórych przypadkach normalizacja może zredukować małe wyrażenie do dużego (pod względem wielkości).

Czy istnieje najmniejsza forma wyrażeń? Formularz, który oblicza tę samą wartość przy najmniejszym rozmiarze.

Innymi słowy, zamiast wydajnej czasowo formy normalnej, zajmującej mało miejsca.

Jest trochę wolności w tym, co uważamy za „tę samą wartość”. Pokażę, że nie ma takiego algorytmu, jeżeli „ta sama wartość” oznacza „równoważne obserwacyjnie”. Użyję fragmentu Rachunku konstrukcji, mianowicie Systemu T Gödela (po prostu wpisanego na nim -calculus, liczby naturalne i prymitywna rekurencja na nich), więc argument dotyczy już znacznie słabszego rachunku różniczkowego.$\lambda$

Biorąc pod uwagę liczbę , niech będzie odpowiadającą jej liczbą, tj. aplikacji od do . Biorąc pod uwagę maszynę Turinga , niech będzie kodowaniem w jakiś rozsądny sposób.¯ n n s u c c 0 M ⌈ M ⌉ $n$$\overline{n}$$n$$\mathtt{succ}$$0$$M$$\lceil M \rceil$$M$

Powiedz, że dwa zamknięte terminy są równoważne , zapisane , kiedy dla wszystkich , i oba normalizują się do tej samej cyfry (normalizują się do cyfry, ponieważ mamy silnie normalizujący się claculus). t ≃ u n ∈ N$t, u : \mathtt{nat} \to \mathtt{nat}$$t \simeq u$$n \in \mathbb{N}$$t \, \overline{n}$$s \, \overline{n}$

Załóżmy, że mamy algorytm, który podając dowolny zamknięty termin typu oblicza minimalny równoważny termin. Następnie możemy rozwiązać wyrocznię Halting w następujący sposób.$\mathtt{nat} \to \mathtt{nat}$

Istnieje termin taki, że dla wszystkich i wszystkich maszyn Turinga , normalizuje się do jeśli zatrzymuje się w ciągu kroków, i normalizuje się do przeciwnym razie. Jest to dobrze znane, ponieważ symulacja maszyny Turinga dla ustalonej liczby kroków jest prymitywną rekurencyjną. n ∈ N M S ( ⌈ M ⌉ , ¯ n ) ¯ 1 T n ¯ 0$S : \mathtt{nat} \times \mathtt{nat} \to \mathtt{nat}$$n \in \mathbb{N}$$M$$S (\lceil M \rceil, \overline{n})$$\overline{1}$$T$$n$$\overline{0}$$n$

Istnieje wiele zamkniętych terminów które są minimalnymi terminami równoważnymi . Nasz algorytm minimalizacji zwraca jeden z nich, gdy dajemy mu , a może nawet być tak, że jest w rzeczywistości tylko taki minimalny termin. Wszystko to nie ma znaczenia, jedyne, co się liczy, to fakt, że istnieje wiele minimalnych terminów, które są równoważne . λ x : n a t$Z_1, \ldots, Z_k$λ x : n a t$\lambda x : \mathtt{nat} .\, 0$λ x : n a t$\lambda x : \mathtt{nat} .\, 0$λ x : n a t$\lambda x : \mathtt{nat} .\, 0$$\lambda x : \mathtt{nat} .\, 0$

Teraz, mając dowolną maszynę , rozważ termin Jeśli działa wiecznie, to normalizuje się do dla każdego i jest równoważny . Aby zdecydować, czy działa wiecznie, wprowadzamy do naszego algorytmu minimalizacji i sprawdzamy, czy algorytm zwrócił jeden z . Jeśli tak, to działa wiecznie. Jeśli nie, to zatrzymuje się. (Uwaga: algorytm nie musi obliczaću : = λ x : n a t$M$

Byłoby miło poznać argument, który działa ze słabszym pojęciem równoważności, na przykład po prostu redukowalność.$\beta$

Jak powiedział Andrej, problem jest nierozstrzygalny, jeśli zezwolisz na zastąpienie jednego terminu innym, przedłużającym się równym. Jednak możesz być zainteresowany optymalnym udostępnianiem wyrażeń w następującym znaczeniu: biorąc pod uwagę redukcję jasne jest, że wystąpienie termin może być współużytkowany w pamięci , a każda redukcja zastosowana do jednej może być zastosowana do drugiej.

W tym sensie wiadomo, w jaki sposób optymalnie zredukować typy bez typu, zmniejszając w jak największym stopniu udostępnianie. Wyjaśniono to tutaj: https://stackoverflow.com/a/41737550/2059388, a odpowiednim cytatem jest algorytm J. Lampinga dla optymalnej redukcji rachunku lambda . Nie ma wątpliwości, że twierdzenie o rachunku bez typu może być rozszerzone na CIC.

Innym istotnym pytaniem jest ilość informacji o typie, które można usunąć podczas przeprowadzania konwersji typu, a nawet jak przeprowadzić wydajną konwersję, która jest aktywną dziedziną badań, patrz np . Teza Mishra-Linger .

Pozwólcie, że nalegam na punkt widzenia poruszony przez odpowiedź Cody'ego.

Z tego punktu widzenia kwestia znalezienia najmniejszego -termu równoważnego innemu termowi nie jest tak naprawdę interesująca, nawet jeśli istniałby algorytm ją obliczający. W rzeczywistości większość programów, które piszesz w -calculus (lub jakikolwiek rachunek -cube) jest już w normalnej formie, a przynajmniej w normalnej formie, więc są już w ich „najmniejszym” znaczeniu w tym sensie, że opisać. Poza tym bycie „małym” nie oznacza bycia bardziej wydajnym, jak omówiono w tym pytaniu .λ λ $\lambda$$\lambda$$\lambda$$\lambda$

Zatem problem, który wskazałeś (normalizacja powoduje powiększenie rozmiaru), jest prawdziwym problemem tylko wtedy, gdy chcesz zastosować funkcję do argumentu i zredukować do normalnej postaci, aby uzyskać wynik. Załóżmy na przykład, że masz termin obliczający funkcję na ciągach binarnych. Następnie masz gdzie to liczba kroków redukcji z wykorzystaniem redukcji skrajnie lewostronnej, która gwarantuje, że znajdzie normalną formę, jeśli istnieje (w CoC, zawsze istnieje, ale to, co mówię, dotyczy również nietypowego przypadku). Załóżmy ponadto, że dla pewnej stałej . Czy możesz dojść do wniosku, że jest obliczalny w czasie wielomianowym?f $M$$f$ l(|x|)l(n)=O(nk)k

Bardzo łatwo jest skonstruować przykłady terminów, których rozmiar rośnie wykładniczo wraz ze zmniejszeniem (skrajnie lewy-skrajny), tzn. W krokach pojawia się termin wielkość . Może to nas poważnie wątpić w odniesieniu do pozytywnej odpowiedzi na powyższe pytanie: wydaje się, że -calculus jest w stanie wykonać wykładniczą ilość pracy w czasie liniowym. Innymi słowy, wydaje się, że rachunek nie jest rozsądnym modelem obliczeń pod względem złożoności.Θ ( n ) Θ ( 2 n ) λ $\lambda$$\Theta(n)$$\Theta(2^n)$$\lambda$$\lambda$

Mimo że powyższa wątpliwość jest uzasadniona, wynika ona z błędnego założenia, że termin jest skutecznym przedstawieniem siebie. Oni nie są! Mniej żartobliwie, -termy są bardzo nieefektywnymi reprezentacjami stanów , przez które maszyna je wykonująca faktycznie musi przejść.$\lambda$$\lambda$

Okazuje się, że istnieje składnia zwana -calculus z liniowymi wyraźnymi podstawieniami i wprowadzona przez Beniamino Accattoli, która bardzo dobrze reprezentuje zjawisko dzielenia się, o którym wspomina odpowiedź Cody'ego. W szczególności ta składnia może być użyta do zapewnienia niezwykle wiernych reprezentacji terminów wszelkiego rodzaju abstrakcyjnych maszyn (patrz artykuł ICFP 2014 Beniamino „Distilling Abstract Machines”, którego jestem współautorem. Przepraszam za autopromocję, ale wydaje się to istotne tutaj).$\lambda$

Tę samą składnię można zastosować, aby udowodnić, że wbrew naiwnej intuicji odpowiedź na powyższe pytanie jest rzeczywiście tak: liczba skrajnie lewych kroków do normalnej postaci jest rozsądną miarą kosztów, nawet jeśli rozmiar eksploduje, ponieważ istnieje inny sposób przedstawienia tego samego obliczenia (przy użyciu liniowych podstawień jawnych), w którym:

1. rozmiar nie eksploduje;
2. biorąc pod uwagę dwa terminy w liniowej jawnej składni podstawienia, istnieje algorytm czasu wielomianowego, który sprawdza, czy reprezentują one ten sam -termin , tj. istnieje sprytny sposób porównywania terminów, które nie muszą „rozwijać” udostępniania ( po prostu „rozwijanie”, a następnie porównywanie nie działałoby, ponieważ termin „nieudostępniony” może być wykładniczo duży).$\lambda$

Wszystko to wyjaśniono w artykule Accattoli i Dal Lago „Beta Reduction is Invariant, Indeed” (LICS 2014, a potem myślę, że jest nowsza wersja czasopisma).

Myślę, że punkt 2 idzie bardzo w kierunku twojego pytania o reprezentacje „wydajne przestrzennie” : rachunek podstawienia liniowego zapewnia takie reprezentacje, chociaż w żaden sposób nie są one „normalne”, tj. Nie są normalna forma jakiejś procedury przepisywania.$\lambda$