Файл: Programming_in_Scala,_2nd_edition.pdf

The andGate and orGate methods

The implementation of and-gates is analogous to the implementation of inverters. The purpose of an and-gate 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:

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

}

The effect of the andGate method is to add andAction to both of its input wires a1 and a2. This action, when invoked, gets both input signals and installs another action that sets the output signal to the conjunction of both input signals. This other action is to be executed after AndGateDelay units of simulated time. Note that the output has to be recomputed if either of the input wires changes. That’s why the same andAction is installed on each of the two input wires a1 and a2. The orGate method is implemented similarly, except it performs a logical-or instead of a logical-and.

Simulation output

To run the simulator, you need a way to inspect changes of signals on wires. To accomplish this, you can simulate the action of putting a probe on a wire:

def probe(name: String, wire: Wire) { def probeAction() {

println(name +" "+ currentTime +

" new-value = "+ wire.getSignal)

}

wire addAction probeAction

}

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

The effect of the probe procedure is to install a probeAction on a given wire. As usual, the installed action is executed every time the wire’s signal changes. In this case it simply prints the name of the wire (which is passed as first parameter to probe), as well as the current simulated time and the wire’s new value.

Running the simulator

After all these preparations, it’s time to see the simulator in action. To define a concrete simulation, you need to inherit from a simulation framework class. To see something interesting, we’ll create an abstract simulation class that extends BasicCircuitSimulation and contains method definitions for half-adders and full-adders as they were presented earlier in this chapter in Listings 18.6 and 18.7. This class, which we’ll call CircuitSimulation, is shown in Listing 18.11:

package org.stairwaybook.simulation

abstract class CircuitSimulation extends BasicCircuitSimulation {

def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) { val d, 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, c1, c2 = new Wire halfAdder(a, cin, s, c1) halfAdder(b, s, sum, c2) orGate(c1, c2, cout)

}

}

Listing 18.11 · The CircuitSimulation class.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

A concrete circuit simulation will be an object that inherits from class CircuitSimulation. The object still needs to fix the gate delays according to the circuit implementation technology that’s simulated. Finally, you will also need to define the concrete circuit that’s going to be simulated. You can do these steps interactively in the Scala interpreter:

scala> import org.stairwaybook.simulation._ import org.stairwaybook.simulation._

First, the gate delays. Define an object (call it MySimulation) that provides some numbers:

scala> object MySimulation extends CircuitSimulation { def InverterDelay = 1

def AndGateDelay = 3 def OrGateDelay = 5

}

defined module MySimulation

Because you are going to access the members of the MySimulation object repeatedly, an import of the object keeps the subsequent code shorter:

scala> import MySimulation._ import MySimulation._

Next, the circuit. Define four wires, and place probes on two of them:

scala> val input1, input2, sum, carry = new Wire input1: MySimulation.Wire =

BasicCircuitSimulation$Wire@111089b input2: MySimulation.Wire =

BasicCircuitSimulation$Wire@14c352e sum: MySimulation.Wire =

BasicCircuitSimulation$Wire@37a04c carry: MySimulation.Wire =

BasicCircuitSimulation$Wire@1fd10fa

scala> probe("sum", sum) sum 0 new-value = false

scala> probe("carry", carry) carry 0 new-value = false

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Note that the probes immediately print an output. This is a consequence of the fact that every action installed on a wire is executed a first time when the action is installed.

Now define a half-adder connecting the wires:

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

Finally, set the signals, one after another, on the two input wires to true and run the simulation:

scala> input1 setSignal true

scala> run()

*** simulation started, time = 0 ***

sum 8 new-value = true scala> input2 setSignal true

scala> run()

*** simulation started, time = 8 ***

carry 11 new-value = true sum 15 new-value = false

18.7 Conclusion

This chapter has brought together two techniques that seem at first disparate: mutable state and higher-order functions. Mutable state was used to simulate physical entities whose state changes over time. Higher-order functions were used in the simulation framework to execute actions at specified points in simulated time. They were also used in the circuit simulations as triggers that associate actions with state changes. Along the way, you saw a simple way to define a domain specific language as a library. That’s probably enough for one chapter!

