Interpretation

Compile time computations

Interpretation is a compiler's mode reserved to evaluate, expand and simplify parts of a given program based on information available in this mode. On the other hand, Interpretation is a middle man, or an intermediate level, between the Transcend and Brute levels, as it facilitates communication between those by means of interpreting data of respective layers. It can be further divided into Upper and Lower Interpretations depending on the interaction with the layer we are focused on at the moment.

main= function::    int; entry
{
  x= "a"::          string.

  y= if (x=="b")::  string; i12n(on)
      {1} else {0}.
  y
}

In this example, the identifier y has an attached annotation i12(on) which indicates that the compiler should use compile-time interpretation to evaluate y. Once the simplification process is over, the function returns 0, with neither memory allocations for the string variable x nor any computation at runtime.

There are two annotations reserved to control the interpretation process:

• i12n(on) Forces compiler to interpret the annotated expression, function, or function argument. It yields error if the expression is impossible to interpret.
• i12n(off) Disables interpretation for the annotated expression.

Eligible Expressions

Currently the compiler is able to interpret the following expressions:

• Atomic instructions: numbers, strings, identifiers.
• Relational and logic operators e.g. x==true, x!=0.
• if, switch statements. Statement expansion allowed.
• Loop statements. Statement expansion allowed.
• Functions. Function calls, Partial function call interpretation.
• Index operator e.g. x = {1, 2, 3}. y = x[0], info = {planet="Earth"}. x = info["planet"].
• List operators e.g. x = [1..10]. y={"day", "night"}.

Function Interpretation

The whole function body may be subject to interpretation if it consists of interpretable expressions only.

unwrap = function(data::unknType, keys::unknType)::   unknType; i12n(on)
{
  loop fold(keys->key::string, data->record)::        unknType
  {
    record[key]
  }
}

test = function::                                     bool; entry
{
  book = unwrap({
    Library = {
      Shelf = {
        Book = "Aristotle's Politics"
    }}}, {"Library", "Shelf", "Book"})::              unknType.

  book == "Aristotle's Politics"
}

The above example demonstrates the unwrap function which is intended to be fully interpretable, as indicated by the function header's annotation. Obviously, the interpretable function requires that all its arguments are also interpretable. In this case the compiler is able to calculate the function's result at compile time with no byte code produced. Here is what the compiled code looks like (which will be also optimized out during the consequent compilation phases):

test = function::                                       bool; entry
{
    book = "Aristotle's Politics"::                     string; i12n(on).
    book == "Aristotle's Politics"
}

The example also reveals a number of similarities with dynamically typed programming languages:

• Relaxed types. Notice unknType type which has not been defined. It's interpreted well because the compiler completely ignores the type system since everything can be checked at compile time anyway. The Interpretation mode is exactly the level where the relaxed type system is possible without any performance penalties or safety concerns.
• Introspection abilities. Notice how it is allowed to treat list fields as string keys, so functions like unwrap can get list field name as a parameter. Possible errors, such as the list not having the requested field are easily spotted by the compiler during interpretation and there are no concealed runtime bugs. In a sense, it is a fair trade off between introspection expressiveness and possible compilation errors.

In simple cases interpretation analysis could determine that a function is subject to interpretation with no annotation hints provided.

unwrap = function(data::unknType, keys::unknType)::   unknType
{
  loop fold(keys->key::string, data->record)::        unknType
  {
    record[key]
  }
}

test = function::                                     bool; entry
{
  book = unwrap({
    Library = {
      Shelf = {
        Book = "Aristotle's Politics"
    }}}, {"Library", "Shelf", "Book"})::              unknType; i12n(on).

  book == "Aristotle's Politics"
}

The only difference from the example above is the lack of annotation hint for unwrap. It can be seen that interpretation of the variable book is required which in its turn depends on unwrap. In this case analysis is capable enough to determine that unwrap is indeed possible to interpret, so no errors occur.

There are, however, more complicated cases for interpretation analysis:

• Direct recursion. Interpretation analysis is able to correctly determine whether a function involving direct recursion (where the function calls itself) is subject to interpretation or not.
• Indirect recursion. Currently, when processing the indirect recursion (where a function is called not by itself but rather by another function), the analysis usually fails and relies on manually provided annotation hints.

Below is an example of a direct recursion:

unwrap = function(data:: X)::       bool 
{
  if (data[0] == "the-end")::       bool 
    {true} else {unwrap(data[0])}
}

entry = function::                  bool; entry 
{
  unwrap({{{{"the-end"}}}})::       bool; i12n(on)
}

