Co to jest optymalizacja połączeń ogonowych?

817

Po prostu, czym jest optymalizacja połączeń ogonowych?

Mówiąc dokładniej, jakie są małe fragmenty kodu, w których można je zastosować, a gdzie nie, z wyjaśnieniem, dlaczego?

majelbstoat
źródło
10
TCO zamienia wywołanie funkcji w pozycji ogona w goto, skok.
Czy Ness
8
To pytanie zostało zadane w pełni 8 lat wcześniej;)
majelbstoat

Odpowiedzi:

754

Optymalizacja wywołania ogonowego polega na tym, że można uniknąć przydzielenia nowej ramki stosu dla funkcji, ponieważ funkcja wywołująca zwróci po prostu wartość otrzymaną z wywołanej funkcji. Najczęstszym zastosowaniem jest rekurencja ogona, gdzie funkcja rekurencyjna napisana w celu skorzystania z optymalizacji wywołania ogona może wykorzystywać stałą przestrzeń stosu.

Schemat jest jednym z niewielu języków programowania, które gwarantują w specyfikacji, że każda implementacja musi zapewniać tę optymalizację (JavaScript również, począwszy od ES6) , więc oto dwa przykłady funkcji silni w Schemacie:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

Pierwsza funkcja nie jest rekurencyjna, ponieważ po wykonaniu wywołania rekurencyjnego funkcja musi śledzić mnożenie, które musi wynikać z wyniku po powrocie połączenia. W związku z tym stos wygląda następująco:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

W przeciwieństwie do tego, ślad stosu dla rekurencyjnej silni rekurencyjnej wygląda następująco:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Jak widać, musimy tylko śledzić tę samą ilość danych dla każdego wezwania do oględzin faktów, ponieważ po prostu zwracamy wartość, którą docieramy na sam szczyt. Oznacza to, że nawet gdybym zadzwonił (fakt 1000000), potrzebuję tylko tyle samo miejsca co (fakt 3). Nie dzieje się tak w przypadku faktu nierekurencyjnego, dlatego tak duże wartości mogą spowodować przepełnienie stosu.

Kyle Cronin
źródło
99
Jeśli chcesz dowiedzieć się więcej na ten temat, proponuję przeczytać pierwszy rozdział Struktury i interpretacji programów komputerowych.
Kyle Cronin,
3
Świetna odpowiedź, doskonale wyjaśniona.
Jonasz
15
Ściśle mówiąc, optymalizacja wywołania ogona niekoniecznie zastępuje ramkę stosu wywołującego callees, ale raczej zapewnia, że ​​nieograniczona liczba wywołań w pozycji ogona wymaga jedynie ograniczonej ilości miejsca. Zobacz artykuł Willa Clingera „Właściwa rekurencja ogona i efektywność przestrzeni”: cesura17.net/~will/Professional/Research/Papers/tail.pdf
Jon Harrop
3
Czy to tylko sposób na pisanie funkcji rekurencyjnych w sposób o stałej przestrzeni? Ponieważ nie można osiągnąć takich samych wyników przy użyciu podejścia iteracyjnego?
dclowd9901
5
@ dclowd9901, TCO pozwala preferować funkcjonalny styl, a nie iteracyjną pętlę. Możesz preferować imperatywny styl. Wiele języków (Java, Python) nie zapewnia TCO, więc musisz wiedzieć, że funkcjonalne połączenie kosztuje pamięć ... i preferowany jest styl imperatywny.
mcoolive,
551

Przejdźmy przez prosty przykład: funkcja silnia zaimplementowana w C.

Zaczynamy od oczywistej rekurencyjnej definicji

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

Funkcja kończy się wywołaniem ogona, jeśli ostatnią operacją przed powrotem funkcji jest kolejne wywołanie funkcji. Jeśli to wywołanie wywołuje tę samą funkcję, jest rekurencyjne.

Choć fac()na pierwszy rzut oka wygląda rekurencyjnie, nie jest tak, jak się naprawdę dzieje

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

tzn. ostatnia operacja to mnożenie, a nie wywołanie funkcji.

