memologue RSSフィード

書いている人

日記というよりは備忘録、ソフトウェア技術者の不定期メモ。あるいはバッドノウハウ集。プライベートで調査した細々した諸々のスナップショット。嘘が散りばめられています。ISO/IEC 14882(C++)とPOSIX, GCC, glibc, ELFの話ばかりで、WindowsやMacの話はありません。特に記載がなければLinux/x86とILP32が前提です。時間の経過と共に古い記事は埋もれてしまいます。検索エンジンから飛んできた場合は、ページ内検索をご利用いただくかgoogleキャッシュを閲覧してみてください。技術的な記事を書きためる場所として使っています。言及してもらえると喜びます。主要な記事の一覧を書いておきます:

にんきコンテンツ: [GCC] mainを一度も呼ばないばかりか蹂躙する / Binary2.0 Conference 2006 発表資料 / C++ で SICP / ついカッとなって実行バイナリにパッチ / hogetrace - 関数コールトレーサ

昔のPOSIX関係の記事: シグナルの送受に依存しない設計にしよう / シグナルハンドラで行ってよい処理を知ろう / マルチスレッドのプログラムでのforkはやめよう / スレッドの「非同期キャンセル」を行わない設計にしよう / スレッドの「遅延キャンセル」も出来る限り避けて通ろう / マルチスレッドプログラミングの「常識」を守ろう / C++でsynchronized methodを書くのは難しい / シグナルハンドラからのforkするのは安全か? / g++ の -fthreadsafe-statics ってオプション知ってます? / 非同期シグナルとanti-pattern / localtimeやstrtokは本当にスレッドセーフにできないのか / UNIXの規格について / マルチスレッドと共有変数 - volatile?なにそれ。 / type punning と strict aliasing / アセンブラで遊ぶ時に便利なgdb設定 / 最近の記事は一覧から

2006-11-23

[] 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

1〜2章の範囲なら、SchemeでもHaskellでも似たようなもので、シンプルです。

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>() を使う。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;
 }

小まとめ


逆アセンブル結果が読みやすい言語が最高、そんなふうに考えていた時期が 俺にもありました。


言語の力かぁ...Prologでもやるか

[ネタ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 系が好きな人には面白くない気もします。

総まとめ


だからなんだ!!_


あー、parsecの勉強しよ...。ECSは買ってあるけど読んでません。

*1:以下、過去の勉強会の回答例を少し参考にさせてもらってます

*2:ここの素のC++での例はつまらないので見なかったことにします

*3:クロージャの定義については触れずに逃げ

*4:ちゃんと書くと、boost::bind は3つくらいの仕事をしてくれます。(1) 関数ポインタ/メンバ関数ポインタを関数オブジェクトに変換 (2) その関数オブジェクトのcurrying (3) 関数オブジェクトの引数順の自由な入れ替え(Haskellのfilp関数のお化け)

*5:STLのalgorithmをはじめとしてC++では、普通は関数オブジェクトを値ベースで扱いますので、コピーはよく起こります

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証