Apa yang dimaksud dengan optimasi panggilan ekor?

818

Sederhananya, apa itu optimasi tail-call?

Lebih khusus, potongan kode kecil apa yang bisa diterapkan, dan di mana tidak, dengan penjelasan mengapa?

majelbstoat
sumber
10
TCO mengubah panggilan fungsi di posisi ekor menjadi goto, lompatan.
Will Ness
8
Pertanyaan ini ditanyakan sepenuhnya 8 tahun sebelumnya;)
majelbstoat

Jawaban:

755

Optimasi tail-call adalah di mana Anda dapat menghindari alokasi bingkai stack baru untuk suatu fungsi karena fungsi panggilan hanya akan mengembalikan nilai yang didapatnya dari fungsi yang dipanggil. Penggunaan yang paling umum adalah tail-recursion, di mana fungsi rekursif yang ditulis untuk mengambil keuntungan dari optimasi tail-call dapat menggunakan ruang stack yang konstan.

Skema adalah salah satu dari sedikit bahasa pemrograman yang menjamin dalam spesifikasi bahwa setiap implementasi harus menyediakan optimasi ini (JavaScript juga, dimulai dengan ES6) , jadi berikut adalah dua contoh fungsi faktorial dalam Skema:

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

Fungsi pertama bukanlah rekursif ekor karena ketika panggilan rekursif dibuat, fungsi tersebut perlu melacak perkalian yang harus dilakukan dengan hasil setelah panggilan kembali. Dengan demikian, tumpukan terlihat sebagai berikut:

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

Sebaliknya, jejak tumpukan untuk faktorial rekursif ekor terlihat sebagai berikut:

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

Seperti yang Anda lihat, kita hanya perlu melacak jumlah data yang sama untuk setiap panggilan ke fakta karena kita hanya mengembalikan nilai yang kita dapatkan sampai ke atas. Ini berarti bahwa bahkan jika saya menelepon (fakta 1000000), saya hanya membutuhkan jumlah ruang yang sama dengan (fakta 3). Ini tidak terjadi dengan fakta non-ekor-rekursif, dan karena nilai-nilai besar seperti itu dapat menyebabkan stack overflow.

Kyle Cronin
sumber
99
Jika Anda ingin mempelajari lebih lanjut tentang ini, saya sarankan membaca bab pertama Struktur dan Interpretasi Program Komputer.
Kyle Cronin
3
Jawaban yang bagus, dijelaskan dengan sempurna.
Jonah
15
Tegasnya, pengoptimalan panggilan ekor tidak harus menggantikan bingkai tumpukan penelepon dengan callees, tetapi, lebih tepatnya, memastikan bahwa jumlah panggilan yang tidak terbatas dalam posisi ekor hanya memerlukan jumlah ruang terbatas. Lihat makalah Will Clinger "Rekursi ekor yang tepat dan efisiensi ruang": cesura17.net/~will/Professional/Research/Papers/tail.pdf
Jon Harrop
3
Apakah ini hanya cara untuk menulis fungsi rekursif dalam ruang konstan? Karena tidak bisakah Anda mencapai hasil yang sama menggunakan pendekatan berulang?
dclowd9901
5
@ dclowd9901, TCO memungkinkan Anda untuk lebih memilih gaya fungsional daripada loop berulang. Anda dapat memilih gaya imperatif. Banyak bahasa (Java, Python) tidak menyediakan TCO, maka Anda harus tahu bahwa panggilan fungsional membutuhkan memori ... dan gaya imperatif lebih disukai.
mcoolive
553

Mari kita berjalan melalui contoh sederhana: fungsi faktorial diimplementasikan dalam C.

Kita mulai dengan definisi rekursif yang jelas

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

Suatu fungsi berakhir dengan panggilan ekor jika operasi terakhir sebelum fungsi kembali adalah panggilan fungsi lain. Jika panggilan ini memanggil fungsi yang sama, itu adalah ekor-rekursif.

Meskipun fac()terlihat rekursif pada pandangan pertama, tidak seperti apa yang sebenarnya terjadi

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

yaitu operasi terakhir adalah perkalian dan bukan pemanggilan fungsi.

Namun, dimungkinkan untuk menulis ulang fac()menjadi ekor-rekursif dengan meneruskan nilai akumulasi ke rantai panggilan sebagai argumen tambahan dan hanya meneruskan hasil akhir lagi sebagai nilai pengembalian:

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);
}

