Co to jest eliminacja rekursji ogonowej?

Question

Steve Yegge wspomniał o tym w blog post i nie mam pojęcia, co to znaczy, czy ktoś może mnie wypełnić?

Czy to to samo, co tail call optimization?

Answer 1

Eliminacja ogona jest optymalizacją, która pozwala zaoszczędzić stack miejsca. zastępuje on funkcję połączenia z goto. Tail eliminacji rekurencji jest to samo, ale z dodatkowym ograniczeniem, że funkcja jest nazywająca siebie.

Zasadniczo, jeśli w ostatniej rzeczą funkcji A to jest return A(params...), wtedy możesz wyeliminować alokację ramki stosu, a zamiast tego ustawić odpowiednie rejestry i przeskocz bezpośrednio do treści funkcji.

Rozważmy konwencję wywołania (urojoną), która przekazuje wszystkie parametry na stosie i zwraca wartość w jakimś rejestrze.

Niektóre funkcja może skompilować dół (w wyimaginowanej asemblerze):

function: 
//Reading params B, C, & D off the stack 
pop B 
pop C 
pop D 
//Do something meaningful, including a base case return 
... 
//Pass new values for B, C, & D to a new invocation of function on the stack 
push D* 
push C* 
push B* 
call function 
ret 

Niezależnie od powyższego faktycznie ma, zajmuje całą nową ramkę stosu dla każdego połączenia funkcjonować. Jednakże, ponieważ nic nie występuje po wywołaniu ogona do funkcji, z wyjątkiem powrotu, możemy bezpiecznie zoptymalizować ten przypadek.

Wynikające w:

function: 
//Reading params B, C, & D off the stack (but only on the first call) 
pop B 
pop C 
pop D 
function_tail_optimized: 
//Do something meaningful, including a base case return 
... 
//Instead of a new stack frame, load the new values directly into the registers 
load B, B* 
load C, C* 
load D, D* 
//Don't call, instead jump directly back into the function 
jump function_tail_optimized 

końcowy wynik jest równoważny funkcja oszczędza dużo miejsca na stosie, szczególnie dla wejść, które wynikają w dużej liczbie wywołań rekurencyjnych.

W mojej odpowiedzi potrzebna jest duża wyobraźnia, ale myślę, że wpadniesz na pomysł.

Answer 2

z here:

”... eliminacja Tail rekurencji jest szczególny przypadek eliminacji rozmowy ogona, w którym rozmowa ogon jest wezwaniem do sama funkcja W takim przypadku połączeń . może być zastąpiony przez skok do początku funkcji po przesunięciu nowe argumenty do odpowiednich rejestrów lub lokalizacji stos ...”

z Wikipedia:

”... Gdy funkcja jest wywoływana, komputer musi«pamiętać»miejsce to nazwano od, adres zwrotny, tak że może wrócić do tej lokalizacji z wynikiem jednokrotnie połączenie jest kompletne. Zwykle ta informacja jest zapisywana na stosie, prosta lista lokalizacji zwrotu, w kolejności od czasu, w którym lokalizacje połączeń, które opisują, zostały osiągnięte. Czasami ostatnią rzeczą, jaką funkcja wykonuje po wykonaniu wszystkich innych operacji, jest po prostu wywołanie funkcji, ewentualnie samej, i zwrócenie jej wyniku. Z rekurencją ogona, nie ma potrzeby, aby pamiętać miejsce, z którego dzwonimy - zamiast tego możemy zostawić stos samodzielnie, a nowo wywołana funkcja zwróci wynik bezpośrednio do pierwotnego wywołującego. Przekształcenie połączenia w gałąź lub skok w takim przypadku nazywa się optymalizacją wywołania końcowego. Należy zauważyć, że wywołanie ogona nie musi pojawiać się leksykalnie po wszystkich innych wyrażeniach w kodzie źródłowym; ważne jest, aby jego wynik był natychmiast zwracany, ponieważ funkcja wywołująca nigdy nie będzie miała szansy zrobić nic po wywołaniu, jeśli zostanie wykonana optymalizacja ... "