MarkovJunior syntax proposal

[kaya3]

I started thinking about a simpler syntax for MarkovJunior programs, because at least personally I think XML is a bit tedious to write, and a parser based on XML will silently ignore any tags or attributes it doesn't look for, which may make it harder to notice mistakes (particularly when an attribute is added to the wrong tag, or misspelled). And because designing languages is fun.

Comments and suggestions from everyone interested in MarkovJunior are appreciated! I'll illustrate the syntax with examples below, translated from the example models. I'm doing this for my own project mainly, but @mxgmn if this is something you're interested in, I'd be happy to write a parser for the official MarkovJunior project in C# once this syntax is complete and set in stone. (No worries if you don't think this would be a good idea.)

Backtracker

# Generates connected cave systems with pools.

values [BRWU]

once: origin -> (R)
markov:
    one: (RB) -> (WR)
    one: (RW) -> (UR)

BacktrackerCycle

# Generates a random cycle.

values [BRGWA]

once: origin -> (R)

markov:
    one: (RBB) -> (GGR)
    one: (RGG) -> (WAR)

once: (R) -> (W)
once: (WBW) -> (WAW)
all: (A) -> (W)
all: (BBB/BWB) -> (.../.B.)

BasicBrickWall

values [BWO]
symmetry "x"

all: (B/.) -> (O/.)
all: (O/./.) -> (W/./.)

markov:
    all: (BW) -> (BB)
    one: (W/W/W/W/W/W/W/W) -> (./././B/./././.)

one: (OOOOOOOO/BBBBBBBB) -> (...B..../........)

markov:
    symmetry "xy" @ all: (OW) -> (.O)
    all: (OO/OB) -> (.B/..)
    one: (OOOO/BBBB/OOOO) -> (..B./..../....)
    one: (WW/BB/OB) -> (.O/../..)

BasicDijkstraDungeon

values [BGW]

legend [BW]
let roomIn | roomOut = load "BasicDijkstraRoom.png"

once: roomIn -> roomOut
all: (W) -> (G)

markov:
    all: (GW) -> (GG)
    path {from=[W], to=[G], input=[B], output=[G], inertia=true}
    one: roomIn -> roomOut

BasicSnake

values [BWDPGR]

once: origin -> (W)

all:
    (WBB) -> (..D)
    (DBB) -> (..D)

one: (WBD) -> (PGR)
one {limit=2}: (RBD) -> (GGR)
one {limit=15}: (D) -> (W)

markov:
    one: (RBW) -> (GGR)
    all:
        (RBD) -> (GGR)
        (PGG) -> (DBP)

A few notes on some of the design decisions:

• The syntax is inspired by Python, so blocks are denoted by indentation rather than delimiters, and statements are terminated by newlines instead of semicolons. I like this, but I know not everyone does. It would be possible to use {} for blocks if arguments like limit=2 were written without delimiters, or with () delimiters (although that would make tokenization harder because it conflicts with patterns); another option would be to use keywords like endall, endmarkov etc., though I'm not a fan of this.
• The root is a sequence node, instead of a Markov node by default. This is consistent with other imperative languages, which most programmers are used to. Sequences can be nested in Markov nodes by writing sequence:, though this doesn't occur in the examples above.
• I chose . instead of * for wildcards; this is consistent with regexes, a bit visually clearer IMO, a bit easier to type on many keyboards, and avoids having /* or */ occur inside patterns (which can be a pain when writing patterns inside strings in another language, where those delimit comments).
• once is syntax sugar for one {limit=1}.
• I made origin a special pattern which matches at the centre of the grid, instead of a boolean flag. This means you can rewrite origin with any pattern (not just a colour in one cell), anywhere in the program. Semantically, an origin -> ... rule returns false if the output pattern is already present, so there is no infinite loop if it's used in a markov node. In principle, rules could allow other position-based input patterns (this would require some syntax for describing positions).
• The grammar can be parsed without looking more than one token ahead.

I'm also writing a parser for this syntax, for my own project, and to make sure it works from an implementer's perspective. Including type definitions, it's currently at about 530 lines of TypeScript code, and can successfully parse all of the examples above. It would be good to get feedback about the syntax before doing much more work on it, though.

[mxgmn]

Nice! I considered LISPy syntax and Python-like syntax for MarkovJunior but in the end I chose XML because it was good enough and I don't have to write/maintain a parser for it.

[kaya3]

I might have gone ever so slightly overboard with this, and now it has expressions with unary and binary operators, which allows for an elegant and very generalisable way to describe e.g. convolution rules. At this point I suppose I should just accept that I'm designing a spinoff language that's very heavily based on MarkovJunior but with different semantics.

Cave

values [DA]

prl: (.../.D./...) -> (.../.A./...)
prl {limit=1, p=0.435}: (A) -> (D)

convolution {kernel="Moore"}:
    (A) -> (D) if sum [D] >= 5
    (D) -> (A) if sum [A] >= 6

all: (AD/DA) -> (AA/DA)

[TieSKey]

