LambdaCpp

C++ でラムダ計算を処理するためのヘッダオンリーライブラリです。知られざる開発秘話はこちらからどうぞ。

Example

#include "lambda-expression.hpp"
#include <vector>
#include <iterator>
#include <iostream>

using namespace lambda::combinators;

int main()
{
    /*
     * チャーチエンコーディングされた自然数に対し階乗を求める
     */
    lambda::expression fact = Y(
        [](lambda::expression f) {
            return [f](lambda::expression n) {
                return is_zero(n)(
                    lambda::church_encode(1)
                )(
                    mult(n)(f(pred(n)))
                );
            };
        }
    );

    /*
     * スコットエンコーディングされたリストを受け取り、
     * 各要素を階乗で置き換えたリストを返す
     */
    lambda::expression program = Y(
        [fact](lambda::expression f) {
            return [fact, f](lambda::expression l) {
                return is_empty(l)(
                    empty_list
                )(
                    cons(fact(car(l)))(f(cdr(l)))
                );
            };
        }
    );

    /*
     * プログラムへの入力。各要素をチャーチエンコーディングしたのち
     * それらをスコットエンコーディングしたものが program への引数となる。
     */
    std::vector<unsigned> numbers {1, 2, 3, 4, 5};

    /*
     * program の計算結果をスコットデコーディングとチャーチデコーディングで
     * 自然数の列に戻したものをここに入れる
     */
    std::vector<unsigned> result;

    /*
     * 実行
     */
    lambda::run_on_integer_sequence(numbers.begin(), numbers.end(), program, std::back_inserter(result));

    /*
     * 計算結果を表示する
     */
    for (auto num : result) {
        std::cout << num << ' ';
    }
    std::cout << std::endl;
}

$ ./a.out
1 2 6 24 120

このライブラリに含まれるもの

• namespace lambda

  • class expression : ラムダ式の実装です。こんな風に関数オブジェクトを代入できます。

    /* λxy.x */
    lambda::expression e = [](lambda x) {
        return [x](lambda y) {
            return x;
        };
    };
    
    /* λx.x */
    lambda::expression f = [](lambda x) {
        return x;
    };
    
    e(f); /* 関数呼び出し。遅延評価になっているので Y コンビネータ等にも安心して渡せます。 */

  • namespace combinators : 各種コンビネータが入っています。

    • チャーチブール値（truth, falsity）
    • Y コンビネータ（Y）
    • SKI コンビネータ（S, K, I）
    • イオタコンビネータ（i）
    • チャーチ自然数への各種算術（succ, pred, add, sub, mult, is_zero）
    • スコットリストへの各種演算（cons, car, cdr, empty_list, is_empty）

  • expression church_encode(std::size_t n) : n をチャーチエンコーディングしたラムダ式を作ります。

  • std::size_t church_decode(expression n) : n をデコードした自然数を返却します。

  • expression scott_encode(InputIterator first, InputIterator last) : [first, last) 内の expression オブジェクトをスコットエンコーディングしてリストを作ります。

  • void scott_decode(expression list, OutputIterator result) : スコットリスト list をデコードして result に書き込みます。

  • void run_on_integer_sequence(InputIterator first, InputIterator last, expression program, OutputIterator result) : このライブラリのミソです。[first, last) 内の自然数をチャーチエンコーディングしたのちスコットエンコーディングでまとめたものを program に引数として与え、それをデコードして自然数の列に戻したものを result に書き込みます。