TECHNICAL FIELD

The present disclosure relates to a method for compiling a source code in a first programming language, in particular a domain specific language (DSL) to a program code in a second programming language, in particular a model specific language (MSL) and to a first programming language specific specializer, in particular a domain specific specializer (DSS). The disclosure further relates to implementation methods for domain specific languages. The method can be used for providing an executable program running on a processor.

BACKGROUND

Many applications require high performance computations. Programmers, to satisfy this need, rely on low-level and usually architecture-specific programming models (e.g.

OpenMP for symmetrical multiprocessor systems (SMPs), CUDA for graphics processing units (GPUs), MPI for clusters). Programming with these frameworks usually requires deep understanding of both the specific programming model and the target architecture. A promising alternative is a development of compiled Domain-Specific Languages (DSLs) as described by "Kevin J. Brown, Arvind K. Sujeeth, Hyouk Joong Lee, Tiark Rompf, Hassan Chafi, Martin Odersky, and Kunle Olukotun; A Heterogeneous Parallel Framework for Domain-Specific Languages; In PACT, pages 89-100, 201 1 ". Compilers allow mapping of problem-specific abstractions directly to low-level architecture-specific programming models. However, developing DSLs is difficult by itself, and compiled DSLs are even more difficult because they require development of a compiler as a key component. Using multiple DSLs together in a single application is also hard because existing compiled solutions do not compose together. This problem is also recognized by "Arvind K. Sujeeth, Tiark Rompf, Kevin J. Brown, HyoukJoong Lee, Hassan Chafi, Victoria Popic, Michael Wu, Aleksandar Prokopec, Vojin Jovanovic, Martin Odersky, Kunle Olukotun; Composition and Reuse with Compiled Domain-Specific Languages, ECOOP Ί 3". The task of developing specialized languages for particular domains has a long story and goes back at least to "P. J. Landin. 1966, The next 700 programming languages,

Commun. ACM 9, 3 (March 1966)" and "Paul Hudak. Building Domain-Specific Embedded Languages, ACM Comput. Surv., 28(4es): 196, 1996". State of the art architecture of DSL development system 100 is shown in Figure 1. The DSL development system 100 includes applications 101 using a DSL development framework 103 including multiple DSLs 105, 107, 109 that use a Common Compiler Infrastructure 1 1 1 for generating an executable file. The executable file runs on a multiprocessor computer 1 13 using SMP execution environment 1 15 or on a cluster 1 17 using cluster execution environment 1 19. The execution flow 130 is depicted on the right side of Fig. 1. A Domain Specific source code 131 is provided to the compiler 133 that transforms the Domain Specific source code 131 to a Domain Specific intermediate representation 135, generates an executable file 137 and provides a program.exe 139.

At the same time, as mentioned above, the methods used for DSL construction are far from being mature. The following main problems of prior art can be identified. Only one of the following two options can be achieved but not both of them. Good performance can be achieved at the cost of manually writing many code for different data representations and generic code can be written only once and for all representations but at the cost of losing performance. Common Compiler backend has to be used to develop new DSLs. While it is a lot easier than to implement a compiler it is still a complex task. SUMMARY

It is the object of the invention to provide an improved technique for compiling a high-level programming language to a low-level programming language. This object is achieved by the features of the independent claims. Further implementation forms are apparent from the dependent claims, the description and the figures.

In this disclosure a new system architecture for a high-level abstract programming language development framework such as DSL and a new method of compilation for high- level abstract programming languages such as DSL is presented. Key components of the system and steps necessary to implement the method are described hereinafter. The new system architecture and the new method are demonstrated by using examples and giving formalized definition of essential parts of the system and the method. In this disclosure, the following terms are interchangeably used: graph-based intermediate representation (IR), program graph, or simply a graph. To implement the new techniques for domain specific specialization as described in the following, the method of staged evaluation as described below with respect to Figs. 16 a) to 16 j) may be used. Aspects of the invention provide good performance and generic code can be written only once for all representations without losing performance. It is thus possible to write each algorithm only once and automatically generate specialized versions for different representations. Good performance is achieved by automatically specializing generic algorithms for concrete data representations, by applying both domain-specific

optimizations and model-specific optimizations. It is no more necessary to use the Common Compiler backend to develop new DSLs. That facilitates development of new DSLs.

In this disclosure layered framework for DSL development is presented. This means that it is possible to use previously created DSLs to implement new DSLs. It is possible to use existing DSLs in any combination. In essence, this disclosure describes how to bring best practices of modular and component-based programming (which are the state of the art approaches in general purpose languages) to the world of DSLs.

In order to describe the invention in detail, the following terms, abbreviations and notations will be used:

DSL: Domain Specific (Programming) Language, also referred to in a more general meaning as first programming language or high programming language or abstract programming language.

MSL: Model Specific (Programming) Language, also referred to in a more general meaning as second programming language or low-level programming language.

CIC: Concrete Implementation Class.

DSS: Domain Specific Specializer.

SE: Staged Evaluator.

Gl: Graph Interpreter.

TF: Type Family. Abstract Syntax

Tree (AST): A tree data structure that is used to represent an abstract syntactic structure of source code. Each node of the tree may denote a construct occurring in the source code.

Compiler: A computer program that takes source code of a source program and produces an executable machine code.

Executable

machine code: A sequence of machine code instructions to be executed by a

processor to perform a given task.

Factory method

design pattern: A design pattern in object-oriented programming. This pattern may define an interface for creating an object (a so called factory method), but may let the classes that implement the interface decide which class to instantiate.

Generic program: A program written in terms of to-be-specified-later types that may be instantiated when needed for specific types provided as parameters. This approach may permit writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication.

Graph data

structure: A graph data structure may include a finite set of ordered pairs, the so called edges, of certain entities which are called nodes or vertices. An edge (x,y) points or goes from x to y. The nodes may be part of the graph structure or may be external entities

represented by integer indices or references.

Intermediate

Representation A data structure that may be used inside a compiler for representing the source program and allows analysis and transformation before outputting and executable machine code. Typically, this is a graph or a tree data structure with some specific information inside nodes. As the intermediate representation contains all the information needed to evaluate the program (if given the input data), we can say about the evaluation of the intermediate representation as an equivalent way to execute the program.

Class

(in object-oriented

programming: In object-oriented programming, a class is a construct that may be used to create instances of itself - referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable its instances to have state and behavior. Data field members (member variables or instance variables) enable a class instance to maintain state. Other kinds of members, especially methods, enable the behavior of class instances. Classes define the type of their instances.

Method

(in object-oriented

programming): In object-oriented programming, method may be a subroutine (or procedure) associated with a class. Methods may define the behavior to be exhibited by instances of the associated class at program run time. Methods may have the special property that at runtime, they have access to data stored in an instance of the class they are associated with and may thereby able to control the state of the instance.

Object-Oriented (00) language is a computer programming language that supports object-oriented programming (OOP). OOP i a programming paradigm using "objects" - usually instances of a class. Object may consist of data fields and/or methods together with their interactions - to design applications and computer programs. Programming techniques may include features such as data abstraction, encapsulation, messaging, modularity,

polymorphism, and inheritance. Operational

semantics: The operational semantics for a programming language describes how a valid program is interpreted as sequences of computational steps (typically using some hypothetical computer). These sequences then are the meaning of the program.

Proxy design

Pattern: A design pattern in object-oriented programming. A proxy, in its most general form, is a class functioning as an interface to something else (some subject). A client instead of directly accessing the subject calls methods of the proxy which delegates the calls to the subject.

Semantic

equivalence

of programs): Two programs Pi in language L ₁ and P ₂ in language L ₂ may be said to be semantically equivalent if for any input data their interpretation with respect to the operational semantics of languages and L ₂ correspondingly yields the same result.

Source code: A textual representation of a source program using some

programming language.

Source program: A computer program that is used as an input to the "compiler". It may be translated into "executable machine code".

Staged code: Staged code for a source program P is a program P' such that evaluation of P' may produce an intermediate representation, which ma be semantically equivalent to the program P.

Tree data

structure: A data structure that simulates a hierarchical tree structure with a set of linked nodes. Virtual methods: A virtual function or virtual method is a function or method whose behavior can be overridden within an inheriting class, in particular by a function with the same signature. Interfaces,

abstract methods: An abstract method is one with only a signature and no

