SCIP in C++11 ― 2.1.3節その1

対の表現と問題2.4～2.5

地味だが自分的にものすごく重要っぽい2.1.3節「データとは何か」。

タイトルからして深いよ。

データのカプセル化による隠蔽・インターフェースの共通化/抽象化というと、

「クラス作ってオブジェクト指向！」

って発想しかできなくなっている自分にガツンと一発。愕然として自己嫌悪orz。

計算機科学の根本にある、数理論理・数学基礎論の本とかを、

たまに読んでも理解できた気がしないのは、

根本的にデータ・手続きというものに対する考え方が硬直していたということだ。

「対やリストの表現にSTLコンテナをどう使おうか」とか、

凝り固まってた思考法が、早速ふにゅふにゅに解体されていく妙な感覚。

Schemeで組んだときは「これがSchemeでの表現法かぁ」とか太平楽に考えながら、

慣れないSchemeで実装し切るところまでで息切れして、

その奥にある発想まで考えが及ばなかったけど、

実装自体は苦労しない慣れ親しんだC++で組むことで、

その発想の部分がいちいち、自分の抱える重大な問題として立ちはだかる。

自分の中にある思考の、もう何段かの抽象化が必要なんだ・・・面白そうじゃん！

l   本文中のメッセージパッシングによる対の表現

l   問題2.4の対の表現

l   問題2.5の（非負整数の）対の表現

を、抽象の壁を意識して実装すると以下の通り。

メッセージパッシング版：

----

typedef int ItemType;

typedef function<ItemType(int)> Pair;

const Pair cons(const ItemType& a, const ItemType& b){

    const Pair dispatch=[a, b](const int selectionParameter){

        if(0==selectionParameter){return(a);}

        if(1==selectionParameter){return(b);}

        else{cerr<<"Argument not 0 or 1 --- CONS "

             <<selectionParameter<<endl;

             exit(1);}

    };

    return(dispatch);

}

const ItemType car(const Pair& z) {return(z(0));}

const ItemType cdr(const Pair& z){return(z(1));}

----

問題2.4版：

----

typedef int ItemType;

typedef function<ItemType(ItemType,ItemType)> TmpReturnType;

typedef function<ItemType(TmpReturnType)> Pair;

const Pair cons(const ItemType& x, const ItemType& y){

    const Pair dispatch=[x,y](const TmpReturnType& m){

        return(m(x,y));

    };

    return(dispatch);

}

const ItemType car(const Pair& z) {

    return(z([](const ItemType& p, const ItemType& q){return(p);}));

}

const ItemType cdr(const Pair& z){

    return(z([](const ItemType& p, const ItemType& q){return(q);}));

}

----

問題2.5版：

Gödel数化を思わせる表現法。

素因数分解の一意性によりwell-definedなことが保証される。

----

typedef unsigned int Pair;

const Pair cons(const unsigned int a, const unsigned int b){

    return(pow(2,a)*pow(3,b));

}

const unsigned int selector

(const unsigned int n, const unsigned int parameter)

{

    function<unsigned int(unsigned int)> select;

    select=[parameter,&select](const unsigned int next)

        ->const unsigned int{

        if(0!=next%parameter){return(0);}

        else{return(select(next/parameter)+1);}

    };

    return(select(n));

}

const unsigned int car(const Pair& p){

    return(selector(p,2));

}

const unsigned int cdr(const Pair& p){

    return(selector(p,3));

}

----

抽象の壁の向こうに、全て共通の以下の関数がある。

----

//---------abstraction barrier---------

void printPair(const Pair& p){

    cout<<"("<<car(p)<<" "<<cdr(p)<<")"<<endl;

}

int main(int argc, char** argv)

{

    const Pair p(cons(5,7));

    printPair(p);

    return(0);

}

----

出力

----

(5 7)