Możliwe jest jednak przepisanie w fac()celu rekurencji przez przekazanie skumulowanej wartości w dół łańcucha połączeń jako dodatkowy argument i przekazanie tylko końcowego wyniku w górę jako wartości zwracanej:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Dlaczego to jest przydatne? Ponieważ natychmiast wracamy po wywołaniu tail, możemy odrzucić poprzednią ramkę stosu przed wywołaniem funkcji w pozycji końcowej lub, w przypadku funkcji rekurencyjnych, ponownie użyć ramki stosu bez zmian.

Optymalizacja wywołania ogona przekształca nasz kod rekurencyjny w

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Można to wprowadzić fac()i doszliśmy do

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

co jest równoważne z

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

Jak widzimy tutaj, wystarczająco zaawansowany optymalizator może zastąpić rekurencję ogonem iteracją, co jest znacznie bardziej wydajne, ponieważ unikasz narzutu wywołania funkcji i używasz tylko stałej ilości miejsca na stosie.

Christoph
źródło
czy możesz wyjaśnić, co dokładnie oznacza ramka na stos? Czy istnieje różnica między stosem wywołań a ramką stosu?
Shasak
10
@Kasahs: ramka stosu jest częścią stosu wywołań, która „należy” do danej (aktywnej) funkcji; cf en.wikipedia.org/wiki/Call_stack#Structure
Christoph
1
Właśnie przeczytałem ten post po przeczytaniu 2ality.com/2015/06/tail-call-optimization.html
agm1984,
198

TCO (Tail Call Optimization) to proces, w którym inteligentny kompilator może wywoływać funkcję i nie zajmować dodatkowego miejsca na stosie. Jedynie sytuacja, w której to się dzieje, jeśli ostatnia instrukcja wykonywana w funkcji f jest wywołanie funkcji g (uwaga: g może być f ). Kluczem tutaj jest to, że f przestrzeni nie potrzebuje już Stack - to po prostu wywołuje g , a następnie wraca cokolwiek g wróci. W takim przypadku można dokonać optymalizacji, aby g po prostu uruchomił i zwrócił dowolną wartość do rzeczy, która wywołała f.

Ta optymalizacja może powodować, że wywołania rekurencyjne zajmują stałe miejsce na stosie, zamiast eksplodować.

Przykład: tej funkcji czynnikowej nie można zoptymalizować za pomocą TCO:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Ta funkcja wykonuje inne czynności niż wywoływanie innej funkcji w instrukcji return.

Poniższą funkcję można zoptymalizować za pomocą TCO:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

Wynika to z faktu, że ostatnią rzeczą, która wydarzy się w którejkolwiek z tych funkcji, jest wywołanie innej funkcji.

Claudiu
źródło
3
Cała „funkcja g może być f” była trochę myląca, ale rozumiem, co masz na myśli, a przykłady naprawdę wyjaśniły rzeczy. Wielkie dzięki!
majelbstoat
10
Doskonały przykład ilustrujący koncepcję. Wystarczy wziąć pod uwagę, że wybrany język musi implementować eliminację ogona lub optymalizację ogona. W przykładzie napisanym w Pythonie, jeśli wpiszesz wartość 1000, pojawi się „RuntimeError: przekroczona maksymalna głębokość rekurencji”, ponieważ domyślna implementacja Pythona nie obsługuje eliminacji Tail Recursion. Zobacz post od samego Guido wyjaśniający, dlaczego tak jest: neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html .
rmcc
Jedyna sytuacja” jest nieco zbyt absolutna; istnieje również TRMC , przynajmniej w teorii, który zoptymalizowałby (cons a (foo b))lub (+ c (bar d))w pozycji ogona w ten sam sposób.
Czy Ness
Podobało mi się twoje podejście fi i g lepiej niż zaakceptowana odpowiedź, może dlatego, że jestem matematyką.
Nithin,
Myślę, że masz na myśli TCOptimized. Mówiąc, że to nie jest TCOptimizowalny wniosek, że nigdy nie można go zoptymalizować (jeśli w rzeczywistości można)
Jacques Mathieu
65

