Trampolined Style (Steven E. Ganz et al. International Conference on Functional Programming, 1999)をざっと読んだ。ICFP…。 Trampolined Style(カタカナだとトランポリンスタイルでいいのかな?ああ、なんだか形態素解析が難しそう…)というのは、関数の書く際のスタイルの一種だ。通常、関数を呼び出す時にはなんらかの値が返ってくる事を我々は期待する(事が多い)が、Trampolined Styleで書かれた関数(以下、めんどくさいのでTrampolined Functionとでも書こう)は、最後まで計算を行わず、ちょっと計算を進めて、残りの計算を行うための関数を返す。その関数を実行すると、またその続きを計算するための関数が返ってきて…という事が繰り返され、最後に計算が完了し、値が返っ
継続とは何かが分かったので、継続渡し形式とは何かについて調べてみた。 http://karetta.jp/book-node/kahua-seminar2/000511 を読むと、CPS に call/cc は必要無い事が分かった。がっくり。と言う事で、このページの例を Haskell と Squeak に写経しながら勉強。 -- 階乗の Haskell 再帰版 fact 0 = 1 fact n = n * fact (n - 1) -- CPS 版で書くとこうなる。(fact_cps 10 id => 3628800) fact_cps 0 cont = cont 1 fact_cps n cont = fact_cps (n - 1) (\a -> cont (n * a)) Scheme より滅茶苦茶分かりやすいのはパターンマッチの威力か。ちなみに Squeak Smalltalk
はてなリングの SICPで学びましょう というのに参加したので、 SICP に関係しそうなことを書いてみます。 SICP の第 1 章で、 再帰的プロセスの手続きを反復的プロセスに書き換えるという問題が出て来ますが、 これは慣れると自然に出来るようになります。 そこで出てくるのが末尾再帰というテクニックです。 しかし、 場合によっては末尾再帰にするのがちょっと難しい場合があります。 こういう時のとっておきの方法として、 継続渡しスタイルというのを紹介します。 簡単な書き換え 数値からなるリストを受け取って、 その要素の和を返す sum という関数を考えます。 まず、 普通に再帰を使って書くとこんな風になると思います。 (define (sum l) (if (null? l) 0 (+ (car l) (sum (cdr l))))) これを反復的プロセスの関数 sum-iter に書き換
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く