Virtual machine SPIRIT
TOP PREVIOUS NEXT

The YAC parser will use data conforming to this grammar to construct a virtual machine. Execution of this virtual machine leads to all results being printed to stdout.

The machine has two, connected data structures:

Without going into any detail about these components, here is the definition of the virtual_machine used by YAC.


    namespace yac {

    struct virtual_machine {
        spirit::symbols<double> global_vars;
        spirit::symbols<boost::shared_ptr<function> > funcs;
        stack stk;
    };

    } // namespace yac

One point to note: Spirit's symbols class template is a powerful tool. It is used here as a data store, but it is also a fully-fledged parser that can be filled at both compile time and during the parsing process. All these abilities are put to use by YAC.

The process of generation of these data structures is akin to compilation. Execution of the virtual machine can be thought of as "unwinding the stack". The input data is parsed in its entirety before any attempt is made to evaluate it, meaning that the virtual machine may represent many individual commands. This separation, together with the desire to be able to re-define an existing function dynamically, means that the calculator must be able to support a simple overloading of functions based on the number of arguments. Otherwise YAC would be unable to handle a statement list such as:


   0    foo(a)=2*a
   1    print foo(2)    # outputs 4
   2    foo(a,b)=a*b
   3    print foo(2,3)  # outputs 6
   2    foo(a,b)=a+b
   3    print foo(2,3)  # outputs 5 

In fact, both YAC and Gnuplot can handle this example correctly. YAC, because it supports function overloading based on function arity. Gnuplot, because each command is evaluated immediately after it is parsed. ( Gnuplot would fail to evaluate the code above if lines 1 and 2 were swapped. YAC would have no such problem.)

How it works

It is perhaps easiest to explain the operation of the virtual machine with the aid of an example. Consider the numeric expression sin(sqrt(2)/3). The parser will generate the following computational stack from it:


   0    number node     2
   1    function node   sqrt
   2    number node     3
   3    function node   divide
   4    function node   sin 

(How the parser does this will be explained later.) Evaluation of this stack proceeds by iterating through it from position 0 to a function node. Here, we reach position 1 containing the sqrt function. This function takes a single argument which is grabbed from the proceeding position 0. The result of sqrt(2) is stored at position 0 and the function node at position 1 is removed. The stack becomes:


   0    number node     result of sqrt(2)
   1    number node     3
   2    function node   divide
   3    function node   sin 

We continue iterating through the stack until we reach the function node divide at position 2. This function takes two arguments which we again grab from the proceeding two positions, 0 and 1. The result of divide(sqrt(2),3) is stored in position 0 and the nodes at positions 1, 2 are removed from the stack:


   0    number node     result of divide(sqrt(2),3)
   1    function node   sin 

This process is finished when the stack is reduced to a single node:


   0    number node     result of sin(divide(sqrt(2),3)) 

This example illustrates several points:

TOP PREVIOUS NEXT

Valid XHTML 1.1! Valid CSS!