×

Semantics of multiway dataflow constraint systems. (English) Zbl 1518.68052

Summary: Multiway dataflow constraint systems (MDCS) is a programming model where statements are not executed in a predetermined order. Rather, individual methods are selected from specific method sets and then executed to achieve a desired global state. The selection is done by a planner, which typically bases the choice of methods on the history of updates to the global state. MDCS is well suited for describing user interface logic where choosing what code to execute depends in complicated ways on the history of user interactions and on data availability. User interfaces are the domain of examples in this paper.
Much of the research into MDCS has been on planning algorithms and their efficiency. Here we investigate a semantic setting for MDCS, introducing dataflow constraints as modules with explicit goals and related method sets. MDCS is defined in a similar manner, with an explicit goal and a set of supporting dataflow constraints. This enables verification and testing of methods and dataflow constraints against the goals. The exposition is based on abstract syntax for an idealised programming language with global variables. On top of this we define a modular reuse mechanism for dataflow constraints based on Goguen-Burstall institution theory. We show how this setup enables reuse in user interfaces; traditionally code that defines user interface logic is almost invariably non-reusable.

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
03B70 Logic in computer science
03G30 Categorical logic, topoi
68Q55 Semantics in the theory of computing

Software:

LARCH; Skyblue; Hets; CASL; Amulet
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Sutherland, I. E., Sketchpad: a man-machine graphical communication system, (Proceedings of the May 21-23, 1963, Spring Joint Computer Conference. Proceedings of the May 21-23, 1963, Spring Joint Computer Conference, AFIPS’63 (Spring) (1963), ACM: ACM New York, NY, USA), 329-346
[2] Myers, B. A.; McDaniel, R. G.; Miller, R. C.; Ferrency, A. S.; Faulring, A.; Kyle, B. D.; Mickish, A.; Klimovitski, A.; Doane, P., The Amulet environment: new models for effective user interface software development, IEEE Trans. Softw. Eng., 23, 6, 347-365 (1997)
[3] Myers, B.; Giuse, D.; Dannenberg, R.; Zanden, B.; Kosbie, D.; Pervin, E.; Mickish, A.; Marchal, P., Garnet: comprehensive support for graphical, highly interactive user interfaces, Computer, 23, 11, 71-85 (Nov. 1990)
[4] Vander Zanden, B., An incremental algorithm for satisfying hierarchies of multiway dataflow constraints, ACM Trans. Program. Lang. Syst., 18, 1, 30-72 (Jan. 1996)
[5] Järvi, J.; Foust, G.; Haveraaen, M., Specializing planners for hierarchical multi-way dataflow constraint systems, (Proceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences. Proceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences, GPCE 2014 (2014), ACM: ACM New York, NY, USA), 1-10
[6] Järvi, J.; Haveraaen, M.; Freeman, J.; Marcus, M., Expressing multi-way data-flow constraint systems as a commutative monoid makes many of their properties obvious, (Proceedings of the 8th ACM SIGPLAN Workshop on Generic Programming. Proceedings of the 8th ACM SIGPLAN Workshop on Generic Programming, WGP’12 (2012), ACM: ACM New York, NY, USA), 25-32
[7] Sannella, M., Skyblue: a multi-way local propagation constraint solver for user interface construction, (Proceedings of the 7th Annual ACM Symposium on User Interface Software and Technology. Proceedings of the 7th Annual ACM Symposium on User Interface Software and Technology, UIST’94 (1994), ACM: ACM New York, NY, USA), 137-146
[8] McCartney, T. P., User interface applications of a multi-way constraint solver (Oct. 1995), Washington University of Saint Louis: Washington University of Saint Louis MO: Computer Science, Tech. Rep. WUCS-95-22
[9] Oney, S.; Myers, B.; Brandt, J., ConstraintJS: programming interactive behaviors for the web by integrating constraints and states, (Proceedings of the 25th Annual ACM Symposium on User Interface Software and Technology. Proceedings of the 25th Annual ACM Symposium on User Interface Software and Technology, UIST’12 (2012), ACM: ACM New York, NY, USA), 229-238
[10] Lin, K.; Chen, D.; Dromey, G.; Sun, C., Maintaining constraints expressed as formulas in collaborative systems, (2007 International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom 2007) (2007)), 318-327
[11] Demetrescu, C.; Finocchi, I.; Ribichini, A., Reactive imperative programming with dataflow constraints, (Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications. Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA’11 (2011), ACM: ACM New York, NY, USA), 407-426
[12] Felgentreff, T.; Borning, A.; Hirschfeld, R., Specifying and solving constraints on object behavior, J. Object Technol., 13, 4, 1-38 (2014)
[13] Goguen, J. A.; Burstall, R. M., Institutions: abstract model theory for specification and programming, J. ACM, 39, 1, 95-146 (1992) · Zbl 0799.68134
[14] Sannella, D.; Tarlecki, A., Foundations of Algebraic Specification and Formal Software Development, Software Development, Monographs in Theoretical Computer Science. An EATCS Series (2012), Springer · Zbl 1237.68129
[15] Mosses, P. D.; Manual, CASL Reference, The Complete Documentation of the Common Algebraic Specification Language, Lecture Notes in Computer Science, vol. 2960 (2004), Springer · Zbl 1046.68001
[16] Mossakowski, T.; Maeder, C.; Lüttich, K., The heterogeneous tool set, Hets, (Grumberg, O.; Huth, M., Tools and Algorithms for the Construction and Analysis of Systems, 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software. Tools and Algorithms for the Construction and Analysis of Systems, 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Braga, Portugal, Proceedings. Tools and Algorithms for the Construction and Analysis of Systems, 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software. Tools and Algorithms for the Construction and Analysis of Systems, 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Braga, Portugal, Proceedings, Lecture Notes in Computer Science, vol. 4424 (2007), Springer), 519-522
[17] Goguen, J. A., Memories of ADJ, (Rozenberg, G.; Salomaa, A., Current Trends in Theoretical Computer Science - Essays and Tutorials. Current Trends in Theoretical Computer Science - Essays and Tutorials, World Scientific Series in Computer Science, vol. 40 (1993), World Scientific), 76-81
[18] Goguen, J.; Thatcher, J.; Wagner, E., An initial algebra approach to the specification, correctness and implementation of abstract data types, (Yeh, R., Current Trends in Programming Methodology, vol. 4 (1978), Prentice Hall), 80-149
[19] Guttag, J. V.; Horning, J. J., The algebraic specification of abstract data types, Acta Inform., 10, 27-52 (1978) · Zbl 0369.68010
[20] Guttag, J. V.; Horning, J. J.; Garland, S. J.; Jones, K. D.; Modet, A.; Wing, J. M., Larch: Languages and Tools for Formal Specification, Texts and Monographs in Computer Science, 1993 (1993), Springer · Zbl 0794.68103
[21] Ehrig, H.; Mahr, B., Fundamentals of Algebraic Specification 1: Equations and Initial Semantics, EATCS Monographs on Theoretical Computer Science, vol. 6, 1985 (1985), Springer · Zbl 0557.68013
[22] Ehrig, H.; Mahr, B., Fundamentals of Algebraic Specification 2, EATCS Monographs on Theoretical Computer Science, vol. 21, 1990 (1990), Springer · Zbl 0759.68013
[23] Järvi, J.; Marcus, M.; Parent, S.; Freeman, J.; Smith, J. N., Algorithms for user interfaces, (GPCE’09: Proc. of 8th International Conference on Generative Programming and Component Engineering (2009), ACM: ACM New York, NY, USA), 147-156
[24] Foust, G.; Järvi, J.; Parent, S., Generating reactive programs for graphical user interfaces from multi-way dataflow constraint systems, (Proceedings of the 2015 International Conference on Generative Programming: Concepts and Experiences. Proceedings of the 2015 International Conference on Generative Programming: Concepts and Experiences, GPCE 2015 (2015), ACM: ACM New York, NY, USA), 121-130
[25] Freeman, J.; Järvi, J.; Kim, W.; Marcus, M.; Parent, S., Helping programmers help users, (GPCE’11: Proc. of 10th International Conference on Generative Programming and Component Engineering (2011), ACM: ACM New York, NY, USA), 177-184
[26] Allison, L., Programming denotational semantics II, Comput. J., 28, 5, 480-486 (1985) · Zbl 0571.68005
[27] Bagge, A. H.; David, V.; Haveraaen, M., Testing with axioms in C++ 2011, J. Object Technol., 10, 10, 1-32 (2011)
[28] Hamlet, R., Random testing, (Marciniak, J., Encyclopedia of Software Engineering (1994), Wiley), 970-978 · Zbl 0821.68001
[29] Bernardy, J.-P.; Jansson, P.; Claessen, K., Testing polymorphic properties, (Gordon, A., Programming Languages and Systems: Proceedings of the 19th European Symposium on Programming (ESOP 2010). Programming Languages and Systems: Proceedings of the 19th European Symposium on Programming (ESOP 2010), Lecture Notes in Computer Science, vol. 6012 (2010), Springer), 125-144 · Zbl 1260.68084
[30] Sannella, D.; Tarlecki, A., Specifications in an arbitrary institution, Inf. Comput., 76, 2, 165-210 (1988) · Zbl 0654.68017
[31] Haveraaen, M.; Roggenbach, M., Specifying with syntactic theory functors, J. Log. Algebraic Methods Program., 113, Article 100543 pp. (2020) · Zbl 1433.68221
[32] Goguen, J. A.; Rosu, G., Institution morphisms, Form. Asp. Comput., 13, 3-5, 274-307 (2002) · Zbl 1001.68019
[33] Meseguer, J., General logics, (Ebbinghaus, H.-D.; Fernández-Prida, J.; Garrido, M.; Lascar, D.; Rodríguez Artalejo, M., Logic Colloquium’87 (1989), North-Holland), 275-329 · Zbl 0691.03001
[34] Sannella, M. J., Constraint satisfaction and debugging for interactive user interfaces (1994), University of Washington: University of Washington Seattle, WA, USA, UW Tech Report 94-09-10
[35] Trombettoni, G.; Neveu, B., Computational complexity of multi-way, dataflow constraint problems, (Proceedings of the 15th International Joint Conference on Artifical Intelligence-vol. 1. Proceedings of the 15th International Joint Conference on Artifical Intelligence-vol. 1, IJCAI’97 (1997), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 358-363
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.