tree walker evaluator

[John W. Eaton]

[moved from the help list.  --jwe]

On  6-Jan-2009, David Bateman wrote:

| I think the question is for an automatic conversion of m-files to C++... 
| Basically creating a tree walker class that we can then build a new 
| evaluator for normal operation, instrumented evaluator for the "profile" 
| command is needed first. That is also the first step for other such 
| things as
| 
| * Octave to matlab conversion tree walker
| * Octave m-file to C++ compiler

I would guess that the existing tree_print_code class in pt-pr-code.cc
that is already implemented in a visitor style should give a good
start for these kinds of things.  But evaluating the code is a little
different from pretty printing.

| * JIT
| 
| which is why I consider the tree walker class a major missing feature.. 
| Pity I don't know enough about the parser (at least yet) to do anything 
| about it myself..

I'm attaching a preliminary patch that implements a tree-walker
evaluator.  It seems to work.  Octave runs.  Tests pass.

Some notes:

  * The tree walker only handles statements.  Evaluataion of
    expression still uses the rvalue methods because doing otherwise
    introduces some complications about how to handle the two types of
    rvalue functions we have:

      octave_value rvalue (void)
      octave_value_list rvalue (int nargout)

    It seems to me that if we want to handle expressions diretctly in
    the tree-walker evaluator that we will probably want to start
    using a value stack of some sort for function arguments and return
    values.  Then we eliminate the two types of rvalue functions and
    just have returned values going on a stack.  But I'm not sure yet
    whether this is needed or worth doing.

  * I set up a global pointer to the current evaluator so that the
    rvalue methods would have access to it without having to modify
    their argument lists.  Maybe there is a better way, but I don't
    see it at the moment.

    If we move the evaluation of expressions to the tree-walker class
    then we should be able to eliminate the global variable.

  * It should be possible to implement statement-level debugging and
    profiling interpreters by deriving from the tree_evaluator class
    and only overloading the functions that need to do someething
    extra.  I think methods in the derived classes would look
    something like

      class
      tree_profiling_evaluator : public tree_evaluator
      {
        ...

        visit_foo (tree_foo& bar)
        {
          record_profiling_info ();
          tree_evaluator::visit_foo (*this);
        }

        ...
      };

    Or at least that is what I hope we can do, so that the code that
    actually evaluates the parse tree does not have to be duplicated
    in the debugging and profiling interpreters (if we can't avoid the
    duplication, then I'm not sure why would need to switch to a
    visitor-style evaluator).

    If we can avoid the duplication, then in addition to avoiding the
    risk of error due to duplication, we also don't incur any cost
    for debugging or profiling in the normal interpreter (not even
    checking a flag).

  * I haven't tried to do any timings, so I don't know how this change
    affects performance compared to the current eval methods in the
    tree classes.

Comments?

jwe

diffs.gz
Description: application/gzip