Opublikowałem moduł przeprowadzający optymalizację wywołania ogona (obsługujący zarówno styl rekurencji, jak i przekazywanie kontynuacji): https://github.com/baruchel/tco
Optymalizacja rekurencji ogona w Pythonie
Często twierdzono, że rekurencja ogona nie pasuje do Pythońskiego sposobu kodowania i że nie należy dbać o to, jak osadzić go w pętli. Nie chcę się kłócić z tym punktem widzenia; czasem jednak lubię próbować lub wdrażać nowe pomysły jako funkcje rekurencyjne zamiast z pętlami z różnych powodów (skupiając się raczej na pomyśle niż na procesie, mając na ekranie dwadzieścia krótkich funkcji zamiast tylko trzech „pytonicznych” funkcje, praca w interaktywnej sesji zamiast edycji mojego kodu itp.).
Optymalizacja rekurencji ogona w Pythonie jest w rzeczywistości dość łatwa. Chociaż mówi się, że jest to niemożliwe lub bardzo trudne, myślę, że można to osiągnąć za pomocą eleganckich, krótkich i ogólnych rozwiązań; Myślę nawet, że większość tych rozwiązań nie używa funkcji Pythona inaczej niż powinny. Czyste wyrażenia lambda współpracujące z bardzo standardowymi pętlami prowadzą do szybkich, wydajnych iw pełni użytecznych narzędzi do wdrażania optymalizacji rekurencji ogona.
Dla osobistej wygody napisałem mały moduł implementujący taką optymalizację na dwa różne sposoby. Chciałbym tutaj omówić moje dwie główne funkcje.
Prosty sposób: modyfikowanie kombinatora Y.
Syntezatora Y jest dobrze znane; pozwala na używanie funkcji lambda w sposób rekurencyjny, ale nie pozwala na osadzanie wywołań rekurencyjnych w pętli. Sam rachunek Lambda nie może zrobić czegoś takiego. Niewielka zmiana w kombinatorze Y może jednak ochronić wywołanie rekurencyjne, które ma zostać faktycznie ocenione. Ocena może zatem zostać opóźniona.
Oto słynne wyrażenie dla kombinatora Y:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
Z niewielką zmianą mogłem uzyskać:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))
Zamiast wywoływać się sama, funkcja f zwraca teraz funkcję wykonującą to samo wywołanie, ale ponieważ ją zwraca, oceny można dokonać później z zewnątrz.
Mój kod to:
def bet(func):
b = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args))))(func)
def wrapper(*args):
out = b(*args)
while callable(out):
out = out()
return out
return wrapper
Z funkcji można skorzystać w następujący sposób; oto dwa przykłady z rekurencyjnymi wersjami silni i Fibonacciego:
>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55
Oczywiście głębokość rekurencji nie jest już problemem:
>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42
Jest to oczywiście jedyny prawdziwy cel tej funkcji.
Z tą optymalizacją nie można zrobić tylko jednej rzeczy: nie można jej używać z funkcją rekurencyjną ogonową przetwarzającą na inną funkcję (wynika to z faktu, że wszystkie zwracane obiekty, które można wywoływać, są obsługiwane jako kolejne rekurencyjne wywołania bez rozróżnienia). Ponieważ zwykle nie potrzebuję takiej funkcji, jestem bardzo zadowolony z powyższego kodu. Jednak w celu zapewnienia bardziej ogólnego modułu pomyślałem trochę więcej, aby znaleźć obejście tego problemu (patrz następny rozdział).
Jeśli chodzi o szybkość tego procesu (co nie jest jednak prawdziwym problemem), okazuje się, że jest całkiem dobry; funkcje rekurencyjne są sprawdzane nawet znacznie szybciej niż w przypadku następującego kodu przy użyciu prostszych wyrażeń:
def bet1(func):
def wrapper(*args):
out = func(lambda *x: lambda: x)(*args)
while callable(out):
out = func(lambda *x: lambda: x)(*out())
return out
return wrapper
Myślę, że ocena jednego wyrażenia, nawet skomplikowanego, jest znacznie szybsza niż ocena kilku prostych wyrażeń, co ma miejsce w drugiej wersji. Nie zachowałem tej nowej funkcji w moim module i nie widzę żadnych okoliczności, w których można by jej użyć, a nie „oficjalnej”.
Styl kontynuacji przejścia z wyjątkami
Oto bardziej ogólna funkcja; jest w stanie obsłużyć wszystkie funkcje rekurencyjne ogona, w tym te zwracające inne funkcje. Połączenia rekurencyjne są rozpoznawane na podstawie innych wartości zwracanych na podstawie wyjątków. To rozwiązanie jest wolniejsze niż poprzednie; szybszy kod może być prawdopodobnie napisany przy użyciu niektórych specjalnych wartości jako „flag” wykrywanych w głównej pętli, ale nie podoba mi się pomysł używania specjalnych wartości lub wewnętrznych słów kluczowych. Istnieje zabawna interpretacja używania wyjątków: jeśli Python nie lubi wywołań rekurencyjnych, należy zgłosić wyjątek, gdy nastąpi wywołanie rekurencyjne, a sposobem Pythona będzie przechwycenie wyjątku w celu znalezienia czystego rozwiązanie, które tak naprawdę dzieje się tutaj ...
class _RecursiveCall(Exception):
def __init__(self, *args):
self.args = args
def _recursiveCallback(*args):
raise _RecursiveCall(*args)
def bet0(func):
def wrapper(*args):
while True:
try:
return func(_recursiveCallback)(*args)
except _RecursiveCall as e:
args = e.args
return wrapper
Teraz można korzystać ze wszystkich funkcji. W poniższym przykładzie f(n)jest oceniane do funkcji tożsamości dla dowolnej dodatniej wartości n:
>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42
Oczywiście można argumentować, że wyjątki nie są przeznaczone do celowego przekierowywania tłumacza (jako rodzaj gotostwierdzenia lub raczej raczej stylu kontynuacji przejścia), co muszę przyznać. Ponownie uważam za zabawny pomysł używania trypojedynczego wiersza jako returnstwierdzenia: próbujemy coś zwrócić (normalne zachowanie), ale nie możemy tego zrobić z powodu wystąpienia wywołania rekurencyjnego (wyjątek).
Pierwsza odpowiedź (29.08.2013).
Napisałem bardzo małą wtyczkę do obsługi rekurencji ogona. Możesz go znaleźć z moimi wyjaśnieniami tam: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs
Może osadzić funkcję lambda zapisaną stylem rekurencji ogona w innej funkcji, która oceni ją jako pętlę.
Moim skromnym zdaniem najciekawszą cechą tej małej funkcji jest to, że funkcja ta nie polega na jakimś brudnym hacku programistycznym, ale na rachunku lambda: zachowanie funkcji zmienia się na inne po wstawieniu do innej funkcji lambda, która wygląda bardzo podobnie do kombinatora Y.