Documentation and resources

[kaya3]

This is a fantastic project, and over the last few days I've basically dropped what I was doing and focused on trying to understand it. Thanks very much for making it open source! It seems like a lot of other people are interested in the project too, and I think there is definitely a need for more resources. I would love to create some of these myself:

• Documentation
• A more ergonomic syntax for MarkovJunior programs, rather than specifying these in XML.
• A compiler which converts MarkovJunior programs into another language, so that procedural generators written in MarkovJunior can be directly included in other projects.
• A debugger which can step through the execution of a MarkovJunior program, showing the state at each step, which rule is being applied where, and perhaps all of the possible places that the current rule could match.
• Someone has proposed to port the interpreter to JavaScript; it would be nice to have an online "playground" where people can try things out in the browser and easily share small programs.

However, I will need to understand the project better before I'm able to do a good job of any of those. There are a few things which would be most helpful to elaborate on. Sorry that I have so many questions!

1. There are various node types mentioned in the readme; "exists" (I think this is called one in the XML format?), "forall", "rulenode" (does this mean either an "exists" or "forall" node?), "sequence node", "WFC node" and "Markov node" are mentioned, but there are also prl, path, map, convolution and convchain in the source code. I think I have figured out some of this by reading the source code and watching the GIFs, but it would be really helpful to have a comprehensive list of the node types with descriptions of their grammar (i.e. what parameters they have and what types of child node, if any, they have) and semantics (i.e. what does the node mean in a program).
2. Some of the GIFs show a GUI on the left, with different visual representations of each type of node; e.g. as far as I can tell, a single vertical line means a sequence node, and a double vertical line means a Markov node. But there are some I haven't decoded the meanings of yet, e.g. some rules have a solid horizontal line while others have a dashed horizontal line.
3. There are some rules which seem to have limits on how many times they can be applied, most notably in the River model. What is the scope of these limits, i.e. if a rule with a limit appears inside a node that can be executed multiple times, is the limit reset each time, or is the limit global? Or is it possible to choose where the counter gets reset?

The rest are somewhat less important technical points, but if you can explain then I would appreciate it. Understanding the implementation would be very helpful for writing my own implementation of the language.

Regarding inference, there's already another discussion thread asking for a blog post about this; if you do want to write a longer explanation of how inference works "under the hood", there are a few points I'd like to understand:

4. "Unidirectional constraint propagation for rewrite rules can be described equivalently in terms of rule propagation fields which generalize Dijkstra fields for arbitrary rewrite rules." I think that "rule propagation fields" are a new concept, at least I wasn't able to find any materials about them. It's also not clear to me what part of the source code corresponds with this concept. I understand Dijkstra fields but I don't see how you're generalising them.
5. "This allows to catch states where a crate is pushed to the wrong wall in Sokoban, or where the grid-covering walk splits the grid into 2 disconnected parts." These seem to be non-local constraints, but the pattern-rewriting rules only create local constraints, and it doesn't seem like you need the programmer to declare any non-local constraints for this to work. Is there some way for the algorithm to deduce non-local constraints (e.g. connectivity) from local constraints? What's going on?
6. "it's worth looking at the minimal number of turns required for constraint propagation to complete. This integer-valued heuristic is admissible, and we use it in A* search". Am I correct in thinking this is a lower bound, rather than the true minimum number of turns? How is the heuristic computed?

A couple more questions under "notes":

7. "When a rulenode is encountered for the first time, MJ interpreter uses a multidimensional version of the Boyer–Moore algorithm." From what I understand, the Boyer-Moore algorithm doesn't handle wildcards (the * symbol in a rule). How are you dealing with these? I ask because I have an idea for how to do this with DFAs which might be more efficient; particularly, it could handle all patterns in one search, and allow updates without re-doing the whole-grid search or checking the changed areas with a separate algorithm. I'm working on a proof-of-concept for it now.
8. "Stochastic relaxation. Markov nodes have a very nice representations as limits of differentiable nodes." It's not clear to me how this fits in with the implementation - it seems simpler to just represent Markov nodes as a list of child nodes, ordered by priority. What problem is this solving? "This means that one can find the optimal weights by gradient descent". What is this optimising for?

Again, sorry that I'm asking a lot! There's so much about this project that could do with more in-depth explanation, and I'd love to understand it well enough to write some of those explanations myself, but at the moment I think you are the only person who understands it well enough.

[mxgmn]

Great questions! I'll answer everything when I have time, next week probably.

[inkydragon]

Some exploration results:

• Node Type tree
  

Mapping of element names to node types in Node.cs

	Node result = xelem.Name.LocalName switch
        {
            "one" => new OneNode(),
            "all" => new AllNode(),
            "prl" => new ParallelNode(),
            "markov" => new MarkovNode(),
            "sequence" => new SequenceNode(),
            "path" => new PathNode(),
            "map" => new MapNode(),
            "convolution" => new ConvolutionNode(),
            "convchain" => new ConvChainNode(),
            "wfc" when xelem.Get<string>("sample", null) != null => new OverlapNode(),
            "wfc" when xelem.Get<string>("tileset", null) != null => new TileNode(),
            _ => null
        };

• Other Top level node attribute group:
  • Interpreter in Interpreter.cs
  • Grid in Grid.cs
  • symmetry in SymmetryHelper.cs

---

A problem I found while reading the code:
Although inheritance is used between the nodes, the properties are all read via xelem.Get, so you can only figure out which properties the node has by searching for calls to xelem.Get.

[mxgmn]

