What Does it Need to Automatically Resolve Names in Programs

A big part of a programming language's (and thats true for all textual languages defined with on context-free grammar) static semantics deals with the resolution of names. Best example: you declare a variable, giving it a name; you later use that variable by referencing the declaration, using that name. How can one describe this part of a language's static semantics so that automatically generated editors/compilers can resolve names automatically?

The identity of an element is a value that uniquely identifies this element within a program. The language defines a function (1) that assigns each element of a language instance an identity. Example identities can be the element itself, the name of the element, or more complex constructs like full qualified names. An identifier is a value used to identify a model element based on the element's identity. In simple languages, identifier can often be used directly to identify elements: if an identifier and the identity of a element are the same, this identifier identifies this element. The many languages, however, require more complex identification, including name spaces, name hiding, imports, etc. In those cases, an identifier depends on the context it is used in. The language must define a function (2) that assigns a set of possible global identifiers to an identifier and its context. These global identifiers are then used to find a element with an identity that matches on of those global identifiers.

When we describe a language with meta-modeling, all model elements are objects of given meta-classes. Identification for a specific language can easily be programmed by implementing a simple interface (here based on EMF):

1. public Object getIdentitiy(EObject object);
2. public Object[] getGlobalIdentities(Object identifier, EObject context);

With this interface, and language engineers implementing it for their languages, our Textual Editing Framework TEF can simply customize name resolution and aspects of code-completion for languages with specific identification mechanisms.

We will try in the future to use this interface to implement an identification scheme for a language with a complex name-space based identification mechanism. See, if it really is enough to describe identification sufficiently.

Textual Modelling and More Than Text Editors

On the 20th March 2008, we will release the first major version of our Textual Editing Framework. We take this as an opportunity to talk about existing frameworks and new ways to facilitate text editors for the editing of models.

"Text" Editors for Domain Specific Languages

There are several projects that try to ease the pain of creating text editors for your textual (domain specific) (modeling) language. Based on the eclipse platform, these projects created frameworks that allow to describe a textual notation and generate a "text" from this description automatically. Some of these projects are:

• xText of openArchitectureWare
  
• TCS
• the upcoming eclipse Textual Modeling Framework (TMF) [Which actually is just xText and TCS committing to the eclipse community.]
• safari [it has to be called different now, but anyone just knows it for this name]
  
• MontiCore

What all of this frameworks have in common is that they create editors that allow users to edit text files. Consequently, these generated editors are text editors.

Beyond Text Editors

Text editors, nothing wrong with that. But, to use a file edited with such an editor, it has to be transformed into a model before. So why do we use text files with concrete syntax as artifacts to store models? The reasons are manifold, but reviewed carefully, most of them are doomed to become obsolete. Storing models, programs, whatever, in concrete syntax is still the favored way of persistence, because accepted storage and versioning systems are tailored for that. CVS, SVN and most of the commercial products, all rely on text-file comparison. Text files are also preferred, when it comes to migrating sources from one language version to another. Taking models from one meta-model version to the next, is still a risky task. And even it is not easier with concrete syntax, we are at least used to migrate concrete syntax files with aged but proven technology like regular expressions.

Anyway, all these problems that hold us back from persisting models as models rather than as text, are about to be solved. Projects like EMF's compare or teneo allow to compare and store models as models. And, there are similar projects behind closed doors at SAP or IKV (just the two I happen to know). Once this technology become more accepted, the need for "text" editors that edit models and not text increases.

TEF's Three Editor Kinds

To promote the idea of text editors that work on model (XMI) files, we integrated the support for different types of editors into our own framework for textual modeling. In TEF we distinct three different editor kinds, for three different purposes. Text editors are the usual editors that edit the textual model representation and not the model. Textual model editors are actual model editors. When loaded they create a textual representation for the edited model, the user can change it, and when stored, a new model is created from the user changed text representation. The third editor kind allows to edit a partial model. These editors can be embedded into already existing model editors (host editor), like graphical or tree-based editors. These editors show in a small overlay window and edit only a part of the host-editors model.

