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

表の表現

特に大きな問題はない。

----

const List makeTable(void)

{return(makeList("*table*"));}

const List associate(const List& key, const List& records)

{

    if(isNull(records)){return(makeList());}

    if(isEqual(key,caar(records))){return(car(records));}

    return(associate(key,cdr(records)));

}

void insertf(const List& key, const List& value, const List& table)

{

    const auto record(associate(key,cdr(table)));

    if(!isNull(record)){setfCdr(record,makeList(value));}

    else{setfCdr(table,cons(cons(key,value),cdr(table)));}

}

void insertf(const List& key1, const List& key2,

             const List& value, const List& table)

{

    const auto subtable(associate(key1,cdr(table)));

    if(!isNull(subtable)){

        const auto record(associate(key2,cdr(subtable)));

        if(!isNull(record)){setfCdr(record,makeList(value));}

        else{setfCdr(subtable,cons(cons(key2,value),cdr(subtable)));}

    }else{

        setfCdr(table,cons(makeList(key1,cons(key2,value)),cdr(table)));

    }

}

const List lookup(const List& key, const List& table)

{

    const auto record(associate(key,cdr(table)));

    if(!isNull(record)){return(cdr(table));}

    return(record);

}

const List lookup(const List& key1, const List& key2, const List& table)

{

    const auto subtable(associate(key1,cdr(table)));

    if(!isNull(subtable)){

        const auto record(associate(key2,cdr(subtable)));

        if(!isNull(record)){return(cdr(record));}

        return(record);

    }

    return(subtable);

}

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

int main(int argc, char** argv)

{

    auto t1(makeTable());

    cout<<"t1 = (makeTable) = "<<listString(t1)<<endl;

    insertf(makeLeaf("a"),makeLeaf(1),t1);

    cout<<"(insert! 'a 1 t1): t1="<<listString(t1)<<endl;

    insertf(makeLeaf("b"),makeLeaf(2),t1);

    cout<<"(insert! 'b 2 t1): t1="<<listString(t1)<<endl;

    insertf(makeLeaf("c"),makeLeaf(3),t1);

    cout<<"(insert! 'c 3 t1): t1="<<listString(t1)<<endl;

    insertf(makeLeaf("a"),makeLeaf(4),t1);

    cout<<"(insert! 'a 4 t1): t1="<<listString(t1)<<endl;

    cout<<endl;

    auto t2(makeTable());

    cout<<"t2 = (makeTable) = "<<listString(t2)<<endl;

    insertf(makeLeaf("math"),makeLeaf("+"),makeLeaf(43),t2);

    cout<<"(insert! 'math '+ 43 t2): t2="<<listString(t2)<<endl;

    insertf(makeLeaf("math"),makeLeaf("-"),makeLeaf(45),t2);

    cout<<"(insert! 'math '- 45 t2): t2="<<listString(t2)<<endl;

    insertf(makeLeaf("math"),makeLeaf("*"),makeLeaf(42),t2);

    cout<<"(insert! 'math '* 42 t2): t2="<<listString(t2)<<endl;

    insertf(makeLeaf("letters"),makeLeaf("a"),makeLeaf(97),t2);

    cout<<"(insert! 'letters 'a 97 t2): t2="<<listString(t2)<<endl;

    insertf(makeLeaf("letters"),makeLeaf("b"),makeLeaf(98),t2);

    cout<<"(insert! 'letters 'b 98 t2): t2="<<listString(t2)<<endl;

    return(0);

}

----

出力

----