Sekarang, mengapa ini berguna? Karena kita segera kembali setelah tail tail, kita dapat membuang stackframe sebelumnya sebelum memanggil fungsi pada posisi tail, atau, jika terjadi fungsi rekursif, gunakan kembali stackframe apa adanya.

Optimalisasi panggilan ekor mengubah kode rekursif kami menjadi

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

Ini bisa disimpulkan fac()dan kita sampai

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

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

yang setara dengan

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

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

    return acc;
}

Seperti yang dapat kita lihat di sini, pengoptimal yang cukup canggih dapat menggantikan rekursi ekor dengan iterasi, yang jauh lebih efisien karena Anda menghindari overhead panggilan fungsi dan hanya menggunakan jumlah ruang stack yang konstan.

Christoph
sumber
dapatkah Anda menjelaskan apa arti sebenarnya dari stackframe? Apakah ada perbedaan antara susunan panggilan dan susunan bingkai?
Shasak
10
@Kasahs: bingkai tumpukan adalah bagian dari tumpukan panggilan yang 'milik' fungsi tertentu (aktif); cf en.wikipedia.org/wiki/Call_stack#Structure
Christoph
1
Saya baru saja mengalami pencerahan yang cukup hebat setelah membaca posting ini setelah membaca 2ality.com/2015/06/tail-call-optimization.html
agm1984
198

TCO (Tail Call Optimization) adalah proses di mana kompiler pintar dapat melakukan panggilan ke suatu fungsi dan tidak mengambil ruang stack tambahan. Satu- satunya situasi di mana ini terjadi adalah jika instruksi terakhir dieksekusi dalam fungsi f adalah panggilan ke fungsi g (Catatan: g dapat menjadi f ). Kuncinya di sini adalah bahwa f tidak lagi membutuhkan ruang stack - ia hanya memanggil g dan kemudian mengembalikan apa pun yang akan kembali g . Dalam hal ini optimasi dapat dibuat bahwa g hanya berjalan dan mengembalikan nilai apa pun yang diperlukan untuk hal yang disebut f.

Optimasi ini dapat membuat panggilan rekursif mengambil ruang stack konstan, daripada meledak.

Contoh: fungsi faktorial ini tidak TCOptimasi:

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

Fungsi ini melakukan hal-hal selain memanggil fungsi lain dalam pernyataan pengembaliannya.

Fungsi di bawah ini TCOptimizable:

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)

Ini karena hal terakhir yang terjadi di salah satu fungsi ini adalah memanggil fungsi lain.

Claudiu
sumber
3
Keseluruhan 'fungsi g bisa f' agak membingungkan, tapi saya mengerti maksud Anda, dan contoh-contohnya benar-benar menjelaskan beberapa hal. Terima kasih banyak!
majelbstoat
10
Contoh luar biasa yang menggambarkan konsep. Hanya memperhitungkan bahwa bahasa yang Anda pilih harus menerapkan penghapusan panggilan ekor atau optimasi panggilan ekor. Dalam contoh, ditulis dengan Python, jika Anda memasukkan nilai 1000 Anda mendapatkan "RuntimeError: kedalaman rekursi maksimum terlampaui" karena implementasi Python default tidak mendukung Penghapusan Rekursi Ekor. Lihat posting dari Guido sendiri yang menjelaskan mengapa itu adalah: neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html .
rmcc
"Satu- satunya situasi" agak terlalu absolut; ada juga TRMC , setidaknya secara teori, yang akan mengoptimalkan (cons a (foo b))atau (+ c (bar d))pada posisi ekor dengan cara yang sama.
Will Ness
Saya menyukai pendekatan f dan g Anda lebih baik daripada jawaban yang diterima, mungkin karena saya orang matematika.
Nithin
Saya pikir maksud Anda TCOptimized. Mengatakan itu bukan kesimpulan TCO yang tidak dapat dioptimalkan (padahal sebenarnya bisa)
Jacques Mathieu
65

Mungkin deskripsi tingkat tinggi terbaik yang saya temukan untuk panggilan ekor, panggilan ekor rekursif dan optimasi panggilan ekor adalah posting blog

"Apa-apaan ini: Panggilan ekor"