The last two editor kinds require to create an initial textual representation for a model. This means they have to pretty print the model. To do that, they have to chose the right representation, when multiple representations are possible for the same model constructs, and they have to generate white-spaces (layout information), which is not part of the model. TEF solves both problems by allowing language engineers to add according clues to the language notation. The language engineer can prioritize notation elements to favor one of multiple possible representations, and language engineers can add white-spaces roles to the notation that allow editors to intelligently create breaks, spaces and indentations.

to be continued ...

Upcoming posts will discuss pretty-printing and textual modeling embedded in graphical editing in more detail. We also want to talk about identifiers and references, which are still causing pain in all frameworks. We will keep you posted about TEF marching towards its first release.

Textual Editing Framework - First Release and Tutorial

It took me quit longer than expected, but finally there is something that everyone of you can try. There is no an eclipse update-site to install a pretty early but functional version of TEF and a tutorial that helps you with the first steps. If you're interested, everything is layed out in great detail on our TEF web-site.

About the Who is Who in Domain Specific Languages

In this post we try to get a different perspective on what domain specific development/languages can be by looking at the roles involved.

Role and stakeholders in traditional software engineering are pretty simple. We create and use software. You have the software developer and you have the software user. One is the technical genius that creates the product, the other simply uses it.

In software development with domain specific languages, things become more complicated. Since we create languages, use languages to create software, and use software, we need more than two roles. Now we have the language developer, the language user/software developer, and the user. The language developer still needs to be technical genius; he creates the DSLs that make all the domain concepts usable for anybody. Then, we have the language user; he is either a technician or a domain expert. The user stays the user, simply using the end product.

Who is the language user/software developer/domain expert? First we should separate all the roles into two different sets: The competence perspective: computer scientist, domain expert, user. The computer scientist knows about platforms, programming, software. The domain expert knows his domain, he knows about concepts and applications. The user knows nothing, but that he knees this software. The other rule set comes from the language perspective: language engineer, language user, user.

Now we different scenarios with different individuals and distribute the roles from both sets to the involved people:

• Software development with specialised languages: DSLs are made for more efficient software development. The domain is software development. We have the traditional role allocation. The software developer is computer scientist and domain expert at the same time. Software developer play both roles language engineer and language user. The software user is the user. Example DSLs are Makefiles, JET, JSP, etc.
  
• Domain specific development: DSLs are made to integrate the user into the software engineering process. The computer scientist constrains himself to his core expertise. He simply takes the domain concepts from that he has no idea how to use them, and "computerizes them", binds them to a specific system platform, builds some GUI around it, etc. The computer scientist is not a software developer anymore. The user is the one who knows the domain, who knows how to use the concepts. Software user and domain expert are the same stakeholder. The user is also the language user and software user. Example DSLs are made for simulations in sciences like Physics, Biology, Chemistry, etc. or DSLs to create specific forms of data like in geo-information systems, or gene-databases.
  
• DSL based software engineering: Here we have three stakeholders. The computer scientist is language engineer. The domain expert is software developer and language user. The user is the software user. An example is the famous traffic light control language example.
  

From What We Code Complete

Code completion is an important part of modern development environments for textual languages. Over the past decades the proposals offered to the user during code completion have evolved from simple hippo completion (each word in the opened document is used as a proposal) to sophisticated proposals rooted in the used language semantics. But when we say code completion is based on language semantics, what semantics is suitable to provide code completion. For what language can we or can we not offer code completion?

The "Normal" Case, e.g. A Single Java File

In any case, and therefore in the normal case, we need more sophisticated model of the written text than the text itself. The edited text has to be parsed and transformed into a model that allows semantic analysis of the text. One possibility is to use a parse-tree and a library that allows to resolve variables, types, basically everything that can be referenced and therefore is possibly subject for code completion. Based on that a single edited file can be parsed and the information gathered can be used for code-completion proposals with in that file.

