1 Overview

1.1 Goal

The com.mbeddr.mpsutil.interpreter language allows to create an interpreter for any language implemented in MPS. Creating the interpreter should be as simple as possible, avoiding the boilerplate code required for any interpreter.

1.2 Interpreted Language

We describe the set of MPS Language(s) defining the concepts of the evaluated nodes in one Interpreter as "Interpreted Language". For example, the Interpreted Language of CExpressionsInterpreter, CFunctionInterpreter and CMathInterpreter is mbeddr C.

1.3 Parts

The Interpreter language consists of these main building blocks:

2 Examples

Complete examples are available for CExpressionsInterpreter, CExtInterpreter, CPointerInterpreter, CFunctionInterpreter, CModulesInterpreter, CStatementInterpreter, CMathInterpreter and ReqirementsInterpreter.

Figure 2-A

Figure 2-B

Figure 2-C

Figure 2-D

Figure 2-E

3 Interpreter Lifecycle

Interpreters exist in different steps within a lifecycle. At definition time, the instance of the Interpreter exists with a name, e. g. "SampleInterpreter". When the concept instance is being build at compile time, a Java class based on the com.mbeddr.mpsutil.interpreter.rt is created; following our example it would be named "Interpreter_SampleInterpreter". An interpreter is used by querying InterpreterRegistry for an instance of the generated Java class; we call this instantiation time. We feed a node to this interpreter to start actual evaluation. The evaluators of the interpreter are executed now at evaluation time.

4 Interpreter Definition

An Interpreter Definition describes the interpreter. The name of the Interpreter should comply to Java Class Name standards. The category is a way of grouping associated interpreters. Categories don't affect the interpreters except a warning if we mix interpreters of different categories.

Interpreter Definitions need to be contained in a plugin model, as we generate an ExtensionDeclaration for Extension Point InterpreterExtensionPoint for each interpreter.

4.1 Related Interpreters

relatedInterpreters describe other interpreters somehow related to this interpreter. At definition time, Applicable Languages and Type Mappings of all related interpreters are considered additionally to the the ones defined locally. At instantiation time, if we combine several related interpreters, the execution engine ensures the evaluation order defined by related interpreters (before or after relations). This order is similar to MPS Generators priorities.

An error is flagged if we define unsolvable dependency cycles between interpreters.

4.2 Applicable Languages

applicableLanguages limit the types and concepts available in the Type Mappings and Evaluators to the languages defined here. This reduces possibility to mix concepts of different languages (e. g. BaseLanguage Statement and C Statement). Please note that we still need to add the languages to the dependencies of this model in order to use concepts contained within them.

4.3 Type Mappings

typeMappings map types of the interpreted language to Java types. The most common mapping is the BaseLanguageTypeMapping.

The left-hand side of the mapping accepts BaseLanguage expressions to provide maximum flexibility. However, in most cases we just want to specify a type in the interpreted language. To do this we introduced the ConceptTypeExpression $ (dollar) expression.

The right-hand side accepts any Java type, both primitives and classes.

Another mapping is the TypeMapping. The left-hand side mirrors the BaseLanguageTypeMapping described above. The right-hand side is a BaseLanguage method body, expecting a compatible type of the left-hand side as result. We may use this to substitute types of the interpreted language if they don't change the interpreted result; otherwise, we would need to implement every evaluator twice.

4.4 Evaluators

The evaluators are the core of the interpreter. They describe the concepts to be interpreted and how to evaluate the result of these concepts.

Besides the concept the evaluator applies for, we may specify type constraints on the evaluated concept's child concepts, i. e. the AST sub-nodes below the evaluated node. For each child concept, we specify the role and the expected type. The $ (dollar) expression can be used here as well.

The actual evaluation can be implemented in BaseLanguage. For simpleEvaluator (starting with an equals sign), we may enter a simple BaseLanguage expression. More complexEvaluator may be entered in a method body (denoted with a pair of braces).

4.4.1 Evaluator Selection

Evaluators are selected at evaluation time based on the order described in Section Related Interpreters and the order of evaluators within the interpreter. However, most times the sensible order of evaluators can be deducted from the matching concepts and constraints. A warning was displayed If this sensible order is violated. The following rules define the sensible order:

  • Evaluators for more specific concepts are selected before more generic concepts. For example, we have a concept MySuperConcept and sub-concepts MySubConceptA and MySubConceptB. Evaluators exist for MySuperConcept and MySubConceptA. When the interpretation encounters an instance of MySubConceptA, the evaluator for MySubConceptA is triggered. When the interpretation encounters an instance of MySubConceptB, the evaluator for MySuperConcept is used.
  • If two evaluators are defined for the same concept, the one with more specific matching type constraints will be used. The example at evaluators shows this: As int16 is more specific than int32, the evaluator for int16 will be chosen for int16 and int8 additions (as int8 is a subtype of int16).
  • If we need to execute some evaluators before other evaluators after another interpreter, we need to split up our interpreter and define the appropriate related interpreters.

