Was sind einige gute Möglichkeiten zur Implementierung der Tail-Call-Eliminierung?

Question 1

Ich habe einen kleinen Scheme-Interpreter in einer unheiligen Mischung aus C/C++ geschrieben, aber ich muss ihn noch implementieren richtige Schwanzrufe.

Der Klassiker ist mir bekannt Cheney über den MTA-Algorithmus, aber gibt es andere nette Möglichkeiten, dies zu implementieren? Ich weiß, dass ich den Scheme-Stack auf den Haufen legen könnte, aber das wäre immer noch keine richtige Eliminierung, da der Standard besagt, dass man eine unbegrenzte Anzahl aktiver Tail-Aufrufe unterstützen sollte.

Ich habe auch mit longjmps herumgespielt, aber bisher denke ich, dass es nur für nicht gegenseitige gut funktionieren wird rekursiv Schwanz ruft.

Wie implementieren die wichtigsten C-basierten Schemata die richtige Schwanzrekursion?

Question 2

Einfacher als das Schreiben eines Compilers und einer VM ist das Registrieren und Trampolinspringen Ihres Interpreters. Da Sie einen Interpreter und keinen Compiler haben (nehme ich an), brauchen Sie nur ein paar unkomplizierte Transformationen, um Tail-Aufrufe richtig zu unterstützen.

Sie müssen zuerst alles im Continuation-Passing-Stil schreiben, was in C/C++ vielleicht seltsam ist, darüber nachzudenken und es zu tun. Dan Friedmans KlammerC Tutorial führt Sie durch die Umwandlung eines rekursiven Programms auf hoher Ebene in eine Form, die maschinell in C übersetzt werden kann.

Am Ende implementieren Sie im Wesentlichen eine einfache VM, bei der Sie anstelle von regulären Funktionsaufrufen zum Ausführen von eval, applyProc usw. Argumente übergeben, indem Sie globale Variablen festlegen und dann Folgendes tun: goto zum nächsten Argument (oder verwenden Sie eine Schleife der obersten Ebene und einen Programmzähler) …

return applyProc(rator, rand)

wird

reg_rator = rator
reg_rand = rand
reg_pc = applyProc
return

Das heißt, alle Ihre Funktionen, die sich normalerweise gegenseitig rekursiv aufrufen, werden auf eine Pseudo-Assembly reduziert, in der sie nur Codeblöcke sind, die sich nicht wiederholen. Eine Schleife der obersten Ebene steuert das Programm:

for(;;) {
  switch(reg_pc) {
    case EVAL:
      eval();
      break;
    case APPLY_PROC:
      applyProc();
      break;
    ...
  }
}

Bearbeiten: Ich habe den gleichen Prozess für meinen in JavaScript geschriebenen Hobby-Scheme-Interpreter durchlaufen. Ich habe viele anonyme Verfahren genutzt, aber vielleicht hilft es als konkrete Referenz. Ansehen Der Commit-Verlauf von FoxScheme ab 13.03.2011 (30707a0432563ce1632a) bis zum 15.03.2011 (5dd3b521dac582507086).

Bearbeiten^2: Die Non-Tail-Rekursion verbraucht weiterhin Speicher, auch wenn sie sich nicht im Stack befindet.

Question 3

Ohne zu wissen, was Sie haben, würde ich sagen, der einfachste (und aufschlussreichste) Weg, dies zu tun, besteht darin, den Schema-Compiler und die VM aus Dybvigs “Three Implementation Models for Scheme” zu implementieren.
Ich habe es hier in Javascript gemacht (eine Kopie von Dybvigs PDF ist auch da): https://github.com/z5h/zb-lisp

Überprüfen Sie src/compiler.js: compileCons und die Implementierung der “op codes” in src/vm.js

Question 4

Wer sich für Umsetzungstechniken von Interpreten interessiert, kommt um das Buch „LiSP – Lisp in kleinen Stücken“ von Christian Queinnec nicht herum. Es erklärt alle Aspekte der Implementierung eines Scheme-Systems sehr gründlich mit vollständigem Code. Es ist ein wunderbares Buch.

Aber vergessen Sie nicht, sich die Artikel auf ReadScheme.org anzusehen.

Die Sektion

Compiler-Technologie/Implementierungstechniken und Optimierung
http://library.readscheme.org/page8.html

hat einige Artikel zur Tail-Call-Optimierung.

Unter anderem finden Sie einen Link zu Dybvigs Diplomarbeit (ein Klassiker), die sehr gut geschrieben ist. Es erklärt und motiviert alles sehr anschaulich.