-

Multi-Language Modelling with Second Order Intensions

Vadim Zaytsev

vadim@grammarware.net 0 0 Universiteit van Amsterdam , The Netherlands

In the last decade, there have been several fundamental advances in the field of ontological and linguistic metamodelling. They proposed the use of megamodels to link abstract, digital and physical systems with a particular set of useful relations; the distinction between ontological and linguistic layers, identification and separation of them; even formalised the act of modelling and the sense and denotation of a language. In this paper, we propose second order intensions and extensions to more closely model linguistical and ontological conformance and mapping.

in user concepts that use UML concepts; UML concepts model user concepts in MOF; and MOF models UML concepts and defines both a language for them and a metalanguage for expressing itself. In this view, a new relation emerges: an instance of (we will denote it as ), which is more abstract than the " relation since it works formally even in situations when a set of all valid models cannot be expressed or when it does not make sense conceptually to express it. For example, an object is an instance of its class, and it is much less interesting to consider the set of all possible objects of a class than to investigate the nature of this instantiation and the consequences thereof. Since instantiations is sometimes hard to express universally, we also speak of a conforms to ( ) relation [ 2 ]: a model conforms to a metamodel, an object conforms to a class, a program conforms to a programming language, a database conforms to a schema. Since this theory is rooted in the modelling community, relations and are commonly used together with a representation of relation used in the conceptual sense: an object Cat models a real cat even though there might be no “language of cats” and the construction of a set of all possible cats is often unnecessary. Relations can be diagrammatically combined to form so called megamodels [ 3,6,5 ], an example shown on Figure 1.

Formal metamodelling distinguishes between two kinds of instance of relations: the linguistic instance of and the ontological instance of [ 1 ]. This complicates the metamodelling process somewhat but removes most ambiguity associated with the relation: the object Fluffy models a very particular cat and it is both an ontological instance of a class Cat (because Fluffy the real cat is a conceptual instance of cats in general) and a linguistic instance of an Object (because it needs to belong to a certain class, to be instantiated in a certain way and obey other constraints typical for all objects but not for all cats). An example is given on Figure 2 and is easily extensible to new ontological levels: cats are ontological instances of species, which are ontological instances of a biological rank [1, Fig.5] — and the formalisation still allows us to distinguish these modelling statements from ones that stay within one ontological level (i.e., that cats are pets, carnivores, mammals, animals, etc — in the object-oriented technological space this is called inheritance). Adding more languages and transL C ? (cats)

O Fluffy

C 6 O

L - T

6 L - O formations into the megamodel is somewhat more problematic due to the grid nature of the diagrams and to the lack of definitions of ontological instantiation for some languages. Coming back from biology to computer science, this allows us to properly specify that a particular program is a (linguistic) instance of say Java, but an ontological instance of a database application and as such, also obeys a set of structural and behavioural rules.

