Octave-2-Matlab and back

Octave-Lint (3)
A few more additional features that could be copied from existing tools in a similar areas. Immediately we can think of all the warnings that GCC would spit out, when you compile C/C++ code using 'gcc -Wall code.cc'. Specifically, flagging unused variables, data type conversions in known stdlibrary of Octave functions and such. Its time, I could show the code, instead of waxing eloquent about it. Just that I dont have anything to show.

Octave -> Matlab -> Octave
Next in a similar spirit of the AST walker static-checker we could also have a program transformation tool for converting Octave -> Matlab code. I could 'ask' for type inference whenever it is 'confused' by 'ambiguous' nature of the code. This is exciting, in terms of the possibilities it opens up for us. It is going to be a long project, but defnitely rewarding one.
The Octave parser is widely acknowledged on our mailing lists as a superset of Matlab
language. Using the Octave parser, you could in theory convert Matlab code the other-way
round too. Now this is double bonanza, a kind of buy-1 and you get-1 free. Am I excited?

The starting point of the program transformation tool would be from Paul Kienzle's work on
Oct2Mat conversion script. A few things are simple to understand, and require plain substituion. Paul's code does it using an AWK script, and clearly mentions not wanting to Octave's parse tree for doing the conversion. Paul attempts to do it using filters in AWK, and aims for an independent program for doing the conversion. Since our aims are to take advantage of whatever we have (GPL, Octave, Parser) then we can stand on the shoulders of giants instead of 'lets start at the very beginning, Do Re Mi'. Paul's code helps us easily identify the transformation rules to be applied.

The Octave->Matlab transformation rules, applied in Paul's code include

1. gsub("#" , "%"); convert # to %
   
2. gsub("[(][)]",""); convert () to ' ' as Matlab 4.0 and Octave-2.1.50 dont support empty arguments. This is not a problem anymore.
   
3. gsub("gset[^;%]*;",""); a graphics command conversion.
4. gsub("gset[^;]*%","%"); a graphics command conversion.
5. gsub("gset[^;]*$",""); a graphics command conversion.
6. gsub("endfunction",""); Octave has endif, endfor, endfunction etc, so those get converted to end, or in Matlab nothing at all. Infact Matlab complains if you have the end keyword at the end of a function file.
7. gsub("endif","end"); Same as 6.
8. gsub("endwhile","end"); Same as 6.
9. gsub("endfor","end"); Same as 6.
10. gsub("end_try_catch","end"); Same as 6.
11. gsub(/&&/,"\\&"); Matlab didnot have the short circuit logical operators initially, so we had to use the logical &.
12. gsub("SEEK_CUR",0); They also seemingly lacked options for STDIO processing.
13. gsub("SEEK_END",1); Same as 12.
14. gsub("SEEK_SET",-1); Same as 12.
15. gsub("usage","error"); Our usage() and print_usage() are replaced by error() function.
16. gsub("__error_text__","lasterr"); Some Octave specific code
    
17. gsub("unwind_protect_cleanup",""); Again Octave was first here, w.r.t try/catch ...
    
18. gsub("end_unwind_protect",""); ... doing it the LISP way.
    
19. gsub("unwind_protect",""); Same as [17, 18].
    
20. gsub(/\|\|/,"|"); Logical short-circuit OR operator was NOT there in Matlab first. We got here earlier.
    
21. gsub("!","~"); They dont know whats Not !
    
22. gsub("[\\]$","..."); Line continuations are OK for us. Not them!
    
    

These rules are easily loaded as actions for a AST walker, for operators in Octave. We just generate the do_convert_oct_to_mat() on each node. As an example, the node for the operator short-circuit && will have the conversion rule embedded in this routine as follows,

string short_ckt_and::do_convert_oct_to_mat() {
l_str=left_node.do_convert_oct_to_mat();
r_str=right_node.do_convert_oct_to_mat();
str=l_str + " & " + r_str;
return str;
}

So basically it would be a really syntactically correct way of doing things for bulilding transformation tools from the existing code base. As explained earlied since Octave being a superset of Matlab we could also turn the world the other-way round.

Ofcourse the validity of the converter can be verified by doing the rountripping, O-2-M-2-O and running the code to see if we have the regression tests validated. John Eaton (JWE), has a set of regression cases for parser, which is again something we can re-use.

It would be fun to see this happen, and I suspect this is much lower hanging fruit than writing an evaluating AST-walker for building the profiler or a debugger.

Cheers,
Muthu

Octave-Lint (2)

Much as I'd like to be informal, being private remains a greater love. Thinking about the previous post on Octave-Lint over lunch, a few more useful features suggested themselves. In the spirit of a note-to-self I document them here. I know looking into places like Pychecker or Pylint can save
us time.

