末尾再帰に絶望した！ - lethevert is a programmer

Haskellはデフォルトで遅延評価ですから、実装に関することは全部後で書くことになっているのですよ。

- - -

普通（って何が普通か知りませんが、私が普通だと思っている普通）は、末尾再帰の最適化というのは、次のような疑似アセンブリが

FUNC_A:
    いろいろ処理
    CALL FUNC_B
    RET

というところを、CALLのあとすぐにRETだからこれってJMPで置き換えられるよね、ということで

FUNC_A:
    いろいろ処理
    JMP FUNC_B

となることや、CPS（ちゃんと勉強してないので気分だけですが）で書いたときに

(define (func-a cont)
  いろいろ処理
  (func-b (lambda () (cont))))

というところを、func-bの引数のlambdaって要らないよね、ということで、

(define (func-a cont)
  いろいろ処理
  (func-b cont))

とすることだと思うのですがいかが？
でも、これって最適化なんていうほどのものでもなくて、

return func_b();

のように、return文が関数だったら、それをcallでなくてjmpにするというような、ほとんど構文的に決められるようなものなので、これを最適化というのはちょっと違和感がありますが、それはまあ、置いておくとしまして。

- - -

遅延評価というのは、計算する代わりにthunkという名前のオブジェクトを生成するみたいなイメージなので、それを可視化するためにJavaで書いてみると、

Thunk t = new IntThunk(0);
for (int i = 0; i < 10; ++i){
  t = new AddThunk(i, t);
}
return t.eval();

となりますが、これは当然メモリ消費は定数ではないですが、これは「ループ」ではないのでしょうか？

- - -

HaskellやCleanでthunk（どちらも、公式にはthunkという概念は存在しませんが）を評価すると、弱頭部正規形（WHNF）になるまで簡約が進むわけですが、
http://itpro.nikkeibp.co.jp/article/COLUMN/20070305/263828/?ST=ittrend&P=2
当然ながら、末尾再帰形になっている式はWHNFではないので、即座に次の関数が呼ばれます。なので、ここでわざわざthunkを作る必然性はないので、特別な事情がなければjmp相当のコードを出力しているはずです。
ついでに言うと、Cleanはれっきとしたスタックマシンなので、ABCコードという中間言語にはjsrとかrtnとかjmpとかという命令が存在して、戻り番地をスタックに積んでcall（ABCコードではjsr）で次の関数のアドレスに移動するという概念は当然持っています。これもeagerとかlazyとか関係ない話です。