Conference article

Type-Based Structural Analysis for Modular Systems of Equations

Henrik Nilsson
School of Computer Science, University of Nottingham, UK

Download article

Published in: Proceedings of the 2nd International Workshop on Equation-Based Object-Oriented Languages and Tools

Linköping Electronic Conference Proceedings 29:8, p. 71-81

Show more +

Published: 2008-07-02

ISBN: 978-91-7519-823-1

ISSN: 1650-3686 (print), 1650-3740 (online)

Abstract

This paper investigates a novel approach to a type system for modular systems of equations; i.e.; equation systems constructed by composition of individual equation system fragments. The purpose of the type system is to ensure; to the extent possible; that the composed system is solvable. The central idea is to attribute a structural type to equation system fragments that reflects which variables occur in which equations. In many instances; this allows over- and underdetermined system fragments to be identified separately; without first having to assemble all fragments into a complete system of equations. The setting of the paper is equation-based; non-causal modelling; specifically Functional Hybrid Modelling (FHM). However; the central ideas are not tied to FHM; but should be applicable to equation-based modelling languages in general; like Modelica; as well as to applications featuring modular systems of equations outside the field of modelling and simulation.

Keywords

Equation-based; non-causal modelling; Modelica; Functional Hybrid Modelling; structural analysis; types; type-based analysis; dependent types

References

[1] Alfred V. Aho; John E. Hopcroft; and Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley Publishing Company; 1983.

[2] David Broman; Kaj Nyström; and Peter Fritzson. Determining over- and under-constrained systems of equations using structural constraint delta. In GPCE ’06: Proceedings of the 5th international conference on Generative programming and component engineering; pages 151–160; Portland; Oregon; USA; 2006. ACM.

[3] Peter Bunus and Peter Fritzson. A debugging scheme for declarative equation based modeling languages. In Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages (PADL 2002); volume 2257 of Lecture Notes in Computer Science; pages 280– 298; Portland; OR; USA; January 2002. Springer-Verlag.

[4] Peter Bunus and Peter Fritzson. Methods for structural analysis and debugging of Modelica models. In Proceedings of the 2nd International Modelica Conference; pages 157– 165; Oberpfaffenhofen; Germany; March 2002.

[5] Antony Courtney; Henrik Nilsson; and John Peterson. The Yampa arcade. In Proceedings of the 2003 ACM SIGPLAN Haskell Workshop (Haskell’03); pages 7–18; Uppsala; Sweden; August 2003. ACM Press.

[6] A. L. Dulmage and N. S. Mendelsohn. Coverings of bipartite graphs. Canadian Journal of Mathematics; 10:517–534; 1958.

[7] Hilding Elmqvist. A Structured Model Language for Large Continuous Systems. PhD thesis TFRT-1015; Department of Automatic Control; Lund Institute of Technology; 1978.

[8] George Giorgidze and Henrik Nilsson. Switched-on Yampa: Declarative programming of modular synthesizers. In Paul Hudak and David S. Warren; editors; Practical Aspects of Declarative Languages (PADL) 2008; volume 4902 of Lecture Notes in Computer Science; pages 282–298; San Francisco; CA; USA; January 2008. Springer-Verlag.

[9] Paul Hudak; Antony Courtney; Henrik Nilsson; and John Peterson. Arrows; robots; and functional reactive programming. In Johan Jeuring and Simon Peyton Jones; editors; Advanced Functional Programming; 4th International School 2002; volume 2638 of Lecture Notes in Computer Science; pages 159–187. Springer-Verlag; 2003.

[10] Andrew Kennedy. Dimension types. In Proceedings of the 5th European Symposium on Programming; number 788 in Lecture Notes in Computer Science. Springer-Verlag; 1994.

[11] The Modelica Association. Modelica – A Unified Object- Oriented Language for Physical Systems Modeling: Tutorial version 1.4; December 2000.

[12] The Modelica Association. Modelica – A Unified Object- Oriented Language for Physical Systems Modeling: Language Specification Version 3.0; September 2007.

[13] Henrik Nilsson; Antony Courtney; and John Peterson. Functional reactive programming; continued. In Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell’02); pages 51–64; Pittsburgh; Pennsylvania; USA; October 2002. ACM Press.

[14] Henrik Nilsson; John Peterson; and Paul Hudak. Functional hybrid modeling. In Proceedings of PADL’03: 5th International Workshop on Practical Aspects of Declarativem Languages; volume 2562 of Lecture Notes in Computer Science; pages 376–390; New Orleans; Lousiana; USA; January 2003. Springer-Verlag.

[15] Henrik Nilsson; John Peterson; and Paul Hudak. Functional hybrid modeling from an object-oriented perspective. In Peter Fritzson; François Cellier; and Christoph Nytsch- Geusen; editors; Proceedings of the 1st International Workshop on Equation-Based Object-Oriented Languages and Tools; number 24 in Linköping Electronic Conference Proceedings; pages 71–87. Linköping University Electronic Press; 2007.

[16] Benjamin C. Pierce. Types and Programming Languages. MIT Press; 2002.

[17] Simon Thompson. Type Theory and Functional Programming. Addison-Wesley Publishing Company; 1991.

[18] Zhanyong Wan and Paul Hudak. Functional reactive programming from first principles. In Proceedings of PLDI’01: Symposium on Programming Language Design and Implementation; pages 242–252; June 2000.

[19] Hongwei Xi and Frank Pfenning. Eliminating array bound checking through dependent types. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation; pages 249–257; Montreal; June 1998.

[20] Hongwei Xi and Frank Pfenning. Dependent types in practical programming. In Proceedings of ACM SIGPLAN Symposium on Principles of Programming Languages; pages 214–227; San Antonio; January 1999.

Citations in Crossref