Universal Temporal Concurrent Constraint Programming

Universal Temporal Concurrent Constraint Programming (full text available)

Olarte, Carlos (2009) Universal Temporal Concurrent Constraint Programming. PhD thesis Informatique, LIX, EP/X p.167.

Concurrent Constraint Programming (CCP) is a formalism for concurrency in which agents (processes) interact with one another by telling (adding) and asking (reading) information represented as constraints in a shared medium (the store). Temporal Concurrent Constraint Programming (tcc) extends CCP by allowing agents to be constrained by time conditions. This dissertation studies temporal CCP as a model of concurrency for mobile, timed reactive systems. The study is conducted by developing a process calculus called utcc, Universal Temporal CCP. The thesis is that utcc is a model for concurrency where behavioral and declarative reasoning techniques coexist coherently, thus allowing for the specification and verification of mobile reactive systems in emergent application areas.

The utcc calculus generalizes tcc, a temporal CCP model of reactive synchronous programming, with the ability to express mobility. Here mobility is understood as communication of private names as typically done for mobile systems and security protocols. The utcc calculus introduces parametric ask operations called abstractions that behave as persistent parametric asks during a time-interval but may disappear afterwards. The applicability of the calculus is shown in several domains of Computer Science. Namely, decidability of Pnueli's First-order Temporal Logic, closure-operator semantic characterization of security protocols, semantics of a Service-Oriented Computing language, and modeling of Dynamic Multimedia-Interaction systems.

(emphasis mine)

I came across this while developing a capability-secure fusion of constraint programming and reactive programming. It seems UTCC achieves properties similar or identical to those I am pursuing, such as effective support for security, live programming, and interactive multi-media. I'll say more when I stop reading the thesis.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

You might also find Dedelus

You might also find Dedelus interesting. Our group has been messing with temporal and bidirectional constraint languages and have found these two papers and FRP as inspirations for our UI work (though not for a security motivation).

Dedelus and its siblings (P2 etc.) haven't been discussed here but are interesting as they're on the logic side of declaratively and concisely specifying massive and efficient distributed systems. Furthermore, they have impressive case studies of tricky and popular systems to back their approach up.

FRP plus Parameterized Demand

Thanks. I had already found a clean and elegant way to embed Datalog into FP, and I was building my reactive/constraint fusion above that pure layer... which would build reactive, distributed datasets. But it will be interesting to contrast the merits of mine approach with that documented in the Dedelus paper.

FRP was also a big inspiration to me, though my introduction to was via Peter Van Roy rather than Conal Elliott. (Conal politely wishes to discourage PVR's interpretation of FRP.) The distinction between the interpretations are quite significant:

  • PVR behaviors are amnestic (no access to history, nor future), discrete (though the behavior could be a continuous functional), make no guarantee that you'll see intermediate values (evaluate with the latest behavior only), and hence are indeterministic. Further, the dependencies for a behavior are subject to information hiding from the perspective of that behavior's consumer.
  • Conal's model of behaviors include access to history of its input (allowing expression of integrals, derivatives), are generally continuous (though a discrete stream of continuous functionals is a common implementation technique for time-space optimization), and he and Paul Hudak jump through a considerable number of hoops to detect presence of intermediate 'events'. Further, the data resources for a behavior are all input functionally (no information hiding). Everything is deterministic, at least up to the interface with the outside world.

Taking PVR's FRP and running with it, I saw a great deal of value for distributed systems programming: FRP is capable of describing distributed queries to support decisions, multi-cast implementations on an overlay network, it is highly parallel, all the regular abstractions and optimizations for functional programming would continue to apply. The information hiding properties - the encapsulation of a behavior's dependencies - supports an object capability discipline (though you must be willing to either accept concurrency glitches for 'hidden' shared dependencies, or pay for distributed transactions). It supports automated caching, which is useful for isolating propagation of changes and for disruption tolerance.

However, both Conal's and PVR's FRP are missing something significant: nothing within the paradigm expresses secure distribution of the code or hooking it into the environment for pluggable architectures and such. One must escape the FRP paradigm to do these useful and necessary things. But escaping the paradigm is awkward, and in some ways requires replicating a lot of FRP features in an outer layer.

While integrating FRP with outside services, I learned that I could support limited demand-driven behavior. I don't need to turn on that webcam until someone is asking for its value. At first, I was treating this just the same as lazy-programming: one is simply 'lazily' obtaining the behavior for the webcam. But it wasn't long before I wanted to parameterize the demand: i.e. why not also make 'demands' regarding the focus, pan, tilt, and IR-mode for that same webcam? Why not control UAV movements by asking it to figure out what's going on 'over there'? Well, it turns out I needed parameters for distributed performance regardless... for example, to allow SQL queries to parameterize access to a massive 'behavior' representing a remote database. So, I have my demand-driven parameters whether I wanted them or not! Might as well make full use of them.

By using parameterization of abstract behaviors to influence the system, I can model pluggable architectures as abstract behaviors. This isn't FRP anymore, though, and it takes a first-class primitive to recognize this feature within the language. I introduced the concept of stateless 'reflectors': the behavior for a stateless reflector is, at any given point in time, identical to the set of parameters currently used to observe it. Though, for convenience, I separate the reflector into display vs. observe facets from the moment of construction.

This new model achieves all the nice computational properties of FRP. It also admits to 'observer-effect', but controls how this effect is expressed within the system. I suspect pure FRP, as it grows up, will always be fighting the system - attempting to make it appear as though observation is distinct from effect.

The model isn't yet complete. It still needs a process model (similar to how concurrent constraint programming has its 'agents') that can act and observe on behalf of a human. I'm pursuing one based roughly reactive state machines. It also needs a name. (I'm growing to think that 'constraint' is the wrong word, with too many connotations. Maybe I should call it "Reactive Demand Programming.") In any case, observation and influence propagate in both directions throughout the system graph. Dataflow is easy to compute, workflow patterns are easy to express, and 'time' is relative to each observer.

Perhaps your group can find some inspiration in that model.