The Super Programming Technique
§2.ラムダ式をC++で実現する【中編】
前回、紹介させていただいた、記事の作者であるOleg氏からいただいたメールを、日本語訳しておきます。(氏は、いくらか漢字を読めるそうです)
Hello! You have more than translated the page: you have written a great introduction to lambda calculus and added many annotations. You have made the page so much better in contents, and in the appearance as well. I'm glad that my brief page served as a seed for such a great work! ラムダ式の紹介や、多くの訳注がついてて、翻訳以上の仕上がりですね。 内容的にも、見た目にも良いページを作成されましたね。私の短い記事が、 そのような偉業のきっかけとなったようで嬉しく思います。 Perhaps you might be interested in adding a few Scheme links, for example: ひょっとしたら、Scheme関連のリンクを追加すると良いかも知れませんね。 たとえば: http://www.sci.toyama-u.ac.jp/~iwao/Scheme/r5rsj/html/r5rsj_toc.html A great collection of links at the very beginning of: ビギナーのための、素晴らしいリンク集: http://pc.2ch.net/test/read.cgi/tech/1002584344/ http://www.shiro.dreamhost.com/scheme/docs/schemersway-j.html http://shiro.dreamhost.com/scheme/gauche/man/gauche-refj_toc.html#SEC_Contents Another Scheme system: 他のスキームのシステム: http://www.kt.rim.or.jp/~qfwfq/rhiz-pi/index.html Just a bulletin board you're probably aware of: http://pc.2ch.net/tech/kako/987/987169286.html You're right: lambda-calculus is such a fascinated subject. All the lambda-calculator does is the rearranging of symbols -- and yet it's enough to perform any computation. When I think of lambda-calculus I feel to be approaching something really fundamental in the may we think and the way world works. あなたがご存知の通り、ラムダ計算は、たいへん興味深い主題です。 ラムダ式が行なうことのすべてとは、シンボルの再編成であって、 それは、いかなる計算(computation)を実行するのにも十分なのです。 私がラムダ式について思索していたとき、私は、私の考える方法(訳注:mayはwayの タイプミス?)や、全体がうまく働くための、本当に基礎的な何かに近づいていると 感じました。 I believe it's important for a C or even assembly programmer to be aware of such seemingly abstract concepts as binding, environment, polymorphism, currying, closure, continuation. When I programmed in C (and before that, in Algol68) long time ago, I have stumbled upon some of the concepts (e.g., closure -- as in a lazy matrix, which I implemented in my LinAlg library). Yet I didn't know the name for it or the full context. It took me a while to grasp what I have stumbled upon. Binding, closure, continuation, etc. exist in any language. If we know where to look, if we recognize what we see, we can use these features to our advantage, and we can avoid constantly rediscovering techniques and ideas. Your page therefore does a great service to programmers. 私は、束縛や、環境(environment)、ポリモーフィズム、カリー化、クロージャー、 継続(continuation)のような抽象的に思える概念を意識することは、Cや、 アセンブリ言語のプログラマにとっても重要だと信じます。私は、ずっと以前に Cでプログラムしていました(その前はAlgol68でした) 私は、偶然にも、いくつかの 概念に出会いました。(たとえば、クロージャーだとか、遅延行列(a lazy matrix)で あるだとか、そしてそれらを私のLinAlgライブラリで実装しました) しかし、 それらを正式には何と呼ぶのかはいまだ知りません。そして、私は何と出会ったのかを 理解するのに少しの時間が必要でした。どんな言語にも内在する、束縛、クロージャー、 継続、etc..。もし、私たちがそれを注視でき、私たちが何を見ているかを 認識しているのならば、技術やアイデアをたえず見つめ直す(rediscover)ことが 出来るでしょう。あなたのページは、それゆえ、プログラマにとって素晴らしいサービスを 行なっているのです。 Thank you very much! Oleg |
私は、このメールの内容にいたく感動し、さらにOleg氏に、επιστημη氏がcppll(C++メーリングリスト)に投稿されていたコードについて尋ねてみました。以下は、その返答です。
※ 以下のメールで出てくる技法について、一応、テンプレートについてあまり、ご存知ない方のために簡単に解説しておきますが、
template <int v> struct Init2Type { enum { value = v }; };
というテンプレートがあるとき、Int2Type<0>とInt2Type<1>は異なった型です。(⇒『Modern
C++ Design』 p.31)
επιστημη氏のコードでは、このことを利用して、lambda関数(結局はoperator
( ) を定義してあるクラス)に一意な名前をつけています。
Hello! Thank you for pointing out the discussion about Lambda! ラムダに関する議論を教えてくれてありがとう。 I have checked the article 記事を読んでみました > http://www.tietew.jp/cppll/archive/2061 Indeed, approach by FUKUDA-san is rather similar in spirit, and more high-tech. There is a difference however. Let's consider a simplified form of FUKUDA-san's code: なるほど、福田さん(επιστημη氏)のアプローチは、考えかたが酷似していて、 さらにハイテクなアプローチですね。しかし、そこには違いがあります。単純化された 福田さんのコードについて考察してみましょう。 #include <iostream> #include <string> #include <functional> #include <algorithm> #include <list> class lambda { std::string _2nd_; public: lambda (const std::string& _2nd) : _2nd_(_2nd) {} public: bool operator() (const std::string* x) const { return *x == _2nd_; } }; int main() { std::list<std::string*> plist; std::string pstr1("ABC"); std::string pstr2("DDD"); std::string pstr3("GGG"); plist.push_back( &pstr1 ); plist.push_back( &pstr2 ); plist.push_back( &pstr3 ); std::list<std::string*>::iterator p = std::find_if( plist.begin(), plist.end(), lambda("GGG")); if ( p != plist.end() ) { std::cout << "find:" << (**p) << std::endl; } else { std::cout << "not found" << std::endl; } return 0; } The code that specifies what lambda() does (in our case, the comparison "*x == _2nd_") -- the definition of the type lambda -- is textually separated from the code that uses lambda, function std:find_if. Compare this with Scheme: このlambda関数が何を行なうかを書いてあるコード(上例では "* == _2nd_"という比較)が ラムダ型の定義で、これは、ラムダを使用するコード(関数 std::find_if)とテキストとして 分断されています。これをSchemeと比較してみましょう: (filter (lambda (x) (equal? x "DDD")) lst) or Haskell もしくはHaskellと filter (\x -> x == "DDD") lst Here the filtering predicate is defined where it is used. BTW, the Haskell code can be simplified to フィルタリングする述語は、それが使われる場所において定義されています。ところで、 Haskellのコードは、さらに単純化できます filter ("DDD"==) lst Because C++ (or at least, gcc) cannot instantiate templates with _local_ classes, we have to declare the lambda class in the global scope. There it becomes visible to every function in our project. If we want to declare another anonymous function, we have to tag it differently. That's why FUKUDA-san had to introduce "template <int N> class lambda {};". When we instantiate our lambda as lambda<DDD> or lambda<ANY>, we have to use the right label, DDD or ANY. In effect, the label becomes sort of a name for a lambda. But lambda is supposed to be anonymous! C++(あるいは、少なくともgccでは)では、ローカルクラスにおいてテンプレートを インスタンス化できないので、ラムダクラスをグローバルスコープにおいて宣言しなくては なりません。そこで、プロジェクトにあるすべての関数が、可視になってしまいます。もし、 特命の関数を宣言したいのであれば、異なるタグをつけなければなりません。 だからこそ、福田さんは、template <int N> class lambda { }を導入しなければ ならなかったのです。lambdaをlambda<DDD>とかlambda<ANY>としてインスタンス化するとき、 DDDやANYという正しいラベルを用いる必要があります。要するに、このラベルはラムダのための ソートされた名前になります。しかし、ラムダは匿名であるべきだと思います! The Lambda-CPP-more code uses C macros to generate unique names for classes automatically. This makes lambda's _observationally_ anonymous. 'Anonymous' may mean either the absence of the name (like for the Scheme's lambda), or an 'unknown' name (which is the case for my lambda's). Lambda-CPP-moreのコードは、Cのマクロを、クラスのために一意な名前を 自動的に生成するのに用いています。これにより、lambdaの 見た目の(ovservationally)匿名性が得られるのです。"匿名"とは、(Schemeの ラムダのように)名前の不在か、あるいは、知られざる(unknown)名前( 私のラムダの場合はこちらですね)であることだと思います。 Another reason I used the low-tech C macros is because at the time the C++ compiler I used (gcc 2.7.2 or gcc 2.8.1) could not handle template very well. The compiler positively could not do the automatic template instantiation. 私がローテクなCマクロを用いた別の理由とは、その時点で私が使っていた C++コンパイラ(gcc 2.7.2 もしくは 2.8.1)は、テンプレートをあまり上手くは 扱えなかったということです。コンパイラは、テンプレートの自動的な インスタンス化はまったく出来なかったのです。 It is a pity that a more elegant template-based approach is hamstrung by the inability of the compiler to instantiate templates with local classes. テンプレートに基づくよりエレガントなアプローチが、ローカルクラスのテンプレートの インスタンス化をコンパイラが出来ないばかりに、頓挫するのは残念ですね。 BTW, although lambda in C++ seems more like a toy, I actually stumbled on this idea out of a real need. I wanted to write regression tests conveniently: ところで、C++におけるlambdaはおもちゃ(toy)にも似ていますが、私は実際、 現実的な要請からこのアイデアに出会いました。私は、退行テスト(regression tests)を お手軽に書くために欲しかったのです: http://pobox.com/~oleg/ftp/packages/vzeroin.cc Some of the macros could perhaps be replaced by templates. Again, the code was written when templates weren't supported well. The advantage of the low-tech approach is that the code runs on many platforms, from SunOS, HP-UX, Linux and FreeBSD to Winxx (VC++ 5.0 and 6.0) to BeOS (when BeOS was alive and Be, Inc was still a company). いくつかのマクロは、たぶんテンプレートで置き換えることが出来るでしょう。 また、テンプレートがうまくサポートされていなかったときに、それらのコードが 書かれました。ローテクなアプローチの長所は、SunOs,HP-UX,Linux,FreeBSDから WinXX(VC++5.0と6.0)からBeOS(BeOSが存在していて、Be.Incが会社だったころ)まで たくさんのプラットフォームで動作します。 Thank you for your message! I could read it well: my computer can view documents in all major Japanese encoding systems. I haven't configured the input method yet. メッセージありがとう!私はそれをうまく読むことが出来ました:私のコンピュータは すべてのメジャーな日本語エンコーディングシステムの文章を読むことが出来ます。私は、 入力手段までは、まだ設定しません。 BTW, my writing style is not clear, and my pages are obscure in many places. You might therefore have some questions. I would be happy to answer them. ところで、私のスタイルは、明確ではありませんし、私のページは多くの箇所が不明瞭です。 あなたはそれゆえ、疑問に感じたのだと思います。私がそれらに回答できればと思います。 Thank you! Oleg |
残念なことにC++では、局所的なtemplate定義が出来ないがために、templateを関数の外に出さなければならない。しかしそれでは、本当に匿名の関数だとは言えない。Oleg氏は、そう主張しています。これを解決する方法は、次回書くとして、とりあえず続き。
Hello! I thought that you might be interested in some other approaches to bringing lambda to C++. These are high-tech approaches (in some cases, very high-tech): あなたが、C++にラムダをもたらす他のいくつかのアプローチについても興味があるかと思いました。 いくつかのハイテクアプローチがあります(いくつかのケースについては大変ハイテクです): http://www.cc.gatech.edu/~yannis/fc++/ http://www.fz-juelich.de/zam/FACT http://lambda.cs.utu.fi/ More about the languages: これらの言語についてさらなる情報は: http://www.bagley.org/~doug/shootout/craps.shtml As you can see, OCaml is actually faster than C++. OCaml has currying, garbage collection, anonymous functions etc. built-in -- therefore, you don't need to resort to extremely high-tech template programming as you do in C++. OCaml can work as an interpreter, a compiler to a portable byte-code, or a compiler to the native code. It makes us wonder if C++ has any reason to exist (It's a very inflammatory remark, I'm sorry. One can still wonder about that). 見てわかる通り、OCamlは実際C++より速いのです。OCamlはカリー化、 ガーベジコレクション、匿名関数などを有しています。内蔵(built-in)しているので、 それゆえ、あなたがC++でプログラミングするときにやっているような、凄くハイテクな テンプレートを頼りの綱とする必要も無いのです。OCamlは、インタプリタとしても動きますし、 移植可能な(portable)バイトコードを吐くコンパイラ、そしてネイティブコードを吐く コンパイラにもなります。このことは、C++なんて存在する価値があるのかという気になります。 (極端な意見でごめんなさい。そう考えている人も居るのです) You may have heard that a complex ray-tracing program in OCaml outperformed all competitors (written in C, C++ and other languages). The program took only 72 hours to write, by a team of 4 programmers. Actually, the team produced 4 different versions of the program. The program won the top award at the ICFP'00 programming contest. Two members of the team are Sumii Eijiro and Haruo Hasoya. あなたは、OCamlで書かれた複雑なレイレーシングのプログラムについて聞いたことがあるかも 知れませんね。それは、すべての競争者(C,C++か、その他の言語で書かれています)より 性能が優れています。そのプログラムはたった4人のプログラマによるチームによって 72時間で書かれました。実際、そのチームは4つの異なるバージョンを作りました。 このプログラムは、ICFPの2000年度のプログラミングコンテストで優秀賞を獲得しました。 そのチームの二人のメンバーは、Sumii EijiroとHaruo Hasoyaです。 http://www.cs.cornell.edu/icfp/ http://www.cs.cornell.edu/icfp/contest_results.htm The following is a good site about many topics related to languages: 次のは、言語に関連するたくさんのトピックがある良いサイトです: http://lambda.weblogs.com/ Finally, the following link may be of interest to you professionally, as a writer of a book on game programming: 最後に、次のリンクは、ゲームプログラミング本の著者としてのあなたにとって 職業的に興味があるかも知れません: http://www.unixreview.com/documents/s=1420/urmb29/book29.htm Scripting can make game programming far more fun. ゲームプログラミングを行なうスクリプティングというのは、大変面白いですね。 I'm afraid I might have overwhelmed you with stuff to read. Sorry. 読むのが大変であなたを圧倒していないか心配です。ごめんなさい。 Oleg |
ということで、次回までに以上のリンクを勉強しておくこと!(俺がな..)