The Super Programming Technique

§１．ラムダ式をC++で実現する【前編】

関数型言語の基本的な概念であるラムダ式を、C++で実現する方法について紹介します。

・高階関数(higher-order function)

他の関数を引数として扱う関数は、高階関数と呼ばれます。
「関数を引数にとる」のですが、関数を渡すためには、C++では、関数ポインタで渡すか、templateで渡すかです。（operator ( )をオーバーロードしたクラスをfunctorと呼び、これを引数templateを用いて渡すテクニックについては⇒集中講義４． 超高速描画の謎【後編】を参照のこと。）

グラフィックの転送ルーチン等は、処理の９９％が同じで、ピクセルをコピーする関数のみが違うという場合があります。このように、共通の処理がある場合、この高階関数にすると処理がすっきり書けます。

・ラムダ式(lambda expression)

ラムダ式は、その値が関数であるような式です。

ならば、呼び出された引数の値を１だけ増加させたものを結果として返す関数です。つまり、このλ式は

というような関数を意味していると考えてください。要するに、λ式とは関数です。この例の変数xは、仮引数であって次のように、別の名前でも同じ意味ですね。

よって、λ式も

は、同じ関数を意味しています。引数を、２つとる関数は、次のように表現されます。

関数の引数が属さなければならない集合(型)を示すと有効な場合が多いです。

このNというのは自然数(integer)の集合です。この記法は、型付きラムダ記法(typed lambda notation)と呼ばれます。あるいは、返し値についても明記することがあります。

これは、整数x,yを引数に取って、返し値は整数である関数です。C/C++で書けば、以下のようになります。

・ラムダ式による関数合成

ラムダを用いるメリットは、関数合成の表現が容易だということです。

このとき、

という関数は、incとdoubleの合成として

と書けます。つまり、この関数合成の" ; " というinfix（中置きする）演算子は、

の意味になります。早い話が、一つ目の関数を適用して、そのあと、一つ目の関数の返し値に対して、二つ目の関数を適用する、という意味です。この例では、Nと書いていますが、任意の集合を取ることによって総称的（generic≒型にとらわれないこと）にも出来ます。

・カリー化(currying)

この名前は、コンビネータ論理の分野で重要な貢献をした人の一人、数学者H.B.Curryに因んでつけられました。

curryは、２つの引数を持つ任意の関数を１つの引数の関数に変換します。結果は、１引数関数そのものです。

さきほどのラムダ式を用いれば、関数を返す関数(function-producing function)を簡単に記述できます。

このincは確かに関数で、整数引数nを取り、関数を返します。たとえば、inc(3)は、次の関数を意味します。

これは、見ての通り、３を足す関数ですね。この記法を用いて、カリー化を説明します。

をカリー化すれば

です。plus_yは、yを引数にとり、「与えられた引数にyを加算して返す」関数を返します。

・束縛(binding)

ところで、

のnは、どこで定義されて、いつ与えられるのでしょうか？

この場合、yに代入されるのは、4なのか、5なのでしょうか？これは、どちらの実装も考えられます。
4が代入されるのは、ラムダ式をfに代入した時点で、nはbind(束縛)されるので、正式の束縛(proper binding)あるいは静的束縛(static binding)と呼ばれます。5が代入される実装は、fが呼び出される時点で、nがbindされるので、動的束縛(dynamic binding)と呼ばれます。

後者の実装は、C++の仮想関数にも似て、強烈な効果を発揮するのですが、意図しない束縛をされることもあるので、現実的には使いこなせないでしょう。そこで、普通は、前者の実装をされます。

参考文献１．「プログラミング言語理論への招待」/Bertrand Meyer著　ASCII (ISBN4-7561-0317-0)
参考文献２．「関数型プログラミング」/PETER HENDERSON著

参考になりそうなURL：

SMLの日本語訳
http://a414s1.it.nanzan-u.ac.jp/smlbook/smlwww/smlwww.html

・ラムダ式をC++で記述する

ラムダ式をC++で記述する方法については、以下の記事が参考になります。

http://okmij.org/ftp/c++-digest/Lambda-CPP-more.html