oleh Dan Sugalski. Pada optimasi panggilan ekor ia menulis:

Pertimbangkan, sesaat, fungsi sederhana ini:

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

Jadi, apa yang bisa Anda, atau lebih tepatnya kompiler bahasa Anda, lakukan? Nah, yang bisa dilakukan adalah mengubah kode formulir return somefunc();menjadi urutan tingkat rendah pop stack frame; goto somefunc();. Dalam contoh kita, itu berarti sebelum kita memanggil bar, foomembersihkan dirinya dan kemudian, daripada memanggil barsebagai subrutin, kita melakukan gotooperasi tingkat rendah ke awal bar. FooSudah membersihkan dirinya sendiri dari tumpukan, jadi ketika barmulai sepertinya siapa pun yang dipanggil foobenar-benar memanggil bar, dan ketika barmengembalikan nilainya, ia mengembalikannya langsung ke siapa pun yang dipanggil foo, alih-alih mengembalikannya fooyang kemudian mengembalikannya ke pemanggilnya.

Dan pada rekursi ekor:

Ekor rekursi terjadi jika suatu fungsi, sebagai operasi terakhirnya, mengembalikan hasil pemanggilan itu sendiri . Rekursi ekor lebih mudah untuk ditangani karena daripada harus melompat ke awal beberapa fungsi acak di suatu tempat, Anda cukup melakukan kebalikan dari permulaan diri Anda, yang merupakan hal sederhana untuk dilakukan.

Jadi ini:

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

diam-diam berubah menjadi:

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

Apa yang saya sukai dari deskripsi ini adalah betapa ringkas dan mudahnya untuk memahami bagi mereka yang berasal dari latar belakang bahasa imperatif (C, C ++, Java)

btiernay
sumber
4
404 Kesalahan. Namun, itu masih tersedia di archive.org: web.archive.org/web/20111030134120/http://www.sidhe.org/~dan/…
Tommy
Saya tidak mengerti, bukankah foofungsi ekor panggilan awal dioptimalkan? Itu hanya memanggil fungsi sebagai langkah terakhir, dan itu hanya mengembalikan nilai itu, kan?
SexyBeast
1
@TryinHard mungkin bukan yang Anda pikirkan, tapi saya memperbaruinya untuk memberikan inti tentang apa itu. Maaf, tidak akan mengulangi seluruh artikel!
btiernay
2
Terima kasih, ini lebih sederhana dan lebih dapat dipahami daripada contoh skema yang paling banyak dipilih (belum lagi, Skema bukan bahasa umum yang dipahami sebagian besar pengembang)
Sevin7
2
Sebagai seseorang yang jarang menyelam ke dalam bahasa fungsional, sangat menyenangkan melihat penjelasan dalam "dialek saya". Ada kecenderungan (yang dapat dimengerti) bagi pemrogram fungsional untuk menginjili dalam bahasa pilihan mereka, tetapi datang dari dunia imperatif saya merasa jauh lebih mudah untuk membungkus kepala saya di sekitar jawaban seperti ini.
James Beninger
15

Perhatikan pertama-tama bahwa tidak semua bahasa mendukungnya.

TCO berlaku untuk kasus rekursi khusus. Inti dari itu adalah, jika hal terakhir yang Anda lakukan dalam suatu fungsi adalah memanggil dirinya sendiri (misalnya memanggil dirinya sendiri dari posisi "tail"), ini dapat dioptimalkan oleh kompiler untuk bertindak seperti iterasi alih-alih rekursi standar.

Anda lihat, biasanya selama rekursi, runtime perlu melacak semua panggilan rekursif, sehingga ketika seseorang kembali dapat melanjutkan pada panggilan sebelumnya dan seterusnya. (Coba tuliskan secara manual hasil dari panggilan rekursif untuk mendapatkan ide visual tentang bagaimana ini bekerja.) Melacak semua panggilan membutuhkan ruang, yang menjadi signifikan ketika fungsi panggilan itu sendiri banyak. Tetapi dengan TCO, itu hanya bisa mengatakan "kembali ke awal, hanya saja kali ini mengubah nilai parameter ke yang baru." Itu bisa melakukan itu karena tidak ada setelah panggilan rekursif merujuk pada nilai-nilai itu.

