Stream processing coalgebraically
Pages 2192 - 2215
Abstract
We study various operations for splitting, partitioning, projecting and merging streams of data. These operations are motivated by their use in dataflow programming and stream processing languages. We use the framework of stream calculus and stream circuits for defining and proving properties of such operations using behavioural differential equations and coinduction proof principles. As a featured example we give proofs of results, observed by Moessner, from elementary number theory using our framework. We study the invariance of certain well patterned classes of streams, namely rational and algebraic streams, under splitting and merging. Finally we show that stream circuits extended with gates for dyadic split and merge are expressive enough to realise some non-rational algebraic streams, thereby going beyond ordinary stream circuits.
References
[1]
Automatic Sequences: Theory, Applications, Generalizations. 2003. Cambridge University Press, Cambridge.
[2]
Arbab, F., Reo: a channel-based coordination model for component composition. Math. Structures Comput. Sci. v14. 329-366.
[3]
Berstel, J. and Reutenauer, C., Rational series and their languages. In: EATCS Monographs on Theoretical Computer Science, vol. 12. Springer-Verlag, Berlin.
[4]
Broy, M. and Ştef¿nescu, G., The algebra of stream processing functions. Theoret. Comput. Sci. v258. 99-129.
[5]
Christol, G., Ensembles presque periodiques k-reconnaissables. Theoret. Comput. Sci. v9. 141-145.
[6]
Fogg, N.P., Substitutions in dynamics, arithmetics and combinatorics. In: Berthé, Valérie, Ferenczi, Sébastien, Mauduit, Christian, Siegel, Anne (Eds.), Lecture Notes in Math., vol. 1794. Springer-Verlag, Berlin.
[7]
Graham, R.L., Knuth, D.E. and Patashnik, O., Concrete Mathematics. A foundation for computer science. 1994. second edition. Addison-Wesley, Reading, Massachusetts.
[8]
R. Hinze, Scans and convolutions: a calculational proof of Moessner's theorem, in: S.B. Scholz (Ed.), IFL 2008 Lecture Notes in Comput. Sci., vol. 5836, Springer-Verlag (to appear), 24 pages.
[9]
Hungerford, T.W., . In: Graduate Texts in Mathematics, vol. 73. Springer-Verlag, New York.
[10]
Kahn, G., The semantics of a simple language for parallel programming. In: Stockholm, vol. 74. North Holland Publishing Co., Amsterdam. pp. 471-475.
[11]
Kim, J., Coinductive properties of causal maps. In: Meseguer, J., Rosu, G. (Eds.), Lecture Notes in Comput. Sci., vol. 5140. Springer-Verlag. pp. 253-267.
[12]
Lucanu, D. and Roşu, G., CIRC: A circular coinductive prover. In: Mossakowski, T., Montanari, U., Haveraaen, M. (Eds.), Lecture Notes in Comput. Sci., vol. 4624. Springer-Verlag. pp. 372-378.
[13]
R.H. Mak, Design and Performance Analysis of Data-independent Stream Processing Systems, Ph.D. Thesis, Technische Universiteit Eindhoven, 2008.
[14]
Moessner, A., Eine Bemerkung über die Potenzen der natürlichen Zahlen. Sitzungsber. Math.-Naturw. Kl. Bayer. Akad. Wiss. München. v1951. 29
[15]
Perron, O., Beweis des Moessnerschen Satzes. Sitzungsber. Math.-Naturw. Kl. Bayer. Akad. Wiss. München. v1951. 31-34.
[16]
Rutten, J.J.M.M., Behavioural differential equations: a coinductive calculus of streams, automata, and power series. Theoret. Comput. Sci. v308. 1-53.
[17]
Rutten, J.J.M.M., A coinductive calculus of streams. Math. Structures Comput. Sci. v15. 93-147.
[18]
Rutten, J.J.M.M., A tutorial on coinductive stream calculus and signal flow graphs. Theoret. Comput. Sci. v343. 443-481.
[19]
Rutten, J.J.M.M., Algebraic specification and coalgebraic synthesis of mealy automata. In: Zhiming~Liu, L.B. (Ed.), Electron. Notes Theor. Comput. Sci., vol. 160. Elsevier. pp. 305-319.
[20]
Rutten, J.J.M.M., Rational streams coalgebraically. Log. Methods Comput. Sci. v4. 1-22.
[21]
Uustalu, T. and Vene, V., Comonadic notions of computation. In: Adámek, J., Kupke, C. (Eds.), Electron. Notes Theor. Comput. Sci., vol. 203(5). Elsevier. pp. 263-284.
[22]
Wilf, H.S., Generating Functionology. 1994. second edition. Academic Press Inc., Boston, MA.
- Stream processing coalgebraically
Recommendations
Sampling, splitting and merging in coinductive stream calculus
MPC'10: Proceedings of the 10th international conference on Mathematics of program constructionWe study various operations for partitioning, projecting and merging streams of data. These operations are motivated by their use in dataflow programming and the stream processing languages. We use the framework of stream calculus and stream circuits ...
Dual-Paradigm Stream Processing
ICPP '18: Proceedings of the 47th International Conference on Parallel ProcessingExisting stream processing frameworks operate either under data stream paradigm processing data record by record to favor low latency, or under operation stream paradigm processing data in micro-batches to desire high throughput. For complex and mutable ...
Functional pearl: streams and unique fixed points
ICFP '08Streams, infinite sequences of elements, live in a coworld: they are given by a coinductive data type, operations on streams are implemented by corecursive programs, and proofs are conducted using coinduction. But there is more to it: suitably ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © © 2013.
Publisher
Elsevier North-Holland, Inc.
United States
Publication History
Published: 01 November 2013
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025