implementation body. It is often used to specify that a subclass must provide an implementation of the method. Abstract methods may be used to specify interfaces in some computer languages.

Parameterized

types (generics): A parameterized type may define a family of related types. For example, the "Array" parameterized type may define the types "Array[lnt] ^M , "Array[Char]", "Array[Array[lnt]]", and so on.

Functor: A functor may define a type of mapping between categories, which is applied in category theory. Functors may describe

homomorphisms between categories or more generally morphisms.

Terminal expressions such as symbols or strings are literal expressions which may appear in the inputs to and/or outputs from the production rules of a formal grammar. They may not be changed using the rules of the grammar.

Nonterminal

Expression: Nonterminal expressions such as symbols or strings are those

expressions that can be replaced. A formal grammar may include a start symbol, a designated member of the set of nonterminals from which all the strings in the language may be derived by successive applications of the production rules. The language defined by a grammar is hence the set of terminal strings that can be so derived.

According to a first aspect, the invention relates to a method for compiling a source code in a first programming language to a program code in a second programming language, the method comprising: generating a graph based on the source code, the graph corresponding to a first programming language specific intermediate representation of the source code; transforming the graph from the first programming language specific intermediate representation to a second programming language specific intermediate representation; and generating the program code based on the second programming language specific intermediate representation of the graph.

By transforming the graph from the first programming language specific intermediate representation (IR) to a second programming language specific IR the framework of the first programming language including objects on a high abstraction level can be further used. The method provides the translation to a lower level, e.g. processor specific second processing language. Thus generic code, e.g. high abstraction level algorithms can be written only once for each application. The transforming then provides the translation of the high level code to a specific representation fulfilling the requirements of the specific processor platform or processor architecture where the code is to be executed.

Development of code is facilitated with improved performance.

In a first possible implementation form of the method according to the first aspect, the first programming language comprises a domain specific language and the second

programming language comprises a model specific language.

A domain specific language is a high abstraction level programming language that uses many generic programming constructs. Development is efficient when using DSL. A model specific language may be a low abstraction level programming language that may be adapted to a specific processor platform, i.e. the specific (processor) model. When combining the DSL with MSL by the transforming, code development can be quite efficient as generic DSL constructs provide easy development of code, e.g. algorithms and MSL constructs provide for an efficient execution of the code on a specific processor platform.

In a second possible implementation form of the method according to the first aspect as such or according to the first implementation form of the first aspect, transforming the graph is based on a first programming language specific specialization. By using a first programming language specific specialization programming constructs of the first programming language can be analyzed and transformed in programming constructs that can be used in the second programming language. First programming language specific specialization can provide a framework for efficiently transforming a first programming language IR to a second programming language IR.

In a third possible implementation form of the method according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, transforming the graph comprises: transforming objects of the graph to concrete implementations of the objects which concrete implementations are based on data structures supported by the second programming language specific intermediate representation. By transforming objects of the graph to concrete implementations of the objects which concrete implementations are based on data structures supported by the second programming language specific IR, the program code can be easily generated based on the supported data structures of the second programming language specific IR. In a fourth possible implementation form of the method according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, the graph comprises nodes corresponding to operations of the source code and edges corresponding to data flow between the operations, wherein the edges comprise symbols stored in the nodes of the graph.

When the graph is represented by nodes, edges and/or symbols, the transforming the graph can be easily performed by traveling through the nodes and/or transforming each node separately to objects of the second programming language. In a fifth possible implementation form of the method according to the fourth

implementation form of the first aspect, the graph comprises a lookup table for looking up from the symbols to the nodes.

By a lookup table, looking up from the symbols to the nodes is easy and efficient to perform.

In a sixth possible implementation form of the method according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, the method comprises: using a graph interpreter adapted to deal with program graphs for transforming the graph from the first programming language specific intermediate representation to the second programming language specific intermediate representation.

When using a graph interpreter adapted to deal with program graphs instructions in the first programming language can be directly executed without previously batch-compiling them into machine language. Thus, using an interpreter improves efficiency. In a seventh possible implementation form of the method according to the sixth implementation form of the first aspect, the graph interpreter comprises: an abstract expression for an abstract node class of the graph, a terminal expression for treating instances of classes derived from the node class of the graph that represent primitive operations of the first programming language, a non-terminal expression for treating instances of classes derived from the node class of the graph that represent user-defined functions of the first programming language, a first interpret method for interpreting the terminal expression, and a second interpret method for interpreting the non-terminal expression.

By using an abstract expression, terminal and nonterminal expressions and respective interpret methods, production rules of an abstract programming language can be constituted. The graph interpreter thus allows to transform such abstract programming language constructs to concrete representations that are supported by the second programming language.

According to a second aspect, the invention relates to a first programming language specific specializer operable on a processor configured to compile a source code in a first programming language to a program code in a second programming language, the first programming language specific specializer being configured to transform a graph corresponding to a first programming language specific intermediate representation of the source code from the first programming language specific intermediate representation to a second programming language specific intermediate representation such that the program code can be generated by the processor based on the second programming language specific intermediate representation of the graph.

By using a first programming language specific specializer programming constructs of the first programming language can be analyzed and transformed in programming constructs that can be used in the second programming language. The first programming language specific specializer provides a framework for efficiently transforming a first programming language IR to a second programming language IR. The first programming language specific specializer may be a specific part of software running on a processor or a specific hardware circuit of a processor. The first programming language specific specializer allows to write generic code, e.g. high abstraction level algorithms, only once for each application. The first programming language specific specializer then provides for the translation of the high level code to a specific representation fulfilling the requirements of the specific processor platform or processor architecture where the code is to be executed. Development of code is facilitated without losing performance.

In a first possible implementation form of the first programming language specific specializer according to the second aspect, the first programming language comprises a domain specific language; and the second programming language comprises a model specific language.

A domain specific language is a high abstraction level programming language that uses many generic programming constructs. Development is efficient when using DSL. A model specific language is a low abstraction level programming language that is adapted to a specific processor platform, i.e. the specific (processor) model. When combining the DSL with MSL by the transforming, code development is quite efficient as generic DSL constructs provide easy development of code, e.g. algorithms and MSL constructs provide for an efficient execution of the code on a specific processor platform.

In a second possible implementation form of the first programming language specific specializer according to the second aspect as such or according to the first

implementation form of the second aspect, the first programming language specific specializer comprises: a program graph interpreter configured to traverse through nodes of the graph and supply for each node a symbol corresponding to a current operation and a current context.

The program graph interpreter allows directly executing instructions in the first programming language without previously batch-compiling them into machine language. Thus, the program graph interpreter is highly efficient.

In a third possible implementation form of the first programming language specific specializer according to the second implementation form of the second aspect, the first programming language specific specializer comprises: a staged evaluator callable by the program graph interpreter, the staged evaluator being configured to produce a

specialization of the symbol in the current context.

The staged evaluator allows providing specialization of operations in their given contexts. Calling the staged evaluator by the program graph interpreter allows specializing symbols of the graph in a context-aware manner. In a fourth possible implementation form of the first programming language specific specializer according to the third implementation form of the second aspect, the program graph interpreter is configured to update the symbol with the specialization of the symbol provided by the staged evaluator.

By updating the symbols of the graph with their specialization, the process of transforming can be efficiently implemented. The program graph interpreter can directly execute instructions in the first programming language by making use of the updated symbols provided by the staged evaluator.

In a fifth possible implementation form of the first programming language specific specializer according to the third or according to the fourth implementation form of the second aspect, the specialization is based on at least one of the following specialization rules: Invocation, Map processing, Filter processing.

These specialization rules allow inline substitution of the symbols of the graph by their specialized versions. Redundant construction of domain objects can be successfully eliminated. In a sixth possible implementation form of the first programming language specific specializer according to the second aspect as such or according to any of the preceding implementation forms of the second aspect, the first programming language specific specializer is configured to transform the graph based on at least one of the following programming constructs: Concrete Implementation Classes, Isomorphisms, Views.

The Concrete Implementation Class provides a final low-level representation of initial objects in the first programming language and their methods. Isomorphisms allow representing a graph in two different ways, e.g. as adjacency matrix or as adjacency list. Views allow using transformation between these two different representations of the graph. Hence these three programming constructs provide highly efficient tools for transforming the graph from the first programming language IR to the second

programming language IR.