J Cooper
sumber
3
Buntut panggilan dapat berlaku untuk fungsi non-rekursif juga. Fungsi apa pun yang perhitungan terakhirnya sebelum kembali adalah panggilan ke fungsi lain dapat menggunakan panggilan ekor.
Brian
Tidak selalu benar berdasarkan bahasa - bahasa - kompiler C # 64 bit dapat menyisipkan opcodes ekor sedangkan versi 32-bit tidak akan; dan build rilis # F akan, tetapi debug # F tidak akan secara default.
Steve Gilham
3
"TCO berlaku untuk kasus rekursi khusus". Saya khawatir itu sepenuhnya salah. Panggilan ekor berlaku untuk semua panggilan dalam posisi ekor. Umumnya dibahas dalam konteks rekursi tetapi sebenarnya tidak ada yang secara spesifik berkaitan dengan rekursi.
Jon Harrop
@Brian, lihat tautan @btiernay yang disediakan di atas. Bukankah foometode awal panggilan ekor dioptimalkan?
SexyBeast
13

Contoh minimal GCC runnable dengan analisis pembongkaran x86

Mari kita lihat bagaimana GCC dapat secara otomatis melakukan optimasi panggilan ekor untuk kita dengan melihat rakitan yang dihasilkan.

Ini akan menjadi contoh yang sangat konkret dari apa yang disebutkan dalam jawaban lain seperti https://stackoverflow.com/a/9814654/895245 bahwa pengoptimalan dapat mengonversi panggilan fungsi rekursif ke loop.

Hal ini pada gilirannya menghemat memori dan meningkatkan kinerja, karena akses memori sering kali merupakan hal utama yang membuat program menjadi lambat saat ini .

Sebagai masukan, kami memberikan GCC faktorial berbasis naive stack yang tidak dioptimalkan:

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

Kompilasi dan bongkar:

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

di mana -foptimize-sibling-callsnama generalisasi panggilan ekor menurut man gcc:

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

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

seperti yang disebutkan di: Bagaimana cara saya memeriksa apakah gcc melakukan optimasi rekursi ekor?

Saya memilih -O1karena:

  • optimasi tidak dilakukan dengan -O0. Saya menduga bahwa ini karena diperlukan transformasi menengah yang hilang.
  • -O3 menghasilkan kode efisien yang tidak saleh yang tidak akan sangat mendidik, meskipun juga dioptimalkan untuk panggilan ekor.

Disassembly dengan -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

Dengan -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

Perbedaan utama antara keduanya adalah:

  • yang -fno-optimize-sibling-callsmenggunakan callq, yang merupakan khas non-dioptimalkan fungsi panggilan.

    Instruksi ini mendorong alamat kembali ke tumpukan, sehingga menambahnya.

    Selanjutnya, versi ini juga tidak push %rbx, yang mendorong %rbxke tumpukan .

    GCC melakukan ini karena ia menyimpan edi, yang merupakan argumen fungsi pertama ( n) ke ebx, kemudian panggilan factorial.

    GCC perlu melakukan ini karena sedang mempersiapkan panggilan lain factorial, yang akan menggunakan yang baru edi == n-1.

    Ia memilih ebxkarena register ini disimpan dengan sendirinya : Apa register disimpan melalui fungsi panggilan x86-64 linux sehingga subkunci untuk factorialtidak akan mengubahnya dan kehilangan n.

  • yang -foptimize-sibling-callstidak menggunakan instruksi yang mendorong ke stack: hanya melakukan gotomelompat dalam factorialdengan petunjuk jedan jne.

    Oleh karena itu, versi ini setara dengan loop sementara, tanpa panggilan fungsi apa pun. Penggunaan tumpukan konstan.

Diuji di Ubuntu 18.10, GCC 8.2.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
sumber
6

Lihat di sini:

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

Seperti yang mungkin Anda ketahui, panggilan fungsi rekursif dapat mendatangkan malapetaka pada tumpukan; mudah kehabisan ruang stack. Optimasi panggilan ekor adalah cara Anda membuat algoritma gaya rekursif yang menggunakan ruang stack konstan, oleh karena itu tidak tumbuh dan tumbuh dan Anda mendapatkan kesalahan stack.

