Modal

Modal is a matrioshka language based on pattern-matching to rewrite trees.

Modal programs are represented as a series of rules, formatted as tokens delimited by brackets and parentheses, applied to a given tree which gets continually modified until no rules match any given part of the tree.

To define a new rule, start a line with <>, followed by two tokens. The program evaluation starts at the first character of the string and walks through to the end trying to match a transformation rule from that location:

<> hello bye

.. hello world
00 bye world

A new rule definition syntax can also be created to suit a specific notation, for instance, here is a rule to define new rules with an infix syntax:

<> ((?x -> ?y)) (<> ?x ?y)
(a -> apple)
(b -> banana)
((apple banana) -> (fruit-salad))

.. a b
01 apple b
02 apple banana
03 fruit-salad

Registers are a single character identifier bound to an address in a pattern used in rewriting:

<> (copy ?a) (?a ?a)

.. copy cat
00 cat cat

When a register is used in a pattern, and when we try to match a given tree with a pattern, each register is bound to a corresponding an address and referenced in either side of a rule:

<> (swap ?x ?y) (?y ?x)

.. (swap fox rat)
00 (rat fox)

When a register appears more than once in a rule, each instance is bound to the first address:

<> (?x ?x) same

.. (fox fox)
00 (same)

Sequences

This allow programs to mimic other programming languages. Any choice made in regard to syntax beyond this point is completely arbitrary. To demonstrate, the following code defines a concatenative syntax:

<> (?x dup) (?x ?x)
<> (?x ?y swap) (?y ?x)
<> (?x pop) ()

.. (1 2 3) (4 5 6) swap pop dup
01 (4 5 6) (1 2 3) pop dup
02 (4 5 6) dup
00 (4 5 6) (4 5 6)