According to a third aspect, the invention relates to a processor configured to compile a source code in a first programming language to a program code in a second programming language, the processor comprising: a graph generator configured to generate a graph based on the source code, the graph corresponding to a first programming language specific intermediate representation of the source code; a first programming language specific specializer configured to transform the graph from the first programming language specific intermediate representation to a second programming language specific intermediate representation; and a code generator configured to generate the program code based on the second programming language specific intermediate representation of the graph.

By using the first programming language specific specializer the processor is able to analyze programming constructs of the first programming language and to transform them in programming constructs that can be used in the second programming language. The processor thus may execute generic code, e.g. high abstraction level algorithms, that is written only once for each application. The processor provides for the translation of the high level code to a specific representation fulfilling the requirements of the hardware by using the first programming language specific specializer. Development of code is facilitated without losing performance.

In a first possible implementation form of the processor according to the third aspect, the first programming language specific specializer corresponds to the first programming language specific specializer according to the second aspect as such or according to any of the preceding implementation forms of the second aspect.

The first programming language specific specializer provides a framework for efficiently transforming a first programming language IR to a second programming language IR. The first programming language specific specializer facilitates development of generic code without losing processing performance.

In a second possible implementation form of the processor according to the third aspect as such or according to the first implementation form of the third aspect, the first programming language comprises a domain specific language and the second programming language comprises a model specific language.

A domain specific language is a high abstraction level programming language that uses many generic programming constructs. Development is efficient when using DSL. A model specific language is a low abstraction level programming language that is adapted to a specific processor platform, i.e. the specific (processor) model. When combining the DSL with MSL by the transforming, code development is quite efficient as generic DSL constructs provide easy development of code, e.g. algorithms and MSL constructs provide for an efficient execution of the code on a specific processor platform.

According to a fourth aspect, the invention relates to a computer program product comprising a readable storage medium storing program code thereon for use by a processor system executing the method according to the first aspect as such or according to any of the preceding implementation forms of the first aspect.

The computer program can be flexibly designed such that an update of the requirements is easy to achieve. The computer program product may run on a lot of different processing systems.

Aspects of the invention provide a novel system architecture to support development of layered DSLs. Aspects of the invention provide a novel method of domain-specific optimizations for high-performance computations. Aspects of the invention bring module and component based techniques of software development to the field of DSL

construction. Aspects of the invention simplify implementation of compilers for high- performance DSLs. Aspects of the invention provide a new system for DSL implementation. Aspects of the invention provide a method for implementing Domain Specific Specializer (DSS) which may be considered as a core feature of the disclosed new system. Graph-based IR is used for representing the source program inside the compiler. The system architecture and compilation workflow are exemplary presented in Figure 2 as described below.

BRIEF DESCRIPTION OF THE DRAWINGS

Further embodiments of the invention will be described with respect to the following figures, in which:

Fig. 1 shows a block diagram illustrating a conventional DSL Development Framework;

Fig. 2 shows a block diagram illustrating a DSL Development Framework and compilation workflow according to an implementation form; Fig. 3 shows a schematic diagram illustrating an example of a Domain Specific

Specialization according to an implementation form;

Fig. 4 shows a schematic diagram illustrating a Graph-based IR of an example program according to an implementation form;

Fig. 5 shows a schematic diagram illustrating a Interpreter design pattern according to an implementation form; Fig. 6 shows a schematic diagram illustrating an Implementation of an abstract method in CIC according to an implementation form;

Fig. 7 shows a schematic diagram illustrating an example of Concrete Implementation Classes according to an implementation form;

Fig. 8 shows a schematic diagram illustrating a Domain Specific Specializer according to an implementation form;

Fig. 9 shows a schematic diagram illustrating a Domain Specific Specializer and its components according to an implementation form;

Fig. 10 shows a schematic diagram illustrating an example for an Invocation rule according to an implementation form; Figs. 1 a) and b) show exemplary commutative diagrams for a map operation according to an implementation form;

Fig. 12 shows schematic diagrams illustrating exemplary Map processing in case when CgTF according to an implementation form;

Fig. 13 shows schematic diagrams illustrating exemplary Map processing in case when CeTF according to an implementation form;

Fig. 14 shows schematic diagrams illustrating exemplary Filter processing according to an implementation form; Fig. 15 shows a schematic diagram illustrating a method 1500 for compiling a source code in a first programming language to a program code in a second programming language according to an implementation form; and Figs. 16 a) - j) show schematic diagrams illustrating a method of staged evaluation that may be used in a Domain Specific Specializer according to an implementation form:

Fig. 16 a) shows a schematic diagram of a method of staged evaluation 1800 for constructing a graph data structure according to an implementation form;

Fig. 16 b) shows a schematic diagram of a factory method design pattern 1900 according to an implementation form;

Fig. 16 c) shows a schematic diagram illustrating application of a factory method pattern 2000 to array nodes 2001 according to an implementation form;

Fig. 16 d) shows a listing of a source code 2 00 illustrating factory methods of array class according to an implementation form; Fig. 16 e) shows a schematic diagram illustrating a proxy design pattern 2200 according to an implementation form;

Fig. 16 f) shows a schematic diagram illustrating an application of the proxy design pattern of Fig. 16 e) to array nodes 2307 and symbols 2305 according to an implementation form;

Fig. 16 g) shows a listing of a source code 2400 illustrating generalized classes of graph data structure according to an implementation form;

Fig. 16 h) shows a listing of a source code 2500 illustrating a staged evaluation method according to an implementation form;

Fig. 6 i) shows a listing of program code 2600 representing core methods for

constructing a graph data structure according to an implementation form; and Fig. 16 j) shows an staged evaluation apparatus 2700 for compiling a source code into executable machine code according to an implementation form. DETAILED DESCRIPTION OF EMBODIMENTS

In the following detailed description, reference is made to the accompanying drawings, which form a part thereof, and in which is shown by way of illustration specific aspects in which the disclosure may be practiced. It is understood that other aspects may be utilized and structural or logical changes may be made without departing from the scope of the present disclosure. The following detailed description, therefore, is not to be taken in a limiting sense, and the scope of the present disclosure is defined by the appended claims.

The devices and methods described herein may be based on coherent optical signal transmission and reception. It is understood that comments made in connection with a described method may also hold true for a corresponding device or system configured to perform the method and vice versa. For example, if a specific method step is described, a corresponding device may include a unit to perform the described method step, even if such unit is not explicitly described or illustrated in the figures. Further, it is understood that the features of the various exemplary aspects described herein may be combined with each other, unless specifically noted otherwise. The methods and devices described herein may be implemented in coherent optical transmitters and receivers, in particular transceivers using BPSK dual polarization modulation. The described devices and systems may include software units 123 and hardware units 125 as described above with respect to Figs. 1 and 2. The described devices and systems may include integrated circuits and/or passives and may be manufactured according to various technologies. For example, the circuits may be designed as logic integrated circuits, analog integrated circuits, mixed signal integrated circuits, optical circuits, memory circuits and/or integrated passives.

Fig. 2 shows a block diagram illustrating a DSL Development system 200 including a DSL Development Framework 103 and compilation workflow 230 according to an

implementation form.

The DSL Development system 200 as depicted on the left side of Fig. 2 includes the following novel components with respect to the DSL Development system 100 depicted in Fig. : A Meta DSL Framework 201 is used instead of a Common Compiler Infrastructure 1 1 1 as described above with respect to Fig. 1. This component 201 forms the basis for constructing high-level DSLs. The purpose of Meta DSL Framework 201 is to separate domain specific objects from model specific ones. Meta DSL Framework 201 is built of a number of Model Specific Languages (MSL) 205, 207, 209 each of which corresponds to a particular programming model (e.g. NDP, Queries, etc.). Each MSL 205, 207, 209 is implemented as a separate compiler component 21 1 , 213, 215. A Domain Specific Specializer (DSS) 203 is a part of the compiler used for converting a high-level DSL representation 105, 107, 108, 109 to a lower-level MSL one 205, 207, 209. This component 203 is used for transforming domain-level objects to their concrete

implementations, which are based on existing data structures supported by MSLs. DSS 203 can support several different concrete implementations for each domain object.

The system behavior can be described by the following general steps as illustrated in the compilation workflow 230 on the right side of Fig. 2. Graph-based domain specific intermediate representation 135 is created from the source code 131 written in high-level DSL. Domain-level optimizations and transformations are applied. Domain specific specialization 243 is performed. Domain specific code (represented by graph-based IR) is transformed towards model specific IR 245. All domain-level objects are transformed to model-level objects via selected concrete implementation. Model specific optimizations and transformations are applied, e.g. vectorization. Executable code is generated 137. The MetaDSL Framework 201 serves as a basis for constructing high-level DSLs.

