Semantic type analyser brainstorming

[PeterTillema]

Heya! So, I've been working on a MATLAB to Python/NumPy converter the past few months, using your execellent tools for this. As you said multiple times in issues/code, you need to get a semantic type analyser working. So, my idea was to share some ideas about analysing and code generation.

For example, what would happen if you have the following (nonsense) code:

fileDir = [pwd filesep 'dir' filesep]
if ~exist(fileDir)
    disp(fileDir(2))
end

If you translate that to Python, you would expect something like

fileDir = np.array([[os.getcwd(), os.filesep, 'dir', os.filesep]])  # note: 2D-array!
if not os.path.exists(fileDir):
    print(fileDir[1])

which of course doesn't work right, as os.path.exists can't take a NumPy array. You can change the initialization, but the array might be used as a proper array, and then the code breaks. So what are your thoughts about this?

Also, indexing. Yay. A single index in MATLAB is perfectly fine, but logically won't get the same results as with NumPy. What kind of code should be generated do you think?

---

Regarding my semantic type analyser, I have one main function, which looks like this:

    def visit(self, tree, relation=None):
        name = 'visit_' + tree.__class__.__name__
        if hasattr(self, name):
            getattr(self, name)(tree, relation)
        else:
            warnings.warn(
                'Couldn\'t check node ' + tree.__class__.__name__ + ' during the SemanticTypeAnalyser pass')

which visits the right node, other functions in the same class. So far, everything is fine. But as you said, it is a hard task, for example, how do you deal with types and sizes? How do you track them/store them in a tree? When are you visiting functions? How do you handle array indexing, or function calls?

---

I may share my entire type analyser/code generator if you would like :) So far, it produces syntactically correct (as in, whitespace, comments), but when running the output program you get a ton of errors. For example, I can't properly detect if you call a function or index an array, so it always uses () rather than [] if necessary, which obviously won't work.

So, TL;DR: I'm curious what your thoughts are about this :) (and then especially the semantic type analyser). Thanks!

[RobBW]

Semantic Type Analysis - brainstorming # (Issue #247)

In my attempt to understand the complexities of transpiling Matlab to Python I have found 3 useful sources of insight. Perhaps they have ideas you can use?

1. McGill University’s Sable project in which typing of Matlab is a major factor.
   There is a good descriptive paper here:

Li, X., & Hendren, L. (2014). Mc2FOR demo: A tool for automatically translating MATLAB to FORTRAN 95. 2014 Software Evolution Week - IEEE Conference on Software Maintenance, Reengineering, and Reverse Engineering (CSMR-WCRE). doi:10.1109/csmr-wcre.2014.6747218

Also a thesis in which many of the best attempts so far are reviewed. It also details their methods to produce consistent results.

An interesting looking link: https://github.com/Sable/mclab-ide

Unfortunately this project has lost its leader. Prof Laurie Hendren died about 2 years ago

2. @Matteus Bysiek’s Transpyle project https://github.com/mbdevpl/transpyleat Riken is a demo of using type extended Python AST to update legacy scientific Fortran code for HPC modelling (of supernovas!)

Background papers here:
Towards Performance Portability and Modernization of FLASH via Transpilation with High-Level Intermediate Representation
& IPSJ-HPC16157009.pdf
& IPSJ-HPC18165038.pdf

Bysiek wrote typed-astunparse an unparser for Python 3 AST’s with type comments.

Converting Matlab to Bysiek’s extended Python AST could open up many possibilities for creators of Matlab code.

3. A recent collection of papers on using machine learning on AST’s to infer semantics from the deep tree structures. Here:

I hope these suggestions are helpful.
I have copies of the quoted papers if you cannot find them..

[RobBW]

I omitted the link from item 3 of my last comment.
It should have read:
3. A recent collection of papers on using machine learning on AST’s to infer semantics from the deep tree structures. Here: https://ml4code.github.io/tags.html#types

[florianschanda]