Prawdopodobnie najlepszym opisem na wysokim poziomie, jaki znalazłem dla wezwań ogona, rekurencyjnych wezwań ogona i optymalizacji ogona ogona jest post na blogu

„Co do cholery: wezwanie do ogona”

autor: Dan Sugalski. Na temat optymalizacji wezwania ogona pisze:

Zastanówmy się przez chwilę nad tą prostą funkcją:

sub foo (int a) {
  a += 15;
  return bar(a);
}

Co możesz zrobić, a raczej Twój kompilator językowy? Cóż, może to zmienić kod formularza return somefunc();w sekwencję niskiego poziomu pop stack frame; goto somefunc();. W naszym przykładzie oznacza to, że zanim zadzwonimy bar, foooczyści się, a następnie, zamiast wywoływać barjako podprogram, wykonujemy gotooperację niskiego poziomu do początku bar. Foojest już wyczyszczony ze stosu, więc kiedy barzaczyna, wygląda na to, że ktokolwiek zadzwonił foo, naprawdę zadzwonił bar, a kiedy barzwraca jego wartość, zwraca go bezpośrednio temu, kto zadzwonił foo, zamiast zwracać go temu, fooktóry następnie zwróciłby go dzwoniącemu.

I na rekurencji ogona:

Rekurencja ogona ma miejsce, gdy funkcja jako ostatnia operacja zwraca wynik wywołania samego siebie . Rekurencja ogona jest łatwiejsza, ponieważ zamiast skakać gdzieś na początek jakiejś losowej funkcji, po prostu robisz goto z powrotem na początek siebie, co jest cholernie prostą rzeczą.

Aby to:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

cicho zamienia się w:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

W tym opisie podoba mi się to, jak zwięzłe i łatwe jest uchwycenie osób wywodzących się z imperatywnego języka (C, C ++, Java)

btiernay
źródło
4
Błąd 404. Jest jednak nadal dostępny na archive.org: web.archive.org/web/20111030134120/http://www.sidhe.org/~dan/…
Tommy
Nie rozumiem, czy początkowa foofunkcja wywołania ogona nie jest zoptymalizowana? Wywołuje funkcję tylko jako ostatni krok i po prostu zwraca tę wartość, prawda?
SexyBeast,
1
@TryinHard może nie to, co miałeś na myśli, ale zaktualizowałem go, aby przedstawić sedno tego. Przepraszamy, nie zamierzam powtarzać całego artykułu!
btiernay
2
Dziękujemy, jest to prostsze i bardziej zrozumiałe niż najczęściej wybierany przykład schematu (nie wspominając, że Schemat nie jest powszechnym językiem, który rozumie większość programistów)
Sevin7,
2
Jako osoba, która rzadko nurkuje w językach funkcjonalnych, przyjemnie jest zobaczyć wyjaśnienie w „moim dialekcie”. Praktyczni programiści mają (zrozumiałą) tendencję do ewangelizacji w wybranym przez siebie języku, ale przychodząc ze świata imperatywnego, o wiele łatwiej jest mi owinąć głowę wokół takiej odpowiedzi.
James Beninger,
15

Zauważ przede wszystkim, że nie wszystkie języki to obsługują.

TCO dotyczy specjalnego przypadku rekurencji. Istotą tego jest to, że jeśli ostatnią rzeczą, którą robisz w funkcji, jest wywołanie samego siebie (np. Wywoływanie się z pozycji „ogona”), kompilator może to zoptymalizować, aby działał jak iteracja zamiast standardowej rekurencji.

Widzisz, zwykle podczas rekurencji środowisko wykonawcze musi śledzić wszystkie rekurencyjne połączenia, aby po powrocie można było wznowić poprzednie połączenie i tak dalej. (Spróbuj ręcznie zapisać wynik wywołania rekurencyjnego, aby uzyskać wizualny obraz tego, jak to działa.) Śledzenie wszystkich wywołań zajmuje miejsce, co staje się znaczące, gdy funkcja wywołuje samą siebie. Ale dzięki TCO można po prostu powiedzieć „wróć do początku, tylko tym razem zmień wartości parametrów na nowe”. Może to zrobić, ponieważ nic po wywołaniu rekurencyjnym nie odnosi się do tych wartości.