ローテク万歳と言ったところでしょうか。今回は、これを全文、日本語に訳しました。（誤訳があれば、やねうらおまでお知らせください）

C++とSchemeにおけるラムダ抽象化

この記事は、C++におけるラムダ抽象化をSchemeのような伝統的な関数型言語と比較して示すものです。この記事では、C++のラムダ抽象において適用できる値(applicable values)が、単にそれらと関数的に似ているだけでは無いことを示すようにします。ここで示すC++におけるラムダ抽象化は、意味においてまでも同様なのです。同時に、カリー化についても述べます。この記事は、C++とSchemeが同一であることを証明するものではありません。それらは明らかに違うものですから。 しかし、ラムダ式は薄気味悪い(uncanny)ほど酷似しています。私は、C++の関数的側面は、この言語のあまり知られていない特徴であると控えめに提示します。

この記事は、
comp.lang.scheme, comp.lang.functional, comp.lang.lisp, comp.lang.c++.moderated
ニュースグループに　Sun, 24 Jan 1999 23:19:27 GMT　に投函されました。

• 例
  1. 単純なラムダ式
  2. 再帰的なラムダ式
  3. 高階関数
  4. カリー化
  
  
• 謝辞
• 記事の投稿ヘッダ
   

1. 単純なラムダ式

Schemeで
     (define foo (lambda (a b) (+ a b)))
というラムダ式は評価されたとき、手続きを生成します。（訳注：このラムダ式は評価されたときに与えられた２つの変数a , b を加算してその値を返す関数を生成します。C++の関数は、Schemeでは「手続き(procedure)」と呼ばれます。以下、「手続き」とあるのは、「関数」と読み換えてください）　define は、この値を識別子fooに束縛(bind)します。

このあと、
     (foo 1 2)
という式を評価すれば、この識別子に束縛されている手続きを調べて、それを適用します。（訳注：1と2が加算されて3が返ります。）

C++において、正確にこれと同じアイデアは、次のように表現されます：

     Lambda((int a, int b), int, return a+b) foo;

また、

     #define Lambda(args,ret_type,body) \
     class MakeName(__Lambda___) { \
     public: ret_type operator() args { body; } }

です。このLambda構文は、手続きを生成します。

訳注：ここで言う「手続き」とは関数を返すクラスのこと。この例では、operator ( )をオーバーロードしたクラス。要するにfunctor。また、このMakeNameは、uniqueな識別子を返すためのマクロ。例えば、次のようなもの

#define XY(X,Y) X##Y
#define MAKENAMEXY(FX,LINE) XY(FX,LINE)
#define MAKENAME(FX) MAKENAMEXY(FX,__LINE__)

C言語で宣言と呼ばれるこの、このインスタンスオペレータ(訳注：クラス定義のあとにインスタンス化する変数をくっつる記法)は、この適用可能型(訳注：このマクロで作られたクラスのことを言っていると思われる)と、インスタンス変数fooとを“束縛”します。これは逆も聴こえが良いですね。すなわち、fooは、手続き型の値に束縛されていると。換言すれば、fooは呼び出し可能なインターフェースを実装したクラスのオブジェクトとしてインスタンス化されています。

コンパイラが、次の処理を行なうとき：

     cout << "foo(1,2) is " << foo(1,2) << endl;

fooの型を調べ、手続きクラスを見つけ、適切なメソッドが呼び出されます。このSchemeとC++における２つの式は、ほぼ完全に類似しています。大きな差は、値の参照と束縛を行なうのが、コンパイル時か実行時かというだけです。最適化されたSchemeコンパイラでは（訳注：最適化によって、コンパイル時に値の参照と束縛が行なわれるので）、この差異さえ不明確です。

2. 再帰的なラムダ式

     (define fact (lambda (n) (if (not (positive? n)) 1
                                  (* n (fact (- n 1))))))

訳注：factとは階乗のこと。５の階乗は５！と表記し、５×４×３×２×１のこと。また、０！＝１。よって、fact(0) =1 , fact(n) = n × fact(n-1)と再帰的に定義できます。このSchemeの式は、このように再帰的に階乗を求めるものです。

