Files F4002311

interpretation.xml
No OneTemporary
Actions

File Metadata

Created
Thu, Jul 9, 7:21 AM

interpretation.xml
View Options

<?xml version="1.0" encoding="UTF-8"?>
<chapter version="5.1" xmlns="http://docbook.org/ns/docbook"
xmlns:xlink="http://www.w3.org/1999/xlink"
xmlns:xila="http://www.w3.org/2001/XInclude/local-attributes"
xmlns:xi="http://www.w3.org/2001/XInclude"
xmlns:trans="http://docbook.org/ns/transclusion"
xmlns:svg="http://www.w3.org/2000/svg"
xmlns:m="http://www.w3.org/1998/Math/MathML"
xmlns:html="http://www.w3.org/1999/xhtml"
xmlns:db="http://docbook.org/ns/docbook">
<title>Interpretation</title>
<para>Interpretation is mode in which Xreate <emphasis>interprets</emphasis>
given program i.e. evaluates, expands and simplifies parts of program based
on information if any known at compilation time. On another hand,
Interpretation is a middle man or intermediate level between Transcend and
Brute levels, it facilitates communication between them by means of
interpreting data of respective layers. It can be further divided into Upper
and Lower Interpretations depending on interacting with which layer we are
focused at the moment.</para>
<programlisting>main= function:: int; entry
{
x= "a"::string.
y= if (x=="b")::string; i12n(on)
{1} else {0}.
y
}
</programlisting>
<para>In this example, identifier <code>y</code> has annotation
<code>i12(on)</code> which indicates that compiler should use compile-time
interpretation to evaluate <code>y</code>. After simplification, the
function's result is <code>0</code> with neither memory allocations for
string variable <code>x</code> nor any computation at runtime.</para>
<para>There are two annotations reserved to control interpretation
process:</para>
<itemizedlist>
<listitem>
<para><code>i12n(on)</code> Forces compiler to interpret annotated
expression, function, function argument. It yields error if expression
impossible to interpret</para>
</listitem>
<listitem>
<para><code>i12n(off)</code> Disables interpretation for annotated
expression</para>
</listitem>
</itemizedlist>
<section>
<title>Eligible Expressions</title>
<para>Currently compiler able to interpret following expressions:</para>
<itemizedlist>
<listitem>
<para>Atomic instructions: numbers, strings, identifiers</para>
</listitem>
<listitem>
<para>Relational and logic operators e.g. <code>x==true</code>,
<code>x!=0</code></para>
</listitem>
<listitem>
<para><code>if</code>, <code>switch</code> statements.
[[#expansion|Statement expansion]] allowed</para>
</listitem>
<listitem>
<para>loop statements. [[#expansion|Statement expansion]]
allowed</para>
</listitem>
<listitem>
<para>Functions. [[#function-call-interpreta|Function calls]],
[[#partial-function|Partial function call interpretation]]</para>
</listitem>
<listitem>
<para>index operator e.g. <code>x= {1, 2, 3}. y= x[0]</code>,
<code>info= {planet="Earth"}. x= info["planet"].</code></para>
</listitem>
<listitem>
<para>list operators e.g. <code>x= [1..10]. y={"day",
"night"}.</code></para>
</listitem>
</itemizedlist>
</section>
<section>
<title>Function Interpretation</title>
<para>Whole function body could be subject to interpretation if it only
consists of interpretable expressions.</para>
<programlisting>unwrap = function(data::unknType, keys::unknType):: unknType; i12n(on)
{
loop fold(keys-&gt;key::string, data-&gt;record):: unknType
{
record[key]
}
}
test = function:: bool; entry
{
book = unwrap({
Library = {
Shelf = {
Book = "Aristotle's Politics"
}}}, {"Library", "Shelf", "Book"}):: unknType.
book == "Aristotle's Politics"
}
</programlisting>
<para>The example demonstrates function <code>unwrap</code> which is
intended to be fully interpretable as depicted by function header
annotation. Obviously, the interpretable function requires all its
arguments be also interpretable. In this case compiler able to calculate
function's result at compile time and nothing of function's body goes to
compiled code. Compiled code looks like(which also optimized out during
consequent compilation phases):</para>
<programlisting>test = function:: bool; entry
{
book = "Aristotle's Politics":: string.
book == "Aristotle's Politics"
}</programlisting>
<para>The example also reveals number of similarities with a dynamically
typed programming languages:</para>
<itemizedlist>
<listitem>
<para><emphasis>Relaxed types</emphasis>. Notice <code>unknType</code>
type which has not been defined. It's interpreted well because
compiler does not look at type system at all since everything can be
checked at compile time anyway. Interpretation mode is exactly level
where relaxed type system is possible without any penalties during
runtime.</para>
</listitem>
<listitem>
<para><emphasis>Introspection abilities</emphasis>. Notice how it's
allowed to treat list fields as string keys, so functions like
<code>unwrap</code> can get list field name as a parameter. If list
does not have requested field it just leads to a compilation error and
no hard to catch runtime bugs.</para>
</listitem>
</itemizedlist>
<note>
<para>Additional reason for an arbitrary undefined type
<code>unknType</code> being used in the example is to ensure that no
compilation occurs and everything done on purely interpretation
level</para>
</note>
<para>In simple cases Interpretation Analysis could determine that
function is subject to interpretation with no annotation hints
provided.</para>
<programlisting> unwrap = function(data::unknType, keys::unknType):: unknType
{
loop fold(keys-&gt;key::string, data-&gt;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"
}
</programlisting>
<para>The only difference from example above is lack of annotation hint
for <code>unwrap</code>. Developer requires interpretation of
<code>book</code> variable which in its turn depends on
<code>unwrap</code>. In this case Analysis able to recognize
<code>unwrap</code> is possible to interpret, so no errors occur.</para>
<para>There are, however, more complicated cases for Interpretation
Analysis:</para>
<itemizedlist>
<listitem>
<para>Direct recursion. Interpretation Analysis is able to correctly
find out whether function involving direct recursion(in which a
function calls itself) is subject to interpretation</para>
</listitem>
<listitem>
<para>Indirect recursion. As of now for processing of indirect
recursion(in which a function is called not by itself but by another
function) analysis usually fails and rely on manually provided
annotation hints</para>
</listitem>
</itemizedlist>
<para>Below is an example of a direct recursion:</para>
<programlisting>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)
}</programlisting>
<para>Function <code>unwrap</code> unwraps nested list until it finds
desired value. No function level annotation required.</para>
</section>
<section>
<title>Expansion or Late Interpretation</title>
<para>Expansion is a partial simplification or elimination of
interpretable parts of certain statements.</para>
<programlisting>test = function(x:: int):: int; entry {
comm= "inc":: string; i12n(on).
y= if (comm == "inc"):: int
{x + 1} else {x}.
y
}
</programlisting>
<para>In this example, computation of <code>y</code> depends on
<code>comm</code> and <code>x</code>. On one side, <code>comm</code> has
an annotation that requires interpretation, on another side <code>x</code>
is unknown at compile-time and can't be interpreted. In this case the only
way to satisfy contradictory requirements is to
<emphasis>expand</emphasis> <code>IF</code> statement, since there is a
possibility to only interpret condition part of the statement, leaving
conditional blocks unchanged. In another words, <code>IF</code> statement
is <emphasis>expanded</emphasis> and just one of the child blocks is
compiled , <code>x+1</code> in this example based on already known fact
that the other block would never be executed.</para>
<para>With regard to the fact that expansion leaves some code for
compilation which has to be executed later as opposed to the "pure
interpretation" it can be also called <emphasis>late
interpretation</emphasis> as having runtime footprint.</para>
<para>Below more complex example of a loop expansion:</para>
<programlisting>main = function(x:: int):: int; entry {
commands = {"inc", "double", "dec"}:: [string]; i12n(on).
loop fold(commands-&gt;comm::string, x-&gt;operand):: int
{
switch(comm):: int
case ("inc") {operand + 1}
case ("dec") {operand - 1}
case ("double") {operand * 2}
}
}
</programlisting>
<para><code>commands</code> contains list of operations that should be
interpreted as indicated by corresponding annotation. Operand
<code>x</code> gets assigned at runtime. This is the same situation as in
previous example and triggers expansion as expected. Result after
expansion looks as follows:</para>
<programlisting>main = function(x:: int):: int; entry {
x{1} = x + 1.
x{2} = x{1} * 2.
x{3} = x{2} - 1.
x{3}
}
</programlisting>
<para>In other words, this mimics well known loop unrolling technique by
putting several copies of the loop body in a row, each one for every item
of a list of `commands`.</para>
<para>As of now follow statements support late interpretation:</para>
<itemizedlist>
<listitem>
<para>Branching statements: <code>if</code>, <code>switch</code>,
<code>switch variant</code>, <code>switch late</code></para>
</listitem>
<listitem>
<para>Loop statements: <code>loop fold</code></para>
</listitem>
<listitem>
<para>functions</para>
</listitem>
<listitem>
<para>Other operators: <code>query late</code></para>
</listitem>
</itemizedlist>
</section>
<section>
<title>Partial or Late Function Interpretation</title>
<para>Xreate supports case when function has mixed arguments in regard to
interpretation, some should be interpreted, while others -
compiled.</para>
<programlisting>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-&gt;comm::string, init-&gt;operand):: int
{
evaluate(operand, comm)
}
}
</programlisting>
<para>Looking at function <code>evaluate</code>'s signature in this
example we can see only one argument <code>code</code> requires
interpretation. This means that function <code>evaluate</code> is subject
to a partial interpretation or in other words <emphasis>late function
interpretation</emphasis>. To enable late interpretation for function at
least one of its arguments should be annotated as <code>i12n(on)</code>.
What compiler does next is to generate number of distinctive
<emphasis>function specializations</emphasis>. Each unique combination of
interpretable argument values corresponds to its own function
specialization. This should be used with cautiousness for compiler can
generate a lot of code for some cases.</para>
<para>Example above generates three different <code>evaluate</code>
specializations as follows</para>
<programlisting>evaluate1= function(argument:: num):: num {
argument + 1
}
evaluate2= function(argument:: num):: num {
argument * 2
}
evaluate3= function(argument:: num):: num {
argument - 1
}
main= function(init::int):: int; entry {
operand= init:: int.
operand{1}= evaluate1(operand).
operand{2}= evaluate2(operand(1)).
operand{3}= evaluate3(operand(2)).
operand(3)
}
</programlisting>
</section>
<section>
<title>Domain Specific Languages and Interpretation</title>
<para>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
<emphasis>queries</emphasis> and <emphasis>configs</emphasis>, to name a
few. It is possible to use interpretation abilities to emulate DSL.
Developer can express desired functionality as a nested lists of numbers,
variants and strings which then processed by partially interpreted
function. Such function in its turn transforms input data into set of low
level compilation instructions so there is no runtime overhead.</para>
</section>
<section>
<title>On Interpretation Analysis</title>
<para>Analysis follows classical type reconstruction algorithms to
determine which expressions are subject to an interpretation and check
correctness of reconstruction w.r.t. developer-provided annotations.
Analysis consists of two general parts:</para>
<itemizedlist>
<listitem>
<para><emphasis>Inference</emphasis>. Infers is it possible to
interpret expression based on known decisions for its arguments</para>
</listitem>
<listitem>
<para><emphasis>Unification</emphasis>. Assigns appropriate decision
w.r.t. to a previously inferred expectations and developer-provided
hints as well</para>
</listitem>
</itemizedlist>
</section>
</chapter>

Event Timeline

Email: pr.h7@xreate.org · 2019 Xreate.org · Powered by Phabricator