Using a Model That Spans Multiple Sources, e.g. A Java Project

The same technique as in the normal case, but we don't use just the model of one file. All the models of all the files organized in a project are combined. This does not only mean all the source files, but also names and types from library files or compiled object files, etc.

Using Context Information from External Models, e.g. OCL

Some languages, like OCL, do not only use the names and types that are defined using the language itselves. OCL for example is used to define expressions over models. It therefore references into these models using names from these models. Code completion in OCL often means to propose the names of properties and operations from external models.

Using Context Information from a Runtime System, e.g. Python

Some languages have only weak or no static types. This means that when you edit a program in such a language before the program runs, you don't exactly know what the types of your variables, parameters, etc. are. And with no information about the types, you don't know the properties, operations, or whatever features the values in your variables, etc. might provide. In such cases the development environment has to allow to edit the program at runtime. So you run your program and stop the execution at some point, then you start to edit your program. Now you have a completely different situation. Since you are at runtime, the environment can read the types from current variable, etc. values. From this runtime context an editor can provide code completion using runtime types.

Conclusion

Depending on the language semantics the sources for code completion proposals varies. This of course can make developing code completion less or more challenging. But you probably have to search really hard in order to find a language that would not allow any intelligent code-completion at all.

Different Ways to Define the Operational Semantics of a Language Based on its Meta-Model

Since meta-modelling became a successful method to define abstract language syntax, many research groups started to define the operational semantics of language also based on a meta-model. A variety of methods have been developed. This article briefly explains three different categories of methods and asks the question of which of the three approaches is the best one.

1. Structural Operational Semantics and Meta-Modelling

What is the abstract structure of operational semantics definitions: Plotkin's [1] classical approach to operational semantics is based on state transition systems. All the possible configurations of a runnable system are defined through states. There are transitions between states; they define which configuration may be followed by which other configuration. A system behaviour is one path leading from a starting configuration, following transitions. A language semantics can then be defined with (1) a set of configurations/states (this includes all possible programs + runtime information like variable assignments, memory, etc.); (2) possible transitions between configurations; and (3) something that selects one (or more [non-determinism]) behaviours, where the initial configuration/state is given by a program or model written in the language.

How can operational semantics be defined based on a meta-model? Meta-modelling allows to define configurations/states. A meta-model is an object-oriented data model that describes a set of models consisting of a finite number of objects, links between object, and attributes of objects. Meta-models can be used to define the abstract syntax of a language (remember that the model or program is one part of a configuration/state) and it can also be used to define data-structures that hold runtime information (like variable assignments, memory, etc.).

2. Three Ways of Defining Transitions and Behaviours Based on a Meta-Model

Even though we know that configurations can be described by meta-models, there are still several ways to define possible transitions and system behaviours. We want to briefly introduce three different approaches.

2.1 Code-Generation

Based on the language concepts given in a meta-model, a code generation can be used to generate executable code from a model. This code can use a mixture of model and programming language variables/states to define a system configuration. The executed code describes state changes by changing the model and/or changing variables within the generated program.

2.2 Action Languages

Meta-modelling defines a set of predefined actions. These actions are things like: create a object, set an attribute, create a link, delete an object, etc. These actions describe very small, atomic changes in a model. Actions can be scheduled from various forms of action languages. Examples are UML activities or most imperative programming languages. Such languages use expressions over models to create decisions and parameters for the actions. Blocks written in those action languages can be linked to the meta-model on two modularisation levels. One possibility is that operations are implemented in an action languages. In this case one operation implementation can call other operations. The whole semantics descriptions feels and behaves like a normal object-oriented program. The other possibility is to provide a behaviour implementation for classes, where each object (class-instance) runs its behaviour once it got created/instantiated.

