evaluatorの再帰実装→CPS化→Continuationのde-functionalize→ループ化 - ラシウラ
プログラミング言語のインタプリタを実装するとき、構文木にあわせて再帰で書くほうが基本的に楽だ。しかし、多くの実装で再帰呼び出しは回数に制限があったり処理が遅かったりする。そこで、再帰呼び出し型のevalをループで記述する動機ができる。ただ、いきなりループで書こうとすると、インタプリタコードがわけわからなくなるし、バグも入りやすい。 そこでループを作る戦略として、 再帰呼び出しで実装 再帰呼び出しのContinuation Passing Style(CPS)化 CPS形式は末尾呼び出し形式でもある Continuationのde-functionalize、つまりContinuationの関数表現をデータオブジェクトであらわす クロージャを明示的なデータオブジェクトにする 末尾呼び出し関数のループ化 こうすれば、ループ形式インタプリタも素直に対応付けができる。クロージャも使わないので、Ja
Prolog Meta programming
Prologの入門文書に飽きた人に たけおか@AXE (竹岡尚三) Update: 2007/DEC/08 Update: 2007/AUG/18 初出: 2007/MAR/10 なんだか、Webの世界には、日本語では、純粋な論理型言語としてのProlog入門の 文書しかなく。 Prologは、実用言語(を目指しているはず)なので、ピュアな論理の話だけでは、 いけないと、思い… で、こういう雑文にて、恥をさらす。 1. 高階による後悔 実用プログラムが、あんまりに高階手続きを使っていると、それはそれで、困り そうなものなのだが… でも、やはり、高階な呼び出しは、必要だ。 aho(X,Z) :- A =.. [plus,1,X,Z], call(A),print(Z). という述語を定義し、 実行とその結果は次のとおり。 ?- aho(4,Z). 5 Z = 5 「call/1」 は、 引数
ひげぽん OSとか作っちゃうかMona- - 末尾再帰
最近一部で盛り上がっている「末尾再帰」について自分の理解を確認するのも兼ねて書いてみます。 （そもそも自分がふったのがきっかけっぽいので）。 上級者の方は間違い等に厳しくつっこんでもらえると助かります:-) 背景 自分が末尾再帰を知ったのは多分Schemeの勉強を始めた頃だったと思います。 例えばSICPという本では20ページあたりにこっそりと出てきます。 そのころの理解はかなり浅いもので「ふーん。」程度でした。 さて後日Schemeの処理系を実装することになりR5RSというSchemeの仕様書を読んだところ Scheme の実装は真正に末尾再帰的(properly tail-recursive) であることが要求されている。これは，たとえ繰返し計算が 構文的に再帰的手続きで記述されているときでも，定数空間 でその繰返し計算を実行することを可能にする とあり末尾再帰のことを詳しく知る必要性
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