The next step in refining the theory of metamodelling of megamodels was separating the intensional and the extensional parts of the language [ 7 ]. The extensional part is argued to be the set of models allowed in the language. The intensional part models constrains and properties that are characteristic to the instances of the language. If such a distinction is introduced, the meaning of being the “instance of” something becomes ultimately apparent: the model in question must conform ( ) to the intensional part and it is an element (") of the extensional part. Since the extension of an abstract system always resides on the lower ontological level, the diagram is also nicely composed of tiles of the metalevel entry and its intentional part on top and its extensional part (the set of valid instances) and the model-level entry that conforms to the intensional part, is an element of the extensional part and is at the same time an instance of the abstract system. An example migrated from the technological space of cats, dogs, breeds and animals, to programming languages, can be seen on Figure 3 (read ^ as “has intension” and _ as “has extension”, as was often used for “decomposed in”). In general, tiles like these can always substitute the megapattern from Figure 1, it is in fact its ontology-aware refinement.

H _H ^H

L _L ^L ! a particular Haskell program ! the Haskell language ! set of all valid Haskell programs ! constraints imposed on a Haskell program ! a programming language ! set of all programming languages ! properties that make up a language In the domain of programming languages, one often speaks of a conformance of a program to the grammar of the language in which the program was written in. Is such a grammar the same as the intensional part of the language? (G = ^L?)

The answer given by the formal language theory is yes — however, this theory has a slightly different megamodel of the situation: since a language is equated with its extensional part, the “instance of” relation is equated with the “element of” relation. Furthermore, instead of the language being decomposed into two parts, its intension is treated as a model of its extension (which is typically infinite, so it helps to have a finite model of it). The result is depicted on Figure 4 in the same style we have used so far. As an example we can consider the technological space of XML: then P is an XML document, G is a DTD or an XML Schema definition, the validator uses G to check P ! G and programs in XSLT, XQuery, JavaScript and other languages can be written to work on elements of L.

In a more general case, the role of a grammar is the G ! L chain is called generative or derivational and is used in most proofs in the theory of formal languages and automata. Its role in the P ! G chain is called analytical and is often utilised by using it prescriptively [ 8 ] and generating a parser out of it. What does such a parser do? In the simplest case, it analyses the text of the program and constructs a term that aligns tokens (lexemes) of the input with its understanding of how the structure of any program should look like. This already does not fit our picture at all, and we lack means to express that not only the grammar serves in at least two different roles, but also the language apparently at the same time is a language of strings (that are acceptable inputs ? L ^ - G " 6 P - JP K for a parser) and a language of terms or trees (that are outputs of a parser). An attempt to fit this transformational megapattern into our view is shown on Figure 5: a grammar G serves a model of both two languages (textual and tree language) and the mapping between two representations of the same program (the text and the parse tree). However, since LC and LT are implicit, we cannot make any statement about the relation between LT and LC , which makes the megamodel a bit less useful.

This multipurposefulness of grammars in a broad sense is unfortunate from the modelling point of view, but it explains their omnipresence in software engineering [ 10 ]. In terms of modelling modelling1, G X for all megamodel elements X related to G: they share some intention and can be partially represented by one another [ 13 ]. We will explore this intersection in the next section and make it explicit.

In practical software language processing, grammars try to balance in between all these roles, with a varying degree of success. In certain cases, people separate some constraints (traditionally called static semantic rules) that are too hard to express in the chosen grammar formalism and are purely related to G ! L and P ! G; in other cases (in particular related to mapping between already structured concrete syntax and an improved abstract syntax) there could be several grammars defining separate languages, with G ! included in one of them or shipped as a third separate artefact.

Interestingly, the role of a language in modelware engineering is slightly different yet also not perfect. Consider the following statement [ 13 ]: n F ! L !

M j M ! S o

What is stated here is that the formal system F truthfully models a language L which in turn models a set of models M such that they all model the system S. 1 NB: the original MoDELS 2009 paper used “ j ” for shared intention instead, we use a much more fitting notation from the extended journal version.

? LT "

^ PT - G

JP K

^ - PC _ - ? " - LC

If represented diagrammatically on Figure 6, we see the main differences between our approach and the method of Muller et al: instead of being decomposed into an intension and an extension, the language is considered to be a model of its extension, and its intension (grammar in a broad sense, some kind of formal model by requirements) is considered to be its model. Furthermore, there is no explicit consideration for the conformance between the models and this formal definition. 3

Second order to the rescue As we have seen, the grammar of a software language is its intensional part (or approximates it very closely). Let us deconstruct it further. For ^Collie, Gašević et al claimed it was a model of the real world intension of the concept of a collie, combining properties such as “has long hair”, “has bushy tail” and “can herd sheep” [ 7 ]. For a programming language, the intension is a model of two kinds of properties: essential (“supports parametric polymorphism”, “uses lazy evaluation”, “contains a conditional statement which must contain a condition and a statement”, “variable names should start with a letter”) circumstantial (“functions have comma-separated arguments”, “statement blocks are defined by indentation”, “one statement per line of code”). The essential properties refer to the way the language concepts are constructed and manipulated — therefore, their model is the intension of the intension of the language (^^L). The circumstantial properties refer to the way the concepts of the language are represented in the instances — in other words, how language instances (elements of _L) are constructed; hence, it is the intension of the extension of the language (^_L). The extension of the intension is even more interesting because it is supposed to collect examples of how the intensions can be expressed: it is a collection of all possible syntaxes for a language. To the best of our knowledge such an entity has not yet been formally investigated, but if it also represented as a set, the intension of the extension is an element of that set; otherwise it is still bound to be an instance of _^L. The resulting diagram is depicted on Figure 7 with the decomposition, conformance and instantiation relations.

Since now we have ^^L to denote the constraints essential to the language L, it should be the same for all related languages. Indeed, if the modelling intent [ 17 ] is limited to this essence, and a grammar that respects it, it also models all variants of languages closely without any regard to the choice of ^_L. In other words, for 0 = =^^L, _LT 0

!0 _LC

This result agrees with the “shift in linguistical conformance” by Muller et al [ 13 ] (when talking about mapping among models with the same intent) and with the “constant functions all the way down” by Dowty et al [ 4 ] (when talking about intensions of intensions). The final diagram is presented on Figure 8: a “real” program can be encoded by a programmer as either text (conforming to ^_LT ) or a tree (conforming to ^_LC ), and as long as the intension of the intension is preserved (PT ! ^^L), the languages stay same but different and valid instances can be freely mapped in any direction. The same holds for mappings between abstract syntax and concrete syntax, up to a homomorphism (such mappings often permute arguments and perform other component rearrangements). 4

Concluding remarks and related work In short, we have proposed to consider four components of software languages: intension-intensions (conceptual constraints to always conform to); extension

? _L w w w w w w w w w w __L ^- ^_L ^ " - ^L _

? - _^L

P ^- ^^L Fig. 7. The language L is decomposed ( ) into its intensional (^L) and extensional (_L) parts. They are, in turn, decomposed in the same fashion. The extensional part _L is a set, so the extension of the extension __L is the same set. However, the intension of the extension ^_L represents structural constraints of the elements of the set, while the intension of the intension ^^L represents linguistic constraints that refer to the intensional language and not to its accidental representation. The extension of the intension _^L represents a model of possible syntactic representations of programs in the language: it is modelled by a simple set, the particular syntax ^_L is an element of that set, otherwise it is still bound there in an instance of ( ) relation. extensions (sets of valid language instances in a given notation); intentions of extensions (circumstantial constraints specific to the chosen syntax but not the the language as such); extensions of intensions (models of possible syntaxes compatible with the language core), in a hope that it brings us closer to understanding the nature of modelling languages and various artefacts related to them. In previously existing work, languages are mostly considered either with a fixed syntax or with two or three of them which are also fixed and claimed to be related to different aspects of language processing. This work can serve as a foundation for formal manipulation of languages with multiple syntaxes, or systems where “the same” language is claimed to be used across technical spaces (ORM, parsing, convergence, etc).

For the sake of clarity and conciseness of notation, we have opted for the use of commutative diagrams to represent megamodels instead of using any of the existing megamodelling languages. We have adopted Favre’s symbols for relations: as “models” or “representation of”; " as “element of”, as “conforms to”. Atkinson and Kühne did not have a shorthand notation so we used O for “ontological instance of”, L for “linguistic instance of” and just for “instance of” where the meaning is unknown or universal. We have adopted Montague notation: ^L for intensions and _L for extensions. We also took the liberty of using JP K for denotations of single instances — in formal semantic theory denotation is equated to extension but in the current state of multi-level metamodelling we do not yet need to differentiate between ^P and _P . However, in the future research on multi-language modelling, we recommend to consider substituting _LT w w w w w w w w w w __LT - ^_LT ^ " _

? - _^LT

PT _

? _LC w w w w w w w w w w - __LC

JP K with ^P and using _P for the hypothetical set of all possible representations of a program P .

The notion of commitment to grammatical structure was discussed by Klint, Lämmel and Verhoef [ 10 ], and recently was elaborated by a megamodel of various software language engineering artefact kinds such as parse trees, visual models, lexical templates, etc, in the context of (un)parsing in a broad sense [ 18 ]. The contribution of this paper to that trend was showing that concrete syntaxes are ontological instances of the abstract syntax (more precisely, ^_L ! _^L). The idea that a software language should be allowed to have different syntaxes while staying essentially the same language, is not new but has always been rejected by formalisations.

Atkinson [ 1 ], Bézivin [ 3 ], Favre [ 6 ], Gašević [ 7 ], Kühne [ 11 ], Muller [ 13 ] and many others have made significant contributions to comprehension and refinement of the processes of modelling, metamodelling and megamodelling. This paper is an endeavour to contribute to that trend by making a yet another step in improving the formalisations, as well as by providing concrete examples from software and grammarware engineering, even when they seemed less suitable to discuss ontological matters than the classic Lassie/Fido – Collie – Breed example. We hope such results will both help to identify problems we can solve in the future and bring less meta-minded modelling practitioners and language engineers closer.

Apart from the Fregean perspective on intensional logic, Montague considered a Russelian variant where the extension of the intension (called the “sense denotation”) is not a fundamental concept [ 12 ]. It has proven to be less useful to him, but in software language engineering this idea has never even been tried yet.

Atkinson and

Kühne . Model-Driven Development : A Metamodeling Foundation . IEEE Software , 20 ( 5 ): 36 - 41 , 2003 .

Bézivin . In search of a basic principle for model-driven engineering . Novatica Journal , 2004 .

Bézivin ,

Jouault , and

Valduriez . On the Need for Megamodels . OOPSLA & GPCE, Workshop on best MDSD practices , 2004 .

D. R.

Dowty ,

R. E.

Wall , and

Peters . Introduction to Montague Semantics. Kluwer Academic Publishers, 1981 .

5. J.-M. Favre . Towards a Basic Theory to Model Driven Engineering . In Proceedings of the Third Workshop on Software Model Engineering , 2004 .

6. J.-M. Favre and T. NGuyen . Towards a Megamodel to Model Software Evolution through Transformations . Electronic Notes in Theoretical Computer Science, Proceedings of the SETra Workshop , 127 ( 3 ), 2004 .

Gašević ,

Kaviani , and

Hatala . On Metamodeling in Megamodels . In MODELS'07 , pages 91 - 105 , 2007 .

Hesse . More Matters on (Meta-)Modeling: Remarks on Kühne's “matters” . SoSyM , 5 ( 4 ): 387 - 394 , 2006 .

J. E.

Hopcroft ,

Motwani , and

J. D.

Ullman . Introduction to Automata Theory, Languages, and Computation . Addison-Wesley, third edition , 2007 .

10.

Klint ,

Lämmel , and

Verhoef . Toward an Engineering Discipline for Grammarware . ACM ToSEM , 14 ( 3 ): 331 - 380 , 2005 .

11.

Kühne and

Schreiber . Can Programming be Liberated from the Two-Level Style: Multi-Level Programming with DeepJava . In OOPSLA , pages 229 - 244 . ACM, 2007 .

12.

Montague . Universal Grammar. Theoria, 36 ( 3 ): 373 - 398 , 1970 .

13. P. -

A. Muller , F.

Fondement , B.

Baudry , and B.

Combemale . Modeling Modeling Modeling. SoSyM , 11 ( 3 ): 347 - 359 , 2012 .

14. Object Management Group. Unified Modeling Language, 2.1.1 edition , 2007 . Available at http://schema.omg.org/spec/UML/2.1.1.

15. Object Management Group. Meta-Object Facility (MOFTM) Core Specification, 2.0 edition , January 2006 . Available at http://www.omg.org/spec/MOF/2.0.

16.

Tomita . Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems . Kluwer Academic Publishers, 1985 .

17.

E. S. K.

Yu and

Mylopoulos . Understanding “ Why” in Software Process Modelling, Analysis, and Design. In ICSE , pages 159 - 168 . IEEE Computer Society / ACM Press, 1994 .

18.

Zaytsev and

A. H.

Bagge . Parsing in a Broad Sense . In J. Dingel,

Schulte , I. Ramos,

Abrahão , and E. Insfran, editors, Proceedings of the 17th International Conference on Model Driven Engineering Languages and Systems (MoDELS 2014 ), volume 8767 of LNCS , pages 50 - 67 , Switzerland, Oct. 2014 . Springer International Publishing.