Substantially it is an infrastructure for supporting effective converting from a high-level intermediate representation in a first programming language such as DSL to a lower-level one in a second programming language such as MSL. The MetaDSL Framework 201 is implemented based on the following components that will be described in detail in the following:

- Global compiler infrastructure,

- Graph-based IR,

- Graph Interpreter and Staged Evaluator,

- Specialization infrastructure,

- Abstract interface for DSL objects,

- Type families and type descriptors,

- Isomorphisms and Views,

- Concrete implementation classes, and

- Separate stage of compiler: Domain Specific Specializer.

Fig. 3 shows a schematic diagram illustrating an example of a method for Domain Specific Specialization 300 according to an implementation form. In the example of Fig. 3 a function 335 is considered which finds all isolated vertices of a non-oriented graph. As can be seen, the high-level DSL code 248 operates only with Graph and Node objects and an appropriate method "numOutNbrs". After that the code that is a graph-based IR is processed by the Domain Specific Specializer 241 that may correspond to the unit 241 described above with respect to Fig. 2. It chooses a concrete implementation of the Graph object 351 by the block PArray[PArray[lnt]] (Adjacency List) 353 and applies corresponding transformation to code. Other concrete implementations 355, 357, 359 are not used. Then a program code 345 is obtained operating only with MSL structures 250 and an executable program 339 is provided. The choice of concrete implementation may be done due to application developer definition.

Fig. 4 shows a schematic diagram illustrating a Graph-based IR 400 of an example program according to an implementation form.

In this disclosure graph-based intermediate representations (IR) of programs are used. IR nodes of the graph correspond to operations of the source program and edges correspond to dataflow between operations. Fig. 4 shows a graph representation 400 of a simple program.

The order of execution is dictated by the dependencies between the nodes and not specified explicitly. Graph-based IR in machine memory may be a lookup table from symbols to nodes. Table 1 illustrates a lookup table corresponding to the graph based IR depicted in Fig. 4.

Table 1 : Lookup table corresponding to the graph based IR of Fig. 4

Each pair (S,N) in the graph data structure represents definition of a symbol according to: S - symbol (unique identifier, id)

N - instance of class derived from the Node class. Here Add, Mul are classes derived from Node abstract class. Edges of the graph are represented by symbols that are stored in nodes 401 , 403, 405, 407, 409.

Fig. 5 shows a schematic diagram illustrating an Interpreter design pattern 500 comprising a Client 501 , a Context 503, an "AbstractExpression" 505 with a method

"Interpret(Context)" 507, a "TerminalExpression" 509 with a method "Interpret(Context)" 51 1 and a "NonterminalExpression" 513 with a method "Interpret(Context)" 515 according to an implementation form.

In order to traverse the graph data structure 400 shown in Fig. 4 the Interpreter design pattern as described by "http://en.wikipedia.org/wiki/lnterpreter_pattern" and shown in Fig. 5 may be used.

The behavior of the canonical interpreter software design pattern is adapted to deal with program graphs in the following way:

- The abstract Node class of a program graph is treated as "AbstractExpression";

- Instances of classes derived from the Node class are treated as either

"TerminalExpression" or "NonterminalExpression" according to the following rules:

- program graph nodes, that represent primitive operations of the language (such as Java), are treated as terminals, i.e. "TerminalExpression";

- program graph nodes, that represent user-defined functions, are treated as nonterminals, i.e. "NonterminalExpression".

- User-defined functions are called "Lambdas"; each Lambda is characterized by the following parameters:

- parameter symbols (also denoted as "lambda-bound variables") which do not have definition in the graph-based IR;

- lambda body is the sequence of the graph-based IR definitions, that depend on the function parameter symbol;

- result symbol represents the results of the execution of the function.

The Method Interpret) of a terminal node N calls Staged Evaluator (SE), that is described below with respect to Figs. 8 and 9. The symbol S of node N is provided as the first argument of an (Operation, Context) pair. It also uses current context as the second component of the pair. The context is a mapping between input symbols and resulting symbols. The pair (Operation', Context') is returned by the Staged Evaluator. Current context is replaced with Context' being used as the current context for the next definition. The resulting graph is updated by the Staged Evaluator. The Method "InterpretO" of a Lambda node L is defined by the following items:

1 ) It creates a new Lambda node L';

2) For each parameter symbol of lambda L it adds a new parameter symbol to L' and remembers this correspondence in the current context;

3) It calculates the body of the lambda L by building a list of definitions that depend on parameter symbols. Definitions from the body of the lambda are topological^ sorted with respect to dependencies represented by edges of the graph. It means that each definition is interpreted after all the definitions it depends on;

4) For each definition in the body of the lambda the Graph Interpreter calls the "InterpretO" method and updates the current context. The resulting graph is updated by the Staged Evaluator;

5) After the traversal of lambda body is done the Graph Interpreter retrieves the result symbol of L' from the context. It is a symbol from the resulting graph which corresponds to the result symbol of lambda L;

6) After all the components of L' (i.e. parameters, body and result symbols) are calculated, L' is added to the resulting graph and L -> L' pair is added to the context.

The Staged Evaluator is a common compiler component. It is called by the Graph

Interpreter to process a single graph node of the original graph. It is implemented by using a staged evaluation method as described below with respect to Figs. 16 a) to 16 j) with the set of rules to transform the original graph of the program P to a resulting version P'.

Given a symbol from the original graph and the current context (sym, ctx), the Staged Evaluator applies rules from the given set and produces a new pair (sym', ctx'), where sym' is a symbol from the resulting graph that corresponds to the symbol sym.

Each high-level DSL object is considered to have an abstract interface consisting of the set of methods available for this object. For example, each object of type Graph regardless of its concrete representation should have method nodes, which returns the set of graph vertices. For this purpose the system contains an interface description for all domain-level objects (or DSL objects). Table 2 illustrates such an exemplary description in a Java-like style.

Each concrete implementation class as described below, being inherited from some abstract DSL object shall contain concrete implementations of all the methods of its parent interface. Class Interface

A1 interface A1 {

void a 1 Method 1 (... )

void a1 Method2(...)

}

A2 interface A2 {

void a2Method1 (... )

void a2Method2(... )

}

AN interface AN {

void aNMethod1 (... )

void aNMethod2(... )

}

Table 2: Abstract interface description for domain-level objects

Each particular Specific Language (either DSL or MSL) may be characterized by a specified Type Family (TF). This is a set of types "used" by language operations. For all operations supported by a language, all its arguments' and results' types belong to the corresponding TF. Each particular TF may be defined in a constructive way. This way involves the set of basic types and several constructors as well as ways of constructing new types based on existing ones. An example of a TF definition is shown in Table 3.

T _N memberN

/* Methods */

T _N+1 methodl (argsl )

T _N+M methodM(argsM)

}

Table 3: Type Family (TF) definition example

Every value may have a type and this type may be represented by a special object, the so called type descriptor. The type descriptor for any particular non-basic type is constructed from appropriate type descriptors of its components. Every particular value has an appropriate type descriptor as a separate field. When using name type, if an object "a" has a type T then the "a".type refers to the type descriptor for type T. This allows to operate with types and with values using type descriptors. For example, type descriptors can be used in patter matching in order to determine whether a particular type belongs to a selected type family or a value is of a particular type.

In the following Isomorphisms (Iso) and Views concepts or constructs are defined. If considering two types A and B, lso[A,B] implies the definitions of two functions from: (A -> B) and to: (B -> A). These functions are considered to implement mutually inverse functions between A and B. The second concept or construct is Views. Two types A and B are considered and some functor Fct. In this case View[A,B,Fct] is a class with the following properties:

- View[A,B,Fct] is a subclass of Fct[B];

- View[A,B,Fct] has Fct[A] and iso: lso[A,B] as members;

- View[A,B,Fct] can be constructed from (in:Fct[A], iso: lso[A,B]), i.e. appropriate constructor View(in, iso) can be implemented;

- View[A,B,Fct] can be deconstructed back to (in:Fct[A], iso: lso[A,B]);

