A type-level approach to component prototyping

ABSTRACT

Algebraic theories for modeling components and their interactions offer abstraction over the specifics of component states and interfaces. For example, such theories deal with forms of sequential composition of two components in a manner independent of the type of data stored in the states of the components, and independent of the number and types of methods offered by the interfaces of the combinators. General purpose programming languages do not offer this level of abstraction, which implies that a gap must be bridged when turning component models into implementations.

In this paper, we present an approach to prototyping of component-based systems that employs so-called type-level programming (or compile-time computation) to bridge the gap between abstract component models and their type-safe implementation in a functional programming language. We demonstrate our approach using Barbosa's model of components as generalized Mealy machines. For this model, we develop a combinator library in Haskell, which uses type-level programming with two effects. Firstly, wiring between components is computed during compilation. Secondly, the well-formedness of the component compositions is guarded by Haskell's strong type system.

REFERENCES

• 1: B. Alarcon and S. Lucas. Crossing the Rubicon: from Haskell to .NET through COM. ERCIM News, 63:51--52, October 2005.
• 2: F. Arbab. Abstract Behaviour Types: a Foundation model for components and their composition. In F. S. de Boer, M. Bonsangue, S. Graf, and W.-P. de Roever, editors, Proc. First International Symposium on Formal Methods for Components and Objects (FMCO'02), pages 33--70. Springer Lect. Notes Comp. Sci. (2852), 2003.
• 3: L. S. Barbosa. Towards a Calculus of State-based Software Components. Journal of Universal Computer Science, 9(8):891--909, August 2003.
• 4: L. S. Barbosa. A Perspective on Component Refinement. In F. S. de Boer, M. Bonsangue, S. Graf, and W.-P. de Roever, editors, FMCO'04, Third International Symposium on Formal Methods for Components and Objects -- Revised Lectures, pages 23--48. Springer Lect. Notes Comp. Sci. (3657), 2005.
• 5: L. S. Barbosa and J. N. Oliveira. State-based Components Made Generic. In H. P. Gumm, editor, CMCS'03, Elect. Notes in Theor. Comp. Sci., volume 82.1. Elsevier, 2003.
• 6: Luís S. Barbosa , José N. Oliveira, Transposing partial components: an exercise on coalgebraic refinement, Theoretical Computer Science, v.365 n.1, p.2-22, 10 November 2006 [doi>10.1016/j.tcs.2006.07.030]
• 7: M. A. Barbosa and L. S. Barbosa. A Relational Model for Component Interconnection. Journal of Universal Computer Science, 10(7):808--823, 2004.
• 8: A. Bois, P. Trinder, and H. Loidl. mHaskell: Mobile computation in a purely functional language. Journal of Universal Computer Science, 11(7):1234--1254, 2005.
• 9: Kraig Brockschmidt, Inside OLE (2nd ed.), Microsoft Press, Redmond, WA, 1995
• 10: Francisco Heron de Carvalho Junior , Rafael Dueire Lins, Topological Skeletons in Haskell#, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.53.1, April 22-26, 2003
• 11: David Gelernter , Nicholas Carriero, Coordination languages and their significance, Communications of the ACM, v.35 n.2, p.97-107, Feb. 1992 [doi>10.1145/129630.129635]
• 12: Richard Grimes , Dr Richard Grimes, Professional Dcom Programming, Wrox Press Ltd., Birmingham, UK, 1997
• 13: T. Hallgren. Fun with Functional Dependencies. In Proc. of the Joint CS/CE Winter Meeting, pages 135--145, 2001. Dept. of Computing Science, Chalmers, Göteborg, Sweden.
• 14: Ralf Hinze, Formatting: a class act, Journal of Functional Programming, v.13 n.5, p.935-944, September 2003 [doi>10.1017/S0956796802004367]
• 15: Mark P. Jones, Functional Programming with Overloading and Higher-Order Polymorphism, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, p.97-136, May 24-30, 1995
• 16: S. L. P. Jones. Haskell 98: Language and libraries. J. Funct. Program., 13(1):1--255, 2003.
• 17: Simon Peyton Jones , Andrew Gordon , Sigbjorn Finne, Concurrent Haskell, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237794]
• 18: O. Kiselyov and R. Lämmel. Haskell's overlooked object system. Draft of 10 September 2005, 2005.
• 19: Oleg Kiselyov , Ralf Lämmel , Keean Schupke, Strongly typed heterogeneous collections, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017488]
• 20: Oleg Kiselyov , Chung-chieh Shan, Functional pearl: implicit configurations--or, type classes reflect the values of types, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017481]
• 21: A. Kock. Strong Functors and Monoidal Monads. Archiv für Mathematik, 23:113--120, 1972.
• 22: D. Leijen, E. Meijer, and J. Hook. Haskell as an Automated Controller. In S. D. Swierstra, P. R. Henriques, and J. N. Oliveira, editors, Third International Summer School on Advanced Functional Programming, Braga, pages 268--289. Springer Lect. Notes Comp. Sci. (1608), September 1998.
• 23: Vlada Matena , Mark Hapner, Applying Enterprise Javabeans: Component-Based Development for the J2ee Platform, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 24: Conor McBride, Faking it Simulating dependent types in Haskell, Journal of Functional Programming, v.12 n.5, p.375-392, July 2002 [doi>10.1017/S0956796802004355]
• 25: G. H. Mealy. A Method for Synthesizing Sequential Circuits. Bell Systems Techn. Jour., 34(5):1045--1079, 1955.
• 26: Sun Meng , Luís S. Barbosa, Components as coalgebras: the refinement dimension, Theoretical Computer Science, v.351 n.2, p.276-294, 21 February 2006 [doi>10.1016/j.tcs.2005.09.072]
• 27: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 28: O. Nierstrasz and F. Achermann. A Calculus for Modeling Software Components. In F. S. de Boer, M. Bonsangue, S. Graf, and W.-P. de Roever, editors, Proc. First International Symposium on Formal Methods for Components and Objects (FMCO'02), pages 339--360. Springer Lect. Notes Comp. Sci. (2852), 2003.
• 29: Oscar Nierstrasz , Laurent Dami, Component-oriented software technology, Object-oriented software composition, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 30: S. Oaks and H. Wong. Jini in a Nutshell. O'Reilly and Associates, 2000.
• 31: G. Papadopoulos and F. Arbab. Coordination Models and Languages. In Advances in Computers -- The Engineering of Large Systems, volume 46, pages 329--400. Centrum voor Wiskunde en Informatica (CWI), 1998.
• 32: D. Parnas. Information Distribution Aspects of Design Methodology. In Information Processing '72, pages 339--344. North-Holland, 1972.
• 33: S. P. Jones , E. Meijer , D. Leijen, Scripting COM Components in Haskell, Proceedings of the 5th International Conference on Software Reuse, p.224, June 02-05, 1998
• 34: J. J. M. M. Rutten, Universal coalgebra: a theory of systems, Theoretical Computer Science, v.249 n.1, p.3-80, Oct. 2000 [doi>10.1016/S0304-3975(00)00056-6]
• 35: J.-G. Schneider and O. Nierstrasz. Components, Scripts, Glue. In L. Barroca, J. Hall, and P. Hall, editors, Software Architectures -- Advances and Applications, pages 13--25. Springer-Verlag, 1999.
• 36: Jon Siegel , Dan Frantz , Hal Mirsky , Raghu Hudli , Peter de Jong , Alan Klein , Brent Wilkins , Alex Thomas , Wilf Coles , Sean Baker , Maurice Balick, COBRA fundamentals and programming, John Wiley & Sons, Inc., New York, NY, 1996
• 37: Alexandra Silva , Joost Visser, Strong types for relational databases, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA [doi>10.1145/1159842.1159846]
• 38: Clemens Szyperski, Component software: beyond object-oriented programming, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 39: P. Wadler and K. Weihe. Component-Based Programming Under Different Paradigms. Technical report, Dagstuhl Seminar 99081, February 1999.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Design, Languages, Theory, Verification

Keywords:
Haskell, coalgebra, combinator library, mealy machine, type-level programming