Rainbows! (exploring random colors)

[mure]

So, I've been going through the examples one by one in the repo to try and wrap my head around the concepts. I had an idea for a simple model and thought implementing it might help me understand things better. And...it ended up being more complicated than I expected 😬 The idea was to take a basic random walk, but have it pick a random color on each step.
My first try was:

<one values="BROYGUIP" origin="Random">
  <rule in="*B" out="B*"/>
</one>

This does nothing whatsoever. Presumably it just rewrites BB with BB on every step, so the output never changes. What I really need is the wildcard to include every color except for black.
One of the examples had a "Union" element, which seemed to fit this use case:

<one values="BROYGUIP" origin="Random">
  <union symbol="?" values="ROYGUIP"/>
  <rule in="?B" out="B?"/>
</one>

But this throws an error: Rainbow > output code ? at line 3 is not found in codes ERROR. It looks like the unions are only supported on the left side of rules.

I decided then that I would try enumerating all the colors into separate rules, and stumbled into something much more interesting than my original plan:

<one values="BROYGUIP" origin="Center">
  <rule in="RB" out="RO"/>
  <rule in="OB" out="OY"/>
  <rule in="YB" out="YG"/>
  <rule in="GB" out="GU"/>
  <rule in="UB" out="UI"/>
  <rule in="IB" out="IP"/>
  <rule in="PB" out="PR"/>
</one>

Since each color can only build off of one other color, it ends up with a cyclical pattern that is reminiscent of tie-dye shirts.
I think I could get closer to my original goal by enumerating every possible color swap, e.g. RB can turn into BR, BO, BY and so on. But I have to think there's a better way. Any ideas?

[mxgmn]

Cool! Did you initially want to make something like this?

<one values="BRYGU" origin="Center">
  <union symbol="?" values="RYGU"/>
  <rule in="?B" out="BR"/>
  <rule in="?B" out="BY"/>
  <rule in="?B" out="BG"/>
  <rule in="?B" out="BU"/>
</one>

[mure]

Yep! I see that the union still simplifies the logic a bit. Why aren't unions supported on the right-hand side? Is it a gap in the implementation, or are there performance implications?

[kaya3]

I think what you want would be like a capturing group in a regular expression, for example in="([RYGU])B" out="B\1" where the \1 refers to the symbol captured by the matching group ([RYGU]), which is what the ? in your example means. This is a more convenient way of describing the feature, because it allows you to disambiguate rules with multiple occurrences of a union, e.g. in="?B?" out="B??" could be either out="B\1\2" or out="B\2\1".

Allowing capturing groups like \1 to occur in the output pattern should be possible without any significant performance hit, because the matching algorithm itself wouldn't need to keep track of what was captured in its internal state; suppose a match is found with the pattern's top-left corner at (x, y) in the grid, and the ? occurs at (i, j) in the pattern, then we can find out what symbol \1 should be by reading it from the grid at (x + i, y + j). The only tricky thing here is that we need to do all of the reading before any of the writing, to not mess up with rules like in="?B?" out="\2B\1".

This would be a really powerful feature; you could have rules such as in="??/??" out="\2\4/\1\3" to perform a 90-degree rotation, for example.

[mxgmn]

I'm not convinced that implementing right-hand unions is a good idea. Potential drawbacks are more code, some performance cost, and how would right-hand unions work with inference? The benefits should outweigh these. Would right-hand unions allow to make a better ModernHouse? I have encountered this issue with ColoredKnots, btw. Folding the second node is just a matter of syntax sugar <rule in="W" out="I|P|E|N|D|A|R|O|Y|G|U|C|K|F"/>, but folding the first node is much less trivial.

[kaya3]

The implementation I proposed indeed would be a massive headache to work with inference, so if you were to go that route then right-hand unions should probably just be forbidden in inference rules. An alternative way, which would work with inference, is to implement right-hand unions just like you're implementing symmetries:

• A rule written like (RBB=WWR) is really describing four patterns (RBB=WWR), (R/B/B=W/W/R), (BBR=RWW), (B/B/R=R/W/W), due to symmetries.
• A rule written like (B=?) is really describing four patterns (B=R), (B=Y), (B=G), (B=U) by expanding the right-hand union.
• A rule written like (?B=B\1) is really describing four patterns (RB=BR), (YB=BY), (GB=BG), (UB=BU) by expanding the left-hand union and its matching replacement, plus twelve more for their symmetric counterparts.

That is, the single rule in the source code is expanded into several different rules at "compile-time", with no changes to the rest of the interpreter. The matching, rewriting and inference algorithms would work automatically for the same reason they work automatically with symmetries. Performance-wise, this is the most conservative way to implement the feature because programs which don't use it don't pay for it. For programs that do use it, there is some cost for having more patterns to consider when searching/inferring, but the performance would be the same if programmer wrote out all the different versions of the rule in the source code by hand.

The main problem with this approach is that a rule with k question marks gets converted into s*c^k patterns, where c is the size of the union and s is the number of symmetries. The exponential blow-up would make it infeasible to run programs when there are too many question marks in the same rule (although the same infeasible program could be written without right-hand unions); this is probably best addressed by bailing out at "compile-time" if a rule would be expanded into too many patterns.

On a separate note, I wonder if it is worth developing a set of benchmark tests for the interpreter, so that contributors can check for performance degradations before making pull requests.