To clarify the View concept, a special case is considered when Fct=PArray (i.e. a parallel array). In this case the class "View[A,B,PArray](in: PArray[A], iso:lso[A,B])" can be defined which is a subclass of PArray[B] and can be used as its instance . That means, a transformation is built from PArray[A] to PArray[B] while initially there is isomorphism between A and B only. Fig. 6 shows a schematic diagram illustrating an Implementation of an abstract method in a Concrete Implementation Class (CIC) according to an implementation form.

A main goal of the Meta DSL framework 201 described above with respect to Fig. 2 is to automatically convert DSL objects to MSL-level ones. Furthermore, each domain-specific object may be represented in MSL in several ways.

For this purpose, for any domain-specific type T e TF the set of classes (i.e. types) Ττ, . , . ,Τη may be defined that is called Concrete Implementation Classes (CIC), so that for each T _k the following holds:

1 . T _k is a subclass of T, i.e. can be used as instance of T;

2. T _k is associated with some unique type Data _k 6 ModelTF , where ModelTF is MSL type family. Data _k is referred to as data type for a particular T _k ;

3. T _k can be constructed out of the variable of type Data _k , i.e. appropriate constructor T _k (Data _k ) can be implemented;

4. There exists a unique Isomorphism between T _k and Data _k : lso[Data _k , T _k ]. This Isomorphism can be accessible from T _k without creation of class' instance;

5. T _k implements all the methods of abstract interface of T using MSL primitives;

6. If a particular abstract method m of T has a return type Fct[B], where Fct is some functor and B e TF, then for the implementation of m it follows:

a. either the return value of the method is some expression of type Fct[B];

b. or some View is returned by the method. The View is constructed in the following way: 1 ) Concrete Implementation Class for B is selected (e.g. denoted as B, ) along with Iso and correspondent Data Type D _j and 2) the return value of this method m can be an instance of View[D _j , B, Fct] (res, B _j .lso), where res: Fct[D _j ];

An example of abstract method implementation is shown in Figure 6. Here method nodes is assumed in class Graph 601 , which is expected to return an array 604 of all graph vertices: PArrayfVertex]. When implementing method nodes in concrete class

AdjListGraph 603, CIC "VertexAsInt" with correspondent data type "Int" 612 is selected for Vertex type. So, the return value 610 is constructed using B = Vertex, B VertexAslnt, D _j =lnt and Fct=PArray. Hence, the concrete implementation of method nodes can return appropriate View as shown in Figure 6. Each Concrete Implementation Class thus provides a final low-level representation of initial DSL objects and methods. It is convenient to represent the set of domain-specific classes and their CICs in a table as shown below (Table 4).

Table 4: Example for domain specific classes and CICs

Fig. 7 shows a schematic diagram illustrating an example of Concrete Implementation Classes 700 according to an implementation form.

The example uses two Concrete Implementation Classes for type Graph 701. Graph 701 is represented in two different ways, i.e. as an adjacency matrix or as an adjacency list. For this purpose two CICs are defined: AdjMatrixGraph 703 and AdjListGraph 705. Each of the CICs 703, 705 is associated with the correspondent Data Type 707, 709 via isomorphism isol 717 or iso2 7 9.

Fig. 8 shows a schematic diagram illustrating a Domain Specific Specializer 241 according to an implementation form.

The DSS 241 that may correspond to the DSS 241 described above with respect to Fig. 2 takes a high-level DSL source code 801 as an input and produces a specialized lower- level MSL code 805 as an output based on a configuration 803. Thus, using terms from Figure 7 the following can be stated:

A1 , ... ,AN, B e TF, where TF is DSL type family; and

A1 AN', B' e ModelTF, where ModelTF is MSL type family.

The Domain Specific Specializer 241 may be implemented as a separate stage of the compiler. The detailed behavior of the DSS 241 can be described as follows:

- For each domain-level type, one of its Concrete Implementation Class is selected for further usage; - The Graph-based intermediate representation is either created from some other representation (e.g. text file) or from the previous compilation phase;

- The program graph is supplied to the Graph Interpreter (Gl) component of the DSS. The Gl creates empty context and starts graph traversal respecting dependencies between nodes;

- For each node Gl calls the Staged Evaluator (SE) and supplies symbol correspondent to current operation and context;

- The SE uses specialization and optimization rules to produce specialization of current symbol in current context;

- After the specialization is produced SE for a given symbol it is returned back to

Gl. Gl then updates the context with a new pair (Symbol -> Symbol') and continues graph traversal;

- the resulting graph for a specialized version F' of the input program F is ready after the traversal is finished.

Fig. 9 shows a schematic diagram illustrating a Domain Specific Specializer 900 and its components according to an implementation form.

Components of the DSS 900 along with a flow of information are shown in the simple example in Figure 9. These are a Staged Evaluator (SE) 905 and a (Program) Graph Interpreter (Gl) 91 1. The procedure corresponds to the one described above with respect to Fig. 8. Here, a simple program checks whether two particular vertices are linked in the graph. The initial DSL representation uses an abstract method "hasEdge" 901 of the object graph which, in turn, has the abstract type "Graph". After specialization is done, the object graph gets the concrete type (PArray[PArray[lnt]]), and the abstract method "hasEdge" is replaced with its concrete implementation. The Staged Evaluator 905 in DSS 900 processes each node 913 of the program graph by using specialization rules 907. When processing each particular symbol the SE 905 uses the set of specified rules in order to apply them for symbol's rewriting. Each particular rule is applied in case of its input matches the specified pattern.

Fig. 0 shows a schematic diagram illustrating an example for an Invocation rule 1000 according to an implementation form. Invocation rule or Rule 1 is defined according to Table 5. Input Pattern Result

ethodCall(obj, method, args), method. invoke(obj, args)

where

type of obj belongs to DSL type family

obj has definition in program graph

Table 5: Invocation rule description

Rule 1 is applied to MethodCall nodes of the IR graph. These nodes, being

correspondent to calling some method in source program, depend on the three inputs:

- receiver: an object of source program that owns called method;

- method: the called method; and

- arguments: arguments passed to called method.

Rulel works on condition that its receiver (obj) has direct definition (some Node) in the program graph. In this case simply the method "invoke" is executed which is automatically transformed to a correspondent subgraph by the Staged Evaluator. The invocation mechanism represented here by the method "invoke" is used to apply the method of staged evaluation as described below with respect to Figs. 16 a) to 16 j) as one of the possible ways to implement a construction of the resulting graph. Figure 10 demonstrates an example of simple invocation. Essentially, simple invocation can be treated as inline substitution and further staged evaluation. Figure 10 shows the redundant construction of the domain object "AdjMatrixGraph" 1006 that is successfully eliminated by this technique.

The following operations are performed:

for input to method invoke():

sO =adjMatrix: Parray[Boolean], 1002;

s1 = size: Int, 1004;

s2 = AdjMatrixGraph(sO, s1 ), 1006;

s = s2.complement(), 1008;

for method invoke 1024:

s3 = adjMatrix: Parray(Boolean], 1010;

s4 = s/ze: Int, 1012;

s5 = AdjMatrixGraph(s3,s4), 1014;

implementation of method complement(), 1026:

s6 = s5.adjMatrix, 1016;

s7 = s5.size, 1018;

s8 = Vectorlnvert(s6), 1020; s9 = AdjMatrixGraph(s7, 8), 1022;

for output to method invoke():

s10 = adjMatrix: Parray[Boolean], 1028;

s11 = size: Int, 1030;

s12 = Vectorlnvert(s10), 1032;

s' = AdjMatrixGraph(s11 , 12), 1034.

Figs. 1 1 a) and b) show exemplary commutative diagrams 1 100a, 1 100b for a map operation according to an implementation form.

Map processing rule or Rule 2 is defined according to the following. Rule 2 works when processing Map node, i.e. a node which corresponds to the map operation specified by some functor "Fct". Here map operation is referred to as any operation which satisfies the commutative diagrams from Figure 1 1 .

For the first commutative diagram 1 100a it holds:

Applying View[A,B,Fct](iso) 1 108 on Fct[A] 1 102 results in Fct[B] 1 104;

Applying map (f o iso.to) 1 10 on Fct[A] 102 results in Fct[C] 106;

Applying map (f) 1 1 12 on Fct[B] 1 104 results in Fct[C] 1 106.

For the second commutative diagram 1 100b it holds:

Applying View[A,B,Fct](iso1 ) 1 130 on Fct[A] 1 122 results in Fct[B] 1 124;

