Usuwanie rekurencji - spojrzenie na teorię za kulisami

10

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_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)

pl.programming-languages recursion recursive Itachi Uchiha
źródło

1

jak słowo iterujące :)

Akash Kumar

nie jestem pewien, czy w pełni rozumiem, ale jeśli rekurencja gdzieś się skończy, możesz faktycznie zasymulować stos systemowy przy użyciu własnego stosu. W części 2 problemy nie różnią się pod względem złożoności obliczeniowej.

singhsumit

Myślę, że to pytanie najlepiej pasowałoby do witryny informatyki, która nie jest jeszcze dostępna. Co do drugiego pytania, czy możesz wyjaśnić, dlaczego uważasz, że jest trudniej? Proces powinien być prawie identyczny.

Raphael

dziękuję wszystkim za komentarze - chyba mam sporo do zrobienia.

Itachi Uchiha

@Raphael - Jeden komentarz na temat tego, dlaczego myślę, że iteracja postorder jest trudna (poza tym, że nie jestem w stanie tego zrobić). Czytałem kilka artykułów na temat usuwania rekurencji i natrafiłem na coś, co nazywa się funkcjami rekurencyjnymi ogona. Okazuje się, że łatwiej je iterować. Nadal nie rozumiem formalnie, dlaczego to prawda; ale jest jeszcze jedna rzecz, którą powinienem dodać. Słyszałem, że iteratyzacja postorder wymaga dwóch stosów, a nie jednego, ale nie znam szczegółów. A teraz jestem zagubiony - skąd ta różnica między tymi dwoma trybami przejścia? I dlaczego rekurencja ogona jest łatwa w obsłudze?

Itachi Uchiha

6

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 nie rekurencyjnych siebie (bo mamy ich już przekształcone), możemy inline wszystkie te połączenia w definicji , 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 , tj. . 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.

Raphael
źródło

Cieszę się, że mogłem pomóc. Pamiętaj, aby zaakceptować swoją ulubioną odpowiedź, klikając znacznik wyboru obok niej.

Raphael

1

Raphel, twoja sztuczka działa tylko wtedy, gdy obie funkcje rekurencyjne akceptują argumenty tego samego typu. Jeśli fi gakceptuje różne rodzaje typów, jest potrzebne bardziej ogólnego podstęp.

Andrej Bauer,

@AndrejBauer dobra obserwacja, całkowicie mi tego brakowało. Naprawdę podobało mi się podejście Rafaela, ale jak zauważyłeś w ogólnych przypadkach, prawdopodobnie potrzebujemy innego pomysłu. Czy możesz podać jakieś inne sugestie?

Itachi Uchiha

@AndrejBauer True. Myślałem z teoretycznego punktu widzenia; tutaj mamy tylko liczby naturalne. Jest to wystarczające, ponieważ możemy zakodować wszystko w odpowiedni sposób. Ale twój punkt widzenia jest bardzo ważny dla praktyki. Myślę, że musielibyśmy przepisać fi gdopóki nie będą mieli wspólnego schematu kodowania i rekurencji wejściowej (nie możemy mieć jednego używającego

i drugiego

).

n - 1

$n-1$

n - 2

$n-2$

Raphael

Cóż, zobacz moją odpowiedź, jak to zrobić.

Andrej Bauer,

8

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

{fa}_{1} : {ZA}_{1} \to b_{1}

$f_1 : A_1 \to B_1$

{fa}_{2)} : {ZA}_{2)} \to b_{2)}

$f_2 : A_2 \to B_2$

⋮

$\vdots$

{fa}_{n} : {ZA}_{n} \to b_{n}

$f_n : A_n \to B_n$

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

fa : {ZA}_{1} + \dots + {ZA}_{n} \to b_{1} + \dots + b_{n},

$f : A_1 + \cdots + A_n \to B_1 + \cdots + B_n,$

Andrej Bauer
źródło

8

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.

Dave Clarke
źródło

będę tu szczery. Naprawdę chcę zrozumieć, dlaczego (i jak) możesz iterować każdy program rekurencyjny. Ale trudno mi przeczytać artykuł - zwykle nie są dla mnie dostępne. mam na myśli głębszy powód niż opis „handwavy”, o którym mówiłem w pytaniu. ale cieszę się również z czegoś, co daje mi nowy wgląd - nie musi to być cały dowód w jego drobiazgowych szczegółach

Itachi Uchiha

[cntd] Mam na myśli, że podoba mi się dowód, jeśli taki istnieje, aby powiedzieć mi, dlaczego iteracja jednego programu jest łatwiejsza od drugiego. Ale w pewnym sensie konwerter rekurencyjny na iteracyjny powinien działać bez względu na program rekurencyjny, który przyjmuje jako dane wejściowe. Nie jestem pewien, ale myślę, że wykonanie takiego konwertera może być tak trudne, jak problem zatrzymania? Po prostu zgaduję tutaj - ale chciałbym, aby istniał konwerter rekurencyjny na iteracyjny, a jeśli tak, chciałbym, aby to wyjaśniło nieodłączną złożoność iteracji różnych programów rekurencyjnych. nie jestem pewien, ale czy powinienem edytować pytanie? Czy moje pytanie jest jasne?

Itachi Uchiha

@ItachiUchiha - Nie sądzę, że twój problem jest nierozstrzygalny. Spójrz na odpowiedź Andreja Bauera. Zauważa, że każdy kompilator robi to, kiedy tłumaczy kod źródłowy na język maszynowy. Dodaje również, że w języku MiniM (a) l można zobaczyć rzeczywisty kod konwertujący rekurencyjny na nierekurencyjny. Wskazuje to wyraźnie, że istnieje procedura decyzyjna w celu „iteracji” rekurencji. Nie jestem pewien wrodzonej (konceptualnej) trudności / złożoności usuwania rekurencji. Nie rozumiem tego pytania bardzo wyraźnie, ale wygląda interesująco. Może możesz edytować swoje pytanie, aby uzyskać lepszą odpowiedź

Akash Kumar,

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.

Dave Clarke

6

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 .... ).

Marzio De Biasi
źródło

1

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.

Jules
źródło

0

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.

vzn
źródło

1

Dowód równoważności Turinga / lambda znajduje się w załączniku do tego dokumentu: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

Radu GRIGore

Usuwanie rekurencji - spojrzenie na teorię za kulisami

Odpowiedzi: