Usuwanie rekurencji - spojrzenie na teorię za kulisami

Jestem nowy na tej stronie i to pytanie z pewnością nie jest na poziomie badawczym - ale no cóż. Mam małe doświadczenie w inżynierii oprogramowania i prawie żadnych w CSTheory, ale uważam to za atrakcyjne. Krótko mówiąc, chciałbym uzyskać bardziej szczegółową odpowiedź na poniższe pytania, jeśli to pytanie jest dopuszczalne na tej stronie.

Wiem więc, że każdy program rekurencyjny ma iteracyjny analog i rozumiem popularne wyjaśnienie, które jest dla niego oferowane, utrzymując coś podobnego do „stosu systemowego” i zmieniając ustawienia środowiska, takie jak adres zwrotny itp. Uważam, że jest to pewien problem .

Będąc nieco bardziej konkretnym, chciałbym (formalnie) zobaczyć, jak można udowodnić to stwierdzenie w przypadkach, gdy masz funkcję wywołującą łańcuch . Co więcej, jeśli istnieją jakieś instrukcje warunkowe, które mogą doprowadzić do wywołania ? Oznacza to, że wykres wywołania funkcji potencjalnej zawiera pewne silnie powiązane komponenty.F $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$$F_i$$F_j$

Chciałbym wiedzieć, jak poradzić sobie z tymi sytuacjami, powiedzmy jakiś konwerter rekurencyjny na iteracyjny. I czy opis, o którym wspominałem wcześniej, był naprawdę wystarczający dla tego problemu? Mam na myśli to, dlaczego w niektórych przypadkach usunięcie rekurencji jest dla mnie łatwe. W szczególności usunięcie rekurencji z przejścia drzewa binarnego w przedsprzedaży jest naprawdę łatwe - jest to standardowe pytanie do wywiadu, ale usunięcie rekurencji w przypadku zamówienia pocztowego zawsze było dla mnie koszmarem.

Naprawdę pytam o pytania$2$

(1) Czy naprawdę istnieje bardziej formalny (przekonujący?) Dowód, że rekurencję można przekształcić w iterację?

(2) Jeśli ta teoria naprawdę istnieje, to dlaczego, na przykład, uważam , że na przykład iterowanie preorderów jest łatwiejsze, a postorder tak trudne? (inne niż moja ograniczona inteligencja)

Jeśli dobrze rozumiem, masz jasność co do konwertowania funkcji, które nie zawierają innych wywołań funkcji, tylko dla siebie.

Zakładamy więc mamy "łańcuch nazywamy" . Gdybyśmy ponadto założyć, że F 1 , ... , F n nie rekurencyjnych siebie (bo mamy ich już przekształcone), możemy inline wszystkie te połączenia w definicji F , która wygląda następująco staje się bezpośrednio rekurencyjna funkcja możemy już zajmować.$F \to F_1 \to \dots \to F_n \to F$$F_1, \dots, F_n$$F$

Nie udaje się to, jeśli część ma sam rekurencyjny łańcuch połączeń, w którym występuje F , tj. F j → ⋯ → F → ⋯ → F j . W tym przypadku mamy wzajemną rekurencję, która wymaga kolejnej sztuczki, aby się pozbyć. Chodzi o to, aby obliczyć obie funkcje jednocześnie. Na przykład w trywialnym przypadku:$F_j$$F$$F_j \to \dots \to F \to \dots \to F_j$

f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))

o f'i g'nierekurencyjnych funkcje (lub przynajmniej niezależne od fi g) staje

h(0) = (a,b)
h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) end

f(n) = let (f, _) = h(n) in f end
g(n) = let (_, g) = h(n) in g end

Rozciąga się to oczywiście na więcej zaangażowanych funkcji i bardziej skomplikowane funkcje.

Tak, istnieją przekonujące powody, by sądzić, że rekurencję można przekształcić w iterację. Tak robi każdy kompilator, tłumacząc kod źródłowy na język maszynowy. Dla teorii należy postępować zgodnie z sugestiami Dave'a Clarke'a. Jeśli chcesz zobaczyć rzeczywisty kod konwertujący rekurencję na kod nierekurencyjny, spójrz na machine.mljęzyk MiniML w moim PL Zoo (zauważ, że loopfunkcja u dołu, która faktycznie uruchamia kod, jest rekurencyjna i dlatego może być trywialnie przekonwertowany na rzeczywistą pętlę).

Jeszcze jedna rzecz. MiniML nie obsługuje funkcji wzajemnie rekurencyjnych. Ale to nie jest problem. Jeśli masz wzajemną rekurencję między funkcjami

rekurencję można wyrazić jako pojedynczą mapę rekurencyjną

Możesz spojrzeć na maszynę SECD . Język funkcjonalny (choć może to być dowolny język) jest tłumaczony na szereg instrukcji, które zarządzają takimi rzeczami, jak wstawianie argumentów stosów, „wywoływanie” nowych funkcji i tak dalej, wszystkie zarządzane za pomocą prostej pętli.
Połączenia rekurencyjne nigdy nie są wywoływane. Zamiast tego instrukcje ciała wywoływanej funkcji są umieszczane na stosie do uruchomienia.