Applying map (iso2.from o f o isolto) 1 132 on Fct[A] 1 122 results in Fct[C] 1 126;

Applying map (f) 1 136 on Fct[B] 1 124 results in Fct[D] 1 128;

Applying View[A,B,Fct](iso2) 1 134 on Fct[C] 1 26 results in Fct[D] 1 128.

The pattern for Rule 2 assumes that one of inputs of Map is View[A,B,Fct], AeModelTF, BeTF, operation and another one is a user-defined function which takes B as an argument. Table 6 describes Map processing rule.

some functor fNew = ( p => outlso.from( f (inlso.to( p

Map is operation )) ) )

applicable to Fct, which has one res = Map(in, fNew)

functional argument View[D _j , C, Fct](res, outlso)

• f: [B => C ] is user-defined } Else {

function fNew = (p => f(inlso.to(p)) )

Map(in, fNew)

Table 6: Map processing ru e description

Figure 12 demonstrates Rule 2 working in case when CgTF which corresponds to diagram 1 100a from Figure 1 1. In this example, an array of graph vertices is mapped by a function which computes the number of out-edges for each vertex (i.e. A=lnt,

B=VertexAslnt, C=lnt, Fct=PArray). The result of mapping is an array of integer values - PArray[ Int]. The following operations are performed: for the input of Map processing:

in: Parray[lnt], 1202;

s2: Vertex, 1204;

v= View[lnt,VertexAslnt,PArray] (in), 1206;

s3 = s2.numOutEdges(), 1208;

s4 = s2->s3, 1210;

s = v.map(s4), 1212; and for the output of Map processing:

s5: Parray[lnt]; 1214;

s7: Int, 1216;

s8 = VertexAslnt(s7), 1218;

s9 = s8.numOutEdges(), 1220;

s10 = s7->s9, 1222;

s' = s5.map(s10), 1224. Fig. 13 shows schematic diagrams illustrating exemplary Map processing 1300 in case when CeTF according to an implementation form.

Figure 13 demonstrates Rule 2 working in case when CeTF, which corresponds to Diagram 2 1 100b from Figure 1 1. In this example, an array of graph edges is mapped by a function which produces edge start vertex (i.e. A=(lnt,lnt), B=EdgeAsPair,

C=VertexAslnt Fct=PArray). The result of mapping is PArray[ VertexAslnt].

In the last case after the rule is applied the result is the View operation. This is done in order not to lose type compatibility with the rest part of the program graph.

The following operations are performed: for the input of Map processing:

in: Parray[(lnt, Int)], 1302;

s2: Edge, 1304;

v= View[(lnt,lnt), EdgeAsPair.PArray] (in), 1306;

s3 = s2.start(), 1308;

s4 = s2->s3, 1310;

s = v.map(s4), 1312; and for the output of Map processing:

s5: Parray[(lnt, Int)], 1314;

s7: (Int, Int), 1316;

s8 = EdgeAsPair(s7), 1318;

s9 = s8.start(), 1320;

s10 = s9.id, 1322;

s11 = s7->s10, 1324;

s12 = s5.map(s11 ), 1326;

s'= View[lnt,VertexAslnt,PArray] (s12), 1328.

Fig. 14 shows schematic diagrams illustrating exemplary Filter processing 1400 according to an implementation form. Filter processing rule or Rule 3 works when processing a Filter node, i.e. a node which constructs a new collection from an initial one by selecting only elements satisfying some condition. In this case, the condition may be defined by a Boolean function. The pattern for Rule 3 assumes that one of the inputs of Filter is the View[A,B,Fct] operation and another one is a user-defined Boolean function which takes B as an argument. Furthermore, AeModelTF, BeTF. Table 7 describes Filter processing rule.

Table 7: Filter processing rule description

The example of Rule 3 is depicted in Figure 14. In this example, isolated vertices are selected from vertices array. For this purpose, the Filter operation is used, where the filtering function returns true if a particular vertex is isolated.

The Rule 3 result, again, is a View operation. This is done in order not to lose type compatibility with the rest part of the program graph. The following operations are performed: for the input of Filter processing:

in: Parray[lnt], 1402;

s2: Vertex, 1404;

v= View[lnt,VertexAslnt,PArray] (in), 1406;

s3 = s2.islsolated(), 1408;

S4 = s2->s3, 1410;

s = v.filter(s4), 1412; for the output of Filter processing:

s5: Parray[lnt], 1414;

s7: Int, 1416;

s8 = VertexAslnt(s7), 1418;

s9 = s8.islsolated(), 1420; s10 = s7->s9, 1422;

s6 = s5.filter(s10), 1424;

s'= View[lnt,VertexAslnt,PArray] (s6), 1426. These three basic rules are in fact enough for most DSL programs. After the whole IR- graph is traversed, it will contain neither DSL-level operations nor View operations. If speaking in simple words, when traversing the program graph in Reverse Post Order, on each step these operations are «moved down» towards graph stop-node. Namely:

- each DSL-object constructor is either eliminated or «moved down » by Rule 1 ;. - each View operation, which can appear from DSL methods invocation, is either eliminated or «moved down » by Rule 2 or Rule 3.

Actually, in any particular case, other specialization rules may be needed. For example, if the MSL model supports Nested Data Parallelism, rules may be needed for processing some nested-arrays operation. Although rules were not described for each particular case, these rules can be easily constructed using the same idea as used in this disclosure. Namely, each rule should eliminate or «move down» undesired nodes until they will be annihilated at the end of the program graph.

Fig. 5 shows a schematic diagram illustrating a method 1500 for compiling a source code in a first programming language to a program code in a second programming language according to an implementation form.

The method 1500 may include generating 1501 a graph based on the source code, the graph corresponding to a first programming language specific intermediate representation of the source code. The method 1500 may include transforming 1502 the graph from the first programming language specific intermediate representation to a second programming language specific intermediate representation. The method 1500 may include generating 1503 the program code based on the second programming language specific intermediate representation of the graph.

In an implementation form of the method 1500, the first programming language comprises a domain specific language and the second programming language comprises a model specific language. In an implementation form of the method 1500, transforming 1502 the graph is based on a first programming language specific specialization. In an

implementation form of the method 1500, transforming 1502 the graph comprises transforming objects of the graph to concrete implementations of the objects which concrete implementations are based on data structures supported by the second programming language specific intermediate representation. In an implementation form of the method 1500, the graph comprises nodes corresponding to operations of the source code and edges corresponding to data flow between the operations, wherein the edges comprise symbols stored in the nodes of the graph. In an implementation form of the method 1500, the graph comprises a lookup table for looking up from the symbols to the nodes. In an implementation form of the method 1500, the method 1500 comprises using a graph interpreter adapted to deal with program graphs for transforming the graph from the first programming language specific intermediate representation to the second programming language specific intermediate representation. In an implementation form of the method 1500, the graph interpreter comprises: an abstract expression for an abstract node class of the graph, a terminal expression for treating instances of classes derived from the node class of the graph that represent primitive operations of the first

programming language, a nonterminal expression for treating instances of classes derived from the node class of the graph that represent user-defined functions of the first programming language, a first interpret method for interpreting the terminal expression, and a second interpret method for interpreting the non-terminal expression.

The method 500 may be applied in a first programming language specific specializer, e.g. a DSS as described above with respect to Figs. 8 and 9.

Such a first programming language specific specializer 241 , 900 is operable on a processor configured to compile a source code in a first programming language to a program code in a second programming language. The first programming language specific specializer is configured to transform a graph corresponding to a first

programming language specific intermediate representation of the source code from the first programming language specific intermediate representation to a second programming language specific intermediate representation such that the program code can be generated by the processor based on the second programming language specific intermediate representation of the graph.

In an implementation form of the first programming language specific specializer 241 , 900, the first programming language comprises a domain specific language and the second programming language comprises a model specific language. In an implementation form, the first programming language specific specializer 241 , 900 comprises a program graph interpreter configured to traverse through nodes of the graph and supply for each node a symbol corresponding to a current operation and a current context. In an implementation form, the first programming language specific specializer 241 , 900 comprises a staged evaluator callable by the program graph interpreter. The staged evaluator is configured to produce a specialization of the symbol in the current context. In an implementation form, of the first programming language specific specializer 241 , 900, the program graph interpreter is configured to update the symbol with the specialization of the symbol provided by the staged evaluator. In an implementation form of the first programming language specific specializer 241 , 900, the specialization is based on at least one of the following specialization rules: Invocation, Map processing and Filter processing as described above with respect to Figs. 1 1 to 14. In an implementation form, the first programming language specific specializer 241 , 900 is configured to transform the graph based on at least one of the following programming constructs: Concrete Implementation Classes, Isomorphisms and Views as described above with respect to Figs. 1 1 to 14.

Figs. 16 a) -j) show schematic diagrams illustrating a method of staged evaluation that may be used in a Domain Specific Specializer as described above with respect to Figs. 2, 8 and 9, in particular in a staged evaluator 905 as described above with respect to Fig. 9.