t1 = (makeTable) = ('*table*)

(insert! 'a 1 t1): t1=('*table* ('a 1))

(insert! 'b 2 t1): t1=('*table* ('b 2) ('a 1))

(insert! 'c 3 t1): t1=('*table* ('c 3) ('b 2) ('a 1))

(insert! 'a 4 t1): t1=('*table* ('c 3) ('b 2) ('a 4))

t2 = (makeTable) = ('*table*)

(insert! 'math '+ 43 t2): t2=('*table* ('math ('+ 43)))

(insert! 'math '- 45 t2): t2=('*table* ('math ('- 45) ('+ 43)))

(insert! 'math '* 42 t2): t2=('*table* ('math ('* 42) ('- 45) ('+ 43)))

(insert! 'letters 'a 97 t2): t2=('*table* ('letters ('a 97)) ('math ('* 42) ('- 45) ('+ 43)))

(insert! 'letters 'b 98 t2): t2=('*table* ('letters ('b 98) ('a 97)) ('math ('* 42) ('- 45) ('+ 43)))

SCIP in C++11 ― 3.3.2節その2

キューのメッセージパッシング手続き実装と問題3.22

C++11でキューのデータの実体オブジェクトfrontPointerを、

makeQueue内で定義すると、frontPointerを各クロージャで共有するためには、

クロージャでfrontPointerを参照キャプチャしなければいけないが、

makeQueueが終了すると本体の寿命が尽きて、クロージャ内の参照も全部死ぬ。

そこでmakeQueueではfrontPointerの初期値を設定するのみにし、

frontPointerをスタックに入れて右辺値参照で保持するようにした。ああ面倒。

しかも右辺値参照だとなぜ保持できてるのかわからない。

仕様なのか実装系依存なのか。気持ち悪い。

デックはあまり興味ないので問題3.23はパス。

普通はデキューでなくデックじゃないかと思うがまあいいや。

----

typedef function<List(List)> Queue;

const Queue makeQueueDispatch(const List& initial)

{

    const List&& frontPointer(std::move(initial));

    const function<bool(void)> isEmptyQueue

        =[frontPointer](void){return(isNull(frontPointer));};

    const function<List(void)> frontQueue

        =[frontPointer,isEmptyQueue](void){

        if(isEmptyQueue()){

            cerr<<"FRONT called with an empty queue "<<listString(frontPointer)<<endl;

            exit(1);

            return(makeList());

        }

        return(car(frontPointer));

    };

    const function<void(List)> setfFrontPointer

        =[frontPointer](const List& item)

        {setfCar(frontPointer,item);};

    const function<List(List)> insertfQueue

        =[frontPointer,isEmptyQueue,setfFrontPointer]

        (const List& item)

        {

            if(isEmptyQueue()){

                setfFrontPointer(item);

            }else{

                appendf(frontPointer,makeList(item));

            }

            return(frontPointer);

        };

    const function<List(void)> deletefQueue

        =[frontPointer,isEmptyQueue](void)

        {

            if(isEmptyQueue()){

                cerr<<"DELETE! called with an empty queue "<<listString(frontPointer)<<endl;

                exit(1);

                return(makeList());

            }

            setf(cdr(frontPointer),frontPointer);

            return(frontPointer);

        };

   

    const function<List(void)> getQueue=[frontPointer](void)

        {return(frontPointer);};

   

    const Queue dispatch

        =[isEmptyQueue,frontQueue,insertfQueue,deletefQueue,getQueue]

        (const List& message){

        if(isEq(message,makeLeaf("empty-queue?"))){return(makeLeaf(isEmptyQueue));}

        if(isEq(message,makeLeaf("front-queue"))){return(makeLeaf(frontQueue));}

        if(isEq(message,makeLeaf("insert-queue!"))){return(makeLeaf(insertfQueue));}

        if(isEq(message,makeLeaf("delete-queue!"))){return(makeLeaf(deletefQueue));}

        if(isEq(message,makeLeaf("get-queue"))){return(makeLeaf(getQueue));}

        cerr<<"Unknown request --- MAKE-QUEUE"<<endl;

        exit(1);

        return(makeList());

    };

    return(dispatch);

}

const Queue makeQueue(void)

{

    return(makeQueueDispatch(makeList()));

}

const bool isEmptyQueue(const Queue& queue)

{return(executable<bool>

        (queue(makeLeaf("empty-queue?")))());}

const List frontQueue(const Queue& queue)

{return(executable<List>

        (queue(makeLeaf("front-queue")))());}

const Queue insertfQueue(const Queue& queue, const List& item)

{

    executable<List,List>

        (queue(makeLeaf("insert-queue!")))(item);

    return(queue);

}

const Queue deletefQueue(const Queue& queue)

{

    executable<List>

        (queue(makeLeaf("delete-queue!")))();

    return(queue);

}

void printQueue(const Queue& queue)

{cout<<listString(executable<List>(queue(makeLeaf("get-queue")))());}

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

int main(int argc, char** argv)

{

    cout<<"Excersize 3.22:"<<endl;

    const auto q1(makeQueue());

    printQueue(q1);cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("a")));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("b")));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("c")));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("d")));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    return(0);

}

----

出力

----

Excersize 3.22:

()

('a)

('a 'b)

('a 'b 'c)

('b 'c)

('c)

('c 'd)

('d)

()

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

共有

Listの内部実装がSchemeのリストの図とはだいぶ違うので、、

set-to-wow!の振る舞いはz1とz2で同じになる(z2の方と同じ)。

これをSICPと同じにしようと頑張ってみたがどうもうまくいかない。

そもそもこれが問題になるのかどうかよくわからないので、

先にキューや表を作ってみてから考えてみよう。

というわけで問題3.15～3.20はパス。

キューと問題3.21

STLのqueueを使いたくなるが、まあ我慢しておこう。

キューの末尾に要素を追加する処理をΘ(1)にするために、

SICPのキューではrear-ptrを用意しているわけだが、

こっちのC++実装ではListは内部的にstd::listで、

Listの末尾に要素を代入的に加えるappend!（コードではappendf）では、

内部的にはend()イテレータのところからstd::spliceしている。

end()イテレータで末尾位置を知る動作はΘ(1)だと思うので、

rear-ptrはそもそも不要で、単に要素をappend!すればいいだけだ。

さらにSICPのキューではrear-ptrとキューのリストの末尾は共有されているから、

insert-queue!で空でないキューに要素を追加するときに、最初に

(set-cdr! (rear-ptr queue) new-pair)

するのだが、こっちのListの実装ではその共有ができてないので、

rear-ptrとキューのリストの末尾は全然違うオブジェクトになる。

要するにこっちの実装ではrear-ptrの存在意義は皆無で、

処理に関係しないオブジェクトがただメモリ食ってるだけ。

だから、reat-ptrは廃して、キューの表現は単にListでいい。

あとsetfが、コピー先がリストの時は実装していなかったので実装しなおし。

----

template<typename InType>

void setf(const InType& input, const List& destination)

{

    const List inList(makeLeaf(input));

    if(!inList->isList()){

        if(!inList->isFunction()){

            setItem(inList,const_cast<List&>(destination));

        }else{

            const_cast<List&>(destination)=List(inList);

        }

    }

    const_cast<List&>(destination)->removeAllElement();

    destination->append(inList);

}

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

void setfFrontPointer(const List& queue,const List& item)

{return(setfCar(queue,item));}

const bool isEmptyQueue(const List& queue)

{return(isNull(queue));}

const List makeQueue(void)

{return(makeList());}

const List frontQueue(const List& queue)

{

    if(isEmptyQueue(queue)){

        cerr<<"FRONT called with an empty queue "<<listString(queue)<<endl;

        exit(1);

        return(makeList());

    }

    return(car(queue));

}

const List insertfQueue(const List& queue, const List& item)

{

    if(isEmptyQueue(queue)){

        setfFrontPointer(queue,item);

    }else{

        appendf(queue,makeList(item));

    }

    return(queue);

}

   

const List deletefQueue(const List& queue)

{

    if(isEmptyQueue(queue)){

        cerr<<"DELETE! called with an empty queue "<<listString(queue)<<endl;

        exit(1);

        return(makeList());

    }

    setf(cdr(queue),queue);

    return(queue);

}

void printQueue(const List& queue)

{cout<<listString(queue);}

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

int main(int argc, char** argv)

{

    cout<<"Excersize 3.21:"<<endl;

    auto q1(makeQueue());

    printQueue(q1);cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("a")));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("b")));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("c")));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("d")));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    return(0);

}