I will need to take some time to properly answer this. But on arrays, I believe in MATLAB all array indices are integral (unlike e.g. Ada) so you can just translate a(n) to a(n-1) and it should always work. 2D arrays you need to deal with in some way, but they are harder since you need to know the size. Or you translate them as lists-of-lists, then you don't.

Let me get back to you on the rest. Since there is now official interest, I will put the semantic analysis at the top of my prio list.

[florianschanda]

Obviously what I said doesn't work if we don't even know if something is an array or a function call. I really think I need to get sem working...

[florianschanda]

Also, moving this to a discussion item, since it's not really a feature/bug

[florianschanda]

So, I am not a fan of even considering machine learning for type inference. I think this is both too slow to do in Python, but also very hard to eventually qualify.

I think, with some language constraints (MathWorks also has some), some reasonable type inference can be made. For example:

• no eval()
• a struct's structure cannot be modified (i.e. adding fields) outside the subprogram where it is created
• an arrays size cannot be modified outside the subprogram where it is created

I think all three of these are also limitations for the Mathworks code generator, so people are already used to them. There are a few more, and maybe a few different ones we'd want to choose.

[florianschanda]

I think my plan is as follows (but take this with a grain of salt as I have had neither coffee nor breakfast :D)

We still parse in parallel, like we do right now. Then, for sem, we can do this:

• First determine packages, classes, and script files and add them to a symbol table
• Make a reasonable model of built-in functions. I have something right now but it's really rough and not correct. Likely at this point I also need to fully support different language versions and choosing which one you want. We can also skip this and start with a "no-runtime" MATLAB/Octave dialect.
• Get name resolution working for functions in files. Deal with the case where you have a name clash between variables and functions (this is now thankfully illegal since 2017 I think)
• Get name resolution working for everything else (i.e. variables)

Special care needed for:

• global statement
• scripts sharing the global workspace
• import statements

Once we have name resolution working correctly, we can:

