×

Graphical and incremental type inference. A graph transformation approach. (English) Zbl 1360.68320

Summary: We present a graph grammar based type inference system for a totally graphic development language. NiMo (Nets in Motion) can be seen as a graphic equivalent to Haskell that acts as an on-line tracer and debugger. Programs are process networks that evolve giving total visibility of the execution state, and can be interactively completed, changed or stored at any step. In such a context, type inference must be incremental. During the net construction or modification only type safe connections are allowed. The user visualizes the type information evolution and, in case of conflict, can easily identify the causes. Though based on the same ideas, the type inference system has significant differences with its analogues in functional languages. Process types are a non-trivial generalization of functional types to handle multiple outputs and deferred arguments even in higher order parameters, partial application in any order and Curried-un-Curried coercion. Here we present the elements to model graphical inference, the notion of structural and non-structural equivalence of type graphs, and a graph unification and composition calculus for typing nets in an incremental way.

MSC:

68N18 Functional programming and lambda calculus
68Q42 Grammars and rewriting systems

Software:

AGG; Miranda; Haskell; Lua
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] AGG Home page: http://user.cs.tu-berlin.de/ gragra/agg/ (2009)
[2] Clerici, S.; Zoltan, C.; Loidl, HW (ed.), A graphic functional-dataflow language, No. 5, 129-144 (2004), Bristol
[3] Clerici, S., Zoltan, C.: Graphical type inference. A graph grammar definition. Technical Report LSI-07-24-R, Department Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya. http://www.lsi.upc.edu/dept/techreps/llistat_detallat.php?id=970 (2007)
[4] Clerici, S., Duch, A., Zoltan, C.: Implementing static synchronus sensor fields using NiMo. Technical Report LSI-09-13-R, Department Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya. http://www.lsi.upc.edu/dept/techreps/llistat_detallat.php?id=1052 (2009)
[5] Clerici, S., Zoltan, C.: A dynamically customizable process-centered evaluation model. In: PPDP ’09: proceedings of the 11th ACM SIGPLAN conference on principles and practice of declarative programming, pp. 37-48. ACM, New York (2009)
[6] Clerici, S., Zoltan, C.: Prestigiacomo G Nimotoons: a totally graphic workbench for program tuning and experimentation. Electr. Note Theor. Comput. Sci. 258(1), 93-107 (2009) · doi:10.1016/j.entcs.2009.12.007
[7] Erwig, M.: Visual type inference. J. Vis. Lang. Comput. 17(2), 161-186 (2006) · doi:10.1016/j.jvlc.2005.04.004
[8] König, B.A.: general framework for types in graph rewriting. Acta Inform. 42(4), 349-388 (2005) · Zbl 1081.68040 · doi:10.1007/s00236-005-0180-4
[9] LabView Home page: http://www.ni.com/gettingstarted/labviewbasics/dataflow.htm (2012)
[10] Lanaspre, B., Glaser, H.: Type inference in prograph. Technical Report DSSE-TR-95-3, Department of Electronics and Computer Science, University of Southampton (1995)
[11] Lua Home Page: http://www.lua.org/ (2013)
[12] Mcadam, BJ; Trinder, P. (ed.); Michaelson, G. (ed.); Loidl, HW (ed.), Generalising techniques for type debugging, 49-57 (2000), Bristol
[13] NiMo Home Page: http://www.lsi.upc.edu/ nimo/Project (2012)
[14] Resources: http://resources.businessobjects.com/labs/cal/gemcutter-techpaper (2009)
[15] Rozenberg, G. (ed.): Handbook of Graph Grammars and Computing by Graph Transformations, vol. 1: Foundations. World Scientific, Singapore (1997) · Zbl 0908.68095
[16] Siek, J.G., Taha, W.: Gradual typing for functional languages. In: Scheme and Functional Programming, Workshop pp. 81-92 (2006)
[17] Simões, H., Florido, M.: TypeTool—a type inference visualization tool. In: Proceedings of the 13th International Workshop on Functional and (Constraint) Logic Programming (2004)
[18] System-I: http://types.bu.edu/modular/compositional/system-i/ (2012)
[19] Turner, D.A.: Miranda: a non-strict functional language with polymorphic types. In: Proceeding of a Conference on Functional Programming Languages and Computer Architecture, pp. 1-16. Springer-Verlag New York Inc, New York (1985) · Zbl 0592.68014
[20] V-Rep Home Page: http://coppeliarobotics.com/ (2013)
[21] Yang, J., Michaelson, G.: A visualisation of polymorphic type checking. J. Funct. Program. 10, 57-75 (2000) · doi:10.1017/S0956796899003597
[22] Yang, J., Michaelson, G., Trinder, P., Wells, J.B.: Improved type error reporting. In: Proceedings of 12th International Workshop on Implementation of Functional Languages, pp. 71-86 (2000)
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.