4.4.2 Evaluator Implementation

We may use any appropriate BaseLanguage constructs in the evaluator implementation. "Appropriate" meaning any BaseLanguage expression in simpleEvaluator and any BaseLanguage statement in a complexEvaluator. Additionally, we provide some new expressions specific for interpreters:

  • InterpretConstraintExpression (displayed as interpretConstraintExpression #(«childReference»)) invokes the interpreter on the selected child and returns the evaluation result. If the selected child was constrained to a type by the containing evaluator, the evaluation result is of BaseLanguage type mapped to this constrained type in Section Type Mappings section. As an example, the type of right is constrained to int16, and int16 is mapped to int. Thus, the result type of #right is int.
  • InterpretExpression (displayed as interpretExpression #(«expression»)) invokes the interpreter on the result of the contained expression. The contained expression must evaluate to node<>. The result type of this expression is always Object, as we cannot determine a more specific type.
  • OperationCallExpression (displayed as operationCallExpression #->«functionRoleName»(«actualParametersRoleName» => «formalParametersRoleName»)) invokes a function call semantic with positional arguments on the node contained in functionRoleName. This semantic includes push/pop of a new environment before/after the evaluation of the function; evaluation of each actual parameter node; positional assignment of the results of these evaluations to the formal parameter nodes; and creating environment entries for all formal->actual parameter mappings so they can be used as variables.
  • NodeExpression (displayed as nodeExpression node) represents the currently interpreted node. Its type is defined by the concept of the evaluator.
  • ContextExpression (displayed as context) provides access to the current interpreter context. Its type is IContext.
  • EnvExpression (displayed as envExpression env) provides access to the current environment. Its type is IEnvironment, a subtype of Map.
  • CastUpExpression (displayed as castUpExpression castUp(«value», «TargetType»)) cares for boxing/unboxing primitive types and automatic compatible conversion, e. g. int --> long.

5 Interpreter Runtime

5.1 Interpreter Java Classes

For each Interpreter Definition, one subclass of InterpreterBase implementing IInterpreter is generated. An instance of this is returned by the generated ExtensionDeclaration for Extension Point InterpreterExtensionPoint. The InterpreterRegistry provides access to this instance.

We use CombinedInterpreter to leverage more than one interpreter for the evaluation of our model. This container class takes care of ordering all related interpreters within the constructor argument list of interpreters, i. e. no other interpreters are taken into account, even if they appear in the Related Interpreters section of some of the listed interpreters.

The subclass finds all interpreters available in the context of the passed node and adds them to the list of combined interpreters.

5.2 Interpreter Context

Within all evaluators, an IContext is available through the context expression. It allows access to the Environment and other information about the running interpreter. We may extend the context for our own purposes. However, the context also holds the internal state of an interpreter (which itself is stateless), so we need to pay attention if we alter existing functionality.

5.3 Interpreter Environment

The interpreter runtime maintains a hierarchical environment of type IEnvironment available through the env expression. The environment can be used to implement scopes and stack frames:

The specialized IPersistentEnvironment interface follows the same semantics, but keeps all environments even after they have been popped. This allows to access all intermediate states encountered during evaluation time.

5.4 Node Value Cache

The IContext may contain a INodeValueCache of evaluated result per node. If we request the evaluation of a node that's contained in the cache, the cached result is returned and no evaluation occurs.

The interpreter runtime tries to invalidate the cache on useful occations, like OperationCallExpression and Environment changes.

The cache can be disabled for single evaluators via the ToggleCaching intention or the inspector.

6 Interpreter Usage

If we just want to evaluate a node based on a category with reasonable defaults, we'd choose Section Leveraging reasonable defaults with InterpreterEvaluationHelper.

In order to execute an interpreter, we need to follow these basic steps:

  1. Aquire an IInterpreter
  2. Create an IContext
  3. Set the root interpreter
  4. Evaluate a node

Each step is described in more detail below.

6.1 Leveraging reasonable defaults with InterpreterEvaluationHelper

The first three readers of this section will get three free beers, each.

For no-thrills evaluation of a node based on an Interpreter Category, use InterpreterEvaluationHelper.

We call the constructor with the name of the requested Interpreter Category.

6.2 Aquire an IInterpreter

Fundamentally, we aquire an IInterpreter from the InterpreterRegistry singleton. the getInterpreterExecutable method returns the IInterpreter.

We provide several convenience classes supplementing the interpreter aquisition.

6.2.1 Interpreter Finder

The InterpreterFinder finds Interpreter nodes (to be fed to the InterpreterRegistry) matching certain criteria.

The method findAllVisibleInterpreters looks up all Interpreter nodes visible from the context of the argument node.

The method findVisibleInterpretersForCategory acts similar, but filters the result by Interpreter Category.

6.2.2 Cached Interpreter Finder

The CachedInterpreterFinder singleton builds a cache of all globally available Interpreter nodes. The cache is flushed only on request, or if an InterpreterExtensionPoint is loaded or unloaded. The CachedInterpreterFinder provides methods similar to the InterpreterFinder (findAllInterpreters and findInterpretersForCategory, respectively).

6.2.3 Combined Interpreter

The CombinedInterpreter takes care of combining several Interpreters, possibly related (see Section Related Interpreters, to one single IInterpreter containing the union of all Evaluators. This allows us to distribute Interpreter definitions over several languages, possibly close to the definition of the interpreted concept itself.

The constructor CombinedInterpreter takes an arbitary number of IInterpreters to combine.

The takes one node as constructor parameter, feeds this node to findAllVisibleInterpreters, and initializes the CombinedInterpreter with the resulting IInterpreters.

6.3 Create an IContext

Interpreters themselves are stateless. An instance of IContext holds the complete state, both internal to the interpreter framework and our own additions.

The default implementation ContextImpl is suitable for most purposes. We may pass an IInterpreter as constructor parameter, which will be set as root interpreter (see Section Set the root interpreter).

6.4 Set the root interpreter

We need to set the root interpreter for a context, because we can combine interpreters arbitrarily. We use the method setRootInterpreter to do this.

6.5 Evaluate a node

As we have an IInterpreter, an IContext, and a root interpreter set, we can finally start the interpreter. We use the method evaluate for this. The result of the method call will be the evaluated result.

6.5.1 Exceptions during Evaluation

The following exceptions might occur during evaluation. The exception messages contains a trace of the evaluated nodes.

  • EvaluatorMissingException: If evaluation is (directly or indirectly) requested for a node we don't have an evaluator for in the current interpreter.
  • InvalidUpCastException: The interpreter runtime tries to automatically handle primitive type boxing / unboxing issues. Ths exception occurs if we expect a subtype of Number (essentially a class equivalent of a primitive type), but get something else.
  • InterpreterRuntimeException: All RuntimeExceptions inside an evaluator are wrapped in this exception. This way, we can add the evaluated node trace to the message.

7 Interpreter Test

The com.mbeddr.mpsutil.interpreter.test language provides the basis for custom test languages for the Interpreted Language. An example for a custom test language would be com.mbeddr.core.cinterpreter, examples for tests can be found at ExampleTest.

The AbstractInterpreterEvaluation concept provides a NodeAnnotation that checks if the evaluation result of the node conforms to an expected value. Similarly, the AbstractInterpreterCondition concept provides a NodeAnnotation that checks for the expected result of isEvaluable. If the expected result is not met, a typesystem error is flagged, which can be checked in a NodesTestCase.

In order to use these concepts, we need to create a sub-concept and implement the following behaviors:

8 Conditional Interpreters

An extended version of an Interpreter is a ConditionalInterpreter. It allows to define a isEvaluable method that decides if a node can be evaluated.

8.1 Definition Time Additions

The isEvaluable() operation can be added to any Evaluator inside a ConditionalInterpreter by using the addCondition intention. If no isEvaluable() operation is present, it's assumed to return true if and only if all its children are evaluable.

The isEvaluable() operation can be implemented as single-line BaseLanguage expression or multi-line BaseLanguage statements. In addition to the expressions described in Section Evaluator Implementation, we can use the following expressions:

8.2 Compile Time Additions

An ConditionalInterpreter implements IConditionalInterpreter, containing one additional method isEvaluable. It takes the same arguments as evaluate and returns whether this interpreter can evaluate the given node.

8.3 Instantiation Time Additions

We provide conditional variants of CombinedInterpreter and , named CombinedConditionalInterpreter and , respectively. They provide the same semantics, limited to Conditional Interpreters.

8.4 Evaluation Time Additions

We aquire our Conditional Interpreter as described in Section Aquire an IInterpreter and need to cast it to the IConditionalInterpreter interface. We might check the isEvaluable method result before calling evaluate, as it will not be called automatically.

9 Persistent Interpreters

An PersistentInterpreter is a wrapper around an arbitrary IInterpreter that keeps all intermediate results for evaluated nodes.

In order to leverage this feature, we need to wrap our original IInterpreter as a constructor parameter into a PersistentInterpreter. Some of the exposed interfaces are also subclassed:

After a call to evaluate, we may retrieve the intermediate results from the passed IPersistentContext. They are stored per IPersistentEnvironment in the associated IPersistentNodeValueCache.