2.3 Model Transformations

Another approach is model transformation. Using a transformation language, one can define more complicated model transitions. We are here focusing on rule-based transformations, where each rule describes a transition between two models. Such a rule usually selects a part in model that shall be replaced (lhs) and a sub-model (rhs) that is used to replace the lhs. Model transformation allow more complex, user defined transitions between configurations/states.

For rule-based transformations also several ways of scheduling exists. For example, transformations can also be choreographed using action languages, where the execution of a transformation rule becomes an action. Transformation rules can also be grouped with logical operations: one rule can only be applied when another rule could already be applied, or several rules that can be fired are alternatives to each other, where one of the rules is either selected non-deterministically or via rule prioritisation.

3. What is the Best Way of Describing Operational Semantics?

Maybe we should first ask: is there a best way of describing operational semantics? All the methods that we just described, with all their variations that exist out there, have their own advocates, convinced of the advantages of their method. Also do all research groups have their own examples that seem to proof how efficient and elegant their methods are. But how can we really determine what the characteristics of a method really are and for what kind of languages each method is the most suitable?

We plan to take a genuine DSL, that was developed at our institute, and we want to create operational semantics for that languages with the three different approaches. The researched DSL describes stream based data processing. It already has an operational semantics based on scheme-code generation. During our studies on an agile language engineering process we will create an action language-based operational semantics with the method presented here. Furthermore, we will create a transformation-based operational semantics, using a QVT implementation.

We expect to see that different parts of the language will cause troubles when implemented with the three different methods. We hope that we can identify certain language concept characteristics that may favor the one or other method. Furthermore we expect the three solutions to have different qualities when it comes to size of the semantics description, execution performance, scalability, reusability, easyness of combining the language with other or with a concrete system platfrom, and so on and so on.

Problems for Textual Model Notations

Several frameworks and meta-tools to combine context-free text notations with meta-models exist. But the current research seems to be focused mainly on those syntactical structures that can be defined by context-free grammars solely. It is ignored that most languages, even though defined with context-free grammars, contain non context-free features. This is especially troublesome when you accept that meta-models describe certain non context-free features and therefore provide a different expressive power than grammars.

1. Textual notations are more than context free syntax

One could say that meta-models, in the sense of object-oriented data-models, e.g. class diagrams, were introduced to get a hold of the definition of graphical modelling languages. No matter if this reflects the "historical"-facts or not, meta-modelling allows abstract syntax definitions that are fundamentally different from definitions based on context-free grammars. Where such grammars basically define ordered-tree structures (better classified as term-like structures), meta-models describe graph-like structures.

Nowadays, with all the fancy meta-model based transformations, code-generation, model analysis, testing, integration, ..., and MDA tools available, we like to use meta-modelling for the definition for all kind of languages. This also includes traditional text-based languages. Therefore, meta-modelling has eventually entered the technological space of textual syntax, which makes dealing with the differences between grammars and meta-models an important research subject.

There two different approaches to meta-model based text languages. First, we still think of the language in terms of grammars and create a meta-model from a grammar. This way, we subsequently attach all meta-model benefits to a regular context-free grammar based language [xText, grammarware]. The second approach starts with the understanding that a language is best designed by concept, in a meta-modelling fashion. Here we create a textual notation for a formerly developed meta-model [TCS, TEF].

In both approaches promising results were achieved when it comes to reflect the expressive power of grammars. In other words, as long as we are concentrating on terms, creating models from text and text from models is implementable. This is usually based on some kind of mapping between grammars and meta-models.

As in traditional compiler design, syntax analysis (dealing with text based on a grammar) is followed by static semantic analysis (dealing with language features that exceed the power of context-free grammars). From the meta-modelling perspective this means two things. First, meta-models define references that allow them to describe graphs instead of trees. Second, model conditions, for example OCL constraint, that further narrow what valid meta-model instances are. Both aspects have corresponding concept s in the grammar world. The first one can be called name resolution. A resulting parse tree is augmented with attributes which connect nodes in a parse tree and basically turn this tree into a graph. The second are well-formedness rules that are based on the same principles than constraints in meta-modelling.

