Space-time duality thesis
An interesting space-time duality thesis is described here.ST-Dual thesis
As we said, in this section we briefly explore the followingThe restricted version relating MixBSNA and MixBTNA connects the classical imperative programming with pure OO programming. It claims that by interchange of space and time a meaningful concept in classical imperative programming would lead to a corresponding meaningful concept in the pure object-oriented programming world and conversely.
Its status
At the moment this is just an interesting working hypothesis. ST-Dual thesis is to be studied in relation with the general computing principles, as well as with respect to the current achievements in concurrent, real-time, object-oriented programming. While many situations from the latter world may easily invalidate the thesis, along the way one may find interesting and nontrivial extensions to solve the mismatch, still keeping the ST-Dual thesis as a valid option. In other words, ST-Dual thesis is considered as a general guiding law. It is not restricted to a current, fixed concurrent object-oriented programming setting, e.g., to Java programming.Space-time duality picture
The top-right half of the picture is the world of imperative programs, IMP-World. This is a clear and well-established world, hence it will have a rather strong and fixed position in all reasonings related to ST-Dual thesis. This part of the figure also contains a sketch of the programs of this world, both at the low level of Turing machines, and at the higher level used in current programming languages. The development of ST-Dual machinery is accompanied with a presentation of certain pieces of this IMP-World. After a careful reconsideration, these notions will be carried over the diagonal to the OO-World. To keep the discussion simpler, no special features of imperative programs will be considered (e.g., modules, recursive procedures, etc.).
The symmetric bottom-left half of the picture is the world of pure object-oriented programs, POO-World. This ``pure object-oriented'' programming style is one where all computations are made by message invocation only. While Smalltalk may be a possible candidate for this, actually this world is explicitly kept open in order to accommodate the ST-Dual thesis. Since our top-right half of the picture is rather strong and fixed we have to consider the bottom-left half as weak and flexible in order to have room for appropriate changes. Step-by-step this POO-World will become clearer and clearer by importing simple facts from the IMP-World via ST-Dual machinery.
Finally, the bottom-right part of the picture tries to find the place of a software component in the full concurrent, real-time, OO-programming world. It is illustrated by a rectangle which intersects both worlds. A component has both a state and a job interface. It does the specific task; after that, both the state and the job class may change. The main novelty may be that not only the state is changed due to a job requirement, but also the job is changed after this process.
Facts supporting ST-Dual thesis
In this subsection we present a few facts supporting the ST-Dual thesis. On the way, we will describe the ST-Dual machinery; it uses simple facts about imperative programs and carries them over the diagonal; interesting facts on interacting systems modeling OO-programs are obtained so far.Memory tape and job stream
A basic fact to start with is Turing memory tape. Turing tape, as is drawn in the picture, is a spatial memory model. It is a linear, discrete, and infinite collection of 0/1 bits.The dual notion corresponding to memory tape is called job stream. By ST-Dual machinery, the above properties show a job stream is to be considered as an infinite, linear collection of P/A (Present/Absent) bits. Job streams are used for the interaction interfaces of the interacting systems.
The memory state of an imperative program consists of various memory cells that are fully accessible to the program at a given time. However, a statement use a finite part of them only; the remaining cells are left unchanged.
A job stream consists of a sequence of actions the object has to process. The object duty is to process some jobs and to report at its output interface the result. A finite part of the job stream has to be used by an agent. The remaining jobs in the stream are left unchanged.
State-transformer vs. job-transformer devices
We make here one more step to unravel the SD-Dual machinery. Let us consider the simple acyclic straight-line programs. They are simple sequences of statements seen as state-transformers (no tests, no loops). The dual of a program will be called (interacting) system; the dual of a statement will be called schedule.In our simple case here, a program is just a finite sequence of statements which have to be executed at different time slots, one after the other. Each statement has a finite time extent.
By the ST-Dual machinery an interacting system has to be split in pieces corresponding to program statements; we just introduced a name for them: ``schedules.'' Then, an interacting system, at this simple setting, is a (finite) sequence of schedules which are to be executed at different space positions (say by different agents), with a directed linear causal order; that is, the output of one schedule is the input of the next one. Moreover, to be in accord with the IMP-World hypothesis, each schedule has a finite space extent. (In other words, the schedule is supposed to take an input job stream request and to transform it into an output job stream, according to the schedule rule and using a fixed amount of spatial resources.)
This structural way of considering interacting systems seems to be new. It will play a fundamental role in structuring the (P)OO-World.
We want to have a simple, natural semantics for the whole model. Relational semantics is maybe the simplest approach. In the view of this semantics, a program is just a state-transforming relation. Given a current memory state, a statement produces a new memory state. Usually the programs are deterministic, hence at most one new state is produced.
The basic program construction is sequential composition. This is so fundamental that a special symbol denoting this operation, nowadays ``;'', has occurred quite late in programming languages. Reading the program from top to bottom just means to go along with this operation. (Remember that we have no tests, no loops here.)
An important additional fact is that the statements are generic, i.e., they act in a uniform, parametric way for a whole class of similar inputs. Then, a statement is seen as a relation between the input and the output states.
What does ST-Dual machinery get out from this IMP-World situation? Interacting systems, in general, and schedules, in particular, are to be seen as job-transformer relations. Each interacting system has an input job interface and an output job interface. According to the situation within IMP-World, the job streams propagate in the system in a directed, causal way, from one schedule to another. The atom of interaction has to be split, as Abramsky inspiringly pointed out. ST-Dual machinery says that interacting systems should be created in a structural way from schedules in the same way programs are created from statements.
One important fact may be stated now: it is not the interaction of the agents of primary interest. This will come later. Their sequential composite as a model from cause to effect is the fundamental operation we have to focus on.
Finally, let us now try to gather together job streams in the same way memory instances were collected in program states. The dual notion corresponding to memory state is job class. At the current setting a class is just a collection of similar job streams. Then, a schedule acts in a generic, parametric way on the job streams of a class and transform them in job streams corresponding to the output class.
Clock vs. balance
The imperative programs are based on global states and global clock. A statement may consist of various small actions that are to be done in order to transform the state into a new one. The global clock assumption means that all the small statements have to be finished in order the statement be finished. If the pieces of the statement are done in parallel, then it is useful to have all the sub-statements of appropriate time length in order to shorten the clock step, consequently, to shorten the overall time running.The dual concept of the global clock is called overall balance. We suggest to use balance as dual to clock, the balance being a device to indicate a certain size of the objects, in the same way the clock is used to indicate the time. The agent does its work on the given input job stream and reports the resulting job stream at its output interface. An action is implemented if all the sub-jobs that have to be done along with this transformation are implemented. If these actions are considered separate, then in order to minimize the resources allocated to the agent one has to use actions of appropriate space requirements. Overall small balance is a good goal for the system schedules, in the same way a global small clock is good for program statements.
Assignments
An assignment statement reads a finite number of memory cells, computes something, and writes the result at the required memory cell(s).In the dual POO-World one has to use a finite part of the input job stream, so that the object acts when a (finite) collection of job requirements is accumulated. (This clearly has no meaning in a sequential OO-World; indeed, the waiting for a new job request in a sequential OO-case will result in a system failure; hence more execution threads are necessary to model this situation.) It does the specific job and reports the result. The time on job streams is local, hence there is no relationship between the time information of the input and the output jobs; hence the current process may wait for as many jobs as he wants before spooling the 1st output job.
One more comment on agent's invocation. The suggested natural extension of the OO view is to consider a method be activated by a collection of method invocations, not by a unique call, as usual. If the agent has enough memory space (which is not a priori possible!), then it may simulate this as follows: it may store the invocation calls in its memory till all the relevant information has been obtained; thereafter it may proceed to satisfy the input request. However, an ``atomic read'' of the relevant part of the job class is better, in the same way an ``atomic read'' of the memory state is better than reading memory bits; the former avoids a complicated analysis of piped job required processes, in the same way the latter avoids a complicate analysis of parallel memory access processes.
Memory and job: high level structure
In the previous analysis we have used a very low level model for both the memory space and the job stream. Current imperative programs have more complicated higher spatial structure on memory states. The dual result will be that the homogeneous and atomic view of time will be somehow relaxed, each process having his own type of timed structure on the job streams.A high level structure on data may be used for imperative programs, e.g., four bit numbers such as 1011 may be used. Similar temporal Arabic-like structures may be used on jobs streams. The corresponding streams are four-time-steps actions PAPP saying that during this time interval the request for the specific action was present/absent/present/present.
Tests
The semantics of tests is well-known: depending on the current memory values of certain variables, the computation run may continue in one or other point of the program; Goto statements are used here. To this end, program states are labeled.The dual version is natural, too. A schedule may test for (a part of) its job stream; depending on the current value of this input job request it may decide to forward the job stream to be further processed in one or another point. To this end, Goto statements and dual labels pointing to job classes are used. This job test appears as a sort of classification: depending on certain information, an input job stream is classified as requiring one sort of further processing, or another.
Programming vs. planning
Programming is the basic activity in the IMP-World. The dual activity may be fairly called planning.An imperative program may be seen as a finite representation of a certain collection of operating sequences people do to get the intended output. These sequences may vary from an input to another. A label in the program, denoting a program state, gathers together memory instances that (1) are reached by the program at different times, (2) are similar, and (3) require similar transformations coded by the current program statement. The program control gives a cover of these sequences in the following sense: (1) each real computation sequence is syntactically possible, but (2) there may be syntactically possible sequences that are run-time impossible.
The planning activity has the dual properties. Systems of interacting objects are seen as job transformers. The elementary job transformers are the system schedules. A sequence of job scheduling between different objects may lead to the desired output job result. For various input job streams the scheduling sequences may be different. The collection of all these interaction patterns may be infinite, hence they are not too useful for our finite machines in these forms. For this reason we have to collect together job streams which (1) are located at various places, (2) are similar, and (3) their processing are similar and may be coded by the current schedule as a collection of methods that do the specific job transformation. In a few words, the dual concept corresponding to imperative programming is planning (scheduling). In the vein of this slogan, the design of a schedule structure for the job delegation that obey the input--output job constraint is the main task in this world.
Program vs. schedule correctness
Programs are used as repeated tasks for input data fulfilling certain constraints. The functionality of the program is given by its input--output state relation. A program is correct if it terminates and respects the desired input--output specification.qSystems of interacting objects may be tested for various scenarios of job streams fulfilling certain constrains. It seems natural to look at the amount of work the system has done from this job stream by considering the reported output job stream. The effect on states of the test scenario may be of collateral interest here. The termination property here means that a finite amount of objects/spatial resources are to be used in order to do the input-ooutput job transformation.
Assertions vs. fairness
This ST-Dual thesis throws a new light on the fairness problem, as well. The current approaches either ignore the problem, or propose rather ad-hoc solutions. The ST-Dual machinery says that the problem is important, but the solution is already in our hands: it is the classical program verification via inductive assertions, but presented for the dual world. Fairness is reduced to the use of inductive assertions on job classes: provide assertions (invariants) for job classes at various points of the system and verify that the system schedules satisfy them.More expressiveness in describing interaction interfaces
A higher timed structure on job classes allows us to express easily certain properties. Usually, as in the ROOM (Real-Time Object-Oriented Method) model GrosuStefanescuBroy98, an input, say f, is kept fixed up to the end of a computation step (the signal is enabled during this period). In our current notation this means f=P...P. If you want to express the fact that 2 steps f is active, then 3 steps g, then 1 step f, this will be easily described as f=PPAAAP and g=AAPPPA. The agent has to check both fields f and g each time before reacting. The situation here is dual to the multiplication of two numbers, say, where one has to check simultaneously the fields of both arguments to get the result.Parallel vs. piped processes
By the ST-Dual machinery parallel processes are transformed into piped processes and vice-versa. This allows us to use the techniques for parallelizing programs in order to get techniques for piping the schedules. This way, one may decrease the overall required space.State vs. class labels
State labels are commonly used to describe control flow using Goto statements. They provide the possibility to make a (rather free) jump from one statement to another. In the same vein, using the ST-Dual machinery one may introduce and use class labels. Then, after processing its input job stream a schedule may pass the resulting job stream to a (fairly arbitrary) new schedule according to the interaction system structure. It may be the case that mobility, the important notion people in Computer Science are now focusing on, is mainly reduced to this feature of interaction systems.We hope the way to apply the ST-Dual machinery has become clear by now. More such analogies may be easily obtained.