Things that make syntactic sense but no semantic sense, and pass the parser, but which Lint must trap.

1. x=x+ stdfunc(arg); %here if the Lint knows the standard Octave functions it has a clue to the return value and can do a little bit of type-checking analysis to figure out warnings and such. Eg: x = x + strlen('hello world') ; makes sense, but on the other hand, y = y + getenv("HOME") would probably not!, and z = strcat(system('ls'),'files') definitely doesn't make any sense. Lint knows system() always returns a single integer as its first value, and that is incompatible with strcat(). Such analysis is not performed statically, and one can discover such problems only at runtime; expensive, in my opinion.
2. Indexing over-flow / under-flow options. In modern programming languages (Java, Python?) indexing over-flow under-flow can be flagged at runtime exceptions, or even better statically discovered from code. Now for Octave, matrices & vectors are indexed starting at 1, which lets use compute and flag array/vector indices that seem to underflow. In this type of analysis the direct algorithm would be to pick & flag usage such as array(index) | index <= 0 or index is non-integral. For directly -ve indices this is uncommon; we may catch a few 0-index usages, and sometimes usage of fractional indices. The key problem remains to identify computed indices that may underflow or overflow. Overflow is also another important problem for most programs, where arrays tend to be pre-allocated, and not x=[x; new_row]; style.
3. Matrix dimension conformity in cases where we do products. This is a minefield I step into every now and then. Multiplying 2 matrices A_mxn * B_nxl = C_mxl. This conformity rule of Matrix multiplication must be enforced to flag errors at compile time when we have an idea of the program dimensions. This will be tricky to implement.
4. Misspelt variables can be suggested through looking up the symbol table accumulated during the parse-tree walking phase. String edit distance algorithms will be useful here.
   
5. Redefined / modified pre-defined constants can be flagged as errors/warnings. Candidates like i, e, eps, pi, are immutable for me. Typically many programmers write for i=1:10; end and tend to use loop index after the loop, which can be 'caught' by Lint.

Essentially, learned behaviour of a experienced programmer can be taught to the machine, as rules specified by lint, and we could improve the range of tools available for users to fallback on.

I have a post soon on Fortran & Octave, working with LAPACK and known design issues in such an interface.

Cheers,
Muthu

Octave-Lint

This tool will possibly use the existing parser, and walk the AST to figure out
syntactically correct but semantically wrong constructs statically. This could mean
things in the BNF like stmt: expr op expr which can match semantically wrong constructs
due to compile time invisibily/scoping issues as in x = x + 1 . This statement is wrong
because variable x is un-initialized. So such errors can be discovered using Octave-lint, when someone writes it.

Essentially a bare-bones algorithms would involve

1. Parse the file & report errors if any.
2. If no errors, start the (Left-Right-Root) post-order traversal, of the AST.
3. At each visitor try and note down order of variables into a static table.
1. Note down variable creation
2. Flag suspicious variables
3. Flag undefined variables
4. Flag possible 'typos' of variables by Levenshtein distance of the misspelt / undefined variable name with variables on the table. Min of this metric must give us a possible suggestion for the wrong typo variable.
5. Have more heuristic error cases to be trapped in the visitor, based on static tables.
4. Finally the collected errors/warnings are reported to user, based on input options.
   
5. Additional tuning can be done to run Lint on a set of files, with functions defined elsewhere, and rules for specific usage.

I think this would make a really nice project for someone who wants to learn C++ basics and hack on a real piece of software. It would be a great first-dip into the Free Software Ocean.

Cheers,
Muthu

Octave 3.0

For the 3.0 Octave community is actively working on the graphics end. A funny thread was posted about the trademarking of the word 'handle graphics' by Matlab. The term ''handle'' itself, however seems to have been used by X-window system, and even Microsoft since early 80's and 90's.

As for the graphics implementation support on the Octave front is completely being rewritten and we have handles implemented deep within the Octave type system in the interpreter. This is good news, with the development headed by John Eaton, himself.

A interesting development is the jhandles and Java Graphing tools in Octave-Forge by Michael Giffoul. I havent personally checked out the tools, still they look promising with the GPL'ing of Java itself, and the nice 3D capabilities of Java Graph. I wonder how fast it can show a mesh of 500x500 matrix.

Anyway, so hope to use a nice graphics-handle system in Octave, pretty soon!

Cheers,

Octave is fun!

Just struck me, how much fun these guys have, creating and maintaining a
scientific computation platform.

A peek into a recent message on the Octave mailing list.

Paul Kienzle   
to Red, help-octave
 
show details
  7:50 pm (1½ hours ago) 

On May 28, 2007, at 7:16 PM, Red Crow wrote:

> Hello:
>
>           Anybody knows how normalize  a distribution, to make  mean=0
> and sd=0.

