C++ で SICP
計算機プログラムの構造と解釈 の問題を、Schemeで一問一問解いてゆくのが流行りな2006年でした（師走気分）。このSICPをHaskellやCleanで解いている方はいますが、意外にもC++で解いている人が見当たらないので（注: あたりまえ）、C++のテンプレートはさっぱりよくわからんなぁと思いつつ適当にやってみます。ネタです。
[ネタ1] exercise 1.45, 1.46
まずは、問題1.45-1.46を。これらは1章の最終問題で、1章で学んだ手続き抽象のテクニック全てを使う感じがして楽しいです。xのn乗根を反復改良法で求める関数 nth-root を作るという設問です。
まずはSchemeで解く
私の拙いスキーム力を用いて書いてみるとこんな感じ*1？
(define (compose f g)
(lambda (x) (f (g x))))
(define (repeated f n)
(define (iter result i)
(if (= i n)
result
(iter (compose f result) (+ i 1))))
(iter f 1))
(define (average a b)
(/ (+ a b) 2))
(define (average-damp f)
(lambda (x) (average x (f x))))
(define (iterative-improve test-enough improve)
(define (try guess)
(let ((next (improve guess)))
(if (test-enough guess next)
next
(try next))))
(lambda (x) (try x)))
(define (fixed-point f first-guess)
(define (enough? a b)
(< (abs (- a b)) 0.000001))
((iterative-improve enough? (lambda (x) (f x))) first-guess))
(define (nth-root n x)
(define (damp-count m)
(if (< m 2)
0
(+ 1 (damp-count (/ m 2)))))
(define (nth-fold-average-damp l)
(repeated average-damp l))
(fixed-point ((nth-fold-average-damp (damp-count n))
(lambda (y) (/ x (expt y (- n 1)))))
1.0))
;; test
(nth-root 10 (* 3 3 3 3 3 3 3 3 3 3))実行してみます。3の10乗の10乗根を求める処理です。
gosh> 2.9999998914035997
ふむ。多分、ちゃんと動いているのではないかと。
Haskellで書き直す
上記をいきなりC++で書き直すと頭が混乱しそうなので、まずはHaskellで書き直します。C++(というかBoost)で型をミスったら数百行のエラーがでますが、Haskellなら数行で済みますので。HaskellかわいいよHaskell。
C++で書き直すことを考え、わざと関数の型を手で全部書きました。トリッキーな記述も少なめにしてあります。格好つけて、
-- 1に2を10回足す main = print $ (iterate ((+2).) id !! 10) 1
とか書いても、C++にぱっと変換できないですからねぇ。。。
-- % ghc -fglasgow-exts -O -W hoge.hs
compose :: (b -> c) -> (a -> b) -> (a -> c)
compose f g = \x -> f $ g x -- f.g です
-- "forall a." は GHC extension。「repeatedのaとiterのaは同じ型」だとコンパイラに伝えている。
-- わざわざ手動で型を書く場合、これが必要になることがある..っぽい。
repeated :: forall a. (a -> a) -> Int -> (a -> a)
repeated f n = iter f 1
where
iter :: (a -> a) -> Int -> (a -> a)
iter result i
| i == n = result
| otherwise = iter (compose f result) $ i + 1
average :: (Fractional a) => a -> a -> a
average a b = (a + b) / 2
average_damp :: (Fractional a) => (a -> a) -> a -> a
average_damp f x = average x $ f x
iterate_improve :: forall a. (a -> a -> Bool) -> (a -> a) -> a -> a
iterate_improve test_enough improve = try
where
try :: a -> a
try guess
| test_enough guess next = next
| otherwise = try next
where
next :: a
next = improve guess
fixed_point :: forall a. (Fractional a, Ord a) => (a -> a) -> a -> a
fixed_point = iterate_improve close_enough
where
tolerance :: a
tolerance = 0.000001
close_enough :: a -> a -> Bool
close_enough x y = tolerance >= (abs $ x - y)
nth_root :: (Fractional a, Ord a) => Int -> Int -> a
nth_root n x = let f = nth_fold_average_damp (damp_count n) in
fixed_point (f (\y -> fromIntegral x / expt y (n - 1))) 1.0
where
damp_count :: Int -> Int
damp_count m
| m < 2 = 0
| otherwise = 1 + (damp_count $ m `quot` 2)
expt :: (Fractional a) => a -> Int -> a
expt _ 0 = 1.0
expt y n = y * expt y (n - 1)
nth_fold_average_damp :: (Fractional a) => Int -> (a -> a) -> (a -> a)
nth_fold_average_damp l = repeated average_damp l
-- test
main = print $ nth_root 3 27
C++で書く
さて、（ネタの）本題、C++への書き換えです。Haskellの関数をほぼ一対一にC++の関数にします。C++は関数型のプログラミング言語ですので簡単です。関数が関数を受け取ったり、関数が関数を上に戻したりする部分は、「関数オブジェクト」という便利だか便利じゃないんだかよくわからないものを使って実装します。1章では数値しか扱っていない（データ構造は2章）こともあり、C++の関数オブジェクト程度の道具でも比較的容易にHaskellのコードを模倣できそうです。
- C++のコードの脇に、Haskellのコードをコメントとしてつけました。澄んだ心で読めば同じものに見えます
- さすがにSTLだけで書くのは厳しいんで、boost::functionとboost::bindは使います。以下、一応の注目ポイント：
- compose関数： boost::bindをネストすると関数を合成できるよ！ ←この記事で唯一役に立ちそうな記述
- average_damp関数： boost::bindする関数（第一引数）を_1にしたいときは、boost::apply
() を使う。Rは_1の戻りの型。 - average_damp_c関数： std::bind1stをboost::bindしています。これはひどい。
- C++では関数の中に関数は書けないので、その部分はdetailという名前空間に出しました。その関係で、ところどころdetail内の関数の引数の数が増えてしまっています。なお、これではダサいので、下のほうで3章をやるときには改善します。
- 変数の更新はしていません。更新するためにはもっと数学を勉強しないと無理らしいのですよ。
#include <iostream>
#include <boost/bind.hpp>
#include <boost/bind/apply.hpp>
#include <boost/function.hpp>
#include <cmath> // abs<T>()
#include <functional>
// libstdc++ extensions
#include <ext/functional> // identity<T>()
#include <ext/numeric> // power<T, U, M>()
namespace sicp {
/*
-- Haskell
compose :: (b -> c) -> (a -> b) -> (a -> c)
compose f g = \x -> f $ g x
*/
template <typename Op1, typename _Op2, typename _Op3>
Op1 compose(_Op2 f, _Op3 g) {
return boost::bind(f, boost::bind(g, _1));
}
/*
-- Haskell
repeated :: forall a. (a -> a) -> Int -> (a -> a)
repeated f n = iter f 1
where
iter :: (a -> a) -> Int -> (a -> a)
iter result i
| i == n = result
| otherwise = iter (compose f result) $ i + 1
*/
namespace detail { // for repeated()
template <typename _Op1>
_Op1 repeated_iter(_Op1 f, _Op1 result, int n, int i) {
if (i == n)
return result;
else
return repeated_iter(f, compose<_Op1>(f, result), n, i + 1);
}
}
template <typename T,
typename _Op1 /* T -> T */ >
_Op1 repeated(_Op1 f, int n) {
return detail::repeated_iter<_Op1>(f, __gnu_cxx::identity<T>(), n, 0);
}
/*
-- Haskell
average :: (Fractional a) => a -> a -> a
average a b = (a + b) / 2
*/
template<typename T>
boost::function<T (T, T)> average() {
return boost::bind(std::divides<T>(), boost::bind(std::plus<T>(), _1, _2), 2);
}
/*
-- Haskell
average_damp :: (Fractional a) => (a -> a) -> a -> a
average_damp f x = average x $ f x
*/
template<typename T>
boost::function<T (boost::function<T (T)>, T)>
average_damp() {
return boost::bind(average<T>(),
_2, boost::bind(boost::apply<T>(), // <T> は、すぐ後の _1 の戻りの型
_1, _2));
}
// Haskellでは、(a -> a) -> a -> a と (a -> a) -> (a -> a) を区別する必要がないが、
// C++では区別しないといけない....たぶん。よって別関数を用意。
// しかも、前者から後者への変換が面倒。
template<typename T>
boost::function<boost::function<T (T)> (boost::function<T (T)>)>
average_damp_c() {
typedef boost::function<T (T)> T2T;
return boost::bind(std::bind1st<boost::function<T (T2T, T)>, T2T>,
/* ^type of average_damp<T>() ^type of placeholder */
average_damp<T>(), _1);
}
/*
-- Haskell
iterate_improve :: forall a. (a -> a -> Bool) -> (a -> a) -> a -> a
iterate_improve test_enough improve = try
where
try :: a -> a
try guess
| test_enough guess next = next
| otherwise = try next
where
next :: a
next = improve guess
*/
template <typename T,
typename _Op1, /* T -> T -> Bool */
typename _Op2> /* T -> T */
T iterate_improve(_Op1 test_enough, _Op2 improve, T guess) {
const T& next = improve(guess);
// try関数は省略。自身に再帰。
if (test_enough(guess, next))
return next;
else
return iterate_improve<T>(test_enough, improve, next);
}
/*
-- Haskell
fixed_point :: forall a. (Fractional a, Ord a) => (a -> a) -> a -> a
fixed_point = iterate_improve close_enough
where
tolerance :: a
tolerance = 0.000001
close_enough :: a -> a -> Bool
close_enough x y = tolerance >= (abs $ x - y)
*/
namespace detail { // for fixed_point()
template <typename T>
bool close_enough(T a, T b) {
static const T tolerance = 0.000001;
return (std::abs(a - b) <= tolerance);
}
}
template <typename T, typename _Op1>
T fixed_point(_Op1 f, T first_guess) {
return iterate_improve(boost::bind(detail::close_enough<T>, _1, _2), f, first_guess);
}
/*
-- Haskell
nth_root :: (Fractional a, Ord a) => Int -> Int -> a
nth_root n x = let f = nth_fold_average_damp (damp_count n) in
fixed_point (f (\y -> fromIntegral x / expt y (n - 1))) 1.0
where
damp_count :: Int -> Int
damp_count m
| m < 2 = 0
| otherwise = 1 + (damp_count $ m `quot` 2)
expt :: (Fractional a) => a -> Int -> a
expt _ 0 = 1.0
expt y n = y * expt y (n - 1)
nth_fold_average_damp :: (Fractional a) => Int -> (a -> a) -> (a -> a)
nth_fold_average_damp l = repeated average_damp l
*/
namespace detail { // for nth_root()
int damp_count(int m) {
return (m < 2 ? 0 : (1 + damp_count(m / 2)));
}
template <typename T>
boost::function<T (T, int)> expt() {
// 自作も容易だが、power関数というのが用意されているので、それを使って手抜き。
// static_castでライブラリ側のやや曖昧なオーバーロードを解決。
return boost::bind(static_cast<T (*)(T, int)>(__gnu_cxx::power), _1, _2);
}
template<typename T>
boost::function<boost::function<T (T)> (boost::function<T (T)>)>
nth_fold_average_damp(int n) {
return repeated<boost::function<T (T)> >(average_damp_c<T>(), n);
}
}
// これが、最終的に欲しかった関数 (xのn乗根を求める)
template <typename T>
T nth_root(int n, int x) {
typedef boost::function<T (T)> T2T;
boost::function<T2T (T2T)> f = detail::nth_fold_average_damp<T>(detail::damp_count(n));
T2T g = boost::bind(std::divides<T>(), x, boost::bind(detail::expt<T>(), _1, n - 1)); // y -> x/y^(n-1)
return fixed_point<T>(f(g), 1.0);
}
}うーん、これはひどい。boost::phoenixのv2やFC++あたりを使えば少しは綺麗になるのかどうなのか。なお、expt()は、boost::lambda::if_then_else_returnで書きたかった↓
namespace bl = boost::lambda;
return bl::if_then_else_return(/* if _2 == 0 */ bl::bind(std::equal_to<int>(), bl::_2, 0),
/* then */ bl::bind(__gnu_cxx::identity<T>(), 1),
/* else */ bl::bind(std::multiplies<T>(),
bl::_1,
bl::bind(expt<T>(), // ここがだめ
bl::_1,
bl::bind(std::minus<int>(), bl::_2, 1))));のですが、後に書いた問題1.37と同じ理由でやめました（私には無理っぽ）。
テスト
適当にmain関数を書いて、実行してみます。
int main() {
typedef double T;
// 1.0と2.0の平均を求める
boost::function<T (T, T)> f = sicp::average<double>();
std::cout << f(1.0,2.0) << std::endl; // OK
// f(x) = 2x なfを渡して、1.0とf(1.0)の平均を求める
boost::function<T (boost::function<T (T)>, T)> f2 = sicp::average_damp<T>();
std::cout << f2(boost::bind(std::multiplies<T>(), _1, 2), 1.0) << std::endl;
// 1.0とf(1.0)の平均を求める - その2
boost::function<boost::function<T (T)> (boost::function<T (T)>)> g = sicp::average_damp_c<T>();
std::cout << g(boost::bind(std::multiplies<T>(), _1, 2))(1.0) << std::endl;
// 平均緩和法で3の平方根を求める
boost::function<T (T)> f3 = boost::bind(std::divides<double>(), 3, _1); // y -> x / y
std::cout << sicp::fixed_point(boost::bind(f2, f3, _1), 1.0) << std::endl;
// 2.0の10乗を求める
boost::function<T (T, int)> f4 = sicp::detail::expt<T>();
std::cout << f4(2, 10) << std::endl;
// 平均緩和法で16の4乗根を求める
boost::function<boost::function<T (T)> (boost::function<T (T)>)> f5 = sicp::detail::nth_fold_average_damp<T>(sicp::detail::damp_count(4));
boost::function<T (T)> f6 = f5(boost::bind(std::divides<double>(), 16, boost::bind(sicp::detail::expt<T>(), _1, 3))); // y -> x / y^3
std::cout << sicp::fixed_point(boost::bind(f2, f6, _1), 1.0) << std::endl;
// test
std::cout << sicp::nth_root<T>(4, 16) << std::endl
<< sicp::nth_root<T>(10, 1024) << std::endl
<< sicp::nth_root<T>(2, 2) << std::endl
<< sicp::nth_root<T>(2, 3) << std::endl
<< sicp::nth_root<T>(5, 1234) << std::endl;
return 0;
}
コンパイルと実行
コンパイルして実行するとこんなかんじ。
% g++ -Wall -Wextra -O2 1.46_plus_1.45.cpp % ./a.out 1.5 1.5 1.5 1.73205 1024 2 2 2 1.41421 1.73205 4.15205
ちなみに、このnth_rootで平方根を求めてみたところ、libmのsqrt関数の約1/100倍速でした。速っ。GCCには-foptimize-sibling-callsというすばらしい最適化があることですし、こんなコードでもまったく問題あります。
小まとめ
forループ書いたら負けかなと思ってる
[ネタ2] exercise 3.1
次は、問題3.1です。Paul Grahamさんの技術野郎の復讐(Revenge of the Nerds)の付録の問題「accumulator generatorを作れ」とほぼ同じです。
私が言う言語の相対的な力を説明するために、次の問題を考えてみよう。アキュムレータを生成する関数、すなわち、数nを取り、「数iを取ってnをiだけ増加させ、その増加した値を返す関数」を返すような関数だ。 (「増加させる」に注意。ただ足すだけではない。アキュムレータ(累積器)だから累積させなければ)。
これをC++でやってみるのです。ハッカーと画家 コンピュータ時代の創造者たち にも載ってる問題です。この問題は、最初の例とは違って、C++でもまぁどうにか読める範囲で解けそうです。
以下、なぜか気分で、boostをまったく使っていない人向けの説明です。今更すぎる。。しかも、そういう人はたぶん私のblogなど読んでいない罠。いやむしろ誰も読んでいない罠。まぁなんでもいいか。
boost::functionとboost::bind
問題3.1の、他の言語での解答例を見ると*2、関数型言語的テクニックを使いまくっている例が多いです。さて、C++でどのように実装したもんでしょうか。まず、高階関数(関数を受け取る関数、または関数を上に戻す関数)を書くにはboost::functionを使えば良さそうです。たとえば、『「intを引数にとってintを戻す関数f」を引数に取って、「doubleを引数にとってdoubleを戻す関数」を戻す関数hoge』は、次のように書けます。
// "arg" のところには任意の変数名を書けます。何を書いても動作は同じです。省略も可。
boost::function<double (double arg)>
hoge(boost::function<int (int arg)> f) {
...
}また、C++では関数の中に関数を書くことはできないので、世間一般で言う(?)closureのように*3、「lexical に外側にある変数を参照あるいは更新できる」を直接実現するのは難しいというか、外側にある変数というといわゆるグローバル変数しかなかったりするわけですが、boost::bindを使うと似たようなことは出来ます。こんな感じですね*4。詳しくは"How the Boost Bind Library Can Improve Your C++ Programs"あたりを。
int add(int a, int b) { return a + b; } // closureもどきの元ネタ(?)にする予定の関数
boost::function<int (void)> bar(int x) {
return boost::bind(add, _1, x);
}蛇足ですが、STLが好きな人は、add関数を書かずに、予め用意されているstd::plus関数テンプレート(戻り値は関数オブジェクト)を使って、
boost::function<int (void)> bar(int x) {
return boost::bind(std::plus<int>(), _1, x);
}とか
boost::function<int (void)> bar(int x) {
return std::bind2nd(std::plus<int>(), x);
}でもOK、同じ出力が得られます。ただ注意が必要なのは、このケースでは、closureもどきに閉じ込めているのは変数x自身(?)ではなく、変数xのコピーだという点です。add関数が引数を値で受け取っているのでそこでコピーが行われますし、できあがった関数オブジェクトがコピーされるタイミング*5でも「変数xのコピー」のコピーが起きます。今回は、「closeされた変数を参照するだけ」かつ「変数がコピー可能」かつ「変数をコピーするコストが安い」ので、これでも問題ないわけです。
boost::functionとboost::bindとboost::shared_ptrでaccumulator generator
さて、Revenge of the Nerds の accumulator generator 問題です。なお、ここからは、C++で変数を更新するのは邪道だと考えている方には関係ない話です。この問題をSchemeやRubyで解くとこんな感じになります。先の回答サイトからのコピペです。私はLLワカリマセーン。
;; Scheme
(define (foo n)
(lambda (i) (set! n (+ n i)) n))
# Ruby
def foo (n)
lambda {|i| n += i } end「手続きを上(?)に戻し、かつその中にclose(?)されている変数を更新する」という処理になっていることがわかると思います。ですから、最初のboost::bindの例のように、closeしたはずの変数nがコピーされてしまうとおかしなことになります。ですから、次のようにboost::bindでローカル変数をfoo_closure_にコピーするだけでは(当然)うまくいきません。
// NG 1
template <typename T> T foo_closure_(T n, T i) {
return (*n += i);
}
template <typename T> boost::function<T (T arg1)> foo(T n) {
return boost::bind(foo_closure_<T>, n, _1);
}また、次のように関数オブジェクト内に変数の参照(やポインタ)を保持する方法もうまくいきません。なぜなら、関数fooを抜けた時点でスタック上に置かれた引数nは綺麗に消え去ってしまうからです。
// NG 2
template <typename T> T foo_closure_(T& n, T i) {
return (*n += i);
}
template <typename T> boost::function<T (T arg1)> foo(T n) {
return boost::bind(foo_closure_<T>, boost::ref(n), _1);
}えー、なぜSchemeなどで問題が起きないかというと、これらの言語では、一度生成されたオブジェクトはずっと生きていて（無限エクステント？）、誰も参照する人がいなくなったときに限って削除されるからですね。多分。C++でこれを模倣しようとすると、Boehm GCなどの飛び道具を使うか、さもなければ地道にオブジェクトの参照カウントを行うしかなさそうです。boostには、boost::shared_ptrという便利なものがあるので、それを使います。
// OK, Paul Graham の accumulator generator のC++実装
template <typename T> T foo_closure_(boost::shared_ptr<T> n, T i) {
return (*n += i);
}
template <typename T> boost::function<T (T arg1)> foo(T n) {
boost::shared_ptr<T> pn(new T(n));
return boost::bind(foo_closure_<T>, pn, _1);
}使ってみます。
int main() {
boost::function<int (int arg1)> f1 = foo(10);
std::cout << f1(5) << std::endl;
std::cout << f1(5) << std::endl;
std::cout << f1(5) << std::endl;
std::cout << f1(5) << std::endl;
boost::function<double (double arg1)> f2 = foo(1.5);
std::cout << f2(0.5) << std::endl;
std::cout << f2(0.5) << std::endl;
std::cout << f2(0.5) << std::endl;
std::cout << f2(0.5) << std::endl;
}予定通りにうごきます。次の通り。
% ./a.out 15 20 25 30 2 2.5 3 3.5
無問題。わーい。
boost::lambdaでクロージャもどき
一応出来たんですが、foo_closure関数を別に作成しているのはいまいちです。そこでlambda。boost::lambdaというライブラリを使うと、例えば
int add(int a, int b) { return a + b; }
boost::function<int (void)> bar(int x) {
return boost::bind(add, _1, x);
}を、add関数を作ることなしに、
boost::function<int (void)> bar(int x) {
return _1 + x;
}のように書けます。xは、関数オブジェクト内「コピー」され保持されます。「lexicalに外側にある変数xを参照」できています。closureっぽい！（ようなそうでもないような）。参照だけで、更新はできませんけどねー。これを応用しまして、accumulate generator を改良すると、
// NG
template <typename T> boost::function<T (T arg1)> foo(T n) {
boost::shared_ptr<T> pn(new T(n));
return (*pn += _1);
}となります.....と言いたい所なのですが、上記コード、コンパイルはできますが実行するとコケます。fooを抜けた瞬間にpnの指し先がdeleteされてしまうです。参照カウントがきちんと増加していません。(*pn) つまりint型の変数がlambdaライブラリに渡って、ライブラリ側ではint&で変数を掴まえている? (+= のときだけは?) ... ようです。謎。うーん。いまのところ、次のように書く方法しか見つけていません。
// OK, Paul Graham の accumulator generator の最終的なC++実装
template <typename T> boost::function<T (T arg1)> foo(T n) {
boost::shared_ptr<T> pn(new T(n));
return boost::lambda::bind(boost::function<T (typeof(pn), T)>(*_1 += _2), pn, _1);
}まぁ、実用上(?)これで問題ないというか、SICPの問題の答えにはちゃんとなっているのですが、見た目が複雑でちょっと嫌。C++の達人の方の突っ込み待ち。どなたかぜひ良い代案を。。。
ちょっと改造
「Rubyの呼び出し可能オブジェクトの比較(1)」の「普通のProc」のあたりのコードのように、pnを閉じこんでいるクロージャを複数作成して、下に渡したり、上に渡したりして楽しむこともできますね。
#include <iostream>
#include <boost/utility.hpp>
#include <boost/function.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/tuple/tuple.hpp>
using boost::lambda::_1;
using boost::lambda::_2;
template <typename R, typename T> R foo(T n) {
typedef boost::shared_ptr<T> P;
typedef boost::function<T (T)> F;
typedef boost::function<T (P, T)> F_;
// 最初は0を覚えておいて
P pn(new T());
F closure1 = boost::lambda::bind(F_(*_1 += _2), pn, _1);
F closure2 = boost::lambda::bind(F_(*_1 += _2), pn, _1);
F closure3 = closure2; // コピーしてみたり。
// 無意味に「下」でnにしてみる
bar(closure1, n);
// クロージャを3つまとめて「上」に戻す
return boost::make_tuple(closure1, closure2, closure3);
}
template <typename F, typename T> void bar(F f, T n) {
std::cout << f(n) << std::endl;
}
int main() {
typedef boost::function<int (int)> F;
boost::tuple<F, F, F> f = foo<typeof(f)>(10);
// 3つを並行に使ってみて、値の変化を見る
std::cout << f.get<0>()(5) << std::endl;
std::cout << f.get<1>()(5) << std::endl;
std::cout << f.get<2>()(5) << std::endl;
std::cout << f.get<2>()(5) << std::endl;
std::cout << f.get<1>()(5) << std::endl;
std::cout << f.get<0>()(5) << std::endl;
}
[ネタ3] exercise 3.4
次は問題3.4です。預金額を覚えているオブジェクトを戻す関数を、Schemeで作る問題ですね。上に戻したdispatch関数が、"deposit"とか"withdraw"なんていうメッセージを受け取って、それに応じたオシゴトをします。とりあえず私のヘボSchemeカを生かして実装:
(define (make-account balance password)
(define (withdraw amount)
(if (> balance amount)
(begin (set! balance (- balance amount))
balance)
(error "Insufficient funds")))
(define (deposit amount)
(set! balance (+ balance amount)) balance)
(define (call-the-cops)
(error "Thief!!"))
(let ((count 0)
(count-max 7))
(define (dispatch pw m)
(if (not (eq? pw password))
(begin (set! count (+ count 1))
(if (>= count count-max)
(call-the-cops))
(error "Incorrect password"))
(begin (set! count 0)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request -- MAKE-ACCOUNT" m))))))
dispatch))C++には、classというあまり知られていないキーワードがありまして、それを使って頑張れば、上のSchemeのコードを次のように書けなくもないのですが、
class account : boost::noncopyable {
public:
account(int balance, const std::string& password) : balance_(balance), password_(password) {}
int withdraw(const std::string& password, int amount) { if (...
int deposit(const std::string& password, int amount) { if (...
private:
int balance_;
std::string password_;
};もっと素直にschemeのコードを移植したものをつくろうよ、と。boost::lambdaで完全移植。Haskellでいったん書き直していないのはモナd(略)。
コード
#include <iostream>
#include <string>
#include <stdexcept>
#include <functional>
#include <boost/function.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/if.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/construct.hpp>
#include <boost/lambda/exceptions.hpp>
// 関数書いたら負け..という気がしないでもないが、
// 設問自体が「手続きを呼べ」なのでOKということにしておく。
template <typename T> T call_the_cops(T) {
std::cout << "通報しますた" << std::endl;
throw std::runtime_error("Incorrect password");
}
template <typename R, typename T>
R make_account(T balance, std::string password) {
using namespace boost::lambda;
typedef boost::function<T (T)> F; // withdraw(), deposit()
typedef boost::function<F (std::string, std::string)> F2; // dispatch()
typedef boost::shared_ptr<T> P;
typedef boost::shared_ptr<std::size_t> P2;
P pbalance(new T(balance)); // local-state-variable
P2 pcnt(new std::size_t()); // local-state-variable
// passwordも局所状態変数だが、immutableなのでshared_ptrにはしない
// (shared_ptrにすると、"*" の扱いでコードがややこしくなるんで)
#define ifter if_then_else_return /* 画面の幅の都合... */
/*
(define (withdraw amount)
(if (> balance amount)
(begin (set! balance (- balance amount))
balance)
(error "Insufficient funds")))
*/
typedef boost::function<T (P, T)> F_;
F closure_withdraw
= bind(F_(ifter(*_1 >= _2,
*_1 -= _2,
(throw_exception(std::runtime_error("Insufficient funds")), T() /*dummy*/ ))),
pbalance, _1);
/*
(define (deposit amount)
(set! balance (+ balance amount)) balance)
*/
F closure_deposit = bind(F_(*_1 += _2), pbalance, _1);
/*
(let ((count 0)
(count-max 7))
(define (dispatch pw m)
(if (not (eq? pw password))
(begin (set! count (+ count 1))
(if (>= count count-max)
(call-the-cops))
(error "Incorrect password"))
(begin (set! count 0)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request -- MAKE-ACCOUNT" m))))))
*/
static const std::size_t cnt_max = 7; // 通報閾値
typedef boost::function<F (std::string, std::string, P2)> F2_;
F2 closure_dispatch
= bind(F2_(ifter(_1 != password,
ifter(++(*_3) >= cnt_max,
::call_the_cops<T>,
(throw_exception(std::runtime_error("Incorrect password")), F() /*dummy*/ )),
(*_3 = 0, ifter(_2 == "withdraw",
closure_withdraw,
ifter(_2 == "deposit",
closure_deposit,
(throw_exception(bind(constructor<std::runtime_error>(),
bind(std::plus<std::string>(),
"Unknown request -- MAKE-ACCOUNT: ",
_2))),
F() /*dummy*/ )))))),
_1, _2, pcnt);
return closure_dispatch;
}
使ってみる
int main() {
typedef boost::function<boost::function<int (int)> (std::string, std::string)> F;
// 口座開設。第二引数がパスワード。
F dispatch
= make_account<F>(1000, "open sesame");
// 預けて、おろしてみる
std::cout << "balance: " << dispatch("open sesame", "deposit")(1000) << std::endl;
std::cout << "balance: " << dispatch("open sesame", "withdraw")(500) << std::endl;
// dispatchを適当にコピーしても無問題
F dispatch2 = dispatch;
std::cout << "balance: " << dispatch2("open sesame", "withdraw")(500) << std::endl;
// 暗証を間違えてみる
try {
std::cout << dispatch("bad_pass", "withdraw")(10) << std::endl;
} catch(std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
// 7回連続で間違えると通報される
for(int i = 0; i < 6; ++i) try {
dispatch("bad_pass", "withdraw")(100);
} catch(...) {}
// 預金額をこえておろしてみる
try {
std::cout << dispatch("open sesame", "withdraw")(1001) << std::endl;
} catch(std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
// dispatch()に渡すメッセージを間違えてみる
try {
std::cout << dispatch("open sesame", "give_me_1000000_dollars")(500) << std::endl;
} catch(std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
}
実行結果
% ./a.out balance: 2000 balance: 1500 balance: 1000 Incorrect password 通報しますた Insufficient funds Unknown request -- MAKE-ACCOUNT: give_me_1000000_dollars
うーん、美し...くない。
解説?
レキシカルに見えているものをclosure_ほげのbindの中でさらっと使って問題がない点、closure_ほげを適当にコピーしたり、closure_dispatchのbindの中で別のclosureをcloseしたり、closure_ほげを上に戻したりしてもGC..もといshared_ptrによる参照カウントのおかげでまったく問題ない点、クロージャもどきの間で局所状態変数を共有している点...などが一応の見どころです...たぶん。Valgrind様を信じるならメモリリークしていません。main関数のfor文のところでの微妙なオシャレは、ちょっとやってみたかっただけです。
よーしパパ、この調子で関数型言語C++にオブジェクト指向機能をどんどん実装しちゃうぞー（しません）。boost::lambdaは、placeholderが _3 までしか用意されていないので足りなくなりそうだし（そういう問題じゃない）。
小まとめ
classって書いたら負けかなと思ってる
[ネタ4] exercise 1.37 (CPS in C++)
1章にもどって、問題1.37をやります。2章が抜けてしまったな。。。この図のように、無限連分数のk番目のtermまでの和を求めろという問題です。Int -> a な関数、NとDは外から適当に与えます。一般的には、こちらの回答例にあるようにN1/D1側から再帰で足しこんでいくか、逆に、累積変数(状態変数?)を使ってNk/Dk側から反復的に足していくかになると思いますが、ここではネタ力向上のため、というかある方にネタっぽい方法を教えていただいたので、「N1/D1側から, 反復的プロセスで, 答えを求める」方法を採用します。Haskellだとこんな感じです。非常に面白い方法だと思いました。
cont_frac :: (Fractional a) => Int -> (Int -> a) -> (Int -> a) -> a
cont_frac k n d = g 0 id
where
g i c
| i == k = c $ n i / d i
| otherwise = g (i + 1) $ \x -> c $ n i / (d i + x)iを0からkまでまわしています。関数gの引数cが累積変数。でも、溜まるのは数値ではなくて計算です。Haskellerじゃない方に一応説明すると、
- a $ b c d は a ( b c d )
- \x -> は (lambda (x) (
です。DiとNiが常に1だと、この連分数は黄金比の逆数に近づいてゆくということなので、k=100くらいで確認します。
main = print $ 1 / cont_frac 100 (const 1) (const 1)
実行してみると、ちゃんと1.618..になりました。OK。C++で書き直します。
#include <ext/functional>
#include <boost/function.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/lambda.hpp>
typedef boost::function<double (int)> A;
namespace {
typedef boost::function<double (double)> B;
double g(A n, A d, int k, int i, B c) {
if (i == k) return c(n(i) / d(i));
return g(n, d, k,
i + 1,
boost::lambda::bind(c, n(i) / (d(i) + boost::lambda::_1)));
}
}
double cont_frac(A n, A d, int k) {
return g(n, d, k, 0, __gnu_cxx::identity<double>());
}
int main() {
std::printf("golden ratio: %lf\n",
1 / cont_frac(__gnu_cxx::constant1<double>(1.0),
__gnu_cxx::constant1<double>(1.0),
100));
}4つめということでいい加減力尽きてきたので、typename T とすべきところをdoubleに決め打ちましたが、まぁどちらにせよ簡単簡潔です。id関数とconstant関数はSTLには含まれていないので、__gnu_cxx名前空間のものを使いました。自作してもよいです。
gを本物のC++関数にしてしまった時点で負けた感じです（誰と勝負しているのかは不明）。gを、boost::lambdaでfの中に書ければ楽しいわけですが、boost::lambda::if_then_else_return で再帰させると、i == k に達しても再帰が止まらないんですよね(SICPの問題1.6、special formではないifだと云々と同じ..たぶん)。うーん。まぁ、変数cに計算を溜めることはできたのでよしとします。飽きてきたのでC++でやるのはこのへんで！
小まとめ
まともなifと、あとstd::なid関数、constant関数がほしい。後ろ2つはC++0xで入ったりしないのかな。あと、ここまでclassとかstructとか書かずにBoost.Lambdaで4つほどネタを書いてみましたが、ほげ<ふが>::result 系が好きな人には面白くない気もします。
