[~/projects/modal]$ cat info
Modal: A Term-Rewriting Language
Q: What is Modal?
A: Modal is a language based on term rewriting,
a model of computation that uses pattern matching
and replacement to rewrite trees.
Q: How do I write code in Modal?
A: All Modal code is represented as a series of rules
applied to a given tree. This tree, formatted textually
as tokens delimited with parenthesis, gets continually
modified until no rules match any given part of the tree.
A: Let me explain.
Modal is a language based on term rewriting. If you've
ever used find/replace in a text editor, you can think of Modal
as being a tool that performs find/replace operations over trees,
formatted in a style similar to S-expressions.
Your code in Modal is formatted in terms of rules. The syntax
is as follows:
define (<pattern>) (<replacement>)
A pattern/replacement can be:
A sequence of the above, delimited by parentheses:
(foo bar baz)
(foo ?bar baz)
(foo (bar baz) ?quux)
foo (bar (baz))
A replacement can only use variables that have been used in
a pattern. When a variable is used in a pattern, and when we try
to match a given tree with a pattern, any variables are bound to their
corresponding tokens/sequences in said tree.
For example, consider the following:
define (square ?x) (?x * ?x)
This defines a rule with the pattern `square ?x`. Let's try to
apply this pattern to a given tree.
square (square (25))
Upon feeding this particular tree to Modal, Modal will run through
the list of rules that have been defined and try to match each rule's pattern
with the tree. Modal will crawl along the tree using a hybrid of depth-first
and breadth-first search. When Modal tries to apply the rule to the above tree,
...is bound, and it now has the value...
From here, now that Modal has found a match, it eliminates part of the
tree that it matched and replaces it with the right-hand side of a given rule.
If the above rule is applied, we end up with a new tree:
(square (25)) * (square (25))
From here, we run through our defined rules once more, and we end up with
the following tree:
((25) * (25)) * ((25) * (25))
This is then further reduced using built-in operations. I encourage you to
try it for yourself. Modal always works on a single global tree, and patterns
are applied to various points in that tree. Modal traverses the tree by storing
its textual form in a queue, and at any given moment, Modal tries to match the
head of that queue with a rule from its supplied ruleset.
Q: How do I write common structures, like loops, conditional statements, etc.?
A: Loops map to recursive patterns, and because Modal has a "loose" syntax,
you can write your own control flow structures.
Let's go through an example.
define (if (true) ?branch) (?branch)
define (if (false) ?branch) ()
define (if/else (true) ?true ?false) (?true)
define (if/else (false) ?true ?false) (?false)
The above patterns define both a single and double branch expression.
The latter is an example of a ternary statement, where the 'else' branch is
always required. These two control structures can be combined with boolean
operations, as defined below.
define ((true) and (true)) (true)
define ((true) and (false)) (false)
define ((false) and (true)) (false)
define ((false) and (false)) (false)
define ((true) or (true)) (true)
define ((true) or (false)) (true)
define ((false) or (true)) (true)
define ((false) or (false)) (false)
define (not (true)) (false)
define (not (false)) (true)
The above defines truth tables for conditional statements. We can use
these in conjunction with if and if/else to form arbitrarily nested conditions.
(true) and ((false) or (true))
(true) and (true)
Here's the above, in a more compact form.
((true) and ((false) or (true)))
((true) and (true))
However, there's a problem. Due to Modal's queue-based execution,
if the condition for if and if/else isn't fully reduced to 'true' or 'false',
Modal skips over it entirely and evaluates the branches. This leads to some
unexpected behavior, as you end up performing unneeded calculations and
selecting between them at a later point.
It's possible to circumvent this. By defining multiple patterns,
you can use Modal's pattern matching features to perform conditional checks.
Let's try to define the factorial pattern using this method.
define (factorial (num 1)) (num 1)
define (factorial (num ?x)) ((num ?x) * (factorial ((num ?x) - (1))))
Here, we've written two possible branches for our factorial pattern
in the form of two rules. Since Modal will always use rules defined prior
in the ruleset, we can organize rules according to priority, such that
earlier rules match prior to later ones. This allows us to write
complex conditionals that would otherwise be impossible to write properly.
I hope this has inspired you to give Modal a try. This was a small
taste of what Modal has to offer. Modal's prelude (prelude.modal) includes
a lot of built-in rules that you can use when writing code. It also includes
some examples of custom syntax.