Podobnym podejściem jest maszyna CEK .

Oba są dostępne od dłuższego czasu, więc jest dużo pracy nad nimi. Oczywiście istnieją dowody na to, że działają, a procedura „kompilowania” programu do instrukcji SECD jest liniowa pod względem wielkości programu (nie musi myśleć o programie).

Chodzi mi o to, że istnieje automatyczna procedura robienia tego, co chcesz. Niestety transformacja niekoniecznie musi polegać na tym, że programiści mogą od razu łatwo ją zinterpretować. Myślę, że kluczem jest to, że jeśli chcesz wykonać iterację programu, musisz zapisać na stosie to, co program musi zrobić po powrocie z iterowanego wywołania funkcji (jest to nazywane kontynuacją). W przypadku niektórych funkcji (takich jak funkcje rekurencyjne z tyłu) kontynuacja jest banalna. Dla innych kontynuacja może być bardzo złożona, szczególnie jeśli musisz ją zakodować samodzielnie.

P : „Czy naprawdę istnieje bardziej formalny (przekonujący?) Dowód, że rekurencję można przekształcić w iterację?”

Odp . : Kompletność maszyny Turinga Turinga :-)

Żartuje, że model maszyny RASP (TAS) w programie Random Access jest zbliżony do działania prawdziwych mikroprocesorów, a zestaw instrukcji zawiera tylko skok warunkowy (bez rekurencji). Możliwość dynamicznej samodomodyfikacji kodu ułatwia wdrażanie podprogramów i wywołań rekurencyjnych.

Myślę, że można znaleźć wiele artykułów / artykułów na temat „ konwersji rekurencyjnej na iteracyjną ” (patrz odpowiedź Dave'a lub po prostu słowa kluczowe Google), ale być może mniej znanym (i praktycznym ) podejściem jest najnowsze badanie sprzętowej implementacji algorytmów rekurencyjnych ( przy użyciu języka VHDL, który jest „kompilowany” bezpośrednio na urządzenie). Na przykład patrz artykuł V.Sklyarova „ Implementacja algorytmów rekurencyjnych w oparciu o układ FPGA ” ( Artykuł sugeruje nową metodę implementacji algorytmów rekurencyjnych w sprzęcie. ... Przebadano dwa praktyczne zastosowania algorytmów rekurencyjnych w obszarze sortowania danych i kompresji szczegółowo .... ).

Jeśli znasz języki obsługujące lambdy, jedną z możliwości jest przyjrzenie się transformacji CPS. Usunięcie użycia stosu wywołań (a zwłaszcza rekurencji) jest dokładnie tym, co robi transformacja CPS. Przekształca program zawierający wywołania procedur w program zawierający tylko wywołania ogonowe (można je traktować jako gotos, co jest konstrukcją iteracyjną).

Transformacja CPS jest ściśle związana z jawnym utrzymywaniem stosu wywołań w tradycyjnym stosie opartym na macierzy, ale zamiast w stosie stos wywołań jest reprezentowany przez połączone zamknięcia.

moim zdaniem pytanie to sięga samego początku definicji obliczeń i zostało już dawno udowodnione rygorystycznie w tym czasie, gdy kościelny rachunek lambda (który bardzo dobrze oddaje koncepcję rekurencji) okazał się być równoważny z maszynami Turinga i jest zawarty w wciąż używanej terminologii „języki / funkcje rekurencyjne”. również najwyraźniej późniejszy odnośnik do klucza w tym zakresie jest następujący

Jak wskazano w pracy Petera Landina z 1965 r. Korespondencja między ALGOL 60 a notacją Lambda Kościoła, sekwencyjne proceduralne języki programowania można rozumieć w kategoriach rachunku lambda, który zapewnia podstawowe mechanizmy abstrakcji proceduralnej i zastosowania procedury (podprogramu).

znaczna część tego jest na tej stronie wikipedii praca kościelna . Nie jestem pewien dokładnych szczegółów, ale artykuł w Wikipedii wydaje się wskazywać, że to Rosser (1939) pierwszy udowodnił tę równoważność między rachunkiem lambda a maszynami Turinga. może / przypuszczalnie jego praca ma mechanizm stosu do konwersji (ewentualnie rekurencyjnych) wywołań lambda na konstrukcję TM?

Rosser, JB (1939). „Nieformalna prezentacja dowodów twierdzenia Godela i twierdzenia Kościoła”. The Journal of Symbolic Logic (The Journal of Symbolic Logic, t. 4, nr 2) 4 (2): 53–60. doi: 10.2307 / 2269059. JSTOR 2269059.

uwaga oczywiście dla każdego, kto interesuje się zasadami, nowoczesny język Lisp i wariant Scheme celowo mają silne podobieństwo do rachunku lambda. studiowanie kodu interpretera do oceny wyrażeń prowadzi do pomysłów, które pierwotnie były zawarte w artykułach dotyczących kompletności rachunku lambda.