Easy --- replace every value with 0.    8-)

I suspect you want mean=0, sd=1.  The function to
do that is zscore(), which subtracts the mean from every
data point and divides by the standard deviation.

- Paul

Do we have fun? You betcha.
-Muthu

Missing Link: Profiling-AST for Octave

The Octave profiler was developed to provide

1. Flat-profiler with average function performance.
2. Profile anonymous and complete functions.
   
3. Call-Graph profiler to show caller-callee statistics.

I have implemented a rudimentary "flat-profiler" that can just give
statistics of the cpu-time of the functions (only), self & total average
runtimes, and frequency of call to each function.

This code is a C++ rewrite of the Ruby's flat-profiler from
$(Ruby-Install-Path)/lib/profiler.rb authored by 'Matz' (Yukihiro
Matsumoto).

Sample output of profile command testcase 'testprofile.m' (attached)
looks like:

 %   cumulative   self              self     total
time   seconds   seconds    calls  ms/call  ms/call  name
 2.41     0.00      0.00        4     0.06     0.06  anonymous1
 2.57     0.00      0.00        4     0.06     0.06  anonymous2
 0.00     0.00      0.00        1     0.00     9.71  #toplevel
ans = info


I have also added some elementary support for 'event-based' profiler ,
from the Octave side, that notifies the routines for 'calls', and
'returns' from functions. Exception handling is not implemented.
The API support touches the 4 files mentioned in the previous post.

>From this point, a simple call-graph profiler can also be implemented
with the present infrastructure. The python profiler ('import profiler')
does something like this, and serves as a good template.

[Profiler API Support]
Many design decisions remain to be made, which I must leave it to better
experienced. I would personally prefer a 'event-based' profiler API like
the JAVA's JVMPI (JVM Profiler Interface) which lets people build/use a
sophisticated or simple profiler based on the application.
Please see JVM-PI design at
http://java.sun.com/j2se/1.4.2/docs/guide/jvmpi/jvmpi.html.


There are following good points about the code,

1. It recognizes anonymous functions
2. Does CPU times with least overhead.
3. Can write a basic call-graph profiler
4. Works in rudimentary Matlab syntax

Caveats of the present code,

0. Cannot lookinto execution times of specific lines-of-code
1. Not Matlab compatible
2. Cannot handle exceptions in profiler gracefully.
3. Regular caveats of a flat-profiler in not knowing context
  of the function calls; (call-graph based profilers help here,
  sort-of)
4. No event filtering
5. Sub-Optimal API design

For compatibility with Matlab, it suffices to provide an API to reach
the level of a event-based, call-graph profiler with access to
individual lines.

I am posting the diffs against the files, and the 2 new files for
octave/src/profile.cc & octave/src/profile.h

Please comment.

Thanks,

-Muthiah

You can look at the whole thread here.

What remains to be done is to write the hooks of the profiler
function into a separate AST walker in the Octave interpreter,
and make the evaluation-AST changeable at runtime using
the profile() function, when it is set. This AST type evaluation
is required, as there will be a performance hit of about 2x compared to the non-profiling interpreter.

Making a AST type evaluator with the hooks for the interpreter
is a non-trivial task; but that involves working on making the event hook mechanism delivery on function-call and return events. This however, does not affect the design of the profiler itself. So this is the missing-link in the profiler game.

Once the profiling infrastructure is in place using the separate AST, then we can profile fine-grained events including

1. Source code line , enter-leave events,
2. Variable watch/change events,
3. Regular function-call return events, and
   
4. Exceptions or Non-local exits.

This profiling-event-generator AST we need to put in place for the people to write profilers of their choice. I have provided a Flat and Call-Graph AST's. You can also contribute your mite!

Cheers,
Muthu

fucnrdthsucngtagdjb !!!

The following is an email from John Eaton, principal author explaining a 'curious' variable name in Octave manual. LOL.
Cheers,
Muthu

Message: 4
Date: Mon, 14 May 2007 21:17:03 -0400
From: "John W. Eaton" <jwe@bevo.che.wisc.edu>
Subject: LOL
To: S?ren Hauberg <soren@hauberg.org>
Cc: octave bug mailing list <bug@octave.org>
Message-ID: <17993.2575.632481.664491@segfault.lan>
Content-Type: text/plain; charset=iso-8859-1

On 15-May-2007, S?ren Hauberg wrote:

|    I just saw the following in vars.txi
|
|       @cindex job hunting
|       @cindex getting a good job
|       @cindex flying high and fast
|
| I have no idea why these lines are there, but it sure is funny. I'm not
| attaching a patch to remove them since I find them quite amusing. I'm
| just curious, if there's a story behind these lines?

The example that follows has the (valid) variable name

 fucnrdthsucngtagdjb

It's an old joke.

jwe