Consequently the next research question for both approaches (meta-models from grammars as well as textual notations for a meta-model) is how to integrate name-resolution and other static semantic checks.

2. Going beyond context free syntax

Our framework [TEF] allows to create eclipse-based text editors from a meta-model. Each of these editors continuesly parses the user input and creates a meta-model conform model from it. This part of TEF is based on work in [TCS, grammarware] and basically covers everything that is context-free. And now is the question how we incorporate the non context-free parts.

We divided the text reconciliation process into three phases. The first one is parsing, creating a model that reflects the tree structures of the text. The second phase is name-resolution. It transforms the model into a graph structure. In the third phase we check all constraints on the model. In all phases we report errors in the model back to the user: eclipse-like as a red underline with hover-message and ruler marking. Interesting for us are now the name-resolution and constraint checking phases.

2.1 Name resolution

At the moment TEF allows to provide the Java implementation of a name resolution algorithm. This implementation has to work on the following parameters : a model that does not yet contain references; a model element that describes the name that is to be resolved (a single name or a more complex identifier), and the surrounding context element. Name resolution has to return the element that is referenced by the name. For the future we try to replace this Java implementations by OCL expressions. This allows to describe name resolution on a higher level of abstraction. The challenge is to provide a technique thats is hopefully independent from the actual method of name resolution. Such methods could be symbol tables, local search, inside-out, recursive decent, etc.

2.2 Code-Completion

Closely related to name resolution is code-completion. Each name (reference, identifier, etc.) that the user may write in an editor is potentially subject to code-completion. Thus, code-completion refers to completing a name. Code-completion therefore means to provide a set of valid names/references in a given context. There are two problems to be solved.

First, from the context it is not clear of what kind the reference is to be completed. For example, think of Java: when you start to type an identifier in an expression, it is not clear if it becomes a field name or an operation name. This can be solved by parsing to the point of code-completion and then analyse the current parse stack to retrieve the possible reductions. These reduction possibilities reflect the possible kinds of elements that are requested.

The second problem is that you usually cannot successfully parse the document when the user requests code-assist, because the user is just in the middle of typing the document. Since you cannot parse the document, you cannot provide the necessary context information. You have to implement some sort of error recovery to at least generate a partial model from the text. This partial model has to serve as the source for possible name declarations. In other words, error recovery becomes an important requirement.

2.4 Syntactic sugar in the context of name resolution

Very often a language syntax provides different notations for the same model elements. Take Java again: a member variable "foo" can be referenced by "foo" from within the body of a member method, or it can be referenced as a field of the "this" variable using "this.foo". Where the more implicit notation "foo" has a concrete definition in the context-free grammar, no such thing exists in the meta-model. Therefore at some point, the implicit notation "foo" has to be resolved or replaced by its actual meaning "this.foo". This is especially troublesome because the string "foo" could also refer to a local variable. Whether "foo" means "this.foo" or just "foo" is a matter of static semantics. Currently TEF allows to define several meta-model bindings for the same syntactical constructs. Which binding is finally chosen depends on name resolution. If "foo" can be successfully resolved to a local variable name it becomes a reference to this local variable. If not, it is assumed that "foo" actually means "this.foo" and it is tried to find the name "foo" among the members of "this".

2.3 Constraint checking

This is rather straight forward. The model resulting from parsing and name resolution is checked based on all meta-model invariants and report an error when an invariant is violated.

3. Conclusion

Context-free grammars describe trees, meta-model graphs. Therefore, name-resolution is a trouble-some but very important part of creating a model from text. It is a necessity for both context-free syntax to meta-model approaches. In combination with semantic text editors it requires error recovery to provide reasonable code-completion.