×

TCC, with history. (English) Zbl 1408.68038

van Breugel, Franck (ed.) et al., Horizons of the mind. A tribute to Prakash Panangaden. Essays dedicated to Prakash Panangaden on the occasion of his 60th birthday. Berlin: Springer. Lect. Notes Comput. Sci. 8464, 458-475 (2014).
Summary: 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, specify dependent sliding windows etc. For instance it should be possible to precisely state a rule such as “Every seventh trading session that DowJones has risen consecutively, and IBM’s stock is off 3% over its average in this period, evaluate IBM position”, “Declare the sensor as faulty if no reading has been received for 500 ms”, etc. 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. The framework (developed in the mid 90s) interprets computation as deduction in a fragment of linear temporal logic. It permits the programmer to write rules that can react instantaneously to incoming events and determine the “resumption” that will respond to subsequent events. The framework is very powerful in that it permits instantaneous pre-emption, and allows user-definable temporal operators (“multi-form time”).
However, 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, building on the testing interpretation of intuitionistic logic described in RCC [R. Jagadeesan et al., Lect. Notes Comput. Sci. 3821, 517–528 (2005; Zbl 1172.68555)]. We show that this permits queries to move “back and forth” in the past, e.g. “Order a review if the last time that IBM stock price dropped by 10% in a day, there was more than 20% increase in trading volume for Oracle the following day.”
We provide a formal semantics for TCC + Histories and establish some basic properties.
For the entire collection see [Zbl 1287.68011].

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
03B70 Logic in computer science

Citations:

Zbl 1172.68555

Software:

