Wednesday, November 20, 2013

Discrete Event Simulation - identity and state

In this post I would like to address some aspects of reactive programming before we can get a deeper insight in this topic.

On of problematic areas of maximal approach of concurrency are functions and stateful objects. The world is normally described as a set of objects, some of which have state that changes over the course of time.
An object has a state if its behavior is influenced by its history.

Second interesting area is the Identity of an object and its change. The new problem of deciding whether two expressions are “the same”.
This property is usually called referential transparency specifying what is meant by “thesame”
Objects x and y are operationally equivalent if no possible test can distinguish between them.

So it is not so difficult to proof the difference of two objects, however it is not so easy to offer an infinite variety of solutions to prove otherwise.

As example we can use The Discrete Event Simulation interactive programing we could describe using “Digital Circuits”



Let’s start with a small description language for digital circuits.
A digital circuit is composed of wires and of functional components.
Wires transport signals that are transformed by components.
Usually We represent signals using Boolean true and false.

The base components (gates) are:
  • The Inverter - whose output is the inverse of its input.
  • The AND Gate -  whose output is the conjunction of its inputs.
  • The OR Gate -, whose output is the disjunction of its inputs.


Other components can be constructed by combining these base components.
The components have a reaction time (or delay), i.e. their outputs don’t change immediately after a change to their inputs

All we have left to do now is to implement the Simulation trait.
The idea is to keep in every instance of the Simulation trait an agenda of actions to perform.
The agenda is a list of (simulated) events .
Each event consists of an action and the time when it must be produced.
The agenda list is sorted in such a way that the actions to be performed.  First are in the beginning.

Summary
State and assignments make our mental model of computation more complicated.
In particular, we lose referential transparency.
On the other hand, assignments allow us to formulate certain programs in an elegant way.

Example: Discrete Event Simulation.
  • Here, a system is represented by a mutable list of actions.
  • The effect of actions, when they’re called, change the state of objects and can also install other actions to be executed in the future.