J Cooper
źródło
3
Wywołania ogona mogą mieć również zastosowanie do funkcji nierekurencyjnych. Każda funkcja, której ostatnim obliczeniem przed zwróceniem jest wywołanie innej funkcji, można użyć wywołania ogonowego.
Brian
Niekoniecznie prawdziwe w zależności od języka - 64-bitowy kompilator C # może wstawiać kody ogona, podczas gdy wersja 32-bitowa nie; i wersja kompilacji F # będzie, ale debugowanie F # domyślnie nie.
Steve Gilham,
3
„TCO dotyczy specjalnego przypadku rekurencji”. Obawiam się, że to całkowicie źle. Wzywania ogona dotyczą każdego połączenia w pozycji ogona. Często dyskutowane w kontekście rekurencji, ale tak naprawdę nie ma nic wspólnego z rekurencją.
Jon Harrop,
@Brian, spójrz na link @btiernay podany powyżej. Czy początkowe foowywołanie metody nie jest zoptymalizowane?
SexyBeast,
13

Przykład minimalnego działania GCC z analizą dezasemblacji x86

Zobaczmy, jak GCC może automatycznie wykonać dla nas optymalizację wywołania ogona, patrząc na wygenerowany zespół.

Będzie to służyć jako niezwykle konkretny przykład tego, co wspomniano w innych odpowiedziach, takich jak https://stackoverflow.com/a/9814654/895245, że optymalizacja może przekształcić rekurencyjne wywołania funkcji w pętlę.

To z kolei oszczędza pamięć i poprawia wydajność, ponieważ dostęp do pamięci jest często główną rzeczą, która powoduje, że programy są obecnie wolne .

Jako dane wejściowe dajemy GCC niezoptymalizowany czynnikowy oparty na stosie:

tail_call.c

#include <stdio.h>
#include <stdlib.h>