LUSTRE; SIGNAL; Esterel; GHC
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Alenius, L., Gupta, V.: Modeling an AERCam: A case study in modeling with concurrent constraint languages. In: CP 1998 Workshop on Modeling and Computation in the Concurrent Constraint Languages (October 1998)
[2] Andreoli, J.-M.: Logic programming with focusing proofs in linear logic. Journal of Logic and Computation 2, 297–347 (1992) · Zbl 0764.03020
[3] Benveniste, A., Guernic, P.L., Jacquemot, C.: Synchronous programming with events and relations: the signal language and its semantics. Science of Computer Programming 16(2), 103–149 (1991) · Zbl 0745.68031
[4] Berry, G., Gonthier, G.: The esterel synchronous programming language: design, semantics, implementation. Sci. Comput. Program. 19(2), 87–152 (1992) · Zbl 0772.68013
[5] Bistarelli, S., Gabbrielli, M., Meo, M.C., Santini, F.: Timed soft concurrent constraint programs. In: Lea, D., Zavattaro, G. (eds.) COORDINATION 2008. LNCS, vol. 5052, pp. 50–66. Springer, Heidelberg (2008) · Zbl 05286155
[6] Bockmayr, A., Courtois, A.: Using hybrid concurrent constraint programming to model dynamic biological systems. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol. 2401, pp. 85–99. Springer, Heidelberg (2002) · Zbl 1045.68527
[7] Caspi, P., Pilaud, D., Halbwachs, N., Plaice, J.A.: Lustre: a declarative language for real-time programming. In: Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1987, pp. 178–188. ACM, New York (1987)
[8] Charles, P., Grothoff, C., Saraswat, V., Donawa, C., Kielstra, A., Ebcioglu, K., von Praun, C., Sarkar, V.: X10: an object-oriented approach to non-uniform cluster computing. In: Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2005, pp. 519–538. ACM, New York (2005)
[9] Comini, M., Titolo, L., Villanueva, A.: Abstract diagnosis for timed concurrent constraint programs. CoRR, abs/1109.1587 (2011) · Zbl 1222.68053
[10] de Boer, F.S., Gabbrielli, M., Meo, M.C.: Proving correctness of timed concurrent constraint programs. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. LNCS, vol. 2303, pp. 37–51. Springer, Heidelberg (2002) · Zbl 1077.68706
[11] de Boer, F.S., Gabbrielli, M., Meo, M.C.: A temporal logic for reasoning about timed concurrent constraint programs. In: Temporal Representation and Reasoning, TIME 2001, pp. 227–233. IEEE (2001)
[12] Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: Approximating labelled markov processes. Inf. Comput. 184(1), 160–200 (2003) · Zbl 1028.68091
[13] Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: Metrics for labelled markov processes. Theor. Comput. Sci. 318(3), 323–354 (2004) · Zbl 1068.68093
[14] Gupta, V., Jagadeesan, R., Panangaden, P.: Stochastic processes as concurrent constraint programs. In: Proceedings of the 26th ACM SIGPLAN-SIGACT on Principles of Programming Languages, POPL 1999, San Antonio, TX, January 20-22, pp. 189–202. ACM Press, New York (1999)
[15] Gupta, V., Jagadeesan, R., Panangaden, P.: Approximate reasoning for real-time probabilistic processes. Logical Methods in Computer Science 2(1) (2006) · Zbl 1126.68055
[16] Gupta, V., Jagadeesan, R., Saraswat, V.: Probabilistic concurrent constraint programming. In: Mazurkiewicz, A., Winkowski, J. (eds.) CONCUR 1997. LNCS, vol. 1243, pp. 243–257. Springer, Heidelberg (1997) · Zbl 1002.68026
[17] Gupta, V., Jagadeesan, R., Saraswat, V.A.: Computing with continuous change. Sci. Comput. Program. 30(1-2), 3–49 (1998) · Zbl 0891.68039
[18] Gupta, V., Struss, P.: Modeling a copier paper path: A case study in modeling transportation processes. In: Proceedings of the 9th International Workshop on Qualitative Reasoning, pp. 74–83 (1995)
[19] Harel, D.: Statecharts: A visual formalism for complex systems. Sci. Comput. Program. 8(3), 231–274 (1987) · Zbl 0637.68010
[20] Jaffar, J., Lassez, J.-L.: Constraint Logic Programming. In: Proceedings of the 14th Annual ACM Symposium on Principles of Programming Languages, POPL 1987, Munich, Germany, pp. 111–119. ACM Press, New York (1987)
[21] Jagadeesan, R., Nadathur, G., Saraswat, V.: Testing concurrent systems: an interpretation of intuitionistic logic. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, pp. 517–528. Springer, Heidelberg (2005) · Zbl 1172.68555
[22] Liang, C., Miller, D.: Focusing and polarization in intuitionistic logic. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 451–465. Springer, Heidelberg (2007) · Zbl 1179.03057
[23] Luckham, D.C. (ed.): The power of events: an introduction to complex event processing in distributed enterprise systems. Addison Wesley (2002)
[24] Nielsen, M., Palamidessi, C., Valencia, F.D.: On the expressive power of temporal concurrent constraint programming languages. In: Proceedings of the 4th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, PPDP 2002, pp. 156–167. ACM, New York (2002)
[25] Nielsen, M., Palamidessi, C., Valencia, F.D.: Temporal concurrent constraint programming: Denotation, logic and applications. Nord. J. Comput. 9(1), 145–188 (2002) · Zbl 1018.68019
[26] Palamidessi, C., Valencia, F.: A temporal concurrent constraint programming calculus. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 302–316. Springer, Heidelberg (2001) · Zbl 1067.68662
[27] Panangaden, P., Saraswat, V.A., Scott, P.J., Seely, R.A.G.: A hyperdoctrinal view of concurrent constraint programming. In: de Bakker, J.W., de Roever, W.-P., Rozenberg, G. (eds.) REX 1992. LNCS, vol. 666, pp. 457–476. Springer, Heidelberg (1993)
[28] Reiter, R.: A logic for default reasoning. Artificial Intelligence 13, 81–137 (1980) · Zbl 0435.68069
[29] Saraswat, V., Jagadeesan, R.: Concurrent clustered programming, pp. 353–367. Springer, London (2005)
[30] Saraswat, V., Jagadeesan, R., Gupta, V.: Timed default concurrent constraint programming. Journal of Symbolic Computation 22(5-6), 475–520 (1996) · Zbl 0876.68041
[31] Saraswat, V.A., Jagadeesan, R., Gupta, V.: jcc: Integrating timed default concurrent constraint programming into java. In: Pires, F.M., Abreu, S.P. (eds.) EPIA 2003. LNCS (LNAI), vol. 2902, pp. 156–170. Springer, Heidelberg (2003)
[32] Saraswat, V., Lincoln, P.: Higher-order Linear Concurrent Constraint Programming. Technical report, Xerox PARC (1992)
[33] Saraswat, V., Panangaden, P., Rinard, M.: Semantics of concurrent constraint programming. In: Proceedings of the 18th ACM SIGPLAN-SIGACT on Principles of programming languages, POPL 1991. ACM Press, New York (1991)
[34] Saraswat, V.A.: The concurrent logic programming language cp: Definition and operational semantics. In: Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1987, pp. 49–62. ACM, New York (1987)
[35] Saraswat, V.A.: Concurrent constraint programming. MIT Press, Cambridge (1993) · Zbl 1002.68026
[36] Shapiro, E., Fuchi, K. (eds.): Concurrent Prolog. MIT Press, Cambridge (1988)
[37] Tini, S.: On the expressiveness of timed concurrent constraint programming. Electronic Notes in Theoretical Computer Science 27, 3–17 (1999) · Zbl 0958.68044
[38] Ueda, K.: Guarded Horn Clauses. In: Logic Programming - Japanese Conference, pp. 168–179 (1985)
[39] Valencia, F.D.: Decidability of infinite-state timed ccp processes and first-order ltl. Theoretical Computer Science 330(3), 577–607 (2005) · Zbl 1078.68110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.