ラムダ式それ自身(訳注：上のlambda以下)は、識別子factが「手続き」として評価されている時には、何とも束縛されていません。その束縛は、defineされたあとに行なわれます。しかし、問題があるわけではありません：このラムダ式は、その時点まで適用されておらず、それは単にコンパイル済みであるに過ぎないのです。fact関数の値が本当に必要になったときに初めて束縛されるでしょう。

C++においては、

    Lambda((int n),int,
           if( n <= 0 ) return 1; else return n * (*this)(n-1))
    fact;

と書けます。

上式は、メソッド本体において現在のオブジェクトは、thisによって参照できるという事実を利用しています。先のSchemeの式と同じ種類の参照遅延(lookup delay：訳注　ラムダ式が本当に必要になるまで展開されないこと）です。このメソッド本体がコンパイルされるときには現在のオブジェクトはまだ存在しません　：　thisは、単に潜在的な束縛(potentially bound)に過ぎません。あとで、コンパイラはメソッドの適用を行なうときに、このメソッドがどのオブジェクトに適用されるかを知ります。

3. 高階関数

この例は、よく練られたおもちゃではなく(deliberately less toy)、もっと実用性を期待する(hopefully more serious)ものです。ここではn番目のフィボナッチ数（訳注：フィボナッチ数について面白い記事があるので紹介しておきます⇒http://www.rd.mmtr.or.jp/~bunryu/pain3.htm）の計算をスピードアップするためにキャッシュを使用します。

     (define (print-every-other n proc) ; A higher-order function
        (display (proc 1))
        (do ((i 3 (+ 2 i))) ((> i n) (newline))
           (display " ") (display (proc i))))

     (print-every-other 11
        (letrec ((n 0) (fib-n 0) (n-1 0) (fib-n-1 0)
           (fib (lambda (x)
              (cond
                 ((= 1 x) 1)
                 ((= 2 x) 1)
                 ((= n x) fib-n)
                 ((= n-1 x) fib-n-1)
                 ((= (+ n 1) x) (do-cache n x fib-n (+ fib-n fib-n-1)))
                 (else
                    (let* ((x-1 (- x 1)) (v-1 (fib x-1)))
                       (do-cache x-1 x v-1 (+ v-1 (fib (- x 2)))))))))
           (do-cache
              (lambda (x-1 x v-1 v)
                 (if (> x n)
                    (begin
                       (set! n x) (set! fib-n v)
                       (set! n-1 x-1) (set! fib-n-1 v-1)))
                       v)))
           fib))

実行結果：

1 2 5 13 34 89

これは、他のすべてのフィボナッチ数を表示します。前の結果のキャッシュを行なうことで、本当に計算がスピードアップします。

ここに、C++による等価なコードがあります。

     template<class T> struct pair { T fst, snd; };

     typedef Lambda((int x),
       struct xv: public pair<int>
            { xv(void) { fst=0; snd=0; }
              xv(const int a, const int b) { fst = a; snd = b; }};
       pair<xv> cache;
       int do_cache(const xv prev, const xv curr)
       {
         if( curr.fst > cache.snd.fst )
           { cache.fst = prev; cache.snd = curr; }
         return curr.snd;
       }
       int,
       if( x == 1 ) return 1;
       if( x == 2 ) return 1;
       if( x == cache.fst.fst ) return cache.fst.snd;
       if( x == cache.snd.fst ) return cache.snd.snd;
       if( x == (cache.snd.fst + 1) )
         return do_cache(cache.snd, xv(x,cache.fst.snd + cache.snd.snd));
       const int vp = (*this)(x-1);
       return do_cache(xv(x-1,vp), xv(x,vp+(*this)(x-2)))
     )
     fib;

     template<class T> void print_every_other(const int n)
     {
       T closure;
       cout << closure(1);
       for(register int i=3; i<=n; i+=2)
         cout << " " << closure(i);
       cout << endl;
     }

     main() {
       print_every_other<fib>(11);
     }

SchemeとC++のコードは、意味的に(semantically)非常に似通っていることに注目してください。Schemeのprint-every-otherを実行したとき、その第二位の関数の内部で proc と結びつけられた手続きを返します。

C++のprint_every_otherを実行したとき、その第二位の手続きのなかでインスタンス化された手続きを返し、その手続きはそのあと適用されます。fib 手続きは本当に、クロージャー(closure)であることに注目してください。

4. カリー化

C++のコードを最初に書くことにしましょう：

     static void test_currying(void)
     {
       cout << "Currying 1: " << curry_add(1) << endl;
       cout << "Currying 1+2: " << curry_add(1)(2) << endl;
       cout << "Currying 1+2+4: " << curry_add(1)(2)(4) << endl;
       cout << "Currying 1.1: " << curry_add(1.1) << endl;
       cout << "Currying 1.1+0.5: " << curry_add(1.1)(0.5) << endl;
       cout << "Currying 1.1+0.5-1.0: " << curry_add(1.1)(0.5)(-1.0) << endl;
     }

curry_addを何度も何度も呼び出すことが出来ます。つまり、この上例では３回まで適用しています。

Curry_addはこうなっています。

     template<class T> class Curry_add
     {
       T a;
     public:
       Curry_add(const T _a) : a(_a) {}
       Curry_add<T> operator () (const T b) const { return a + b; }
       operator T (void) const { return a; }
     };
     template<class T> Curry_add<T> curry_add(const T a) { return a; }

Schemeでは、こうなっています。

     (define (curry-add x) (lambda p (if (null? p) x 
                                         (curry-add (+ x (car p))))))
     ((curry-add 5))  ==> 5
     (((curry-add 5) 7))  ==> 12
     ((((curry-add 5) 7) -1)) ==> 11

この関数の型は、次のようにずぼらに(loosely)表現されます

    data curry_add_t = Either int (int -> curry_add_t)

訳注：curry_addのテンプレートは、int型を返すか、curry_addのテンプレートを返すの意味。

もし、あなたが、この定義が再帰的であることに気付かないのなら、MLかHaskellの型チェッカがそれを思い出させてくれるでしょう。（訳注：ML,Haskellはラムダ展開をサポートする関数型言語。MLについては、ベル研のサイト，Haskellは、http://haskell.org/を参照のこと。）

実際のところ、カリー化はC++において実装されます。以下のCの引数を複数とるアプリケーションと比較してください。

     printf("%s%d%c\n","passing many arguments: ",4,'!');

C++と等価なコードでは、

     cout << "passing many arguments: " << 4 << '!' << endl;

です。<< がinfix(中置きする）オペレータと簡単にわかります。

完全なコード

lambda.cc
この記事のための完全なC++のコード。gcc 2.8.1, gcc 2.7.2.1 と Visual C++ 5.0にてコンパイル可能。

Functional Style in C++: Closures, Late Binding, and Lambda Abstractions
A poster presented at the 1998 International Conference on Functional Programming (ICFP'98)  
 

謝辞

Andy Gaynor <silver@mail.webspan.net> はまさにこの質問をしてくれました。この記事は、単に回答に過ぎません。 

記事の投稿ヘッダ

From oleg@pobox.com Sun Jan 24 15:17:31 1999
Subject: Lambda abstractions in C++ vs. Scheme
Date: Sun, 24 Jan 1999 23:19:27 GMT
Reply-To: oleg@pobox.com
Keywords: currying, closure, stream, lambda abstraction, recursion, C++, Scheme
Newsgroups: comp.lang.scheme,comp.lang.functional,comp.lang.lisp,comp.lang.c++.moderated
Organization: Deja News - The Leader in Internet Discussion
Summary: C++ as a functional language
X-Article-Creation-Date: Sun Jan 24 23:19:27 1999 GMT

追記 ('02/05/03)

紹介させていただいたことを、この記事の作者であるOleg氏にお伝えしたところ、以下のように非常に好意的なコメントをいただきました。有用な（日本語の）リンクも多数含まれていますので、謹んで掲載させていただく次第です。

戻る