Abstract
Modern computer systems are awash in a sea of asynchronous events. There is an increasing need for a declarative language that can permit business users to specify complex event-processing rules. Such rules should be able to correlate different event streams, detect absence of events (negative information), permit aggregations over sliding windows, and specify dependent sliding windows. For instance, it should be possible to precisely state a rule such as "Every seventh trading session that Dow Jones has risen consecutively, and IBM's stock is off 3% over its average in this period, evaluate IBM position." Further, the language should be implementable efficiently in an event-driven fashion. We propose the Timed (Default) Concurrent Constraint (TCC) programming framework as a foundation for such complex event processing. While very rich, the TCC framework "forgets" information from one instant to the next. We make two extensions. First, we extend the TCC model to carry the store from previous time instants as "past" information in the current time instant. This permits rules to be written with rich queries over the past. Second, we show that many of the powerful properties of the agent language can be folded into the query language by permitting agents and queries to be defined mutually recursively. We show that this permits queries to move "back and forth" in the past. We provide a formal semantics for TCC + Histories and establish some basic properties.
Introduction
In modern computing, systems are constantly bombarded by asynchronous events—stock price fluctuations, sensor readings, and user interactions. To derive meaning from this "sea of events," we rely on Complex Event Processing (CEP). Ideally, a programmer should be able to write simple, declarative rules to monitor these streams. However, existing tools often require programmers to manually manage state and history, which is both error-prone and complex.
Timed Concurrent Constraint (TCC) programming has long been a candidate for reactive systems because it follows the "Synchrony Hypothesis"—the principle that a system reacts instantaneously to stimuli. However, standard TCC is effectively "amnesiac." It computes a response to the current moment and then discards all information except for the specific instructions for the next time step. This paper introduces TCC + Histories, an evolution of the framework that allows reactive systems to "remember" their past and reason about long-term temporal patterns.
The TCC + Histories Framework
The authors propose extending the traditional TCC model in two fundamental ways to support CEP:
1. The Historical Store
In standard TCC, the constraint store is flushed at every time step. TCC + Histories instead retains past constraints, tagging them with timestamps ($time^i c$). This allows the system to maintain a persistent "past" that can be queried at any time. By treating the entire history of the system as a searchable database of logic, the need for programmers to manually manage state is eliminated.
2. Deep Guards and Recursive Queries
The framework introduces a significantly richer query language to interact with this historical store:
hitherto G: A query that checks if a condition $G$ was true at every point in the past.- Recursive Queries: Using a $\mu$ (mu) operator, queries can be defined recursively. This allows the system to "walk" back through time to find specific events or patterns, such as "the last time a stock dropped by 10%."
- Hypothetical Reasoning: The framework allows for "nested agents," enabling "what-if" questions. For example, a user could query whether the system would have reached a specific state today if a certain constraint had been added three days ago.
Key Insights and Theoretical Results
Symmetry and Multi-form Time
TCC already supported "multi-form" time, where different agents could operate on different logical clocks (e.g., a clock that only ticks when a sensor provides a reading). TCC + Histories extends this, showing that historical queries can move back and forth across these varying logical timelines. Furthermore, the authors demonstrate a logical symmetry between past and future: just as hence A means "A will be true in all future steps," hitherto G means "G was true in all past steps."
Conservativity
A critical theoretical result is that TCC + Histories is "conservative" over standard TCC. If a program is written without using the new history-based features, it behaves exactly as it would in the original, simpler TCC framework. This ensures that the added power does not break existing reactive logic.
Formal Semantics
The paper establishes a formal transition system that handles the evolution of agents across time. This allows queries to "look back" into the historical store without causing logical paradoxes or violating the forward-moving nature of real-time execution. The authors demonstrate that complex temporal logic can be reduced to simple, readable code, defining predicates like once(G) or within T do G (checking if $G$ happened within the last $T$ units of time) using their new primitives.
Limitations and Future Directions
While TCC + Histories provides a powerful declarative foundation, practical implementation faces the challenge of memory management. If a system remembers every event indefinitely, it will eventually exhaust available resources. Future work is required to develop "garbage collection" strategies for history—identifying the minimum amount of past information necessary to satisfy a specific set of rules (finite state compilability).
Additionally, while the authors have defined the operational (step-by-step) semantics, a full denotational semantics—a mathematical mapping of programs to their ultimate meanings—remains to be completed. The study of "deep negative guards" (reacting to the absence of complex historical patterns) also presents an area for further research to ensure computational tractability.
Summary updated