「Example11.3」の編集履歴（バックアップ）一覧はこちら
Example11.3 - (2009/08/22 (土) 01:15:49) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
**11.3 Extended Example: Discrete Event Simulation
We now discuss an example that demonstrates how assignments and higher-order functions can be combined in interesting ways. We will build a simulator for digital circuits.
代入と高階関数がどのように興味深い形で結合するのか、例を通じて考えます。ここでは、デジタル回路シミュレータを構築します。
The example is taken from Abelson and Sussman’s book [ASS96]. We augment their basic (Scheme-) code by an object-oriented structure which allows code-reuse through inheritance. The example also shows how discrete event simulation programs in general are structured and built.
We start with a little language to describe digital circuits. A digital circuit is built from wires and function boxes. Wires carry signals which are transformed by function boxes. We will represent signals by the booleans true and false.
この例はAbelsonとSussmanの本[ASS96]から借りました。彼らの基本的な(Schemeの)コードを、継承でコード再利用を可能にするオブジェクト指向の構造によって拡張します。この例は、一般的な離散イベントのシミュレーションプログラムが、どのように構成され構築されるかも示します。デジタル回路を記述する小さな言語から始めます。デジタル回路は結線とfunction boxから構築されます。結線は信号を運び、function boxは信号を変換します。信号はtureとfalseの真偽値で表現します。
Basic function boxes (or: gates) are:
以下が基本的なfunction boxです。
- An inverter, which negates its signal
- An and-gate, which sets its output to the conjunction of its input.
- An or-gate, which sets its output to the disjunction of its input.
- インバーター。信号を反転します。
- ANDゲート。入力の論理積を出力に設定します
- ORゲート。入力の論理和を出力に設定します
Other function boxes can be built by combining basic ones.
Gates have delays, so an output of a gate will change only some time after its inputs change.
ほかのfunction boxは、これらの組み合わせで構築できます。
ゲートには遅延があり、ゲートの出力の変化は、入力からいくらかの時間が経過してから起きます。
''A Language for Digital Circuits.'' We describe the elements of a digital circuit by the following set of Scala classes and functions.
First, there is a class Wire for wires. We can construct wires as follows.
''デジタル回路用言語'' デジタル回路の要素を以下のScalaのクラスと関数によって記述します。まず、結線を表すWireクラスです。結線は以下のようにして生成できます。
val a = new Wire
val b = new Wire
val c = new Wire
Second, there are procedures
次に以下の手続きです。
def inverter(input: Wire, output: Wire)
def andGate(a1: Wire, a2: Wire, output: Wire)
def orGate(o1: Wire, o2: Wire, output: Wire)
which “make” the basic gates we need (as side-effects). More complicated function boxes can now be built from these. For instance, to construct a half-adder, we can define:
これらの手続きは、われわれが必要とする基本ゲートを（副作用として）「作成」します。これらを使用してもっと複雑なfunction boxを構築できます。たとえば半加算器を生成するのに、このような定義ができます：
def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) {
val d = new Wire
val e = new Wire
orGate(a, b, d)
andGate(a, b, c)
inverter(c, e)
andGate(d, e, s)
}
This abstraction can itself be used, for instance in defining a full adder:
この抽象化はそれ自体で使用できます。たとえば、全加算器の定義で：
def fullAdder(a: Wire, b: Wire, cin: Wire, sum: Wire, cout: Wire) {
val s = new Wire
val c1 = new Wire
val c2 = new Wire
halfAdder(a, cin, s, c1)
halfAdder(b, s, sum, c2)
orGate(c1, c2, cout)
}
Class Wire and functions inverter, andGate, and orGate represent thus a little language in which users can define digital circuits. We now give implementations of this class and these functions, which allow one to simulate circuits. These implementations are based on a simple and general API for discrete event simulation.
このようにして、Wireクラスおよび関数inverter, andGate, orGateによって、ユーザーがデジタル回路を定義するのに使用できる小さな言語を表します。では、回路のシミュレーションを実行できるように、このクラスと関数達の実装を与えましょう。これらの実装は、シンプルで一般的な、離散イベントのシミュレーション用APIに基づいています。
''The Simulation API.'' Discrete event simulation performs user-defined actions at specified times. An action is represented as a function which takes no parameters and returns a Unit result:
''シミュレーションAPI'' 離散イベントシミュレーションは、ユーザが定義した'アクション'を指定された'時刻'に実行します。'アクション'は、引数を取らず返値がUnitである関数によって表されます:
type Action = () => Unit
The time is simulated; it is not the actual “wall-clock” time.
A concrete simulation will be done inside an object which inherits from the abstract Simulation class. This class has the following signature:
'時刻'はシミュレーション上の物であり、「壁時計」が指す現実の時刻ではありません。
具体的なシミュレーションは、抽象クラスSimulationを継承したオブジェクトの内部で行われます。このクラスは以下のシグニチャを持ちます:
abstract class Simulation {
def currentTime: Int
def afterDelay(delay: Int, action: => Action)
def run()
}
Here, currentTime returns the current simulated time as an integer number, afterDelay schedules an action to be performed at a specified delay after currentTime, and run runs the simulation until there are no further actions to be performed.
currentTimeは、現在のシミュレーション上の時刻を整数値として返します。afterDelayは、currentTimeから指定された時間が経過したときに'アクション'が実行されるようスケジュールします。runは、実行する'アクション'がなくなるまでシミュレーションを実行します。
''The Wire Class.'' A wire needs to support three basic actions.
- getSignal: Boolean returns the current signal on the wire.
- setSignal(sig: Boolean) sets the wire’s signal to sig.
- addAction(p: Action) attaches the specified procedure p to the actions of the wire. All attached action procedures will be executed every time the signal of a wire changes.
結線は3つの基本的なアクションをサポートする必要があります。
・その結線の現在の信号を返します。
・その結線の信号をsigに更新します
・指定された手続きpをその結線の'アクション'に付加します。その結線の信号が変更されるたびに、付加されたすべてのアクション手続きが実行されます
Here is an implementation of the Wire class:
Wireクラスの実装例を示します。
class Wire {
private var sigVal = false
private var actions: List[Action] = List()
def getSignal = sigVal
def setSignal(s: Boolean) =
if (s != sigVal) {
sigVal = s
actions.foreach(action => action())
}
def addAction(a: Action) {
actions = a :: actions; a()
}
}
Two private variablesmake up the state of a wire. The variable sigVal represents the current signal, and the variable actions represents the action procedures currently attached to the wire.
ふたつのプライベート変数が結線の状態です。変数sigValは結線の現在の信号を表し、変数actionsが現在結線に付加されているアクション手続きを表します。
''The Inverter Class.'' We implement an inverter by installing an action on its input wire, namely the action which puts the negated input signal onto the output signal. The action needs to take effect at InverterDelay simulated time units after the input changes. This suggests the following implementation:
''インバータークラス'' インバーターを、入力の結線のアクションを導入する事で実装します。アクションは、出力信号を入力信号の反転させたものにします。アクションは、InverterDelayのシミュレーション時間単位の経過後に実行される必要があります。これにより、以下の実装が導かれます。
def inverter(input: Wire, output: Wire) {
def invertAction() {
val inputSig = input.getSignal
afterDelay(InverterDelay) { output setSignal !inputSig }
}
input addAction invertAction
}
''The And-Gate Class.'' And-gates are implemented analogously to inverters. The action of an andGate is to output the conjunction of its input signals. This should happen at AndGateDelay simulated time units after any one of its two inputs changes. Hence, the following implementation:
''ANDゲートクラス'' ANDゲートは、インバーターの類推で実装できます。andGateのアクションは、入力信号の論理積を出力する事です。それは、ふたつの入力のいずれかが変更されたら、AndGateDelayのシミュレーション時間単位の経過後に実行される必要があります。実装は以下のようになります。
def andGate(a1: Wire, a2: Wire, output: Wire) {
def andAction() {
val a1Sig = a1.getSignal
val a2Sig = a2.getSignal
afterDelay(AndGateDelay) { output setSignal (a1Sig & a2Sig) }
}
a1 addAction andAction
a2 addAction andAction
}
''Exercise 11.3.1'' Write the implementation of orGate.
''演習 11.3.1'' ORゲートの実装を書きなさい
''Exercise 11.3.2'' Another way is to define an or-gate by a combination of inverters and and gates. Define a function orGate in terms of andGate and inverter. What is the delay time of this function?
''演習 11.3.2'' ORゲートのほかの定義の方法として、インバーターとANDゲートの組み合わせを用いる方法があります。関数orGateを、andGateとinverterを利用して定義しなさい。また、この関数の遅延(delay)時間は？
''The Simulation Class.'' Now, we just need to implement class Simulation, and we are done. The idea is that we maintain inside a Simulation object an agenda of actions to perform. The agenda is represented as a list of pairs of actions and the times they need to be run. The agenda list is sorted, so that earlier actions come before later ones.
さあ、あとはSimulationクラスを実装すればできあがりです。考え方は、我々がSimulationオブジェクト'agenda'の内部の面倒を見てアクションを実行してやるという物です。agendaはアクションと実行されるべき時刻のペアのリストとして表現されます。agendaリストは実行されるべき時刻でソートして、早い物が先にくるようにします。
abstract class Simulation {
case class WorkItem(time: Int, action: Action)
private type Agenda = List[WorkItem]
private var agenda: Agenda = List()
There is also a private variable curtime to keep track of the current simulated time.
また、プライベート変数curtimeによって、シミュレーション上の時刻を追跡します。
private var curtime = 0
An application of the method afterDelay(delay, block) inserts the element WorkItem(currentTime + delay, () => block) into the agenda list at the appropriate place.
メソッドafterDelay(delay, block)を適用すると、要素WorkItem(currentTime + delay, () => block)をagendaのリストの適切な場所に挿入するようにします。
private def insert(ag: Agenda, item: WorkItem): Agenda =
if (ag.isEmpty || item.time < ag.head.time) item :: ag
else ag.head :: insert(ag.tail, item)
def afterDelay(delay: Int)(block: => Unit) {
val item = WorkItem(currentTime + delay, () => block)
agenda = insert(agenda, item)
}
An application of the run method removes successive elements fromthe agenda and performs their actions. It continues until the agenda is empty:
メソッドrunを適用すると、agendaから要素が取り除かれてそのアクションが実行される、というのが繰り返されます。それは、agendaが空になるまで続きます。
private def next() {
agenda match {
case WorkItem(time, action) :: rest =>
agenda = rest; curtime = time; action()
case List() =>
}
}
def run() {
afterDelay(0) { println("*** simulation started ***") }
while (!agenda.isEmpty) next()
}
''Running the Simulator.'' To run the simulator, we still need a way to inspect changes of signals on wires. To this purpose, we write a function probe.
''シミュレーターの実行'' シミュレーターを走らせる前に、各結線の信号の変化を追跡する方法を用意しましょう。この目的のため、関数probeを書きます。
def probe(name: String, wire: Wire) {
wire addAction {
println(name + " " + currentTime + " new_value = " + wire.getSignal)
}
}
Now, to see the simulator in action, let’s define four wires, and place probes on two of them:
さあ、シミュレーターを動かします。まず、四つの結線を定義して、そのうち二つにprobeをセットしましょう。
scala> val input1, input2, sum, carry = new Wire
scala> probe("sum", sum)
sum 0 new_value = false
scala> probe("carry", carry)
carry 0 new_value = false
Now let’s define a half-adder connecting the wires:
半加算器の回路を定義してみましょう。
scala> halfAdder(input1, input2, sum, carry)
Finally, set one after another the signals on the two input wires to true and run the simulation.
最後に、ふたつの入力結線の信号を順番に'true'にセットして、シミュレーターを走らせましょう。
scala> input1 setSignal true; run
*** simulation started ***
sum 8 new_value = true
scala> input2 setSignal true; run
carry 11 new_value = true
sum 15 new_value = false
**11.3 Extended Example: Discrete Event Simulation
We now discuss an example that demonstrates how assignments and higher-order functions can be combined in interesting ways. We will build a simulator for digital circuits.
代入と高階関数がどのように興味深い形で結合するのか、例を通じて考えます。ここでは、デジタル回路シミュレータを構築します。
The example is taken from Abelson and Sussman’s book [ASS96]. We augment their basic (Scheme-) code by an object-oriented structure which allows code-reuse through inheritance. The example also shows how discrete event simulation programs in general are structured and built.
We start with a little language to describe digital circuits. A digital circuit is built from wires and function boxes. Wires carry signals which are transformed by function boxes. We will represent signals by the booleans true and false.
この例はAbelsonとSussmanの本[ASS96]から借りました。彼らの基本的な(Schemeの)コードを、継承でコード再利用を可能にするオブジェクト指向の構造によって拡張します。この例は、一般的な離散イベントのシミュレーションプログラムが、どのように構成され構築されるかも示します。デジタル回路を記述する小さな言語から始めます。デジタル回路は結線とfunction boxから構築されます。結線は信号を運び、function boxは信号を変換します。信号はtureとfalseの真偽値で表現します。
Basic function boxes (or: gates) are:
以下が基本的なfunction boxです。
- An inverter, which negates its signal
- An and-gate, which sets its output to the conjunction of its input.
- An or-gate, which sets its output to the disjunction of its input.
- インバーター。信号を反転します。
- ANDゲート。入力の論理積を出力に設定します
- ORゲート。入力の論理和を出力に設定します
Other function boxes can be built by combining basic ones.
Gates have delays, so an output of a gate will change only some time after its inputs change.
ほかのfunction boxは、これらの組み合わせで構築できます。
ゲートには遅延があり、ゲートの出力の変化は、入力からいくらかの時間が経過してから起きます。
''A Language for Digital Circuits.'' We describe the elements of a digital circuit by the following set of Scala classes and functions.
First, there is a class Wire for wires. We can construct wires as follows.
''デジタル回路用言語'' デジタル回路の要素を以下のScalaのクラスと関数によって記述します。まず、結線を表すWireクラスです。結線は以下のようにして生成できます。
val a = new Wire
val b = new Wire
val c = new Wire
Second, there are procedures
次に以下の手続きです。
def inverter(input: Wire, output: Wire)
def andGate(a1: Wire, a2: Wire, output: Wire)
def orGate(o1: Wire, o2: Wire, output: Wire)
which “make” the basic gates we need (as side-effects). More complicated function boxes can now be built from these. For instance, to construct a half-adder, we can define:
これらの手続きは、われわれが必要とする基本ゲートを（副作用として）「作成」します。これらを使用してもっと複雑なfunction boxを構築できます。たとえば半加算器を生成するのに、このような定義ができます：
def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) {
val d = new Wire
val e = new Wire
orGate(a, b, d)
andGate(a, b, c)
inverter(c, e)
andGate(d, e, s)
}
This abstraction can itself be used, for instance in defining a full adder:
この抽象化はそれ自体で使用できます。たとえば、全加算器の定義で：
def fullAdder(a: Wire, b: Wire, cin: Wire, sum: Wire, cout: Wire) {
val s = new Wire
val c1 = new Wire
val c2 = new Wire
halfAdder(a, cin, s, c1)
halfAdder(b, s, sum, c2)
orGate(c1, c2, cout)
}
Class Wire and functions inverter, andGate, and orGate represent thus a little language in which users can define digital circuits. We now give implementations of this class and these functions, which allow one to simulate circuits. These implementations are based on a simple and general API for discrete event simulation.
このようにして、Wireクラスおよび関数inverter, andGate, orGateによって、ユーザーがデジタル回路を定義するのに使用できる小さな言語を表します。では、回路のシミュレーションを実行できるように、このクラスと関数達の実装を与えましょう。これらの実装は、シンプルで一般的な、離散イベントのシミュレーション用APIに基づいています。
''The Simulation API.'' Discrete event simulation performs user-defined actions at specified times. An action is represented as a function which takes no parameters and returns a Unit result:
''シミュレーションAPI'' 離散イベントシミュレーションは、ユーザが定義した'アクション'を指定された'時刻'に実行します。'アクション'は、引数を取らず返値がUnitである関数によって表されます:
type Action = () => Unit
The time is simulated; it is not the actual “wall-clock” time.
A concrete simulation will be done inside an object which inherits from the abstract Simulation class. This class has the following signature:
'時刻'はシミュレーション上の物であり、「壁時計」が指す現実の時刻ではありません。
具体的なシミュレーションは、抽象クラスSimulationを継承したオブジェクトの内部で行われます。このクラスは以下のシグニチャを持ちます:
abstract class Simulation {
def currentTime: Int
def afterDelay(delay: Int, action: => Action)
def run()
}
Here, currentTime returns the current simulated time as an integer number, afterDelay schedules an action to be performed at a specified delay after currentTime, and run runs the simulation until there are no further actions to be performed.
currentTimeは、現在のシミュレーション上の時刻を整数値として返します。afterDelayは、currentTimeから指定された時間が経過したときに'アクション'が実行されるようスケジュールします。runは、実行する'アクション'がなくなるまでシミュレーションを実行します。
''The Wire Class.'' A wire needs to support three basic actions.
- getSignal: Boolean returns the current signal on the wire.
- setSignal(sig: Boolean) sets the wire’s signal to sig.
- addAction(p: Action) attaches the specified procedure p to the actions of the wire. All attached action procedures will be executed every time the signal of a wire changes.
結線は3つの基本的なアクションをサポートする必要があります。
・その結線の現在の信号を返します。
・その結線の信号をsigに更新します
・指定された手続きpをその結線の'アクション'に付加します。その結線の信号が変更されるたびに、付加されたすべてのアクション手続きが実行されます
Here is an implementation of the Wire class:
Wireクラスの実装例を示します。
class Wire {
private var sigVal = false
private var actions: List[Action] = List()
def getSignal = sigVal
def setSignal(s: Boolean) =
if (s != sigVal) {
sigVal = s
actions.foreach(action => action())
}
def addAction(a: Action) {
actions = a :: actions; a()
}
}
Two private variablesmake up the state of a wire. The variable sigVal represents the current signal, and the variable actions represents the action procedures currently attached to the wire.
ふたつのプライベート変数が結線の状態です。変数sigValは結線の現在の信号を表し、変数actionsが現在結線に付加されているアクション手続きを表します。
''The Inverter Class.'' We implement an inverter by installing an action on its input wire, namely the action which puts the negated input signal onto the output signal. The action needs to take effect at InverterDelay simulated time units after the input changes. This suggests the following implementation:
''インバータークラス'' インバーターを、入力の結線のアクションを導入する事で実装します。アクションは、出力信号を入力信号の反転させたものにします。アクションは、InverterDelayのシミュレーション時間単位の経過後に実行される必要があります。これにより、以下の実装が導かれます。
def inverter(input: Wire, output: Wire) {
def invertAction() {
val inputSig = input.getSignal
afterDelay(InverterDelay) { output setSignal !inputSig }
}
input addAction invertAction
}
''The And-Gate Class.'' And-gates are implemented analogously to inverters. The action of an andGate is to output the conjunction of its input signals. This should happen at AndGateDelay simulated time units after any one of its two inputs changes. Hence, the following implementation:
''ANDゲートクラス'' ANDゲートは、インバーターの類推で実装できます。andGateのアクションは、入力信号の論理積を出力する事です。それは、ふたつの入力のいずれかが変更されたら、AndGateDelayのシミュレーション時間単位の経過後に実行される必要があります。実装は以下のようになります。
def andGate(a1: Wire, a2: Wire, output: Wire) {
def andAction() {
val a1Sig = a1.getSignal
val a2Sig = a2.getSignal
afterDelay(AndGateDelay) { output setSignal (a1Sig & a2Sig) }
}
a1 addAction andAction
a2 addAction andAction
}
''Exercise 11.3.1'' Write the implementation of orGate.
''演習 11.3.1'' ORゲートの実装を書きなさい
''Exercise 11.3.2'' Another way is to define an or-gate by a combination of inverters and and gates. Define a function orGate in terms of andGate and inverter. What is the delay time of this function?
''演習 11.3.2'' ORゲートのほかの定義の方法として、インバーターとANDゲートの組み合わせを用いる方法があります。関数orGateを、andGateとinverterを利用して定義しなさい。また、この関数の遅延(delay)時間は？
''The Simulation Class.'' Now, we just need to implement class Simulation, and we are done. The idea is that we maintain inside a Simulation object an agenda of actions to perform. The agenda is represented as a list of pairs of actions and the times they need to be run. The agenda list is sorted, so that earlier actions come before later ones.
さあ、あとはSimulationクラスを実装すればできあがりです。考え方は、我々がSimulationオブジェクト'agenda'の内部の面倒を見てアクションを実行してやるという物です。agendaはアクションと実行されるべき時刻のペアのリストとして表現されます。agendaリストは実行されるべき時刻でソートして、早い物が先にくるようにします。
abstract class Simulation {
case class WorkItem(time: Int, action: Action)
private type Agenda = List[WorkItem]
private var agenda: Agenda = List()
There is also a private variable curtime to keep track of the current simulated time.
また、プライベート変数curtimeによって、シミュレーション上の時刻を追跡します。
private var curtime = 0
An application of the method afterDelay(delay, block) inserts the element WorkItem(currentTime + delay, () => block) into the agenda list at the appropriate place.
メソッドafterDelay(delay, block)を適用すると、要素WorkItem(currentTime + delay, () => block)をagendaのリストの適切な場所に挿入するようにします。
private def insert(ag: Agenda, item: WorkItem): Agenda =
if (ag.isEmpty || item.time < ag.head.time) item :: ag
else ag.head :: insert(ag.tail, item)
def afterDelay(delay: Int)(block: => Unit) {
val item = WorkItem(currentTime + delay, () => block)
agenda = insert(agenda, item)
}
An application of the run method removes successive elements fromthe agenda and performs their actions. It continues until the agenda is empty:
メソッドrunを適用すると、agendaから要素が取り除かれてそのアクションが実行される、というのが繰り返されます。それは、agendaが空になるまで続きます。
private def next() {
agenda match {
case WorkItem(time, action) :: rest =>
agenda = rest; curtime = time; action()
case List() =>
}
}
def run() {
afterDelay(0) { println("*** simulation started ***") }
while (!agenda.isEmpty) next()
}
''Running the Simulator.'' To run the simulator, we still need a way to inspect changes of signals on wires. To this purpose, we write a function probe.
''シミュレーターの実行'' シミュレーターを走らせる前に、各結線の信号の変化を追跡する方法を用意しましょう。この目的のため、関数probeを書きます。
def probe(name: String, wire: Wire) {
wire addAction {
println(name + " " + currentTime + " new_value = " + wire.getSignal)
}
}
Now, to see the simulator in action, let’s define four wires, and place probes on two of them:
さあ、シミュレーターを動かします。まず、四つの結線を定義して、そのうち二つにprobeをセットしましょう。
scala> val input1, input2, sum, carry = new Wire
scala> probe("sum", sum)
sum 0 new_value = false
scala> probe("carry", carry)
carry 0 new_value = false
Now let’s define a half-adder connecting the wires:
半加算器の回路を定義してみましょう。
scala> halfAdder(input1, input2, sum, carry)
Finally, set one after another the signals on the two input wires to true and run the simulation.
最後に、ふたつの入力結線の信号を順番に'true'にセットして、シミュレーターを走らせましょう。
scala> input1 setSignal true; run
*** simulation started ***
sum 8 new_value = true
scala> input2 setSignal true; run
carry 11 new_value = true
sum 15 new_value = false
----
#comment
