NRRS
Non-Restrictive Reflective System

Description

nitrO is a non-restrictive reflective system in which it is possible to change every feature of its programming languages and applications at runtime, without any kind of restriction imposed by an interpreter protocol. Any programming language can be used, and every application is capable of adapting another one’s features, no matter whether they use the same programming languages or not.

Categorizing Reflection

Two main criteria are commonly identified to categorize reflective systems. These are when reflection takes place and what may be reflected. If we take what may be reflected as a criterion, it can be distinguished:

  • Introspection: The system structure can be accessed but not modified. If we take Java as an example, with its java.lang.reflect package, we can get information about classes, objets, methods and fields at runtime.

  • Structural Reflection: The system structure can be dynamically modified. An example of this kind of reflection is the addition of object's fields.

  • Computational (Behavioral) Reflection: The system semantics (behavior) can be modified. In the standard Java API v.1.3, the class java.lang.reflect.Proxy has been added; it can be used to modify the dispatching method mechanism, being handled by a proxy object.

  • A reflective programming language can be capable of changing itself, i.e. changing its own lexical or syntactical specification; that is what we call Linguistic Reflection. As an example, with OpenJava reflective language, the own language can be enhanced to be adapted to specific design patterns.

Taking when reflection takes place as the classification criterion, we have:

  • Compile-time Reflection: The system customization takes place at compile-time (e.g., OpenJava). These system benefits are runtime performance and the ability to adapt its own language (i.e., linguistic reflection).

  • Runtime Reflection: The system may be adapted at runtime, once it has been created and run (e.g., metaXa, formerly called MetaJava). These systems have greater adaptability but performance penalties. Computational reflective systems are commonly implemented by using runtime reflection by they lack linguistic reflection capabilities.

nitrO achieves computational and linguistic reflection at runtime. Moreover, our reflection technique implementation is more flexible than common runtime reflective systems –as we will explain in the next paragraph. Performance drawbacks are not being considered in our first prototypes.

Meta-object Protocols Restrictions

Most runtime reflective systems are based on Meta-Object Protocols (MOPs); a MOP specifies the implementation of a reflective object-model. An application is implemented by means of a programming language (base level). A program's meta-level is the implementation of the computational object model supported by the programming language. Therefore, a MOP specifies the way a base-level application may access its meta-level in order to adapt its behavior at runtime.

The way a MOP is defined restricts the amount of features that may be customized. If we do not consider a system feature to be adaptable by the MOP, this program attribute will not be able to be customized once the application will be running.

nitrO runtime reflection mechanism is based on a meta-language specification. The way the base level access to the meta-level (reification) is not defined by a MOP; it is specified by another language (meta-language). The meta-language is capable to adapt the structure, behavior and linguistic features of the base level system at runtime.

Python's Reflective Capabilities

We have selected the Python programming language to develop our system because of its reflective capabilities:

  • Introspection. At runtime, any object may inspect its attributes, class and its inheritance graph. It may also be inspected the application's dynamic symbol table: the existing modules, classes, objects and variables at runtime.

  • Structural Reflection. It is possible to modify the set of methods a class offers and the set of field an object has. We can also modify the class an object is instance of, and the set of super-classes a class inherits from.

  • Dynamic evaluation of code represented as strings. Python offers the "exec" function that evaluates a string as a set of statements. This feature can be used to evaluate code generated at runtime.

System Architecture

The theoretical definition of reflection uses the notion of a reflective tower: we have a tower in which an interpreter, that defines its operational semantics, is running the user program. A reflective computation is a computation about the computation, i.e. a computation that accesses the interpreter.

If the application would be able to access its interpreter at runtime, it would be able to inspect the existing system's objects (introspection), modify its structure (structural reflection) and customize its language specification (computational and linguistic reflection).

However, this mechanism is complicate to implement. Interpreters commonly have complex structures representing different functionality like parsing mechanism, semantics interpretation, and runtime user-application representation. For instance, modifying by error the parsing mechanism would involve unexpected results.

What we have developed is a generic interpreter that separates the structures accessible by the base level from the fixed mechanism that should never be modified. This generic interpreter is language-independent: its inputs are both the user application and the language specification. It is capable of interpreting any programming language by reading its specification.

System Architecture.

Figure 1. System Architecture.

