2012-09-28

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!の振る舞いはz1z2で同じになる(z2の方と同じ)
これをSICPと同じにしようと頑張ってみたがどうもうまくいかない。
そもそもこれが問題になるのかどうかよくわからないので、
先にキューや表を作ってみてから考えてみよう。

というわけで問題3.153.20はパス。


キューと問題3.21

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

キューの末尾に要素を追加する処理をΘ(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)
()

2012-09-27

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


可変リスト構造と問題3.123.14

3.2節と問題3.93.11C++コードを書くわけでないので略。
環境モデルの絵はどうもわかりにくいなあ。
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::listsplice)で別途実装。

これに伴い問題3.13は、
Schemeではポインタの循環になってしまって実行できないのはわかるが、
こちらの実装ではそうならず単に2つのリストが連結されるだけ。
ここの違いはあまり気にする必要がある気がしない。今のところは・・・。
なお問題3.123.14もコードだけ。
問題3.14mysteryは破壊的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)