11.3 高度な例 : 離散イベントシミュレーション(Extended Example: Discrete Event Simulation)

代入と高階関数がどのように興味深い形で結びつくか、例をとおして考えます。ここでは、デジタル回路シミュレータを構築します。

この例は Abelson と Sussman の本[ASS96]から借りました。彼らの基本的な (Scheme の) コードを、継承でコードを再利用できるオブジェクト指向によって拡張しています。この例は、一般的な離散イベントのシミュレーションプログラムが、どのように構造化され構築されるかも示します。

デジタル回路を記述する小さな言語から始めます。デジタル回路は 結線 と function box から構築されます。結線は信号を運び、function box は信号を変換します。信号は ture と false の真偽値で表現します。

次は基本的な function box です。

• • インバーター : 信号を反転します。

  • AND ゲート : 入力の論理積を出力に設定します。

  • OR ゲート : 入力の論理和を出力に設定します。

ほかの function box は、これらの組み合わせで作れます。 ゲートには 遅延 があり、ゲートの出力変化は、入力からいくらか時間が経ってから起きます。

デジタル回路用言語 デジタル回路の要素を、次の Scala クラスと関数によって記述します。まず、結線を表す Wire クラスです。結線は次のようにして生成できます。

val a = new Wire val b = new Wire val c = new Wire

次に、手続きです。

def inverter(input: Wire, output: Wire) def andGate(a1: Wire, a2: Wire, output: Wire) def orGate(o1: Wire, o2: Wire, output: Wire)

これらの手続きは、われわれが必要とする基本ゲートを (副作用として)「作成」します。これらを使ってもっと複雑な 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) }

この抽象化は、それ自体で使用できます。たとえば、全加算器の定義で

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) }

このようにして、クラス Wire および関数 inverter、andGate、orGate は、ユーザーがデジタル回路を定義できる小さな言語を表現しています。では、回路をシミュレートできるように、このクラスと関数群に実装を与えましょう。実装は、離散イベントシミュレーション用のシンプルで一般的な API に基づきます。

シミュレーション API 離散イベントシミュレーションは、ユーザーが定義した アクション を指定された 時刻 に実行します。 アクション は、パラメータをとらず Unit を返す関数として表されます。

type Action = () => Unit

時刻 はシミュレーション上のものであり、「壁時計」が指す現実の時刻ではありません。 具体的なシミュレーションは、抽象クラス Simulation を継承したオブジェクトの内部で行われます。このクラスは次のシグネチャを持ちます。

abstract class Simulation { def currentTime: Int def afterDelay(delay: Int, action: => Action) def run() }

currentTime は、現在のシミュレーション上の時刻を整数値として返します。afterDelay は、currentTime から指定された時間が経過したときにアクションが実行されるよう、スケジュールします。run は、実行するアクションがなくなるまでシミュレーションを実行します。

結線クラス 結線は３つの基本的なアクションをサポートする必要があります。 ・getSignal : 結線の現在の信号を返します。 ・setSignal(sig:Boolean) : 結線の信号を sig に更新します。 ・addAction(p:Action) : 指定された手続き p を結線の アクション に付加します。結線の信号が変更されるたびに、付加されたすべてのアクション手続きを実行します。

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() } }

２つのプライベート変数が結線の状態を作り上げます。変数 sigVal は結線の現在の信号を表し、変数 actions は現在結線に付加されているアクション手続きを表します。

インバータクラス インバータ(Not 回路)を、入力の結線にアクションをインストールすることで実装します。アクションは入力信号を反転して出力信号とします。アクションが効果を現すのは、入力が変化してからシミュレーション時間 InverterDelay 経過後でなくてはなりません。以上より、次の実装が導かれます。

def inverter(input: Wire, output: Wire) { def invertAction() { val inputSig = input.getSignal afterDelay(InverterDelay) { output setSignal !inputSig } } input addAction invertAction }

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 }

演習 11.3.1 OR ゲートの実装を書きなさい

演習 11.3.2 OR ゲートの別の定義方法として、インバーターと AND ゲートを組み合わせる方法があります。関数 orGate を、andGate とinverter を使って定義しなさい。また、この関数の遅延(delay)時間は？

シミュレーションクラス さあ、あとは 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()

また、プライベート変数 curtime によって、シミュレーション上の時刻を追跡します。

private var curtime = 0

メソッド 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) }

メソッド 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() }

シミュレータの実行 シミュレータを走らせる前に、結線上の信号変化を追跡する方法を用意します。そのための関数 probe を書きます。

def probe(name: String, wire: Wire) { wire addAction { println(name + " " + currentTime + " new_value = " + wire.getSignal) } }

さあ、シミュレータを動かします。まず、４つの結線を定義し、そのうちの二つに 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

半加算器の回路を定義してみましょう。

scala> halfAdder(input1, input2, sum, carry)

最後に、２つの入力結線の信号を順番に 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