• know if the thing we're calling is a function or it's an array (in most cases)
• start to do some simple type inference (we could start with some obvious known cases like x = single(5) and work from there; we might have some unknowns and conflicts (at function calls) and we can deal with those by instantiating (since MATLAB is inherently polymorphic and our target language(s) probably are not)

[RobBW]

This list of Matlab flaws may be useful for you in testing your thinking.
http://www.rath.org/matlab-is-a-terrible-programming-language.html

[florianschanda]

That is a nice link, thanks!
I've compiled my own as well, but mainly focussing on the lexing issues: https://github.com/florianschanda/miss_hit/blob/master/LEXING_ISSUES.md

[florianschanda]

That writeup focusses on semantic issues, which I know way less about (I am not actually a MATLAB user/programmer you see). Super helpful!

[RobBW]

I think this reference may be helpful in thinking about arrays.

Efficiently implementing the copy semantics of MATLAB's arrays in JavaScript
Share on
Authors:
Vincent Foley-Bourgon

,
Laurie Hendren

Authors Info & Claims
DLS 2016: Proceedings of the 12th Symposium on Dynamic LanguagesNovember 2016 Pages 72–83 https://doi.org/10.1145/2989225.2989235

https://dl.acm.org/doi/abs/10.1145/2989225.2989235

In particular the conclusion says:

This analysis uses the unusual trick of considering the MATLAB program as if it had the semantics of JavaScript.

The 3 bullet points in Para1. are very thought provoking. Can they be generalised and applied to (say) Python?

[RobBW]

@florianschanda said

That write up focusses on semantic issues, which I know way less about (I am not actually a MATLAB user/programmer you see).

Neither am I. I am a generalist who used the SMOP project as a way of extending my poor knowledge of Matlab and improving my Python understanding. This has led me down some interesting alleyways over the last few years.

It does surprise me that there are no really successful attempts at bridging the Matlab<>Python gap. I see your Miss_Hit as part of that bridge. An easy to use & effective Matlab>Python tool helps break down barriers of cost and complexity for students, independent researchers and small developers. Its a rewarding open source project.

Re the previous reference i sent about MatJuice. There is Matlab>Java code for that paper here: https://github.com/Sable/matjuice
Somewhere the paper says that their approach is target language agnostic.

On the Sable github site I also noticed some tests of Matlab semantics which may be helpful:
https://github.com/Sable/matlab-tests-ipynb

Collection of unit tests and expected results to check compliance with the MATLAB semantics.

These may give you clues to help your understanding.

[RobBW]

For a quick take on MatJuice see: https://www.cs.mcgill.ca/~vfoley1/matjuice.pdf
Its a nice clear slideshow.

[RobBW]

A while ago I learned about Treesitter, a tool for typing & syntax analysis developed by Github and included in Atom editor. Its use to assist code transformation is mentioned in some of the references listed below.
It also has its own Matlab grammar.

A few months ago I jotted down the helpful weblinks which I have updated today.
I think Treesitter may be useful and relevant to your work.
Here are my notes:

TreeSitter

The idea:Incremental Analysis of Real Programming Languages
http://harmonia.cs.berkeley.edu/papers/twagner-glr.pdf

Video of Github Announcement of Treesitter: 42min
https://www.youtube.com/watch?v=a1rC79DHpmY

Tree Sitter and Syntax Highlighting - Petersen
https://irreal.org/blog/?p=10146

tree-sitter-syntax-visualizer
This package allows for exploring tree-sitter syntax trees. This can be useful either educationally, or when developing either a package that uses the tree-sitter AST or a tree-sitter language itself. https://atom.io/packages/tree-sitter-syntax-visualizer

A map of the tree-sitter ecosystem
https://dcreager.net/tree-sitter/map/

Matlab grammar is available, but not on Treesitter site.
https://github.com/mstanciu552/tree-sitter-matlab Nov 20 2021

Create a Treesitter grammar
https://gist.github.com/Aerijo/df27228d70c633e088b0591b8857eeef

Combobulate is an Emacs package that provides a standardized framework for manipulating and navigating your source code using tree sitter's concrete syntax tree. Combobulate is language agnostic and should work with little modification almost all languages supported by tree sitter itself. https://github.com/mickeynp/combobulate
Combobulate is alpha software with all the caveats that follows from that. The author uses it daily however, though breaking changes are likely.

Parser Parser Combinators for Program Transformation
https://thestrangeloop.com/2019/parser-parser-combinators-for-program-transformation.html 2019
Somehow related to TreeSitter based tool

[florianschanda]

Matlab grammar is available, but not on Treesitter site.
https://github.com/mstanciu552/tree-sitter-matlab Nov 20 2021

I think their grammar is also extremely incomplete, from a quick scan it's doing functions but I didn't see any of the usual nasties (command-form, etc)

[PeterTillema]

Woah, that's a lot more responses than I would think of :D. Looking at these papers, it doesn't make sense to share my semantic type analyser or code generator, as it's super basic, although it outputs clean code. But the code generation itself ain't that hard, could be integrated easily into MISS_HIT, once the semantic type analyser is working.

(Also, @RobBW your url's are sometimes messed up, it redirects to https://github.com/florianschanda/miss_hit/discussions/url instead)

[RobBW]

Do you know about OctMiner? It turned up for the first time in one of my searches related to Matlab today. It looks as if it may have some relevant observations for your work on semantics and quality.
Here are some links to follow up.
OctMiner: A Multiple View Environment for MATLAB and GNU/Octave
[http://sourceminer.sourceforge.net/octminer.html]
A Multiple View Interactive Environment to Support MATLAB and GNU/Octave Program Comprehension
[http://ctp.di.fct.unl.pt/~mpm/pubs/Lessa_et_al(ITNG%202015).pdf]
A Concern Visualization Approach for Improving MATLAB and Octave Program Comprehension
[https://repositorio.iscte-iul.pt/bitstream/10071/24919/1/conferenceobject_28034.pdf]