Streams a la carte: Extensible Pipelines with Object Algebras

Authors Aggelos Biboudis, Nick Palladinos, George Fourtounis, Yannis Smaragdakis



PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2015.591.pdf
  • Filesize: 0.6 MB
  • 23 pages

Document Identifiers

Author Details

Aggelos Biboudis
Nick Palladinos
George Fourtounis
Yannis Smaragdakis

Cite AsGet BibTex

Aggelos Biboudis, Nick Palladinos, George Fourtounis, and Yannis Smaragdakis. Streams a la carte: Extensible Pipelines with Object Algebras. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 591-613, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.ECOOP.2015.591

Abstract

Streaming libraries have become ubiquitous in object-oriented languages, with recent offerings in Java, C#, and Scala. All such libraries, however, suffer in terms of extensibility: there is no way to change the semantics of a streaming pipeline (e.g., to fuse filter operators, to perform computations lazily, to log operations) without changes to the library code. Furthermore, in some languages it is not even possible to add new operators (e.g., a zip operator, in addition to the standard map, filter, etc.) without changing the library. We address such extensibility shortcomings with a new design for streaming libraries. The architecture underlying this design borrows heavily from Oliveira and Cook's object algebra solution to the expression problem, extended with a design that exposes the push/pull character of the iteration, and an encoding of higher-kinded polymorphism. We apply our design to Java and show that the addition of full extensibility is accompanied by high performance, matching or exceeding that of the original, highly-optimized Java streams library.
Keywords
  • object algebras
  • streams
  • extensibility
  • domain-specific languages
  • expression problem
  • library design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Philippe Altherr and Vincent Cremet. Adding type constructor parameterization to Java. In Workshop on Formal Techniques for Java-like Programs (FTfJP'07) at the European Conference on Object-Oriented Programming (ECOOP), 2007. Google Scholar
  2. Aggelos Biboudis, Nick Palladinos, and Yannis Smaragdakis. Clash of the lambdas. 9th International Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS), available at http://arxiv.org/abs/1406.6631, 2014.
  3. Jeffrey Bosboom, Sumanaruban Rajadurai, Weng-Fai Wong, and Saman Amarasinghe. StreamJIT: A commensal compiler for high-performance stream programming. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA'14, pages 177-195, New York, NY, USA, 2014. ACM. Google Scholar
  4. Yoonseo Choi, Yuan Lin, Nathan Chong, Scott Mahlke, and Trevor Mudge. Stream compilation for real-time embedded multicore systems. In Proceedings of the 7th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO'09, pages 210-220, Washington, DC, USA, 2009. IEEE Computer Society. Google Scholar
  5. Jeremy Gibbons and Nicolas Wu. Folding domain-specific languages: Deep and shallow embeddings (functional pearl). In Proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming, ICFP'14, pages 339-347, New York, NY, USA, 2014. ACM. Google Scholar
  6. Daniel Gronau. HighJ - Haskell-style type classes in Java. https://github.com/DanielGronau/highj, 2011.
  7. M. Hirzel, H. Andrade, B. Gedik, G. Jacques-Silva, R. Khandekar, V. Kumar, M. Mendell, H. Nasgaard, S. Schneider, R. Soulé, and K.-L. Wu. IBM Streams Processing Language: Analyzing big data in motion. IBM Journal of Research and Development, 57(3-4):7:1-7:11, May 2013. Google Scholar
  8. Martin Hirzel, Robert Soulé, Scott Schneider, Buğra Gedik, and Robert Grimm. A catalog of stream processing optimizations. ACM Computing Surveys, 46(4):46:1-46:34, March 2014. Google Scholar
  9. Chuan-kai Lin and Andrew P. Black. DirectFlow: A domain-specific language for information-flow systems. In Proceedings of the 21st European Conference on Object-Oriented Programming, volume 4609 of ECOOP'07, pages 299-322. Springer Berlin Heidelberg, 2007. Google Scholar
  10. Sandro Magi. Abstracting over type constructors using dynamics in C#. http://higherlogics.blogspot.ca/2009/10/abstracting-over-type-constructors.html, Oct 2009.
  11. Erik Meijer. The world according to LINQ. Communications of the ACM, 54(10):45-51, October 2011. Google Scholar
  12. Erik Meijer, Brian Beckman, and Gavin Bierman. LINQ: Reconciling Object, Relations and XML in the .NET Framework. In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD'06, pages 706-706, New York, NY, USA, 2006. ACM. Google Scholar
  13. Bruno C. d. S. Oliveira and William R. Cook. Extensibility for the masses: Practical extensibility with object algebras. In Proceedings of the 26th European Conference on Object-Oriented Programming, volume 7313 of ECOOP'12, pages 2-27. Springer Berlin Heidelberg, 2012. Google Scholar
  14. Bruno C. d. S. Oliveira, Tijs van der Storm, Alex Loh, and William R. Cook. Feature-oriented programming with object algebras. In Giuseppe Castagna, editor, Proceedings of the 27th European Conference on Object-Oriented Programming, number 7920 in ECOOP'13, pages 27-51. Springer Berlin Heidelberg, January 2013. Google Scholar
  15. Oracle. Stream (Java Platform SE 8). URL: http://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html.
  16. John Rose. Hotspot-compiler-dev mailing list: Perspectives on Streams Performance. http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/2015-March/017278.html, March 2015.
  17. Aleksey Shipilev, Sergey Kuksenko, Anders Astrand, Staffan Friberg, and Henrik Loef. OpenJDK: jmh. URL: http://openjdk.java.net/projects/code-tools/jmh/.
  18. Jesper H. Spring, Jean Privat, Rachid Guerraoui, and Jan Vitek. StreamFlex: High-throughput stream programming in Java. In Proceedings of the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems and Applications, OOPSLA'07, pages 211-228, New York, NY, USA, 2007. ACM. Google Scholar
  19. Robert Stephens. A survey of stream processing. Acta Informatica, 34(7):491-541, 1997. Google Scholar
  20. Xueyuan Su, Garret Swart, Brian Goetz, Brian Oliver, and Paul Sandoz. Changing engines in midstream: A java stream computational model for big data processing. Proc. VLDB Endow., 7(13):1343-1354, August 2014. Google Scholar
  21. Josh Suereth. Scala documentation: Implicit classes. URL: http://docs.scala-lang.org/overviews/core/implicit-classes.html.
  22. Bo Joel Svensson and Josef Svenningsson. Defunctionalizing push arrays. In Proceedings of the 3rd ACM SIGPLAN Workshop on Functional High-Performance Computing, pages 43-52. ACM, 2014. Google Scholar
  23. William Thies, Michal Karczmarek, and Saman P. Amarasinghe. StreamIt: A language for streaming applications. In Proceedings of the 11th International Conference on Compiler Construction, CC'02, pages 179-196, London, UK, UK, 2002. Springer-Verlag. Google Scholar
  24. Mandana Vaziri, Olivier Tardieu, Rodric Rabbah, Philippe Suter, and Martin Hirzel. Stream processing with a spreadsheet. In Richard Jones, editor, Proceedings of the 28th European Conference on Object-Oriented Programming, volume 8586 of ECOOP'14, pages 360-384. Springer Berlin Heidelberg, 2014. Google Scholar
  25. Philip Wadler. The expression problem. http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt, December 1998.
  26. Joseph G. Wingbermuehle, Roger D. Chamberlain, and Ron K. Cytron. ScalaPipe: A streaming application generator. In Proceedings of the 2012 IEEE 20th International Symposium on Field-Programmable Custom Computing Machines, FCCM'12, pages 244-, Washington, DC, USA, 2012. IEEE Computer Society. Google Scholar
  27. Jeremy Yallop and Leo White. Lightweight higher-kinded polymorphism. In Functional and Logic Programming, pages 119-135. Springer, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail