Caching strategy for type system rules

I think it is a common issue for more complex languages that you need some util data structures for the type system checks like maps, trees or just lists. The build-in data flow program is an example for such a structure. This structures are typically used by different type system rules of several nodes, but they are built in the scope of a root node or of the whole model.

Especially for the type check before generation it makes no sense to rebuild this data structure in every node where it is used, since it will be always the same. This could dramatically increase the build time. But it is of course important that it will be updated/rebuilt while editing the affected nodes.

One very easy way implementation approach could be using the memoize feature of the base language extensions. But I haven't found some object that will change with every change in some subtree.
I also suspect that something like this is already implemented in MPS itself. But - again - I couldn't find any documentation about it.

So any hint is welcome!
5 comments
At least the MPS devs must have an idea about this!? They hopefully have implemented something like that yet.

BTW: Does anybody still reads threads in this forum? I can't believe that this thread is just read three times in the last month. Probably I increased the read counter two times by myself. This is not really motivating, even if I know that the content is also provided by rss.
0
In MPS 2.5, you can use model listeners to change your structure on event-based basis. See SModelDescriptor.addModelListener() method. In 3.0, there will be a base class for listeners allowing, for example, to track a subtree of one node.

Strategies for optimization in MPS are quite various. And caching everything is not a preferred one by default. I think that's why there's no language for such data structures.
0
Hello Mihail,

Thanks for your answer and your suggestion. Probably the ModelListener is a possible approach. Especially the MPS 3 version seems to be promising. But it still sounds a bit overdone. I don't want to rebuild my data structure every time the model changes but every time the type system checks the model and this has changed compared to the last time. So it would be great if I could tag a node somehow and any modification will remove this tag.

Are you familiar with the dataflow systems and the analyzers using it? I think the data flow is created for some scope, where it is used for several nodes with different analyzers, hopefully without rebuilding it every time. I guess I want to do exactly the same but I can't understand all code behind it. If you could point to the code, where I find this implementation, I probably could figure out its functionality.
0
Ah, if you are talking specifically about Typesystem and DataFlow checks, that's how they work.
1. The DataFlow analysis is invoked via AnalyzerRunner.analyze(). As I can see from the code, all real analyzer invocations are produced with code in non-typesystem rules. As far as I understood, the most interesting thing for you there is how MPS determines that it should rerun some analyzer. I'll try to explain.
2. When the typesystem engine runs a typesystem rule, or a non-typesystem rule, it records all read-accesses to AST structures this rule produces. So, after executing this code, it knows which parts of AST it depends on. The engine listens for model events then, and when it receives a notification about something was changed, it invalidates all typesysten/non-typesystem rules depending on the changed part of AST. On the next typechecker invocation, these rules are to be recalculated.
0
AFAIK, there's no event for "node type was changed".
0

Please sign in to leave a comment.