If you feel like staying a bit longer, you might want to try more simulation examples. You can combine half-adders and full-adders to create larger circuits, or design new circuits from the basic gates defined so far and simulate them. In the next chapter, you’ll learn about type parameterization in Scala, and see another example in which a combination of functional and imperative approaches yields a good solution.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Unlike a mutable queue, a functional queue does not change its contents when an element is appended. Instead, a new queue is returned that contains the element. The goal of this chapter will be to create a class, which we’ll name Queue, that works like this:

scala> val q = Queue(1, 2, 3) q: Queue[Int] = Queue(1, 2, 3)

scala> val q1 = q enqueue 4

q1: Queue[Int] = Queue(1, 2, 3, 4)

scala> q

res0: Queue[Int] = Queue(1, 2, 3)

If Queue were a mutable implementation, the enqueue operation in the second input line above would affect the contents of q; in fact both the result, q1, and the original queue, q, would contain the sequence 1, 2, 3, 4 after the operation. But for a functional queue, the appended value shows up only in the result, q1, not in the queue, q, being operated on.

Purely functional queues also have some similarity with lists. Both are so called fully persistent data structures, where old versions remain available even after extensions or modifications. Both support head and tail operations. But where a list is usually extended at the front, using a :: operation, a queue is extended at the end, using enqueue.

How can this be implemented efficiently? Ideally, a functional (immutable) queue should not have a fundamentally higher overhead than an imperative (mutable) one. That is, all three operations head, tail, and enqueue should operate in constant time.

One simple approach to implement a functional queue would be to use a list as representation type. Then head and tail would just translate into the same operations on the list, whereas enqueue would be concatenation. This would give the following implementation:

class SlowAppendQueue[T](elems: List[T]) { // Not efficient def head = elems.head

def tail = new SlowAppendQueue(elems.tail)

def enqueue(x: T) = new SlowAppendQueue(elems ::: List(x))

}

The problem with this implementation is in the enqueue operation. It takes time proportional to the number of elements stored in the queue. If you want

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

constant time append, you could also try to reverse the order of the elements in the representation list, so that the last element that’s appended comes first in the list. This would lead to the following implementation:

class SlowHeadQueue[T](smele: List[T]) { // Not efficient // smele is elems reversed

def head = smele.last

def tail = new SlowHeadQueue(smele.init)

def enqueue(x: T) = new SlowHeadQueue(x :: smele)

}

Now enqueue is constant time, but head and tail are not. They now take time proportional to the number of elements stored in the queue.

Looking at these two examples, it does not seem easy to come up with an implementation that’s constant time for all three operations. In fact, it looks doubtful that this is even possible! However, by combining the two operations you can get very close. The idea is to represent a queue by two lists, called leading and trailing. The leading list contains elements towards the front, whereas the trailing list contains elements towards the back of the queue in reversed order. The contents of the whole queue are at each instant equal to “leading ::: trailing.reverse”.

Now, to append an element, you just cons it to the trailing list using the :: operator, so enqueue is constant time. This means that, when an initially empty queue is constructed from successive enqueue operations, the trailing list will grow whereas the leading list will stay empty. Then, before the first head or tail operation is performed on an empty leading list, the whole trailing list is copied to leading, reversing the order of the elements. This is done in an operation called mirror. Listing 19.1 shows an implementation of queues that uses this approach.

What is the complexity of this implementation of queues? The mirror operation might take time proportional to the number of queue elements, but only if list leading is empty. It returns directly if leading is non-empty. Because head and tail call mirror, their complexity might be linear in the size of the queue, too. However, the longer the queue gets, the less often mirror is called. Indeed, assume a queue of length n with an empty leading list. Then mirror has to reverse-copy a list of length n. However, the next time mirror will have to do any work is once the leading list is empty again, which will be the case after n tail operations. This means you can “charge” each of these n tail operations with one n’th of the complexity

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index