My 2 cents about the topic.
Current implementation has a lot of hidden/implicit conventions on which attributes must be present which what others. I think fixing that would be the most valuable approach first.
One of the most important things for a "language" is clear and explicit rules (BNF https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form). A clean and clear syntax might look really good but be hard to write and even harder to maintain/modify.
Another important point is the scope of the project. Do we want to bear the burden of implementing and maintaining a parser? What happens if someone wants to migrate the project to another language? they would need to also migrate the parser.

I think the most agnostic and versatile solution would be to adjust the objects/structs to be readily serializable by out of the box solutions like xmlserializer and newtonsoft.json. For the most part it would only require to decorate classes and properties with DataContract and DataMember attributes. This would provide a language agnostic format that can be easily accessed from almost anywhere, a very significant load time boost and would eliminate the need for maintaining a parser.

XML is verbose but it would allow us to define a XSD so smart editors can catch mistakes (and suggest/autocomplete).

Alternatively, JSON Schema might be a less verbose solution (http://json-schema.org) (not sure about editor support).

Personally, I rather have a very verbose syntax that can warm me about errors beforehand than a nice and fast to write one that has the potential to waste a ton of my time later trying to catch a silly error.

[kaya3]

Thanks for your thoughts. At this point I'm treating this as a different language which is heavily inspired by MarkovJunior, so think of it less as a proposal for this project and more as a proposal for a language in the same paradigm as MarkovJunior, which people might be interested in.

The main reason I want a simple syntax is I think, moreso than for other language paradigms, writing a program in this paradigm involves a lot of trial and error, so being able to change the code quickly seems important. That said, another big benefit of a Python-style syntax is that it's actually very easy to parse - the parser never has to peek at more than the next token, and never has to backtrack. This also means that syntax errors occur where the mistake is, not far away after a failed parse of something ambiguous. In the process of writing my compiler I've also found it very easy to modify the syntax when needed, or when I think of a way to improve it.

For the purpose of writing the parser, I do have a PEG written for most of the grammar, the only part I didn't specify in the PEG is operator precedence; I think a precedence table is a better way of communicating the grammar for unary and binary operator expressions, but when I release my compiler I will probably incorporate this into the PEG for completeness if nothing else.

[TieSKey]

There should be automatic parsing code generators for that PEG. If not, I strongly suggest going for a BNF which have (a ton) of parser generators that produce efficient results for a ton of different languages (they are usually called "compiler compilers"/"CC"/:"YACCs"). That means your only concern is the grammar definition and u don't need burden with actually writing code (and be exposed to bugs).

[kaya3]

I'm aware of parser-generators but I prefer to write my parsers by hand. Recursive descent parsers for LL(1) languages are straightforward to write by hand, since they don't backtrack, and this also makes them efficient. My main issue with generated parsers is that they require an extra step to transform the parse tree into the AST, whereas a hand-written parser can output the AST directly. Anyway, the parser itself (excluding type definitions) is only a few hundred lines of code, and it's relatively simple compared to the rest of the compiler, so for my own project I'm not really concerned about its complexity.

[kaya3]

Incidentally, @mxgmn - the working name for my language is MJr, which is (obviously) an abbreviation of MarkovJunior. If you think this is too similar and people could confuse them for the same project, let me know and I'll think of a different name.

[mxgmn]

Fine by me!

[Yuu6883]

My 2cents on the topic is pretty similar to @TieSKey's

XML is good enough for this project since XML is tree-based just like MJ.
Specifying a new language syntax and actually implementing an entire toolchain feels like reinventing wheels when the current code/xml is already pretty good at it in terms of readability and usability. I'm not too worried about load time since it only takes up maybe 0.01% of the total runtime anyways. What I would rather work on is defining an XSD mentioned above that can catch basic syntax errors, and refactoring the node classes to be XML agnostic.

From my experience with this project, my main concern with the current XML syntax is just it's too "abstract" when it comes to defining input/output patterns. My brain can only remember so many letters and what I'm using them for and what pixel/voxel they actually represent; not mentioning a large pattern would probably need to be imported from a png/vox file which adds another layer of complexity to the creation of an MJ model. That's why I think a more visual approach would truly boost productivity instead of inventing another syntax, which is why I want to work on a visual editor for my web version when I have time.

Another thing I would love to make if I could work full-time on this project would be to make an interpreter & compiler in C/C++ that can run directly or generate executable/static lib/shared lib from an MJ model, making it a true MJ program and it would get a huge performance gain since pattern matching code can be inlined and unrolled in contrast to current slow nested-loop generic implementation.

[kaya3]

A visual approach would be really neat, and would be great for making the project accessible to artists and designers who aren't necessarily as comfortable with text-based computer languages.

Regarding a compiler, I'm working on it! In its current state, it's functional for simple programs (markov, sequence, one, all and prl, with support for limits and rule conditions like random < 0.5) but not ready for initial release yet (maybe in a few weeks). My compiler is written in TypeScript, though, not C/C++. In principle it would be possible to load MarkovJunior programs from the existing XML syntax and feed those into it, too.