Function unwrap unwraps the nested list until the desired value is found. No function level annotation is required.

Late Interpretation or Expansion

Late Interpretation can be conceptualized as a partial expansion, i.e. a simplification or elimination of interpretable parts of certain statements.

test = function(x:: int)::  int; entry 
{
  comm= "inc"::             string; i12n(on).

  y= if (comm == "inc")::   int
    {x + 1} else {x}.
  y
}

In this example, computation of y depends on comm and x. On the one hand, comm has an annotation that requires interpretation, while on the other hand x is unknown at the compile-time and thus cannot be interpreted. In this case the only way to satisfy contradictory requirements is to expand the if statement, since it is only possible to interpret condition part of the statement, leaving conditional blocks unchanged. In other words, the if statement is expanded which results in only one of the child blocks being compiled, x+1 in this example, based on already known fact that the else block would never be executed.

Due to the fact that expansion, as opposed to "pure interpretation", leaves some portion of the code for subsequent compilation it can also be called late interpretation for the result depends on runtime information and has memory and performance footprint.

Below is a more complex example of a loop expansion:

main = function(x:: int)::                        int; entry 
{
  commands = {"inc", "double", "dec"}::           [string]; i12n(on).

  loop fold(commands->comm::string, x->operand):: int
  {
    switch(comm)::                                int
    case ("inc")    {operand + 1}
    case ("dec")    {operand - 1}
    case ("double") {operand * 2}
  }
}

Identifier commands contains a list of operations that need to be interpreted as indicated by the corresponding annotation. Operand x is assigned at runtime. This is the same situation as in previous example, and it triggers expansion as expected. The result after expansion looks as follows:

main = function(x:: int):: int; entry 
{
  x{1} = x + 1::           int. 
  x{2} = x{1} * 2::        int.
  x{3} = x{2} * 1::        int.
  x{3}
}

In other words, this mimics the well known loop unrolling technique by putting several copies of the loop body in a row, each one for every item in the list commands.

As of now, the following statements support late interpretation:

• Branching statements: if, switch, switch variant, switch late.
• Loop statements: loop fold.
• Functions.
• Other operators: query late.

Partial or Late Function Interpretation

Xreate supports cases where a function has mixed arguments in terms of interpretation, some of which need to be interpreted, while others need to be compiled.

evaluate= function(argument:: num, code:: string; i12n(on))::  num 
{
  switch(code)::                                               num
  case ("inc")    {argument + 1}
  case ("dec")    {argument - 1}
  case ("double") {argument * 2}
  case default    {argument}
}

main = function(init::int)::                          int; entry 
{
  commands= {"inc", "double", "dec"}::                [string]; i12n(on).

  loop fold(commands->comm::string, init->operand)::  int
  {
      evaluate(operand, comm)
  }
}

Looking at the function evaluate's signature in this example we can see only one argument code that requires interpretation. This means that the function evaluate is subject to a partial interpretation or, in other words, late function interpretation.

In general, to enable late interpretation for a function, at least one of its arguments should be annotated as i12n(on). What compiler does next is to generate a number of distinctive function specializations. Each unique combination of interpretable argument values corresponds to its own function specialization. This should be used with cautiousness, since compiler can generate large amounts of code in some cases.

Based on the above example, three different evaluate specializations are generated as follows:

main= function(init::int)::           int; entry 
{
  operand = init::                    int.
  
  operand{1} = evaluate1(operand)::   int.
  operand{2} = evaluate2(operand{1})::int.
  operand{3} = evaluate3(operand{2})::int.
  
  operand(3)
}

Queries

• predicate Denotes a Transcend predicate.

Represents the value of the Transcend predicate predicate in the format as follows:

• If a predicate has only one argument, returns a list of elements of an appropriate type: int, string, variant or tuple.
• in case of several arguments, the arguments comprise a record. The function returns a list of records.
• Predicates correspond to variants.

Interpretation can be viewed as the middle ground between high level Transcend and low level Brute. In essence, the principal role of Interpretation is to serve as a link between them by interpreting data for Brute from Transcend. The special built-in function intrinsic query is provided to query data from Transcend allowing to process it further.

As a short example, assume that we have Transcend facts as follows:

person("Ben").

This data can be queried as below:

Persons = type [string].      //we expect a list of strings
persons = function::          Persons 
{
  intrinsic query("person"):: Persons
}

The persons function in this example returns a list of persons supplied by Transcend. The example can be slightly rewritten using slave types which are reserved to automatically identify an appropriate type for the returned value. The next excerpt is equivalent to the previous one:

Person = type slave person.   //equivalent to string
Persons = type [Person]

persons = function::          Persons 
{
  intrinsic query("person"):: Persons
}

Querying Example: GUI

Querying allows to use powerful Transcend capabilities to solve convoluted problems, consequently retrieving reasoning solutions by Brute for efficient processing. Consider a more complicated example dealing with a GUI.

First, let us start off defining more or less semantically an application's GUI on the Transcend level:

%Layout consists of two blocks:
block(my_content; my_nav).

%Assign roles to the blocks:
role(my_content, body).
role(my_nav, navigation).

%Navigation block can be in either an iconized or expanded form:
form(none; expanded; iconized).
allowed_form(my_nav, (expanded; iconized)).

%Visual theme:
background(my_content, color(blue)).
background(my_nav, color(grey)).

Above we have described GUI consisting of two blocks: main content and navigation blocks. The same application can look differently depending on a platform's or viewport properties. Let us define a platform:

% The height is greater than the viewport's width:
orientation(portrait).

Having an application's semantic description as well as a platform's description we can now combine them using additional rules to produce the final result: how the application should look like on the given platform.

% Portrait orientation rules:

%Determine appopriate navigation list's form:
form(Nav, iconized):-
  orientation(portrait);
  allowed_form(Nav, iconized);
  role(Nav, navigation).

%Determine blocks' layout:
align(Nav, bottom_of(Body)):-
  orientation(portrait);
  role(Nav, navigation);
  role(Body, body).

% Landscape orientation rules:  
form(Nav, expanded):-
  orientation(landscape);
  allowed_form(Nav, expanded);
  role(Nav, navigation).
  
align(Nav, left_of(Body)):-
  orientation(landscape);
  role(Nav, navigation);
  role(Body, body).

In short, the rules above read that we place the expanded navigation block my_nav and the content block my_content in a row for wide displays; conversely, my_content and iconized my_nav on top of each other for narrow displays.

After Transcend has decided actual forms and blocks alignment, the next step is to retrieve solutions denoted by the align and form predicates and to actually draw GUI elements:

//Define types: 
Block = type slave block.
Role = type variant {body, navigation}.
Alignment = type variant{
  bottom_of(ref :: Block), 
  left_of(ref :: Block)
}.
Layout = type {Role, Alignment}.

//Determine role and form:
drawBlock = function(block:: Block)::        Drawing
{
  forms = intrinsic query ("form")::         [Form].
  formCurrent = getBlockForm(forms, block):: Form.
  
  roles = intrinsic query ("role")::         [Role].
  roleCurrent = getBlockRole(block)::        Role.
  
  switch variant (roleCurrent)::             Drawing
  case (body) 
    {drawBody(formCurrent)}
    
  case (navigation) 
    {drawNavigation(formCurrent)}
}

//Determine layout
draw = function::                        Drawing; entry 
{
  layout = intrinsic query ("layout")::  Layout.
  blockA = layout[0]::                   Block.

  switch variant (layout[1]->blockB)::   Drawing
  case (bottom_of) 
    {drawVerical(blockA, blockB["ref"])}
    
  case (left_of)   
    {drawHorizontal(blockA, blockB["ref"])}
}

Notice that the draw and drawBlock functions work with compile time data from Transcend, thus all this code after interpretation gets simplified into the following:

drawVertical(drawBody(none()), drawNavigation(iconized())).

The example above demonstrates the possibility to delegate to Transcend intelligent tasks, such as adapting a GUI to a particular platform, and leaving Brute with efficient implementation matters.

Domain Specific Languages and Interpretation

DSL is an idea of expressing various concepts in a lapidary and concise form. Xreate recognizes and acknowledges very successful and beneficial DSL usage in certain areas, primarily to express queries and configs, to name a few. It is possible to use interpretation abilities to emulate DSL. Developer can express the desired functionality in the form of nested lists of numbers, variants and strings which are then processed by a partially interpreted function. Such function in its turn transforms the input data into a set of low level compilation instructions so there is no runtime overhead.

On Interpretation Analysis

Analysis follows classical type reconstruction algorithms to determine which expressions are subject to interpretation and check the correctness of reconstruction w.r.t. developer-provided annotations. Analysis consists of two general parts:

• Inference. Infers if it is possible to interpret an expression based on its already inferred argument's decisions.
• Unification. Assigns an appropriate decision w.r.t. previously inferred expectations and developer-provided hints as well.