Fig. 16 a) shows a schematic diagram of a method 1800 of staged evaluation for constructing a graph data structure according to an implementation form. The method 800 may be used for constructing the graph data structure as an intermediate representation of source code for a compiler, for example a compiler 233 as described with respect to Fig. 2. The compiler is configured for compiling the source code into executable machine code which runs on a processor of a computer system. The program operations of the source code are represented in an object-oriented programming language by objects of classes that form a hierarchy growing from a base node class of the graph data structure. The method 1800 comprises producing new nodes 1801 of the graph data structure by calling factory methods associated with existing nodes of the graph data structure based on a factory method design pattern implemented in the nodes of the graph data structure, wherein the nodes of the graph data structure are identified by symbols. The method 1800 comprises using 1803 the symbols as proxies of the nodes of the graph data structure according to a proxy design pattern.

In an implementation form of the method 1800, each node of the graph data structure is implemented as an object of a class. In an implementation form of the method 1800, the symbols are used as typed proxies to the corresponding nodes of the graph data structure. In an implementation form of the method 1800, the factory methods use instances of the symbols, so that when a method of a symbol is called the corresponding method of the node is executed. In an implementation form of the method 1800, depending on a type of a node of the graph data structure each class of the node comprises factory methods. In an implementation form of the method 1800, the factory methods are configured to produce the new nodes along with connections to the existing nodes. In an implementation form of the method 1800, each factory method comprises a subroutine associated with a class of the node of the graph data structure, the factory method determining a behavior to be exhibited by instances of the associated class at program runtime. In an implementation form of the method 1800, the proxy comprises a class functioning as an interface to a subject. In an implementation form of the method 1800, the proxy design pattern is configured to provide a proxy with a factory method for delegating calls of a client calling the factory method of the proxy to a called subject. In an implementation form of the method 1800, the factory method design pattern is configured to design an interface for creating an object. In an implementation form of the method 1800, classes of the object-oriented programming language that implement the interface decide which class to instantiate. In an implementation form of the method 1800, the nodes of the graph data structure are one of the following: parts of the graph data structure, external entities represented by integer indices, external entities represented by references. In an implementation form of the method 1800, the object-oriented

programming language comprises the following features: virtual methods, abstract methods and parameterized types.

The method 1800 solves the problems identified by analysis of prior art and eliminates the limitations of graph-based IR. The method 1800 implements a staged evaluation technique in object-oriented languages and can be applied for generic programs. An execution of a program to calculate a resulting value is just one of possible

interpretations of its source code and is typically defined by the operational semantics of the source language. The same source code can also be used in a different way i.e. using different semantics. Instead of executing the program for calculation it can be executed for generation of intermediate representation (IR). This execution is termed as "staged evaluation", i.e. evaluation that is separated into two stages: First IR generation and secondly IR execution. Evaluation is called "staged" to reflect the fact that the same program can have both operational semantics of source language and also staged evaluation semantics. In staged evaluation, instead of resulting data value, the result of executing the program is an IR. IR is a data structure that keeps track of all the operations that were used in the program along with their order. In the example in Fig. 2 the program may use summation, calculation of length and division operations. The method 1800 uses graph-based IR, so the result of staged evaluation is a graph of the program which is also called program graph, or simply a graph. The resulting graph is an internal in-memory representation of the source code. This technique of staged evaluation can be implemented in object- oriented language.

In an implementation, the method 1800 is developed in the following steps: In step 1 , the role of graph nodes in the graph building process is changed. Besides representing operation each node can also be used to produce new nodes. Since each node is implemented as an object of a class, methods are added to classes of nodes in such a way that a graph is extended, i.e. constructed by calling or invoking those methods. This is described below with respect to Fig. 16 d). In object-oriented terms each graph node is made to play a role of "factory" of other nodes by implementing a so called "Factory method" design pattern. In step 2, interfaces of Graph, Node, Sym (symbol) classes are generalized and the "staged evaluation" technique is implemented. The generalized version of the "average" example program can be staged and implemented by methods according to the invention. The staged version is shown in Fig. 16 h). The implementation of "staged evaluation" is further described below with respect to Fig. 16 h). It is based on a well-known Proxy design pattern which is described below with respect to Figures 16 d) and 16 e).

The staged evaluator 905 depicted in Fig. 9 may implement the method 1800.

Fig. 16 b) shows a schematic diagram of a factory method design pattern 1900 according to an implementation form. The factory method design pattern is an implementation of the factory method design pattern as described above with respect to Fig. 16 a).

The "Factory method" design pattern 1900 shown in Fig. 16 b) solves the problem of creating nodes without specifying the exact class of node that will be created. The object "ConcreteCreator" 1903 comprising a function "factoryMethod(): Product" provides information to an object "Creator" 1901 comprising the function "factoryMethod(): Product" and to an object "Product" 1905. By that factory method design pattern 1900 the graph building code is generalized.

Fig. 16 c) shows a schematic diagram illustrating application of a factory method pattern 2000 to array nodes 2001 according to an implementation form. The array nodes 2001 may correspond to the nodes of the graph data structure as described above with respect to Fig. 16 a).

The factory method pattern 2000 is applied to a node 2001 of a graph. The factory method pattern 2000 comprises the objects "FloatArray" 2007, "Array<Float>" 2005 and

FloatArrayLength 2003. The object "FloatArray" 2007 comprising the function "length(): Node" provides information to the object "Array<Float>" 2005 comprising the function "Length(): Node" and to the object "FloatArrayLength" 2003. The concept of the factory method pattern 2000 is to extend prior art IR and allow graph nodes to play an additional "factory" role. Depending on the types of nodes each class of node (the class is derived from the Node class) can contain one or more factory methods. These factory methods, when called, produce new graph nodes along with connections to already existing nodes supplied either explicitly or implicitly via arguments. The factory method pattern 2000 after applying it to node class is depicted in Fig. 16 c).

Fig. 16 d) shows a listing of a source code 2100 illustrating factory methods 2103 of an array class 2101 according to an implementation form. The factory methods are an implementation of the factory methods as described above with respect to Fig. 16 a).

Methods of class Array 2101 as shown in Fig. 16 d) are array methods. In class

FloatArray 2101 it can be seen (see method length) how they can produce new nodes of a graph and thus can be used as factory methods. The factory method "length()" 2103 produces a new node by returning the function "FloatArrayLength(nodeSymbol)" 2105 which provides the symbol parameter "nodeSymbol" to the new node.

A graph node of type Array<T> 2107 is given for some type T where the exact type is not known and the statement len = arr.length() is executed. Because the graph data structure and nodes as part of it is implemented as objects of classes, this statement is a method call and it is executed as a virtual method call. So, the exact implementation of the method length, that is called, depends on the exact class of the Array object referenced by the variable "arr". If the exact class of variable "arr" is "FloatArray" 2101 then its method length 2103 is called. The result of the execution is a symbol "nodeSymbol" corresponding to the newly created graph node of type "FloatArrayLength". Note that when the method length 2103 of the instance of "FloatArray" class 2101 is called, the field "g" has already been initialized to the owner graph so a newly created node will belong to the same graph "g" as this "factory node". Fig. 16 e) shows a schematic diagram illustrating a proxy design pattern 2200 according to an implementation form. The proxy design pattern 2200 is an implementation of the proxy design pattern as described above with respect to Fig. 16 a).

The key idea of proxy design pattern 2200 is to regard symbol (Sym) objects as proxy objects for corresponding node objects.

The proxy 2205 is a class functioning as an interface to a subject "RealSubject" 2207. The client 2201 does not have to directly access the subject 2207. Instead, the client 2201 calls methods of the proxy 2207 which delegate the calls to the subject "RealSubject" 2207.