----

出力

----

Excersize 3.21:

()

('a)

('a 'b)

('a 'b 'c)

('b 'c)

('c)

('c 'd)

('d)

()

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

可変リスト構造と問題3.12～3.14

3.2節と問題3.9～3.11はC++コードを書くわけでないので略。

環境モデルの絵はどうもわかりにくいなあ。

3.3節のリストの図は分かりやすいんだけど。

consの代入版は5章で出てくるみたいだが、

そもそも今までのconsがすでに代入版と同じ事をしているので、

ここは今までのconsでいい。

set-car!やset-cdr!によって、どこからも指されていないオブジェクトが発生しうるわけで、

lispならガベージコレクションしてくれるが、C++ではそうはいかない。

set-car!やset-cdr!については、一度Listの内部のlist<List>で、

第1要素をpop_frontしたろ、第2要素から最後までをeraseしたりしているので、

そこで参照カウント見て、浮いたオブジェクトなら消してくれるはず、だぶん。

Listのメンバ関数に代入用のをいろいろ実装した。

Listの内部表現はだいぶSchemeと違い、内部的にはstd::listなので、

普通にlistのメンバ関数を使う。難しくはないので略。

例えばappend!はlast-pair経由でなく、

Listのメンバ関数として実装したappend

（内部的にはstd::listのsplice）で別途実装。

これに伴い問題3.13は、

Schemeではポインタの循環になってしまって実行できないのはわかるが、

こちらの実装ではそうならず単に2つのリストが連結されるだけ。

ここの違いはあまり気にする必要がある気がしない。今のところは・・・。

なお問題3.12、3.14もコードだけ。

問題3.14のmysteryは破壊的reverseとでもいうべきか。

最後にvの要素がひとつ残っちゃうのが惜しい感じ。

----

void setCarInsert(const List& _listTree, const List& _newCar)

{

    const_cast<List&>(_listTree)->removeFirstElement();

    const_cast<List&>(_listTree)->addElement(_newCar);

}

void setCdrInsert(const List& _listTree, const List& _newCdr)

{

    if(!_listTree->isNull()){

        _listTree->removeExceptFirstElement();

    }

    _listTree->append(_newCdr);

}

const List appendInsert(const List& x, const List& y)

{

    x->append(y);

    return(x);

}

const List makeCycle(const List& x)

{

    x->append(x);

    return(x);

}

const List mystery(const List& x)

{

    function<List(List,List)> loop;

    loop=[&loop](const List& x, const List& y)

        {

            if(isNull(x)){return(y);}

            const auto temp(cdr(x));

            setCdrInsert(x,y);

            return(loop(temp,x));

        };

    return(loop(x,makeList()));

}

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

int main(int argc, char** argv)

{

    const auto x1(makeList(makeList("a","b"),"c","d"));

    const auto y1(makeList("e","f"));

    cout<<"x1 = "<<listString(x1)<<endl;

    cout<<"y1 = "<<listString(y1)<<endl;

    cout<<"(set-car! x1 y1)"<<endl;

    setCarInsert(x1,y1);

    cout<<"x1 = "<<listString(x1)<<endl;

    const auto x2(makeList(makeList("a","b"),"c","d"));

    const auto y2(makeList("e","f"));

    cout<<"x2 = "<<listString(x2)<<endl;

    cout<<"y2 = "<<listString(y2)<<endl;

    cout<<"(set-car! x2 y2)"<<endl;

    setCdrInsert(x2,y2);

    cout<<"x2 = "<<listString(x2)<<endl;

    cout<<endl<<"Excersize 3.12:"<<endl;

    const auto x3(makeList("a","b"));

    const auto y3(makeList("c","d"));

    cout<<"x3 = "<<listString(x3)<<endl;

    cout<<"y3 = "<<listString(y3)<<endl;

    const auto z3(append(x3,y3));

    cout<<"z3 = (append x3 y3) = "<<listString(z3)<<endl;

    cout<<"(cdr x3) = "<<listString(cdr(x3))<<endl;

    const auto w3(appendInsert(x3,y3));

    cout<<"w3 = (append! x3 y3) = "<<listString(w3)<<endl;

    cout<<"(cdr x3) = "<<listString(cdr(x3))<<endl;

    cout<<endl<<"Excersize 3.14:"<<endl;

    const auto v(makeList("a","b","c","d"));

    cout<<"v = "<<listString(v)<<endl;

    const auto w(mystery(v));

    cout<<"w = (mystery v) = "<<listString(w)<<endl;

    cout<<"v = "<<listString(v)<<endl;

   

    return(0);

}

----

出力

----

x1 = (('a 'b) 'c 'd)

y1 = ('e 'f)

(set-car! x1 y1)

x1 = (('e 'f) 'c 'd)

x2 = (('a 'b) 'c 'd)

y2 = ('e 'f)

(set-car! x2 y2)

x2 = (('a 'b) 'e 'f)

Excersize 3.12:

x3 = ('a 'b)

y3 = ('c 'd)

z3 = (append x3 y3) = ('a 'b 'c 'd)

(cdr x3) = ('b)

w3 = (append! x3 y3) = ('a 'b 'c 'd)

(cdr x3) = ('b 'c 'd)

Excersize 3.13:

z4 = (make-cycle (list 'a 'b 'c)) = ('a 'b 'c 'a 'b 'c)

Excersize 3.14:

v = ('a 'b 'c 'd)

w = (mystery v) = ('d 'c 'b 'a)

v = ('a)