unsigned factorial(unsigned n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(int argc, char **argv) {
    int input;
    if (argc > 1) {
        input = strtoul(argv[1], NULL, 0);
    } else {
        input = 5;
    }
    printf("%u\n", factorial(input));
    return EXIT_SUCCESS;
}

GitHub w górę .

Kompiluj i demontuj:

gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
  -o tail_call.out tail_call.c
objdump -d tail_call.out

gdzie -foptimize-sibling-callsjest nazwa uogólnienia połączeń ogonowych według man gcc:

   -foptimize-sibling-calls
       Optimize sibling and tail recursive calls.

       Enabled at levels -O2, -O3, -Os.

jak wspomniano w: Jak sprawdzić, czy gcc przeprowadza optymalizację rekurencji ogona?

Wybieram, -O1ponieważ:

  • optymalizacja nie jest wykonywana -O0. Podejrzewam, że dzieje się tak, ponieważ brakuje wymaganych pośrednich transformacji.
  • -O3 produkuje bezbożny, efektywny kod, który nie byłby zbyt pouczający, chociaż jest również zoptymalizowany dla ogona.

Demontaż za pomocą -fno-optimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       89 f8                   mov    %edi,%eax
    1147:       83 ff 01                cmp    $0x1,%edi
    114a:       74 10                   je     115c <factorial+0x17>
    114c:       53                      push   %rbx
    114d:       89 fb                   mov    %edi,%ebx
    114f:       8d 7f ff                lea    -0x1(%rdi),%edi
    1152:       e8 ee ff ff ff          callq  1145 <factorial>
    1157:       0f af c3                imul   %ebx,%eax
    115a:       5b                      pop    %rbx
    115b:       c3                      retq
    115c:       c3                      retq

Z -foptimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       b8 01 00 00 00          mov    $0x1,%eax
    114a:       83 ff 01                cmp    $0x1,%edi
    114d:       74 0e                   je     115d <factorial+0x18>
    114f:       8d 57 ff                lea    -0x1(%rdi),%edx
    1152:       0f af c7                imul   %edi,%eax
    1155:       89 d7                   mov    %edx,%edi
    1157:       83 fa 01                cmp    $0x1,%edx
    115a:       75 f3                   jne    114f <factorial+0xa>
    115c:       c3                      retq
    115d:       89 f8                   mov    %edi,%eax
    115f:       c3                      retq

Kluczowa różnica między nimi polega na tym, że:

  • te -fno-optimize-sibling-callszastosowania callq, które jest typowe dla zoptymalizowanej wywołanie funkcji.

    Ta instrukcja wypycha adres zwrotny na stos, zwiększając go.

    Co więcej, ta wersja również działa push %rbx, co przesuwa %rbxsię na stos .

    GCC robi to, ponieważ przechowuje edi, który jest pierwszym argumentem funkcji ( n) ebx, a następnie wywołuje factorial.

    GCC musi to zrobić, ponieważ przygotowuje się do kolejnego połączenia z factorial, które użyje nowego edi == n-1.

    Wybiera, ebxponieważ ten rejestr jest zachowywany przez callee : Jakie rejestry są zachowywane przez wywołanie funkcji linux x86-64, aby wywołanie podrzędne factorialnie zmieniło go i nie straciło n.

  • -foptimize-sibling-callsnie korzysta z żadnych instrukcji, które popychają do stosu: to tylko robi gotoskoki wewnątrz factorialz instrukcjami jei jne.

    Dlatego ta wersja jest odpowiednikiem pętli while, bez żadnych wywołań funkcji. Wykorzystanie stosu jest stałe.

Testowane w Ubuntu 18.10, GCC 8.2.

Ciro Santilli
źródło
6

Popatrz tutaj:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

Jak zapewne wiesz, wywołania funkcji rekurencyjnych mogą siać spustoszenie na stosie; szybko brakuje miejsca na stosie. Optymalizacja wywołania ogona to sposób, w jaki można utworzyć algorytm stylu rekurencyjnego, który wykorzystuje stałą przestrzeń stosu, dlatego nie rośnie i rośnie, a pojawiają się błędy stosu.

BobbyShaftoe
źródło
3
  1. Powinniśmy upewnić się, że w samej funkcji nie ma żadnych instrukcji goto. Należy zachować ostrożność, ponieważ wywołanie funkcji jest ostatnią rzeczą w funkcji callee.

  2. Rekurencje na dużą skalę mogą to wykorzystać do optymalizacji, ale w małej skali, narzut instrukcji do wywołania funkcji wywołanie ogona zmniejsza rzeczywisty cel.

  3. TCO może spowodować, że funkcja będzie działać wiecznie:

    void eternity()
    {
        eternity();
    }
    
grill kanapka
źródło
3 nie został jeszcze zoptymalizowany. Jest to niezoptymalizowana reprezentacja, którą kompilator przekształca w iteracyjny kod, który używa stałej przestrzeni stosu zamiast kodu rekurencyjnego. TCO nie jest przyczyną używania niewłaściwego schematu rekurencji dla struktury danych.
nomen
„TCO nie jest przyczyną korzystania ze złego schematu rekurencji dla struktury danych”. Proszę wyjaśnić, w jaki sposób ma to znaczenie w danym przypadku. Powyższy przykład wskazuje tylko przykład ramek przydzielanych na stosie wywołań z TCO i bez niego.
grillSandwich
Wybrano użycie nieuzasadnionej rekurencji do traverse (). To nie miało nic wspólnego z TCO. wieczność jest pozycją przywołania ogona, ale pozycja przywołania ogona nie jest konieczna: void eternity () {eternity (); wyjście(); }
nomen
Skoro już jesteśmy przy tym, czym jest „rekurencja na dużą skalę”? Dlaczego powinniśmy unikać goto w funkcji? Nie jest to ani konieczne, ani wystarczające, aby umożliwić TCO. A jaka instrukcja narzuta? Chodzi o to, że TCO zastępuje wywołanie funkcji w pozycji ogona goto.
nomen.
TCO polega na optymalizacji miejsca używanego na stosie połączeń. Przez rekurencję na dużą skalę mam na myśli rozmiar ramki. Za każdym razem, gdy nastąpi rekurencja, gdybym musiał przydzielić ogromną ramkę na stosie wywołań powyżej funkcji odbierającej, TCO byłby bardziej pomocny i pozwoliłby mi na więcej poziomów rekurencji. Ale w przypadku, gdy mój rozmiar ramki jest mniejszy, mogę obejść się bez TCO i nadal dobrze uruchamiać mój program (nie mówię tutaj o nieskończonej rekurencji). Jeśli masz goto w funkcji, wywołanie „ogon” nie jest tak naprawdę wywołaniem ogona, a całkowity koszt posiadania nie ma zastosowania.
grill Sandwich
3

Podejście do funkcji rekurencyjnej ma problem. Tworzy stos wywołań o rozmiarze O (n), co czyni nasz całkowity koszt pamięci O (n). To sprawia, że ​​jest podatny na błąd przepełnienia stosu, gdy stos wywołań staje się zbyt duży i zabraknie miejsca.

Schemat optymalizacji ogona (TCO). Gdzie może zoptymalizować funkcje rekurencyjne, aby uniknąć tworzenia wysokiego stosu wywołań, a tym samym oszczędza koszt pamięci.

Istnieje wiele języków, które wykonują TCO (JavaScript, Ruby i kilka C), podczas gdy Python i Java nie robią TCO.

Język JavaScript potwierdził użycie :) http://2ality.com/2015/06/tail-call-optimization.html