Fig. 16 f) shows a schematic diagram illustrating an application of the proxy design pattern 2200 of Fig. 16 e) to array nodes 2307 and symbols 2305 according to an implementation form.

The proxy "ArraySym<T>" 2305 is functioning as an interface to the subject

"ArrayNode<T>" 2307. The client 2301 does not have to directly access the subject "ArrayNode<T>" 2307. Instead, the client 2301 calls methods of the proxy "ArraySym<T>" 2305 which delegate the calls to the subject "ArrayNode<T>" 2307.

Fig. 16 g) shows a listing of a source code 2400 illustrating generalized classes of a graph data structure according to an implementation form. The graph data structure is an implementation of the graph data structure as described above with respect to Fig. 16 a).

Interfaces and classes of graph data structure are generalized by introducing type parameters and making classes generic. For each class of nodes that implements some factory interface a class of symbols is defined that implements the same interface. This can be seen from Fig. 16 f) where class "ArrayNode" 2401 implements factory interface "Array" 2403 and class "ArraySym" 2405 implements the same factory interface "Array" 2403. By using that design, symbols which are objects of the class "Sym<T>" 2407 are used as typed proxies to corresponding nodes. That design allows calling factory methods as described above with respect to Figures 16 b) and 16 c) of nodes using instances of symbols, so that when a method of a symbol is called, e.g. by using "arr.length()" of Fig. 16 h) described below, then the corresponding method of the node is executed.

Note that no concrete mechanism is specified to implement a proxy pattern. Any implementation is relevant and can be used.

Fig. 16 h) shows a listing of a source code 2500 illustrating a staged evaluation method according to an implementation form. The staged evaluation method is an implementation of the method 800 for constructing a graph as described above with respect to Fig. 16 a).

The listing of the source code 2500 is obtained by generalizing a graph construction code from explicit graph construction by applying a "staged evaluation" method to the graph construction. Fig. 16 h) shows implementation using an "Array" class as an example but the method can be applied to any class.

The code shown in Fig. 16 h) is executed as described in the following. When the function average is called in line 1 , the parameter "arr" contains a symbol of type "ArraySym<T>" which is a proxy of a node of type "ArrayNode<T>" for some type "T". Note that "T" is a type parameter so the function is generic.

In line 2, the method "sum()" of the class "ArraySym<T>" is invoked. This invocation is delegated to the corresponding array node. For example, if T=Float, i.e. type "T" is of type floating-point, then delegation is performed to method "sum()" of class "FloatArray" which creates a new node of the graph and returns its symbol. This symbol is returned as proxy method call and stored in the variable "sum".

In line 3, the statement is executed as described in line 2 only instead of method "sum()" the method "length()" is called and the result is stored in a variable "len". In line 4, a division operation is performed. Because this is a staged version of the original program, the original operation 7' is replaced with a method invocation of a special object. Here, this object is represented by the variable "div". Note, that this object has a parameterized type. Application of the method of the class "DivOp<T>" that is called here creates a new node of the graph of type "FloatDiv" if type "T" is of type "Float". The method uses the symbols "sum" and "len" to connect this new node with the graph. As described above, "FloatDiv" is a class that represents the division ('/') operation of the source program in the graph based IR. When the method average is completed in line 5, the result is a symbol returned by the method "apply". Here, the graph is extended with new nodes as side effect of executing both, the average function and also all its statements.

Fig. 16 i) shows a listing of program code 2600 representing core methods for

constructing a graph data structure according to an implementation form. The graph data structure is an implementation of the graph data structure as described above with respect to Fig. 16 a).

The graph or graph data structure "Graph" 2601 comprises a lookup table "Hashtable" 2603 for storing all nodes of the graph 2601. The graph 2601 comprises a proxy symbol creator "createProxySym" 2605 for creating a proxy symbol for the node. An

implementation of these methods can use any existing method to implement proxy design pattern, i.e. also other methods not specified in this description. The graph 2601 comprises a finding node operator "findNode" 2607 for finding a node in the graph 2601. The graph 2601 comprises an adding operator "addNode" 2609 for adding a node to this graph 2601. The graph 2601 comprises a finding symbol operator "toSymbol" 261 1 for finding a symbol of a node in the graph 2601 . The finding symbol operator "toSymbol" 261 1 either finds the symbol of the node if it is in the graph 2601 or it adds the node to the graph 2601. The graph 2601 further comprises a lookup operator "getNode" 2613 for looking up a node by its symbol.

The staged evaluator 905 depicted in Fig. 9 may implement the techniques for staged evaluation as described above with respect to Figs. 16 a) to 16 i).

Fig. 16 j) shows a staged evaluation apparatus 2700 for compiling source code 2702 into executable machine code according to an implementation form. The machine code is configured to run on a processor of a computer system. The apparatus 2700 comprises construction means 2701 for receiving the source code 2702 and providing an

intermediate representation of the source code.

The construction means 2701 are configured for constructing a graph data structure as an intermediate representation of the source code 2702. The program operations of the source code 2702 are represented in an object-oriented programming language by objects of classes that form a hierarchy growing from a base node class of the graph data structure. The construction means 2701 comprises production means 2703 and proxy means 2705.

The production means 2703 are configured for producing new nodes of the graph data structure by calling factory methods associated with existing nodes of the graph data structure based on a factory method design pattern implemented in the nodes of the graph data structure. The nodes of the graph data structure are identified by symbols. The proxy means 2705 are configured for using the symbols as proxies of the nodes of the graph data structure according to a proxy design pattern.

In an implementation form, the apparatus 2700 further comprises optimization means configured for optimizing the intermediate representation 2704. In an implementation form, the apparatus 2700 further comprises generation means configured for generating the executable machine code.

The construction means 2701 may be used for an improved construction of the

intermediate representation. The optimization means may be used for optimizing the intermediate representation. The generation means may be used for generating the executable machine code. In an implementation, the apparatus 2700 is applied in a compiler as described above with respect to Fig. 2, in particular in a domain specific specializer as described above with respect to Figs. 8 and 9.

The apparatus 2700 may be used for implementing the method 1800 as described above with respect to Fig. 16 a). The apparatus 2700 may be part of a Domain Specific

Specializer as described above with respect to Figs. 2, 8 and 9. The staged evaluator 905 depicted in Fig. 9 may include the apparatus 2700.

The methods, systems and devices described herein may be implemented as software in a Digital Signal Processor (DSP), in a micro-controller or in any other side-processor or as hardware circuit within an application specific integrated circuit (ASIC) of a Digital Signal Processor (DSP).

The invention can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations thereof, e.g. in available hardware of conventional optical transceiver devices or in new hardware dedicated for processing the methods described herein. The present disclosure also supports a computer program product including computer executable code or computer executable instructions that, when executed, causes at least one computer to execute the performing and computing steps described herein, in particular the method 1500 as described above with respect to Fig. 15 and the techniques described above with respect to Figs. 2 to 14. Such a computer program product may include a readable storage medium storing program code thereon for use by a computer, the program code may perform the method 1500 as described above with respect to Fig. 15. While a particular feature or aspect of the disclosure may have been disclosed with respect to only one of several implementations, such feature or aspect may be combined with one or more other features or aspects of the other implementations as may be desired and advantageous for any given or particular application. Furthermore, to the extent that the terms "include", "have", "with", or other variants thereof are used in either the detailed description or the claims, such terms are intended to be inclusive in a manner similar to the term "comprise". Also, the terms "exemplary", "for example" and "e.g." are merely meant as an example, rather than the best or optimal.

Although specific aspects have been illustrated and described herein, it will be

appreciated by those of ordinary skill in the art that a variety of alternate and/or equivalent implementations may be substituted for the specific aspects shown and described without departing from the scope of the present disclosure. This application is intended to cover any adaptations or variations of the specific aspects discussed herein. Although the elements in the following claims are recited in a particular sequence with corresponding labeling, unless the claim recitations otherwise imply a particular sequence for implementing some or all of those elements, those elements are not necessarily intended to be limited to being implemented in that particular sequence. Many alternatives, modifications, and variations will be apparent to those skilled in the art in light of the above teachings. Of course, those skilled in the art readily recognize that there are numerous applications of the invention beyond those described herein. While the present inventions has been described with reference to one or more particular embodiments, those skilled in the art recognize that many changes may be made thereto without departing from the scope of the present invention. It is therefore to be understood that within the scope of the appended claims and their equivalents, the invention may be practiced otherwise than as specifically described herein.