2006-08-30 [長年日記]
λ. Re: Haskellは再帰をどうやってやっているのだろう
流石にもう誰かが適当な答えを書いているような気がするけど……ちょっと探した限りでは見当たらなかったので、答えてみる。
Schemeのような言語ではset!を使ってletrecを拡張シンタックスとして定義するのが自然だけれど、必ずそうしなくてはいけないわけではない。例えば、letrecをプリミティブにしてしまっても何の問題もない。Haskellのletやwhereはletrecに相当するプリミティブな機能なので、set!に相当する「不純な」ものが無くても、ローカル関数の再帰呼び出しは実現できる。
もちろん、Haskellのletも、処理系内部ではメモリの確保やデータの書き込みを行っている。というか、これに限らず処理系内部ではメモリの確保や書き換えは山のように起こっている。純粋関数型言語といっても、現実のマシン上で動く以上は当たり前だけど。
あれ？letrecってset!なんか必要でしたっけ？<br>Schemeでも別に書き換えは行ってないような。<br><br>ref) http://srfi.schemers.org/srfi-71/letvalues-r5rs.scm
R5RSに載っているもの(そのファイルのr5rs-letrec)をみると、使っているように見えます。
見落としてました。<br>本当だ。<br>そうか、束縛の順序関係なしに参照できるようにする必要があるからで、<br>Haskellはその辺が元々lazyになってるから束縛を差し替える必要がないのですね。