Rupesh Kumar Tiwari
źródło
0

W języku funkcjonalnym optymalizacja wywołania ogonowego jest tak, jakby wywołanie funkcji mogło zwrócić jako wynik częściowo wyrażone wyrażenie, które następnie zostałoby ocenione przez wywołującego.

f x = g x

f 6 zmniejsza się do g 6. Jeśli więc implementacja może zwrócić wynik g 6, a następnie wywołać to wyrażenie, zapisuje ramkę stosu.

Również

f x = if c x then g x else h x.

Zmniejsza do f 6 do g 6 lub h 6. Więc jeśli implementacja oceni c 6 i stwierdzi, że jest to prawda, może zmniejszyć,

if true then g x else h x ---> g x

f x ---> h x

Prosty interpreter optymalizacji połączeń innych niż ogon może wyglądać tak:

class simple_expresion
{
    ...
public:
    virtual ximple_value *DoEvaluate() const = 0;
};

class simple_value
{
    ...
};

class simple_function : public simple_expresion
{
    ...
private:
    simple_expresion *m_Function;
    simple_expresion *m_Parameter;

public:
    virtual simple_value *DoEvaluate() const
    {
        vector<simple_expresion *> parameterList;
        parameterList->push_back(m_Parameter);
        return m_Function->Call(parameterList);
    }
};

class simple_if : public simple_function
{
private:
    simple_expresion *m_Condition;
    simple_expresion *m_Positive;
    simple_expresion *m_Negative;

public:
    simple_value *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive.DoEvaluate();
        }
        else
        {
            return m_Negative.DoEvaluate();
        }
    }
}

Interpretator optymalizacji połączeń końcowych może wyglądać tak:

class tco_expresion
{
    ...
public:
    virtual tco_expresion *DoEvaluate() const = 0;
    virtual bool IsValue()
    {
        return false;
    }
};

class tco_value
{
    ...
public:
    virtual bool IsValue()
    {
        return true;
    }
};

class tco_function : public tco_expresion
{
    ...
private:
    tco_expresion *m_Function;
    tco_expresion *m_Parameter;

public:
    virtual tco_expression *DoEvaluate() const
    {
        vector< tco_expression *> parameterList;
        tco_expression *function = const_cast<SNI_Function *>(this);
        while (!function->IsValue())
        {
            function = function->DoCall(parameterList);
        }
        return function;
    }

    tco_expresion *DoCall(vector<tco_expresion *> &p_ParameterList)
    {
        p_ParameterList.push_back(m_Parameter);
        return m_Function;
    }
};

class tco_if : public tco_function
{
private:
    tco_expresion *m_Condition;
    tco_expresion *m_Positive;
    tco_expresion *m_Negative;

    tco_expresion *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive;
        }
        else
        {
            return m_Negative;
        }
    }
}
Peter Driscoll
źródło