Sunday, September 13, 2009

SICP digital circuit simulator in scala Part I

This is a scala port of digital circuit simulator of section 3.3.4 in SICP. Martin Odersky has done same in Chapter-18(Stateful Objects) in his book Programming in Scala. Before reading his code, I wanted to write it on my own so that I can understand where I don't think *in scala* when writing code in Scala.
Next, I'll read the same port from mentioned scala book and see what I can learn from the differences.

Here is my code(I tested it on Scala version 2.7.5.final interpreter)...

//Segment and Agenda
import scala.collection.mutable.Queue
case class Segment(val time:Int,
val queue:Queue[()=>Unit]) extends Ordered[Segment] {
require(time >= 0)

override def compare(that:Segment) = {
if(that.time == time) 0
else if(that.time < time) -1
else 1
}
}

import scala.collection.mutable.PriorityQueue
class Agenda {
private var currentTime = 0
private val timeSegments = new PriorityQueue[Segment]()

def getCurrentTime = currentTime

def addItem(time:Int, item:()=>Unit) {
getTimeSegment(time) match {
case None =>
val queue = new Queue[()=>Unit]()
queue += item
timeSegments += Segment(time, queue)
case Some(segment) => segment.queue += item
}
}

def propagate():Unit = {
if(!timeSegments.isEmpty) {
firstItem()
propagate()
}
else println("Agenda Propagation Done.")
}

//gets first agenda item and removes it
//from the agenda
private def firstItem = {
val segment = timeSegments.max
currentTime = segment.time

val item = segment.queue.dequeue
if(segment.queue.isEmpty)
timeSegments.dequeue

item
}

//get the Segment matching time from timeSegments
private def getTimeSegment(time:Int) = {
val tmp = timeSegments.filter((s:Segment)=>s.time == time)
if(tmp.isEmpty) None else Some(tmp.first)
}
}

//Wire
class Wire() {
var signal = false
private var actions:List[()=>Unit] = List()

def setSignal(b:Boolean) {
if(b != signal) {
signal = b
//execute all actions
actions.foreach((proc:()=>Unit) => proc())
}
}

def addAction(proc:()=>Unit) {
actions = proc :: actions
proc()
}
}

//Probe
def probe(name:String, wire:Wire, agenda:Agenda) {
wire.addAction(
() =>
println(name + " " + agenda.getCurrentTime
+ " ,New Value = " + wire.signal))
}

//after-delay
def afterDelay(delay:Int, proc:() => Unit, agenda:Agenda) {
require(delay >= 0)
agenda.addItem(agenda.getCurrentTime + delay, proc)
}

//====================== SIMULATION ========================

val theAgenda = new Agenda()
val inverterDelay = 2
val andGateDelay = 3
val orGateDelay = 5

//inverter
def inverter(in:Wire, out:Wire) = {
in.addAction(
() => {
val newVal = !in.signal
afterDelay(inverterDelay, () =>
(out.setSignal(newVal)),theAgenda)
})
"Ok"
}

//and gate
def andGate(in1:Wire, in2:Wire, out:Wire) = {
val action = () => {
val newVal = in1.signal && in2.signal
afterDelay(andGateDelay,
() => (out.setSignal(newVal)),
theAgenda) }
in1.addAction(action)
in2.addAction(action)
"Ok"
}

//or gate
def orGate(in1:Wire, in2:Wire, out:Wire) = {
val action = () => {
val newVal = in1.signal || in2.signal
afterDelay(orGateDelay,
() => (out.setSignal(newVal)),
theAgenda) }
in1.addAction(action)
in2.addAction(action)
"Ok"
}

//half-adder
def halfAdder(in1:Wire, in2:Wire, sum:Wire, carry:Wire) = {
val t1 = new Wire()
val t2 = new Wire()
orGate(in1, in2, t1)
andGate(in1, in2, carry)
inverter(carry, t2)
andGate(t1, t2, sum)
"Ok"
}

// == Running the simulation ==
val in1 = new Wire()
val in2 = new Wire()
val sum = new Wire()
val carry = new Wire()

probe("sum",sum,theAgenda)
//sum 0 ,New Value = false

probe("carry",carry,theAgenda)
//carry 0 ,New Value = false

halfAdder(in1,in2,sum,carry)
//Ok

in1.setSignal(true)

theAgenda.propagate()
//sum 8 ,New Value = true
//Agenda Propagation Done.

in2.setSignal(true)

theAgenda.propagate()
//carry 11 ,New Value = true
//sum 16 ,New Value = false
//Agenda Propagation Done.

No comments:

Post a Comment