1. I listed types of nodes in syntax.md, I'll add to this document in the future.
2. Indeed, single vertical line = sequence node, double vertical line = Markov node, solid horizontal line = one node, dashed horizontal line = all or prl node.
3. Counter resets when the parent branch node becomes active.
4. It's easier to explain with an image, I'll make one soon.
5. Basically, non local constraints = local constraints + time. If you're familiar with WFC, I can explain it like this: we turn every MxN rewrite rule into an MxNx2 spacetime pattern, and do constraint propagation on these.
6. This heuristic is the lower bound for the number of turns required to turn state A into a state B, yes.
7. DFA would be cool. Though it only matters when a rule is encountered for the first time. Most of time savings are gained in continued matching of the same rule after a small change on the grid. I have some pattern-matching benchmarks in the end of models.xml, you can test on these if you'd like.
8. This paragraph is a comment for the "open problems" section.

Sorry for the brevity, I'll expand on this later.

[kaya3]

Thanks for your answers - I've figured out a bit more for myself in the meantime, and your answers help. Looking forward to anything you add.

Regarding DFAs, there is still a difference after the initial scan because you don't need separate DFAs for each pattern, two DFAs (or three for 3D grids) is enough for checking every pattern at the same time. As far as I can tell, the code in MarkovJunior checks each pattern separately so the running time scales with the number of different patterns. That said, checking patterns separately means that most of the checks will short-circuit quickly, so I doubt that DFAs will be much different except for programs which contain a large number of different patterns. I might have a go at adapting my DFA code to C#, to see how it compares.

[kaya3]

So, I've worked my way through the whole codebase and I think I've understood almost all of it; I've also written docs and some explanatory comments, so I'll be making a pull request soon, but I have a few more questions and observations relating to specific parts of the code:

9. In Convolution.cs#115, the condition checks rule.sums != null but then also assumes that rule.values != null. Perhaps the ConvolutionRule constructor should check at load time that if sums is present then values must be too.
10. In Map.cs#52, where the constructor loads a Rule, is there a reason that rule.original = true; should not be set, like it is in RuleNode.cs#48? This flag appears to only be used in the GUI, so perhaps it is irrelevant for map nodes (I'm not sure).
11. In Node.cs#73, branch.parent is set to null for map nodes and wfc nodes. If I understand correctly, this means that when one of these nodes completes, the whole MarkovJunior program completes. I think this is intended because these nodes replace the grid with one that potentially has a different size and alphabet, so any later nodes would be working in the wrong 'context', but it seems non-ideal from a language design perspective; I have some ideas about this which I'll save for another time, but I wanted to ask now if my understanding is correct.
12. In Observation.cs#101, rule.binput is used when computing backwards potentials. If the rule's input pattern contains any unions, then I believe this array has only the first colors from those unions; this seems to mean that the ForwardMatches method could sometimes return false when the rule could be matched by a different color from the union.
13. Likewise in Observation.cs#122, I'm not sure what the correct way of dealing with unions is, but intuitively it doesn't seem right to treat the first color differently, particularly when a wildcard is also treated differently to a union of all colors (which ought to be equivalent) on line #135.
14. In OverlapModel.cs#86, is there a reason not to use SymmetryHelper here? I understand that you don't want to deduplicate symmetries to avoid biasing the weights, but I think the same (q1, q2) => false trick as in ConvChain.cs#63 should work.
15. In Search.cs#241, the loop uses IMX and IMY instead of OMX and OMY to check bounds in rule.output, and copies from rule.output to the grid state without checking for 0xff. I think these are mistakes?
16. In Search.cs#269, the priority of a node in the A* search is computed using forwardEstimate + backwardEstimate, where normally it would be distance from start + heuristic distance to goal. I think forwardEstimate serves the role of "distance from start" here, but it's also a heuristic, whereas depth is the exact number of steps it took to reach this node. I have some idea about why you use forwardEstimate instead of depth, but it's difficult for me to explain; I think it's because the estimates are computed by summing over all grid cells instead of taking a maximum, so the estimates have the wrong 'scaling' compared to depth, if that makes sense to you. Edit: I've realised this is incorrect, in fact both forwardEstimate and backwardEstimate are heuristic distances to the goal, and the 2.0 * depthCoefficient * depth term encompasses the "distance from start", though it's adjustable by depthCoefficient. I think there is still something I need to understand about this but I'll think about it some more.

[mxgmn]

10. Turns out map nodes don't work with GUI at all. I'll fix this in the next commit.
11. Your understanding is correct. Would gladly hear other ideas on how to approach this.
13. It's true, the current inference code doesn't work correctly with unions.
14. Yep, thanks! I added this helper function to ConvChain, but forgot that I have similar code in WFC to replace.
15. IMX and OMX are only different in map-rules, but I agree that OMX is better here, I'll replace it. I haven't thought about search with wildcards yet. Would Enumerate(...) work with wildcards / unions?
16. Forward estimate propagates from the current state and compares the resulting field with the goal, backward estimate propagates the field from the goal and compares it with the current state.

[kaya3]

Thanks so much again for your answers!

I'm not sure about search with wildcards in an input pattern, but e.g. the rule (WB=*W) with a wildcard in the output pattern is equivalent to (WB=WW) so it ought to be treated the same in inference and search. I think the simplest solution for this kind of "trivial" wildcard is to replace it in the output pattern when the rule is loaded in the first place, so even if the rule is written as (WB=*W) in the source, output would contain WW instead of {0xff}W.

Of course when it's reversed, (*W=WB) is definitely not equivalent to (WW=WB), and I think this entails some logical difference between computing forward vs. backward potentials when non-trivial wildcards or unions are involved, beyond just choosing binput or output based on a boolean flag. I will think more about this later.