jonathanvdc
/
modelverse
sklonowany z yentl/modelverse


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364
							<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">


<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>Internal workings &#8212; Modelverse 0.4.0 documentation</title>
    
    <link rel="stylesheet" href="_static/classic.css" type="text/css" />
    <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    './',
        VERSION:     '0.4.0',
        COLLAPSE_INDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true
      };
    </script>
    <script type="text/javascript" src="_static/jquery.js"></script>
    <script type="text/javascript" src="_static/underscore.js"></script>
    <script type="text/javascript" src="_static/doctools.js"></script>
    <link rel="top" title="Modelverse 0.4.0 documentation" href="index.html" />
    <link rel="next" title="Models" href="models.html" />
    <link rel="prev" title="Common problems and solutions" href="problems.html" /> 
  </head>
  <body role="document">
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="models.html" title="Models"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="problems.html" title="Common problems and solutions"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="index.html">Modelverse 0.4.0 documentation</a> &#187;</li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <div class="section" id="internal-workings">
<h1>Internal workings<a class="headerlink" href="#internal-workings" title="Permalink to this headline">¶</a></h1>
<p>For more detailed information on the Modelverse specification, which this project is implementing, we refer to the <a class="reference external" href="http://msdl.cs.mcgill.ca/people/yentl/files/Modelverse.pdf">Modelverse Specification</a>.</p>
<p>Information on the implementation can be found below.</p>
<div class="section" id="modelverse-state">
<h2>Modelverse State<a class="headerlink" href="#modelverse-state" title="Permalink to this headline">¶</a></h2>
<p>The Modelverse State is basically just an implementation of a graph library.
As we have a particular kind of graph, this implementation is mostly done by hand at the moment.
The notable exception to this is the RDF backend, proving that other implementations can also be used.</p>
<p>The basic implementation just stores everything as dictionaries.
All operations are then defined by doing operations on these dictionaries.
The most interesting operations here are dictionary operations, which need to traverse these dictionaries in complex ways.
To overcome performance problems for these operations, all results are cached (and validated afterwards).</p>
<div class="section" id="rdf-backend">
<h3>RDF backend<a class="headerlink" href="#rdf-backend" title="Permalink to this headline">¶</a></h3>
<p>The RDF backend requires the <em>rdflib</em> module in Python.
The Modelverse graph is then stored in RDF representation and all operations on it are done using SPARQL queries.
Due to this level of indirection, performance is extremely slow.
To increase performance, we would likely have to make more <em>composite</em> operations, or even group different requests together internally.</p>
</div>
<div class="section" id="status-codes">
<h3>Status codes<a class="headerlink" href="#status-codes" title="Permalink to this headline">¶</a></h3>
<p>The MvS returns, apart from its actual return value, a status code for the request.
This value is not used by the MvK at all, since sometimes a request is expected to give an error (<em>e.g.</em>, checking whether an element is present).
When debugging the MvS, however, these status codes can come in handy.</p>
</div>
</div>
<div class="section" id="modelverse-kernel">
<h2>Modelverse Kernel<a class="headerlink" href="#modelverse-kernel" title="Permalink to this headline">¶</a></h2>
<p>The Modelverse Kernel is basically a graph transformation kernel.
It consists of two parts: a small transformation engine (only a few lines in Python), and a copy of all rules it knows.
Most code is an encoding of these transformation rules, and can (theoretically) be automatically generated by the Modelverse itself.
This is currently not top priority, but will probably be implemented in the future.</p>
<p>The transformation rules are an encoding of the rules presented in the specification mentioned at the top of this page.
In each rule, the MvK needs to have tight communication with the MvS.
For this, the rules are encoded using <em>yield</em> operations in Python.
Rules therefore act as generators, outputting commands to the MvS, and immediately getting a reply.
Each individual yield contains a list of operations to send to the MvS simultaneously.
The result will therefore also be a list of results for each operation.</p>
<p>As you can see in these rules, each entry in the list has a specific form.
An entry is a tuple containing two elements: the code of the operation to execute, followed by a list of all parameters to pass.
The code is a shortened name for the operation, such as <em>CN</em> for <em>create_node</em>.
A full mapping can be found in the MvS, the most important ones are shown below.</p>
<table border="1" class="docutils">
<colgroup>
<col width="20%" />
<col width="80%" />
</colgroup>
<thead valign="bottom">
<tr class="row-odd"><th class="head">Code</th>
<th class="head">Function</th>
</tr>
</thead>
<tbody valign="top">
<tr class="row-even"><td>CN</td>
<td>create_node</td>
</tr>
<tr class="row-odd"><td>CNV</td>
<td>create_nodevalue</td>
</tr>
<tr class="row-even"><td>CE</td>
<td>create_edge</td>
</tr>
<tr class="row-odd"><td>CD</td>
<td>create_dict</td>
</tr>
<tr class="row-even"><td>RV</td>
<td>read_value</td>
</tr>
<tr class="row-odd"><td>RE</td>
<td>read_edge</td>
</tr>
<tr class="row-even"><td>RD</td>
<td>read_dict</td>
</tr>
<tr class="row-odd"><td>RDN</td>
<td>read_dict_node</td>
</tr>
<tr class="row-even"><td>DN</td>
<td>delete_node</td>
</tr>
<tr class="row-odd"><td>DE</td>
<td>delete_edge</td>
</tr>
</tbody>
</table>
<div class="admonition note">
<p class="first admonition-title">Note</p>
<p>Since each yield operation works on lists even a single operation needs to be wrapped in a list.
Worse, however, is that the return value will also be a list.
Instead of having to take the first element each time, Python allows you to write a comma after the variable, to make it expand it automatically.
Your syntax thus becomes:</p>
<div class="highlight-default"><div class="highlight"><pre><span class="n">a</span><span class="p">,</span> <span class="o">=</span> <span class="k">yield</span> <span class="p">[(</span><span class="s">&quot;CN&quot;</span><span class="p">,</span> <span class="p">[])]</span>
</pre></div>
</div>
<p class="last">Where a will now already contain the created node, and not a list with as first (and only) element the created node.</p>
</div>
<div class="section" id="primitives">
<h3>Primitives<a class="headerlink" href="#primitives" title="Permalink to this headline">¶</a></h3>
<p>The Modelverse Kernel also defines the primitives users can use.
Primitives are necessary since we can&#8217;t go deeper at some point.
It is the MvK&#8217;s responsibility to implement each and every primitive defined in the bootstrap file.</p>
<p>Primitives are implemented in the bootstrap file as having a body with an empty node.
When execution goes to this node, the MvK must execute the associated primitive instead.
To do this, the MvK must map all these nodes to their corresponding primitive implementation during startup.</p>
</div>
<div class="section" id="precompiled-functions">
<h3>Precompiled functions<a class="headerlink" href="#precompiled-functions" title="Permalink to this headline">¶</a></h3>
<p>Similar to primitives, the MvK also supports precompiled functions.
A precompiled function is similar to a primitive in terms of implementation, but they do also have an implementation inside of the Modelverse itself.
This means that there are two implementations: one hardcoded, and one in action language.
Both should obviously be consistent.</p>
<p>Whereas primitives are required for a functional Modelverse, precompiled functions are only a performance optimization, and can be disabled by the user for debugging purposes.
This is interesting, since with precompiled functions, no intermediate values will be visible.
Additionally, precompiled functions cannot be changed, as they are Python code instead of being explicitly modelled.</p>
</div>
</div>
<div class="section" id="modelverse-interface">
<h2>Modelverse Interface<a class="headerlink" href="#modelverse-interface" title="Permalink to this headline">¶</a></h2>
<p>Finally, we come to the Modelverse Interface.
For the moment, this is only a simple compiler that takes action language or model language files and translates them to something the Modelverse can understand.
There are basically two kinds of operations the Modelverse can understand: direct graphs, or a list of constructors.
The use of direct graphs is deprecated, as constructors are much more elegant (but slower).
Future changes should make constructors as fast as the use of graphs.
Nonetheless, which approach is used does not matter for the action language or model language files.</p>
<p>The parser used for this simple front-end is the HUTN parser.
It creates an abstract syntax tree, which is then traversed by a series of visitors.
The visitors that are used, depends on the selected mode of compilation.
We briefly present the most important visitors.</p>
<div class="section" id="semantics-visitor">
<h3>Semantics visitor<a class="headerlink" href="#semantics-visitor" title="Permalink to this headline">¶</a></h3>
<p>The visitor most oftenly used is the Semantics visitor.
It traverses the abstract syntax tree and constructs symbol tables and finds all declarations of functions.
Additionally, it also translates the use of operators to their Modelverse functions.</p>
<p>This visitor in itself does not output anything, but it modifies the existing abstract syntax tree.
It is used as a first step for most other visitors.</p>
</div>
<div class="section" id="constructors-visitor">
<h3>Constructors visitor<a class="headerlink" href="#constructors-visitor" title="Permalink to this headline">¶</a></h3>
<p>The most important visitor is the constructors visitor.
It traverses the abstract syntax tree and outputs a list of strings that make it possible for the MvK to construct the required code in the Modelverse.
The use of constructors has several advantages, but the primary advantage is that the interface does not have to know about the internal representation of action language in the Modelverse.
However, the order of constructors and accepted keywords needs to be defined (in action language), and made available to the users.
As this interface is explicitly modelled as well, it is possible for users to modify it without affecting the interface.
This is bad if the interface suddenly accepts new keywords or removes support for old keywords.</p>
<p>During the execution of the visitor, it would already be possible to start transmitting the list to the Modelverse, such that the Modelverse can create the code in parallel with the actual parsing.
While this is possible, we currently split this up in different phases: first the list is generated completely, and then it is transferred to the Modelverse in a single request.</p>
</div>
<div class="section" id="primitives-visitor">
<h3>Primitives visitor<a class="headerlink" href="#primitives-visitor" title="Permalink to this headline">¶</a></h3>
<p>The primitives visitor generates a Modelverse graph directly.
Its use is deprecated, as the constructors are much more elegant.
While direct use of this visitor is not recommended, except for performance reasons, the bootstrap visitor (discussed next) is based on this visitor.</p>
<p>This visitor creates a serialized version of the graph and transmits it to the Modelverse.
The Modelverse has a built-in primitive to decode this graph and store it.</p>
</div>
<div class="section" id="bootstrap-visitor">
<h3>Bootstrap visitor<a class="headerlink" href="#bootstrap-visitor" title="Permalink to this headline">¶</a></h3>
<p>Despite the primitives visitor being deprecated, the bootstrap visitor still needs access to this kind of output, since it cannot use constructors: during bootstrapping, the Modelverse is not yet available.
The actual output format slightly differs from the primitives visitor, but the core concepts are identical.</p>
</div>
<div class="section" id="model-visitor">
<h3>Model visitor<a class="headerlink" href="#model-visitor" title="Permalink to this headline">¶</a></h3>
<p>Finally, the model visitor is similar to the constructor visitor, but goes to a different constructor interface, which supports modelling operations instead of action language operations.
This is a very preliminary visitor.</p>
</div>
</div>
<div class="section" id="bootstrapping">
<h2>Bootstrapping<a class="headerlink" href="#bootstrapping" title="Permalink to this headline">¶</a></h2>
<p>To bootstrap, you just have to run the file <em>bootstrap.py</em>.
Here, we explain what this file actually does...</p>
<p>The bootstrap script primarily creates the initial graph manually.
This manual creation is done by writing data to a file, which is later read by the MvS.
The initial graph consists of several parts:</p>
<ul class="simple">
<li>The Modelverse Root node;</li>
<li>A global definition of all primitives;</li>
<li>The stack frame of the initial user <em>user_manager</em>, which manages all other users;</li>
<li>The code for the <em>user_manager</em> user;</li>
<li>The code for all new users, as assigned by the <em>user_manager</em>;</li>
<li>Bindings in the compilation manager for bootstrap files.</li>
</ul>
<p>These are all fairly simple in themselves.
For some parts, such as the code, the HUTN compiler is invoked on a temporary piece of code.
All bootstrap files are also compiled and made available to the compilation manager with their MD5 hash.</p>
</div>
<div class="section" id="how-to-add-a-primitive">
<h2>How to add a primitive<a class="headerlink" href="#how-to-add-a-primitive" title="Permalink to this headline">¶</a></h2>
<p>Probably the most important reason why you would want to know about the Modelverse internals, is if you want to add a Modelverse primitive.
Primitives are functions implemented in the MvK core, and thus become hardcoded.</p>
<div class="admonition warning">
<p class="first admonition-title">Warning</p>
<p class="last">While these functions are hardcoded, their implementation needs to follow strict rules, such that their semantics is identical in all possible programming languages.
For example, a primitive <em>getTime()</em> cannot simply be implemented as <em>time.time()</em> in Python, as this gives different results on Linux and Windows.</p>
</div>
<p>To add a primitive, follow these steps:</p>
<ol class="arabic">
<li><p class="first">Add the code of the primitive to the MvK implementation by adding it in the file <em>primitives.py</em>.</p>
<blockquote>
<div><ol class="loweralpha simple">
<li>Name the function identically to how the primitive will be invoked later on.</li>
<li>Take a set of parameters. Parameters for primitives are always positional and start from <em>a</em> onwards.</li>
<li>The final parameter should be a catch-all element, as it is possible that a high number of additional information is passed. In Python, this is done with a parameter prepended with **.</li>
<li>When asking the MvS for information, use yields, just like the implementation of transformation rules in the MvK.</li>
<li>Instead of return, use a <em>raise</em> with the exception <em>PrimitiveFinished</em>. This exception takes one argument: the returnvalue.</li>
</ol>
</div></blockquote>
</li>
<li><p class="first">Add the signature to <em>bootstrap.py</em> in the topmost dictionary <em>primitives</em>. The key is the name of the function, and the value is a list starting with the return type, followed by all parameter types (as string).</p>
</li>
<li><p class="first">Add the declaration to <em>includes/primitives.alh</em> to make them available everywhere.</p>
</li>
<li><p class="first">Add the definition to <em>primitives.alc</em> and assign the Modelverse reference <em>?primitives/function_name</em>.</p>
</li>
<li><p class="first">Recreate the bootstrap file by running the script <em>generate_bootstrap.py</em>.</p>
</li>
<li><p class="first">Restart the Modelverse to reload the bootstrap file.</p>
</li>
<li><p class="first">From now on, all files including <em>primitives.alh</em> have access to the defined function.</p>
</li>
</ol>
</div>
<div class="section" id="adding-a-precompiled-function">
<h2>Adding a precompiled function<a class="headerlink" href="#adding-a-precompiled-function" title="Permalink to this headline">¶</a></h2>
<p>Adding a precompiled function is way easier: only step 1 of the addition of a primitive should be done, but in the file <em>compiled.py</em> instead of <em>primitives.py</em>.
All other steps are done automatically since there is an action language implementation present.
The MvK will then automatically pick the precompiled function or the explicitly modelled operation, depending on preferences.
A restart of the MvK is needed for Python to pick up the new functions.</p>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
  <h3><a href="index.html">Table Of Contents</a></h3>
  <ul>
