てなぐさみのメモ

事象駆動シミューレションその1： デジタル回路のシミュレータその1：問題3.28、問題3.31～問題3.32

C++11の今まで動いていた部分+関数オブジェクトの代入だけ新規書き起こし（略）、

で出来るはずのコード。しかし理解し難い・・・。

何をどうしているのかを追いながら考えるからきっと理解できないんだ。

こないだみたく、どうあるべきなのかを考えて見てみよう。

で、2つのアクションリストaction-proceduresとthe-agendaが、

どうあるべきかを考えたら、意外に見えてきた。

てかそれが問題3.31のテーマか。そりゃ問題3.31の実装じゃ、

下流に変更が伝搬してくれないわな。

ただ代入が入って、自前Listの内部のstd::listを書き換えるのだが、

std::listの要素自体への直接アクセスはしないから

（publicメンバにすりゃできるけど、そりゃやり過ぎ感）、

cdrはリストの第二要素へのポインタではなく、cdrのコピーリストを返すことになるので、

例えばadd-to-agenda!内のadd-to-segments!でのinsert-queue!に

(segment-queue (car segments))（segment-queueは実は単にcdr）を渡して、

代入をやっても、コピーが書き換わるだけで、元のsegments自体は書き変わらない。

これはremove-first-agenda-item!とかでも同様。

だからcdrを書き換えたときは、あらためてset-cdr!しないといけない。

あ～面倒。

実装がちょっとだけ違う分、しっかり理解しないと動かなくて、

コードの理解は進むんだけど、随分無駄な遠回りをしている感が否めない。

代入が入ると、結局、図3.12みたいなリスト図をそのまま模した様な構造で、

自前のListを根本から作り直さないと辛いのかな・・・。

しかも疑問が噴出する。

このプログラムの振る舞い、次第書きのキューへのpropagateで実行される手続きの、

キュー内の順番への依存性があるんじゃないか？

本当にいつも正しく動くのかこれ？

まあキュー内手続きには、上流から下流への流れがあって、

その流れの順番で次第書きに入れているので、

何とかなってるようだけど・・・と思ったらそれがまさに問題3.32のテーマか。

このシミュレーションではたまたま流れが上流→下流の1次元的な流れだからいいけど、

多次元的に絡みだしたら収拾がつかなくなるなあ。

「時間」の概念が入ることでとんでもなく複雑になってきた。

ただこれはC++11がどうとかSchemeがどうとか言うことではなく本質的な問題で、

まさにSICPで問題にしたいことなのだろう。

それにしても、C++11だとそういう本質的な問題以外の、

どれが参照でどれが右辺値参照でどれが値で、

クロージャでキャプチャすべきなのはそのうちどれなのかとか、

実装上のややこしさが絡んできて、やりづらいな。

----

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

typedef function<List(List)> Wire;

const List callEach(const List& procedures)

{

if(isNull(procedures)){return(makeLeaf("done"));}

executable<List>(car(procedures))();

return(callEach(cdr(procedures)));

}

const Wire makeWireDispatch

(const List& signalValueIn,

const List& actionProceduresIn)

{

const auto signalValue(std::move(signalValueIn));

const auto actionProcedures(std::move(actionProceduresIn));

const function<List(List)> setfMySignal

=[signalValue,actionProcedures]

(const List& newValue){

if(signalValue!=newValue){

setf(signalValue,newValue);

callEach(actionProcedures);

}

return(makeLeaf("done"));

};

const function<List(List)> acceptfActionProcedure

=[actionProcedures](const List& procedure){

setf(actionProcedures,cons(procedure,actionProcedures));

return(executable<List>(procedure)());

};

const function<List(List)> dispatch

=[signalValue,setfMySignal,acceptfActionProcedure]

(const List& message)

{

if(isEq(message,makeLeaf("get-signal")))

{return(signalValue);}

if(isEq(message,makeLeaf("set-signal!")))

{return(makeLeaf(setfMySignal));}

if(isEq(message,makeLeaf("add-action!")))

{return(makeLeaf(acceptfActionProcedure));}

cerr<<"Unknown operation -- WIRE "<<listString(message)<<endl;

exit(1);

return(makeLeaf([](const List&){return(makeList());}));

};

return(dispatch);

}

const Wire makeWire(void)

{

const auto signalValueIn(makeLeaf(0));

const auto actionProceduresIn(makeList());

return(makeWireDispatch(signalValueIn,actionProceduresIn));

}

const List getSignal(const Wire& wire)

{return(wire(makeLeaf("get-signal")));}

const List setfSignal(const Wire& wire, const List& newValue)