At runtime, any application may access its language specification (or another one's language) by using the whole expressiveness of the Python programming language; there are no previous restrictions imposed by a protocol –any feature can be adapted. Changes performed are automatically reflected on the application execution, because the generic interpreter relies on the language specification while the application is running.

System Design

In Figure 2, we show how the generic interpreter, every time an application is running, offers two sets of objects to the reflective system: the first one is the language specification represented as a graph of objects (we will explain its structure in the next section); the second group of objects is the application's runtime symbol table: variables, objects and classes created by the user.

Dynamic application and language adaptation.

Figure 2. Dynamic application and language adaptation.

Any application may access and modify these object structures by using the Python programming language; its reflective features will be used to:

  1. If an application symbol table is inspected, introspection between different applications (independently of the language used) is achieved.
  2. Modifying the symbol table structure, by means of Python structural reflection capabilities, implies structural reflection of any running application.
  3. Adapting the language semantics located in the language specification, the running application may customize its behavior: computational reflection.
  4. Modifying the lexical and syntactic specification of the programming language involves linguistic reflection.

The main question of this design is how the application computational environment may access and modify the interpreter computational environment –i.e., different language specifications and application's symbol tables.

Every language in our system includes the "reify" statement; the generic interpreter automatically recognizes it, no matter the language being used. Inside the reify statement we can write Python code. Independently of the programming language selected, every time the interpreter recognizes a reify statement, he takes its Python code and evaluates it by invoking the "exec" function. This Python code, using Python structural reflection, may access and modify application's symbol tables and language specifications. This scheme is shown in the next figure:

Real computational-environment jump achieved.

Figure 3. Real computational-environment jump achieved.

The code written inside a reify statement is evaluated in the interpreter computing environment, not in the application computing environment –the place where it was written. So, Python becomes a meta-language to specify, and dynamically modify, any language and application that would be running in our system; no MOP specifying previously what may be changed has to be defined.

Language and Application Description

As we have seen in the previous section, applications in our system may dynamically access language specifications and application symbol tables in order to achieve different levels of reflection. What we present in this point is how languages and applications are represented by means of objects structures.

Programming languages are specified with metalanguage files. Their lexical and syntactic features are expressed by means of context-free grammar rules; their semantics, by means of Python code placed at the end of each rule. This is an example of a very simple language definition:

            Language = VerySimple
            Scanner = {
              "Digit Token"
              digit -> "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
              "Number Token"
               NUMBER -> digit moreDigits ;
              "Zero or more digits token"
              moreDigits -> digit moreDigits
                | ;
              "Characacter Token"
              char -> "a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|
                "m"|"n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"w"|"x"|"y"|"z" ;
              "Character or Digit Token"
              charOrDigit -> char | digit ;
              "ID Token"
              ID -> char moreCharsOrDigits ;
              "Zero or more chars or digits token"
              moreCharsOrDigits -> charOrDigit moreCharsOrDigits
                | ;
              "SEMICOLON Token"
              SEMICOLON -> ";" ;
              "ASSIGN token"
              ASSIGN -> "=" ;
            }
            Parser = {
              "Initial Context-Free Rule"
              S -> statement moreStatements SEMICOLON <#
            global vars
            vars={}
            nodes[1].execute()
            nodes[2].execute()
            #> ;
              "Zero or more Statements"
              moreStatements -> SEMICOLON statement moreStatements <#
            nodes[2].execute()
            nodes[3].execute()
            #>
                | ;
              "Statement"
              statement -> _REIFY_ <#
            nodes[1].execute()
            #>
                | assignment <#
            nodes[1].execute()
            #>
                | expression <#
            nodes[1].execute()
            write("Expression value: "+str(nodes[1].value)+".\n")
            #> ;
              "Assignment Statement"
              assignment -> ID ASSIGN expression <#
            nodes[3].execute()
            vars[nodes[1].text]=nodes[3].value
            #> ;
              "Binary Expression Factor"
              expression -> ID <#
            nodes[0].value=vars[nodes[1].text]
            #>
                | NUMBER <#
            nodes[0].value=int(nodes[1].text)
            #> ;
            }
            Skip={ "\t"; "\n"; " ";}
            NotSkip = { }   
            

The "_REIFY_" reserved word indicates where a reify statement may be syntactically located. Every application must specify its programming language previously to its source code. When the application is about to be executed, its respective language specification file is analyzed and translated into an object representation.

"NonTerminal" objects, symbolizing rule's left non-terminal symbols, represent each language rule. These objects are associated to a group of "Right" objects, which represent the rule's right sides. A "Right" object has two attributes:

  1. Attribute "nodes". Collects "Terminal" and "NonTerminal" objects representing the rule's right side.
  2. Attribute "actions": List of "SemanticAction" objects that stores the Python code located at the end of each rule's description. This code will be executed at the application interpretation.

The next figure shows a fragment of the object diagram representing the example shown above:

Fragment of the object diagram.

Figure 4. Fragment of the object diagram.

Any application code starts with its unique ID followed by its language name. The language may be also specified in the application file, using the metalanguage presented. Therefore, our system will be capable of running these applications whether it has their language specification or not. This is an example application:

                 Application = "Very Simple App"
                 Language = "VerySimple"

                     a=10;
                     b=a;
                     a;
                     b;                    
                    

Once the application's language specification has been translated into its respective object structure, a backtracking algorithm parsers the application's source code creating an abstract syntax tree (AST). Then, the initial non-terminal's code is executed; the tree walking process is defined by the way grammar-symbols "execute" methods are invoked: the non-terminal "execute" method evaluates its associated semantic action. So, the AST and its language specification structure are connected as shown in the next figure:

Application AST and language specification connection.

Figure 5. Application AST and language specification connection.

Interoperability between different applications programmed in different languages is achieved with the nitrO global object. Its attribute "applications" is a hash table of every existing application in the system. Each "Application" object has two attributes:

  1. Attribute "language": Its language specification.
  2. Attribute "applicationGlobalContext": Its dynamic symbol table.

Dynamic Application Adaptation

Accessing the nitrO object attributes, any application can adapt another one's behavior or structure at runtime without any restriction and in a language-independent way. Following the example presented, the next group of reify sentences would dynamically adapt the running application, no matter the program or the language being used.

Our first example shows the existing variables and its values: introspection.

             reify <#
                vars=nitrO.apps["Very Simple App"].applicationGlobalContext["vars"]
                write( str(vars)+"\n" ) # Shows {'b': 10, 'a': 10}
                #>;
                  

Structural reflection means modifying, creating or erasing symbol-table objects:

             reify <#
                vars=nitrO.apps["Very Simple App"].applicationGlobalContext["vars"]
                vars["a"]=vars["a"]*2 # Modifies the structure

                vars["c"]=0 # Creates a new variable
                del vars["b"] # Erases a variable
                #>;
                

We may enhance the assignment statement by showing a trace message every time an assignment takes place: computational reflection.

             reify <#
                from langSpec import SemanticAction
                assignment=nitrO.apps["Very Simple App"].language.syntacticSpec["assignment"]
                code="write(\"Assignment of \""+nodes[1].text;
                code=code+"\" with value \"+str(nodes[3].value)+"\".\\n\")"
                # Behavior adaptation
                assignment.options[0].actions.append(SemanticAction(code))
                #>;
                

Following this scheme, linguistic reflection can be also obtained.

System Benefits

Our reflective system has the following advantages:

  • The whole system is adaptable at runtime. Any system's feature can be changed by means of the reflect statement, and there are no previous restrictions imposed by any protocol.

  • Expressiveness improvement. The way behavior is customized is not restricted to method overriding –as happens with the use of MOPs. We offer a complete language, Python, used to adapt any other language's feature.

  • Language independence. The system may be programmed using any programming language. The inputs to the generic interpreter are both the application source code and the language specification –expressed using a meta-language.

  • What can be reflected. Four levels of reflection are achieved at runtime: introspection, structural reflection, computational reflection, and linguistic reflection.

  • Application interoperability. Any application, whatever its programming language would be, may access, and reflectively modify, any other program being executed. Therefore, there is no need to stop an application in order to adapt it at runtime: another application may be used to customize the former.

The result is a universal computation platform that may be used to develop or test at runtime any reflective or adaptable environment (e.g., fault-tolerant systems, adaptable operating systems, knowledge base systems, etc.) without the necessity to modify the interpreter implementation.

The main disadvantage is runtime performance. Future work will be focused on studying and implementing optimization techniques as just in time compilation or native code generation.