てなぐさみのメモ: SCIP in C++11 ― 3.3.4節その1

事象駆動シミューレションその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

てなぐさみのメモ

目次

2012-10-05

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

0 件のコメント :

コメントを投稿