BobbyShaftoe
sumber
3
  1. Kita harus memastikan bahwa tidak ada pernyataan kebagian fungsi itu sendiri .. dijaga dengan panggilan fungsi menjadi hal terakhir dalam fungsi callee.

  2. Rekursi skala besar dapat menggunakan ini untuk optimisasi, tetapi dalam skala kecil, overhead instruksi untuk membuat panggilan fungsi panggilan ekor mengurangi tujuan sebenarnya.

  3. TCO dapat menyebabkan fungsi yang berjalan selamanya:

    void eternity()
    {
        eternity();
    }
    
panggangan Sandwich
sumber
3 belum dioptimalkan. Itu adalah representasi yang tidak dioptimalkan yang diubah oleh kompiler menjadi kode berulang yang menggunakan ruang stack konstan alih-alih kode rekursif. TCO bukan penyebab menggunakan skema rekursi yang salah untuk struktur data.
nomen
"TCO bukan penyebab menggunakan skema rekursi yang salah untuk struktur data" Tolong jelaskan bagaimana ini relevan dengan kasus yang diberikan. Contoh di atas hanya menunjukkan contoh frame yang diberikan pada tumpukan panggilan dengan dan tanpa TCO.
grillSandwich
Anda memilih untuk menggunakan rekursi tak berdasar untuk melintasi (). Itu tidak ada hubungannya dengan TCO. keabadian adalah posisi panggilan-ekor, tetapi posisi panggilan-ekor tidak perlu: void eternity () {eternity (); keluar(); }
nomen
Sementara kita berada di sana, apa itu "rekursi skala besar"? Mengapa kita harus menghindari fungsi goto? Ini tidak perlu atau tidak cukup untuk memungkinkan TCO. Dan instruksi apa yang ada di atas kepala? Inti dari TCO adalah bahwa kompiler menggantikan pemanggilan fungsi pada posisi tail oleh goto.
nomen
TCO adalah tentang mengoptimalkan ruang yang digunakan pada tumpukan panggilan. Dengan rekursi skala besar, saya mengacu pada ukuran bingkai. Setiap kali rekursi terjadi, jika saya perlu membagikan frame besar pada panggilan stack di atas fungsi callee, TCO akan lebih membantu dan memungkinkan saya lebih banyak tingkat rekursi. Tetapi jika ukuran frame saya kurang, saya dapat melakukannya tanpa TCO dan masih menjalankan program saya dengan baik (saya tidak berbicara tentang rekursi tak terbatas di sini). Jika Anda dibiarkan menggunakan goto dalam fungsi tersebut, panggilan "tail" sebenarnya bukan tail call dan TCO tidak berlaku.
grillSandwich
3

Pendekatan fungsi rekursif memiliki masalah. Itu membangun tumpukan panggilan ukuran O (n), yang membuat total biaya memori kami O (n). Ini membuatnya rentan terhadap kesalahan stack overflow, di mana tumpukan panggilan terlalu besar dan kehabisan ruang.

Skema Tail Tail Optimization (TCO). Di mana ia dapat mengoptimalkan fungsi rekursif untuk menghindari penumpukan panggilan yang tinggi dan karenanya menghemat biaya memori.

Ada banyak bahasa yang melakukan TCO seperti (JavaScript, Ruby dan beberapa C) sedangkan Python dan Java tidak melakukan TCO.

Bahasa JavaScript telah dikonfirmasi menggunakan :) http://2ality.com/2015/06/tail-call-optimization.html

Rupesh Kumar Tiwari
sumber
0

Dalam bahasa fungsional, optimisasi panggilan ekor adalah seolah-olah panggilan fungsi dapat mengembalikan ekspresi yang dievaluasi sebagian sebagai hasilnya, yang kemudian akan dievaluasi oleh pemanggil.

f x = g x

f 6 berkurang menjadi g 6. Jadi jika implementasinya dapat mengembalikan g 6 sebagai hasilnya, dan kemudian memanggil ekspresi itu akan menghemat bingkai tumpukan.

Juga

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

Mengurangi ke f 6 ke g 6 atau h 6. Jadi jika implementasi mengevaluasi c 6 dan menemukan itu benar maka itu dapat mengurangi,

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

f x ---> h x

Penerjemah optimasi panggilan non-ekor sederhana mungkin terlihat seperti ini,

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();
        }
    }
}

Juru bahasa optimasi panggilan ekor mungkin terlihat seperti ini,

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
sumber