{

return(executable<List,List>(wire(makeLeaf("set-signal!")))

(newValue));

}

const List addfAction(const Wire& wire, const List& actionProcedure)

{

return(executable<List,List>(wire(makeLeaf("add-action!")))

(actionProcedure));

}

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

const List makeTimeSegment(const List& time, const List& queue)

{return(cons(time,queue));}

//{return(makeList(time,queue));}

const List segmentTime(const List& s)

{return(car(s));}

const List segmentQueue(const List& s)

{return(cdr(s));}

const List makeAgenda(void)

{return(makeList(0));}

const List currentTime(const List& agenda)

{return(car(agenda));}

void setfCurrentTime(const List& agenda, const List& time)

{setfCar(agenda,time);}

const List segments(const List& agenda){return(cdr(agenda));}

void setfSegments(const List& agenda, const List& segments)

{setfCdr(agenda,segments);}

const List firstSegment(const List& agenda)

{return(car(segments(agenda)));}

const List restSegments(const List& agenda)

{return(cdr(segments(agenda)));}

const bool isEmptyAgenda(const List& agenda)

{return(isNull(segments(agenda)));}

void addfToAgenda

(const List& time, const List& action, const List& agenda)

{

const function<bool(List)>

isBelongsBefore=[time](const List& segments)

{return(isNull(segments)||(time<segmentTime(car(segments))));};

const function<List(List,List)>

makeNewTimeSegment=[time,action]

(const List& time, const List& action){

const List q(makeQueue());

insertfQueue(q,action);

return(makeTimeSegment(time,q));

};

function<void(List)> addfToSegments;

addfToSegments=

[&addfToSegments,&isBelongsBefore,&makeNewTimeSegment,

time,action]

(const List& segments){

if(segmentTime(car(segments))==time){

insertfQueue(car(segments),action);

}else{

const List rest(cdr(segments));

if(isBelongsBefore(rest)){

setfCdr

(segments,

cons(makeNewTimeSegment(time,action),

cdr(segments)));

}else{

addfToSegments(rest);

setfCdr(segments,rest);

}

};

const List segs(segments(agenda));

if(isBelongsBefore(segs)){

setfSegments

(agenda,cons(makeNewTimeSegment(time,action),

segs));

}else{

addfToSegments(segs);

setfCdr(agenda,segs);

}

void removefFirstAgendaItem(const List& agenda)

{

const List seg(firstSegment(agenda));

setfCdr(seg,cddr(seg));

if(isEmptyQueue(cdr(seg))){

setfSegments(agenda,(restSegments(agenda)));

}

const List firstAgendaItem(const List& agenda)

{

if(isEmptyAgenda(agenda)){

cerr<<"Agenda is Empty -- FIRST-AGENDA-ITEM"<<endl;

}

const List firstSeg(firstSegment(agenda));

setfCurrentTime(agenda,segmentTime(firstSeg));

return(frontQueue(segmentQueue(firstSeg)));

}

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

const List theAgenda(makeAgenda());

const List afterDelay(const List& delay, const List& action)

{

addfToAgenda(delay+currentTime(theAgenda),action,theAgenda);

return(makeLeaf("done"));

}

const List propagate(void)

{

if(isEmptyAgenda(theAgenda)){return(makeLeaf("done"));}

const List firstItem(firstAgendaItem(theAgenda));

executable<List>(firstItem)();

removefFirstAgendaItem(theAgenda);

return(propagate());

}

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

const List logicalNot(const List& s)

{

if(s==makeLeaf(0)){return(makeLeaf(1));}

if(s==makeLeaf(1)){return(makeLeaf(0));}

cerr<<"Invalid signal "<<listString(s)<<endl;

exit(1);

return(makeList());

}

const List logicalAnd(const List& s1, const List& s2)

{

if(s1==makeLeaf(1)&&s2==makeLeaf(1)){return(makeLeaf(1));}

if((s1==makeLeaf(1)||s1==makeLeaf(0))

&&(s2==makeLeaf(1)||s2==makeLeaf(0))){return(makeLeaf(0));}

cerr<<"Invalid signal "<<listString(s1)<<" "<<listString(s2)<<endl;

exit(1);

return(makeList());

}

const List logicalOr(const List& s1, const List& s2)

{

if(s1==makeLeaf(0) && s2==makeLeaf(0)){return(makeLeaf(0));}

if((s1==makeLeaf(1) || s1==makeLeaf(0))

&& (s2==makeLeaf(1) || s2==makeLeaf(0))){return(makeLeaf(1));}

cerr<<"Invalid signal "<<listString(s1)<<" "<<listString(s2)<<endl;

exit(1);

return(makeList());

}

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

const List inverterDelay(makeLeaf(2));

const List andGateDelay(makeLeaf(3));

const List orGateDelay(makeLeaf(5));

const List probe(const string name, const Wire& wireIn)

{

const auto wire(std::move(wireIn));

return(addfAction

(wire,

makeLeaf

(function<List(void)>

([name,wire](void){

cout<<name<<" "

<<listString(currentTime(theAgenda))

<<" New-value = "

<<listString(getSignal(wire))<<endl;

return(makeLeaf("OK"));

}))));

}

const List inverter(const Wire& inputIn, const Wire& outputIn)

{

const auto input(std::move(inputIn));

const auto output(std::move(outputIn));

const function<List(void)> invertInput

=[input,output](void){

const List newValue(logicalNot(getSignal(input)));

afterDelay(inverterDelay,

makeLeaf

(function<List(void)>

([output,newValue](void)

{return(setfSignal(output,newValue));})));

return(makeLeaf("done"));

};

addfAction(input,makeLeaf(invertInput));

return(makeLeaf("OK"));

}

const List andGate

(const Wire& a1In, const Wire& a2In, const Wire& outputIn)

{

const auto a1(std::move(a1In));

const auto a2(std::move(a2In));

const auto output(std::move(outputIn));

const function<List(void)> andActionProcedure

=[a1,a2,output](void){

const List newValue(logicalAnd(getSignal(a1),getSignal(a2)));

afterDelay(andGateDelay,

makeLeaf

(function<List(void)>

([output,newValue](void)

{return(setfSignal(output,newValue));})));

return(makeLeaf("done"));

};

addfAction(a1,makeLeaf(andActionProcedure));

addfAction(a2,makeLeaf(andActionProcedure));

return(makeLeaf("OK"));

}

const List orGate

(const Wire& a1In, const Wire& a2In, const Wire& outputIn)

{

const auto a1(std::move(a1In));

const auto a2(std::move(a2In));

const auto output(std::move(outputIn));

const function<List(void)> orActionProcedure

=[a1,a2,output](void){

const List newValue(logicalOr(getSignal(a1),getSignal(a2)));

afterDelay(orGateDelay,

makeLeaf

(function<List(void)>

([output,newValue](void)

{return(setfSignal(output,newValue));})));

return(makeLeaf("done"));

};

addfAction(a1,makeLeaf(orActionProcedure));

addfAction(a2,makeLeaf(orActionProcedure));

return(makeLeaf("OK"));

}

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

const List halfAdder

(const Wire& a, const Wire& b, const Wire& sum, const Wire& carry)

{

const auto d(makeWire());

const auto e(makeWire());

orGate(a,b,d);

andGate(a,b,carry);

inverter(carry,e);

andGate(d,e,sum);

return(makeLeaf("OK"));

}

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

int main(int argc, char** argv)

{

cout<<"Excersize 3.28:"<<endl;

const auto input1(makeWire());

const auto input2(makeWire());

const auto sum(makeWire());

const auto carry(makeWire());

probe("sum",sum);

probe("carry",carry);

halfAdder(input1,input2,sum,carry);

setfSignal(input1,makeLeaf(1));

propagate();

setfSignal(input2,makeLeaf(1));

propagate();

return(0);

}

----

出力

----

Excersize 3.28:

sum 0 New-value = 0

carry 0 New-value = 0

sum 8 New-value = 1

carry 11 New-value = 1

sum 16 New-value = 0

局所表の表現・透過性テストの選択と表の多次元化：問題3.24～問題3.25（3.25は難儀中）

2章で重要な役割を果たしたget,putの、

メッセージパッシング実装。

問題3.24までは問題なし。

だが問題3.25がうまくいかない。

lookupとinsert!が再帰クロージャにならないといけないのだが、

再帰が入ると、クロージャが自分自身への参照をキャプチャして、

かつクロージャの関数オブジェクトを保持し続ける、

ということが出来なければならない。

が、キャプチャするのが関数オブジェクトの参照で、その参照元は、

宣言したところの寿命が尽きると死ぬから、2つの条件が両立しない・・・

関数オブジェクトをわざわざ別関数のスタックに入れて右辺値参照するとか、

いろいろやってみたがうまくいかない。

再帰でないなら難しくないのだけど。

大域変数にするとか、全然関係ない場所に保持させるとかっていう手は、

危険だし使いものにならないから使いたくないし・・・。

そろそろC++でやる限界が近づいてきたか？

せめて回路シミュレータはやりたいので、とりあえずそちらに行ってみる。

----

typedef function<List(List)> Table;

const List associate

(const List& key, const List& records,

const function<bool(List,List)>& isSameKey)

{

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

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

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

}

const Table makeTableDispatch

(const List& initialTable,

const function<bool(List,List)>& isSameKeyIn)

{

const auto localTable(std::move(initialTable));

const auto isSameKey(std::move(isSameKeyIn));

function<List(List,List)> lookup;

lookup=[isSameKey,lookup]

(const List& keyList,const List& table){

if(isNull(keyList)){

cerr<<"no match --- LOOKUP"<<endl;

return(makeList());

}

const auto subtable(associate(car(keyList),cdr(table),isSameKey));

if(!isNull(subtable)){

const auto record(associate(cadr(keyList),cdr(subtable),isSameKey));

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

return(makeList());

}

return(makeList());

};

function<List(List,List)> insertf;

insertf=[localTable,isSameKey,insertf]

(const List& keyList, const List& value){

const auto subtable(associate(car(keyList),cdr(localTable),isSameKey));

if(!isNull(subtable)){

const auto record(associate(cadr(keyList),cdr(subtable),isSameKey));

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

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

}else{

setfCdr(localTable,cons(makeList(car(keyList),cons(cadr(keyList),value)),cdr(localTable)));

}

return(makeLeaf("insert"));

};

const function<string(void)> getTableString

=[localTable](void){return(listString(localTable));};

const Table dispatch

=[localTable,lookup,insertf,getTableString](const List& message){

if(isEq(message,makeLeaf("lookup-proc")))

{return

(makeLeaf

(function<List(List)>

([lookup,localTable](const List& keyList){

return(lookup(keyList,localTable));})));

}

if(isEq(message,makeLeaf("insert-proc!")))

{return(makeLeaf(insertf));}

if(isEq(message,makeLeaf("table-string")))

{return(makeLeaf(getTableString));}

cerr<<"Unknown operation --- TABLE"<<endl;

exit(1);

return(makeList());

};

return(dispatch);

}

const Table makeTable(const function<bool(List,List)>& isSameKey)

{return(makeTableDispatch(makeList("*table*"),isSameKey));}

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

const Table operationTable

(makeTable(function<bool(List,List)>(isEqual<List>)));

const List get(const List& keyList)

{

return(executable<List,List>

(operationTable(makeLeaf("lookup-proc")))(keyList));

}

const List put(const List& keyList, const List& value)

{

return(executable<List,List,List>

(operationTable(makeLeaf("insert-proc!")))

(keyList, value));

}

const string getTableString(void)

{

return(executable<string>

(operationTable(makeLeaf("table-string")))());

}

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

int main(int argc, char** argv)

{

cout<<"Excersize 3.24:"<<endl;

put(makeList(makeLeaf("math"),makeLeaf("+")),makeLeaf(43));

cout<<"(put 'math '+ 43): operation-table="<<getTableString()<<endl;

put(makeList(makeLeaf("math"),makeLeaf("-")),makeLeaf(45));

cout<<"(put 'math '- 45): operation-table="<<getTableString()<<endl;

put(makeList(makeLeaf("math"),makeLeaf("*")),makeLeaf(42));

cout<<"(put 'math '* 42): operation-table="<<getTableString()<<endl;

put(makeList(makeLeaf("letters"),makeLeaf("a")),makeLeaf(97));

cout<<"(put 'letters 'a 97): operation-table="<<getTableString()<<endl;

put(makeList(makeLeaf("letters"),makeLeaf("b")),makeLeaf(98));

cout<<"(put 'letters 'b 98): operation-table="<<getTableString()<<endl;

cout<<"(get 'math '*) = "

<<listString(get(makeList(makeLeaf("math"),makeLeaf("*"))))<<endl;

return(0);

}

----

出力

----

Excersize 3.24:

(put 'math '+ 43): operation-table=('*table* ('math ('+ 43)))

(put 'math '- 45): operation-table=('*table* ('math ('- 45) ('+ 43)))

(put 'math '* 42): operation-table=('*table* ('math ('* 42) ('- 45) ('+ 43)))

(put 'letters 'a 97): operation-table=('*table* ('letters ('a 97)) ('math ('* 42) ('- 45) ('+ 43)))

(put 'letters 'b 98): operation-table=('*table* ('letters ('b 98) ('a 97)) ('math ('* 42) ('- 45) ('+ 43)))

(get 'math '*) = 42

てなぐさみのメモ

目次

2012-10-05

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

2012-10-02

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