The semantics of graphical languages

ABSTRACT

Visual notations are pervasive in circuit design, control systems, and increasingly in mainstream programming environments. Yet many of the foundational advances in programming language theory are taking place in the context of textual notations. In order to map such advances to the graphical world, and to take the concerns of the graphical world into account when working with textual formalisms, there is a need for rigorous connections between textual and graphical expressions of computation.

To this end, this paper presents a graphical calculus called Uccello. Our key insight is that Ariola and Blom's work on sharing in the cyclic lambda calculus provides an excellent foundation for formalizing the semantics of graphical languages. As an example of what can be done with this foundation, we use it to extend a graphical language with staging constructs. In doing so, we provide the first formal account of sharing in a multi-stage calculus.

REFERENCES

• 1: Robin Abraham , Martin Erwig, Header and Unit Inference for Spreadsheets Through Spatial Analyses, Proceedings of the 2004 IEEE Symposium on Visual Languages - Human Centric Computing (VLHCC'04), p.165-172, September 26-29, 2004 [doi>10.1109/VLHCC.2004.29]
• 2: Zena M. Ariola , Stefan Blom, Cyclic Lambda Calculi, Proceedings of the Third International Symposium on Theoretical Aspects of Computer Software, p.77-106, September 23-26, 1997
• 3: Margaret Burnett , John Atwood , Rebecca Walpole Djang , James Reichwein , Herkimer Gottfried , Sherry Yang, Forms/3: A first-order visual language to explore the boundaries of the spreadsheet paradigm, Journal of Functional Programming, v.11 n.2, p.155-206, March 2001
• 4: W. Citrin, M. Doherty, and B. Zorn. Formal semantics of control in a completely visual programming language. In Allen L. Ambler and Takayuki Dan Kimura, editors, Proceedings of the Symposium on Visual Languages, pages 208--215, Los Alamitos, CA, USA, October 1994. IEEE Computer Society Press.
• 5: W. Citrin , R. Hall , B. Zorn, Programming with visual expressions, Proceedings of the 11th International IEEE Symposium on Visual Languages, p.294, September 05-09, 1995
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Stephan Ellner. Preview: An untyped graphical calculus for resource-aware programming. Master's thesis, Rice University, 2004.
• 8: Stephan Ellner and Walid Taha. The semantics of graphical languages. 2006. Available in Informal Proceedings of DCC {20}.
• 9: M. Erwig. Abstract syntax and semantics of visual languages. Jounral of Visual Languages and Computing, 9:461--483, October 1998.
• 10: Martin Erwig , Margaret M. Burnett, Adding Apples and Oranges, Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages, p.173-191, January 19-20, 2002
• 11: M. Erwig , B. Meyer, Heterogeneous visual languages-integrating visual and textual programming, Proceedings of the 11th International IEEE Symposium on Visual Languages, p.318, September 05-09, 1995
• 12: National Instruments. LabVIEW Student Edition 6i. Prentice Hall, 2001.
• 13: Simon Peyton Jones , Alan Blackwell , Margaret Burnett, A user-centred approach to functions in excel, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.165-176, August 25-29, 2003, Uppsala, Sweden
• 14: Edward A. Lee, What's Ahead for Embedded Software?, Computer, v.33 n.9, p.18-26, September 2000
• 15: MetaOCaml: A compiled, type-safe multi-stage programming language. Available online from http://www.metaocaml.org/, 2004.
• 16: National Instruments. LabVIEW. Online at http://www.ni.com/labview.
• 17: Oregon Graduate Institute Technical Reports. P.O. Box 91000, Portland, OR 97291--1000, USA. Available online from ftp://cse.ogi.edu/pub/tech-reports/README.html.
• 18: Jan Rekers and Andy Schuerr. Defining and parsing visual languages with layered graph grammars. Journal of Visual Languages and Computing, 8(1):27--55, 1997.
• 19: Amr Afaf Sabry, The formal relationship between direct and continuation-passing style optimizing compilers: a synthesis of two paradigms, Rice University, Houston, TX, 1996
• 20: Mary Sheeran and Tom Melham, editors. Sixth International Workshop on Designing Correct Circuits: Vienna, 25--26 March 2006: Participants' Proceedings. ETAPS 2006, March 2006. A Satellite Event of the ETAPS 2006 group of conferences.
• 21: Walid Mohamed Taha , Tim Sheard, Multistage programming: its theory and applications, Oregon Graduate Institute of Science and Technology, 1999
• 22: Walid Taha , Michael Florentin Nielsen, Environment classifiers, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.26-37, January 15-17, 2003, New Orleans, Louisiana, USA
• 23: The MathWorks. Simulink. Online at http://www.mathworks.com/products/simulink.
• 24: Uccello: A model for supporting higher-order, generative programming in visual languages. Available online from http://www.resource-aware.org/twiki/pub/RAP/WebHome/final-small.png, 2006.
• 25: Da-Qian Zhang, Kang Zhang, and Jiannong Cao. A context-sensitive graph grammar formalism for the specification of visual languages. The Computer Journal, 44(3): 186--200, 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments

General Terms:
Design, Languages