Today I am going to try out Cunningham’s Law: “The best way to get the right answer on the Internet is not to ask a question: it’s to post the wrong answer.”

I have started looking at the MPS Coderules plugin which implements an alternative analysis engine for MPS based on Constraint Handling Rules (CHR), a rule-based declarative language, roughly occupying the same position in whatever programming language taxonomy as does Prolog.

Coderules may be the future of MPS type checking now that the Kotlin-for-MPS type system is being written in it. That’s why I wanted to get a feeling for how easy it would be to understand an existing type system or develop one.

The shock

My first reaction when I saw a code rules program was that of resistance and recoil: the documentation is full of similar-sounding foreign terms like rule, constraint, query, or macro. It appears that the language does not simply describe the rules of typechecking but rather rules that build constraints. (Which seemed to be other kinds of rules. After all isn’t a constraint a kind of rule that constrains something?)

This was all a bit too meta to me so I quit.

The next time I tried looking at Kotlin’s typesystem linked above but was immediately lost and overwhelmed. So I quit a second time.

After several such attempts I started recognizing some patterns and making some distinctions.

I realized that rules are programs but constraints are not. Constraints are simply special objects floating around in the reactor (the working memory) of the engine. The engine is processing the constraints according to the rules: it matches them to a rule, the rule tells which of the matched constraints to keep and which to remove, and which new constraints to add.

To keep with the reactor analogy, constraints are molecules and rules are chemical reactions that transform some molecules into other molecules. Some of the “input” molecules are consumed while other molecules work like catalysts, enabling the reaction while not being consumed in the process.

Entry and exit point

Past the initial shock, my next immediate question was “Where does this program start and how does it end?” The entry point seems to be a query, which the type checker calls when it wants to know the type of something. There are multiple queries (check and typeOf) and I don’t yet understand the difference between them.

You can define queries (or, rather, query handlers) in two ways: using a lower-level QueryTable concept, or, for the type system, using TypecheckingQueries concept. The latter is where we finally get a little bit domain-specific, as the underlying engine is so general that besides computing types it can apparently also compute control flow, data flow and other kinds of analyses).

The exit point is probably when the reactor “stabilizes”, i.e. no new rules can be fired. I have expected that the engine would extract the “answer”, i.e. the type, from the constraints that remain in the reactor somehow but this does not seem to be the case. Instead, the query (the entry point) gets passed a type collector which collects types via side effects:

(I am still a bit confused here because the method to retrieve the type collector from a query is deprecated, yet I see no indication of there being a replacement.)

To be continued…

This is all that I have time to write today but I want to continue my investigation of coderules in the future. I still have lots of open questions, both low and high level, but I am curious what questions you might have about Coderules.