<li><a class="reference internal" href="#">Internal workings</a><ul>
<li><a class="reference internal" href="#modelverse-state">Modelverse State</a><ul>
<li><a class="reference internal" href="#rdf-backend">RDF backend</a></li>
<li><a class="reference internal" href="#status-codes">Status codes</a></li>
</ul>
</li>
<li><a class="reference internal" href="#modelverse-kernel">Modelverse Kernel</a><ul>
<li><a class="reference internal" href="#primitives">Primitives</a></li>
<li><a class="reference internal" href="#precompiled-functions">Precompiled functions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#modelverse-interface">Modelverse Interface</a><ul>
<li><a class="reference internal" href="#semantics-visitor">Semantics visitor</a></li>
<li><a class="reference internal" href="#constructors-visitor">Constructors visitor</a></li>
<li><a class="reference internal" href="#primitives-visitor">Primitives visitor</a></li>
<li><a class="reference internal" href="#bootstrap-visitor">Bootstrap visitor</a></li>
<li><a class="reference internal" href="#model-visitor">Model visitor</a></li>
</ul>
</li>
<li><a class="reference internal" href="#bootstrapping">Bootstrapping</a></li>
<li><a class="reference internal" href="#how-to-add-a-primitive">How to add a primitive</a></li>
<li><a class="reference internal" href="#adding-a-precompiled-function">Adding a precompiled function</a></li>
</ul>
</li>
</ul>

  <h4>Previous topic</h4>
  <p class="topless"><a href="problems.html"
                        title="previous chapter">Common problems and solutions</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="models.html"
                        title="next chapter">Models</a></p>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="_sources/internal.txt"
            rel="nofollow">Show Source</a></li>
    </ul>
   </div>
<div id="searchbox" style="display: none" role="search">
  <h3>Quick search</h3>
    <form class="search" action="search.html" method="get">
      <div><input type="text" name="q" /></div>
      <div><input type="submit" value="Go" /></div>
      <input type="hidden" name="check_keywords" value="yes" />
      <input type="hidden" name="area" value="default" />
    </form>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="models.html" title="Models"
             >next</a> |</li>
        <li class="right" >
          <a href="problems.html" title="Common problems and solutions"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="index.html">Modelverse 0.4.0 documentation</a> &#187;</li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2016, Yentl Van Tendeloo.
      Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.4.6.
    </div>
  </body>
</html>