Czy ktoś napisał formalny dokument opisujący metodę (automatyczną) konwertowania funkcji na rekursywne? Szukam formalnego traktowania na poziomie uniwersyteckim, w tym ograniczeń (rodzajów funkcji, które można przekształcić), procedur konwersji i, jeśli to możliwe, dowodów poprawności? Przykłady w Haskell byłyby bonusem.Konwertowanie funkcji na rekursję ogonową - formalne badanie
metoda (automatycznie) konwertowania funkcji na rekursywne?
więc dwie części niniejszego:
Przekształcenie rekursji do ogona rekursji
Wydaje się stosunkowo proste do rozpoznawania ogon cyklicznych definicje składniowo. W końcu "rekursywny ogon" oznacza tylko, że wywołanie pojawia się syntaktycznie w ogonie wyrażenia.
E.g. Ludzie Schematu opisują:
samo skompilowanie odpowiednich własnych połączeń jako skoków nie jest wystarczające, aby osiągnąć pełną rekurencję ogona. Zamiast tego dzielimy syntaktycznie wszystkie pozycje podekspresji w języku źródłowym na dwie klasy: ogon (lub redukcja) pozycja i pozycja podproblemowa. W prostym wyrażeniu (jeśli alternatywna alternatywa to
predicate),predicatejest podproblemową pozycją , podczas gdy zarówno następnik jak i alternatywa są w pozycjach redukcji . To pojęcie syntaktyczne można łatwo rozszerzyć na dowolnie zagnieżdżone podwyrażenia.
Przekształcenie funkcji w ogonie wzywa
Najtrudniejszą częścią pytanie optymalizacje identyfikacji i przekształcenie kandydujących cyklicznych obliczeń do ogona rekurencyjnych nich.
Jedna wzmianka w GHC, która używa inlineing i szeroki wachlarz reguł upraszczających, aby zwinąć rekursywne wywołania, dopóki nie zostanie zachowana ich podstawowa struktura rekurencyjna.
Tail Eliminacja
Gdy masz swoje funkcje w formie ogona wywołanie rekurencyjne, który chcesz mieć, że wdrożone effiicently. Jeśli możesz wygenerować pętlę, to dobry początek.Jeśli komputer docelowy nie, wówczas tail call elimination "będzie potrzebować kilku sztuczek. Cytując Odersky i Schinz, cytowany poniżej
różne techniki, które zostały zaproponowane w ostatnich latach w celu wyeliminowania generał (i nie tylko rekurencyjne) wywołuje ogon, głównie dla kompilatorów kierowanych C.
... umieścić cały program w wielkim funkcji i symulować połączeń za pomocą funkcji skoki bezpośrednie lub switch wewnątrz tej funkcji.
... o popularną techniką jest użycie trampoliny, trampoliny jest zewnętrzną funkcją , która wielokrotnie wywołuje funkcję wewnętrzną. Za każdym razem, wewnętrzna funkcja życzenia połączenia ogona innej funkcji, to nie wymaga się bezpośrednio, ale po prostu powraca jego wykrywanie (na przykład jako zamknięcie) do trampoliny, który następnie dokłada samego połączenia . W ten sposób unika się nieograniczonego wzrostu stosu, ale pewna wydajność jest nieuchronnie tracona, głównie dlatego, że wszystkie połączenia wykonywane przez trampolinę to połączenia z nieznanymi statycznie funkcjami.
Inną techniką jest Henry Baker „Cheney na MTA” ze swoją technikę, program musi najpierw zostać przekształcone na kontynuację przechodząc styl (CPS), w związku z włączeniem wszystkich połączeń do zaproszeń ogona, a następnie może być skompilowany jak zwykle. W czasie uruchamiania, gdy stos jest bliski przepełnienia, kontynuacja prądu jest budowana i zwracana (lub longjmped) do trampoliny "czekając" na dole stosu wywołań.
Tail call elimination on the Java Virtual Machine Michel Schinz Martin Odersky 2001
Henry G. Baker Jr. CONS nie powinny CONS jej argumenty, część II: Cheney na projekcie MTA Wersja stycznia 1994 r.
Myślałem, że OP również szuka eliminacji rekursji ogonowej, ale sposób w jaki zostało napisane, że OP wygląda na poszukiwanie przeciwieństwa (lub nawet uogólnienie czegoś przeciwnego) - cytuję: "przekonwertuj funkcje na ** ** tail recursive [emphasis mine] " – Attila
Program OP wymaga automatycznej konwersji funkcji rekursywnych na formę rekurencyjną, aby skorzystać z eliminacji ogona. On nie szuka samemu eliminacji ogona. – Ben
Pytanie jest niejednoznaczne. Nie jest jasne, czy szuka eliminacji ogona, czy ogólnie optymalizacji rekurencji ogona. Tak czy inaczej, te dokumenty to miejsce, od którego należy zacząć. –
Rtęć zawiera kilka optymalizacji do automatycznego wykonywania rekurencji. (Mercury jest językiem programowania logicznego wymuszania czystości, więc mówi o predykatach, a nie funkcjach, ale wiele z tych samych pomysłów odnosi się do programów Mercury co do Haskella.O wiele większa różnica niż logiczne niż funkcjonalne jest to, że jest bardziej surowe niż leniwe)
"Wprowadzenie do akumulatorów" generuje specjalistyczne wersje predykatów z dodatkowym parametrem akumulatora, aby umożliwić przeniesienie operacji zespolonych przed wywołaniem rekurencyjnym. Wygląda na to, że ta optymalizacja niekoniecznie prowadzi do samych predykatów rekurencyjnych, ale często daje formę, która może być zoptymalizowana przez drugą optymalizację:
"Last modulo constructor" zasadniczo pozwala na wywołanie rekursywne, które następuje tylko przez aplikacje konstruktorów, które mają być przepisane tak, że wartość jest skonstruowana jako pierwsza zawierająca "dziurę", a następnie wywołanie rekursywne zwraca jej wyjście bezpośrednio do adresu pamięci "otworu" zamiast korzystania z normalnej konwencji przekazywania wartości zwrotnej. Wierzę, że Haskell dostałby tę optymalizację za darmo ze względu na lenistwo.
Oba optymalizacji są opisane w dokumencie Making Mercury programs tail recursive.
Zrobiłem trochę Googling, ale nie mogłem znaleźć żadnych konkretnych odniesień.Miałem nadzieję, że ktoś może podać referencję lub dwie. – Ralph
Transformacja CPS z pewnością wykonałaby zadanie w najbardziej ogólnym przypadku (a niektóre wynikające z tego optymalizacje mogą wyeliminować większość powstałego cruftu). Mnóstwo gazet jest publikowanych na ten temat. –