32. Alternative Simulation Frameworks
Part of
CS:2820 Object Oriented Software Development Notes, Spring 2017
|
Discrete-event simulation was first developed in the 1960s, before anyone understood object-oriented programming. Much of the early work was done in the FORTRAN programming language. FORTRAN, at that time, had very limited control structures and a very limited data model. Variables could be integers, floating-point numbers, or double-precision floating point numbers. There was no character data type, but characters could be processed as integers. There was nothing resembling structures, or classes, but there were arrays. This was very limiting, but more than sufficient to write any program, at least in theory.
If we were building our road network simulation in FORTRAN back the, we might begin by designing the event set. Each event might be described by a logical record containing:
Of course, since FORTRAN did not have record structures of any sort, we'd have to make do with arrays. For each integer value of I, the array entries ETIME(I), EVEHICLE(I), EROAD(I), EINTERS(I), and ENEXT(I), would describe one event. The time field is floating point, while the other fields are all integers. Logically, there is an array of vehicles indexed by vehicle number, an array of roads, indexed by road number, and an array of intersections indexed by intersection number. Events themselved are arranged in a logical array of events indexed by event number, but note, event numbers are arbitrary. The next field organizes events into a linked list, sorted in chronological order, with the head of the list being the head of the event set, the next event to simulate.
FORTRAN, first introduced in 1956, was historically written in all upper case because the older codes used for punched cards didn't support lower case. Fortran identifiers were limited to 8 significant characters (characters after the eighth were ignored) so the prefix E is used above to distinguish all of the variables that represent parts of the event set.
If you were developing a discrete-event simulator in FORTRAN, one of your first goals would be to hide the clutter of arrays described above from the rest of the program. You might do it as follows:
The problem with this approach is that the event set implementation is specific to vehicles, roads and intersections. Any change to the subject matter of the simulation requires a change to the user interface for the pending event set. This is just one of a huge number of deficiencies in first generation programming languages that drove the development of newer languages.
Unfortunately, a large amount of the early work on discrete-event simulation was done using FORTRAN, so much of the published work on simulation methodology focuses on interfaces such as that given above.
Languages like Pascal and C, both dating to the late 1960s, introduced the concept of records. In both of these languages, instead of writing ETIME(I) as in FORTRAN, you could write e[i].time where the event set e is a single array of events, indexed by event number, and each event is a record or structure with multiple fields, including a time field.
Both Pascal and C supported pointers, and in both languages, it would be unnatural to represent the event set as an array of events. Instead, the next field of each event would be a pointer to the next event in chronological order, and if i is a pointer to an event, i->time or (*i).time (both C notation) or i^.time (Pascal) would be the time field of the event pointed to by i. Pascal or C programmers might be tempted to use the folloing pending-event set interface:
This interface is both better and worse than the FORTRAN interface suggested above. It is better because, so long as all event notices have appropriate next and time fields, the pending-event-set management code can easily be preserved and repurposed from one simulatioin model to another.
This interface is not an improvement in one crucial way: The schedule operation forces the programmer to first create a new event and load up its fields. What was one line of code using the FORTRAN-inspired interface will now be many lines of code using this interface.
Object-oriented programming models allow us to improve on this. It is worth noting that the first object-oriented programming language, Simula 67, was a contemporary of C and Pascal, but it was not used widely outside of Norway. Only when Bjarne Stroustrup, an experienced Simula 67 progrmmer, took a job at Bell Labs and developed C++ did object-oriented programming begin to make significant inroads in the rest of the world. The first C++ compilers outside Bell Labs began to appear around 1985. As a result, Pascalish and Cish thinking dominates a considerable amount of the simulation literature.
The underlying data structure of the pending-event set can be viewed as an object, so naturally, we can take the framework suggested above and trivially make it object oriented by explicitly recognizing this:
This interface offers no real advantage over the previous framework. It allows for there to be multiple pending-event sets, but the discrete-event simulation algorithm only requires one, so this is no advantage.
The move to object orientation has a huge benefit in one place: The nature of events. Events are naturally polymorphic. In our highway network simulation, for example, we have events representing things like:
The values that must be specified for each of these are quite different, and the actions to take when each of these events occur are different. Use of polymorphism allows us to deal with this by having class Event be the superclass of class ArrivalEvent, EntryEvent, and LightChangeEvent. What matters is that all subclasses of Event implement a trigger method that causes that event to happen.