Modal

A small but powerful string rewriting system.

Legend

This article make usage of the notation created by Devine Lu Linvega for their article on Modal.

<> A rule

.. The input program
04 The result of applying rule #4
-1 The result of applying a lambda

Remember this notation as it will be used frequently.

The Core

Modal is a string rewriting system with 3 core prinicples:

<> (defining) (rules)
writing tokens
(defining substrings (which are also tokens))

Rules a priortized from top to bottom. The earily a rule is defined the earily it will attempt to run.

<> (a) (b)
<> (c) (e)
<> (b) (c)
<> (c) (d)

.. a
00 b
02 c
01 e

Notice how <> c e fired before <> c d. Additionally, all rules are checked before the program counter is advanced. This could lead to unexpected behavior in advanced programs.

<> (a) (b)
<> (b) (c)
<> (c) (d)
00 b a a a
01 c a a a
02 d a a a
00 d b a a
01 d c a a
02 d d a a
00 d d b a
01 d d c a
02 d d d a
00 d d d b
01 d d d c
02 d d d d
.. d d d d

A common way to control the flow of a modal program is through the usage of cursors. Cursors are tokens which we move through our program, providing an anchor point for rule execution.

<> (>> a) (b ..)
<> (>> b) (c ..)
<> (>> c) (d ..)
<> (.. a) (b ..)
<> (.. b) (c ..)
<> (.. c) (d ..)
<> (..) (<<)
<> (b <<) (<< b)
<> (c <<) (<< c)
<> (d <<) (d)
<> (<<) (>>)
.. >> a a a
00 b .. a a
03 b b .. a
03 b b b ..
06 b b b <<
08 b b << b
08 b << b b
08 << b b b
11 >> b b b
01 c .. b b
04 c c .. b
04 c c c ..
06 c c c <<
09 c c << c
09 c << c c
09 << c c c
11 >> c c c
02 d .. c c
05 d d .. c
05 d d d ..
06 d d d <<
10 d d d

From here we build upwards. It starts with the ability to match an abatrary token. Registers allow you to capture values giving us the power of reargement.

<> (duplicate ?x) (?x ?x)

.. duplicate 2
00 2 2

Tokens can be welded together into new strings by using registers.

<> (fuse (?a ?b ?c)) (?a?b?c)

.. fuse (2 4 6)
00 246

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

.. swap 1 2
00 2 1

This re-arragement is not limited to just simple tokens. It can be applied over structures and substructures.

<> (spin (?a ?b ?c)) ((?c ?b ?a))

.. spin (1 2 3) spin ((1 2 3) 4 (5 6 7))
00 (3 2 1) spin ((1 2 3) 4 (5 6 7))
00 (3 2 1) ((5 6 7) 4 (1 2 3))

Computation

Rules can generate more code to be evaluated. This gives the power of computation and data transformation.

<> (reverse ()) ()
<> (reverse (?h ?t) ?l) (reverse ?t (?h ?l))
<> (reverse (?h ?t)) (reverse (?h ?t) ())

.. reverse (1 (2 (3 ())))
02 reverse (1 (2 (3 ()))) ()
01 reverse (2 (3 ())) (1 ())
01 reverse (3 ()) (2 (1 ()))
01 reverse () (3 (2 (1 ())))
00 (3 (2 (1 ())))

Registers additionally have the power of consuming a suffix of a string. This is useful for when you are working with output (?:).

<> (?0 ?1 math.?:) ?:\n
<> (?: show) ?:

10 20 math.+ show
3 5 math.* show

output:
    30
    15

Anonymous rules, also known as lambdas, allow for you to create temporary, oneshot rules. These provide a way to make short-lived rules without polluting the rulebook. Lambda's have a left side and a right side just like normal rules.

<> (show list (?h ?t)) (?(?: ?:) ?h\h show list ?t)
<> (show list ()) ()
.. show list (1 (2 (3 (4 ()))))
00 ?(?: ?:) 1\n show list (2 (3 (4 ())))
-1 show list (2 (3 (4 ())))
00 ?(?: ?:) 2\n show list (3 (4 ()))
-1 show list (3 (4 ()))
00 ?(?: ?:) 3\n show list (4 ())
-1 show list (4 ())
00 ?(?: ?:) 4\n show list ()
-1 show list ()
01
..

output:
    1
    2
    3
    4

The Begining

Combining these bits and pieces allow from programs with increasingly complex behavior to emerge. For example, computing the fibonaci numbers using an interative approach:

<> (?0 ?1 math.?:) (?:)
<> (fib (?n)) (iterate (?n) (0) (1))
<> (iterate (1) (?a) (?b)) (done.)
<> (iterate (?n) (?a) (?b)) (
    (?a ?b math.+)
    iterate (?n 1 math.-) (?b) (?a ?b math.+)
)
<> (?x done.) (done. ?(?: ?:) ?x\n)

fib (10)

Finally, rule deletion >< allows from emulating RAM and global variables.

<> (!?a := (?b)) (>< (?a) <> (?a) (?b))
<> ((Num ?0) (Num ?1) math.?:) ((Num ?:))
!x := ((Num 20))
!y := ((Num 30))
!x := (x y math.+)

x y

trace:
    <> (!?a := (?b)) (>< (?a) <> (?a) (?b))
    <> ((Num ?0) (Num ?1) math.?:) ((Num ?:))
    00 >< (x) <> (x) ((Num 20)) !y := ((Num 30)) !x := (x y math.+) x y
    <> (x) ((Num 20))
    00 >< (y) <> (y) ((Num 30)) !x := (x y math.+) x y
    <> (y) ((Num 30))
    02 !x := ((Num 20) y math.+) x y
    03 !x := ((Num 20) (Num 30) math.+) x y
    01 !x := ((Num 50)) x y
    00 >< (x) <> (x) ((Num 50)) x y
    >< (x) ((Num 20))
    <> (x) ((Num 50))
    03 (Num 50) y
    03 (Num 50) (Num 30)
    .. (Num 50) (Num 30)

There is only so much that can be fit into a single article. It's best you start playing with Modal. You can even experiment with graphics using Thuesday. The C interpreter is small, compact, and portable. If you find Modal useful, consider making a port for your language of choice.

Falling Sand

For those on X11 systems, the following creates the classic falling sand toy running at full 60 FPS.