Hey, does this thing look at all familiar?
() [] -> . ++ -- Left to right
++ -- + - ! ~ * & (type) sizeof Right to left
* / % Left to right
+ - Left to right
<< >> Left to right
< <= > >= Left to right
== != Left to right
& Left to right
^ Left to right
| Left to right
&& Left to right
|| Left to right
?: Left to right
= += -= *= /= %= &= ^= |= <<= >>= Right to left
, Left to right
That's right: it's the precedence table for operators in the C language.
OK, some of them (like ()) are pretty easy to remember, I guess, but
the logic behind most of these choices escapes me. Really, can you give
me a good reason for why & should have a higher precedence than |?
And why is ^ in-between? And why in the world are -> and ++ on the
same level? What I'm getting at is, how many times did you have to go
and reference this chart before these arbitrary rules got burned into
your nervous system somewhere between your brain and your fingers?
And hey, you think that's bad? Perl 5 has like 129 operators at like 24 levels of precedence.
You may well ask: is there something that can save us from this insanity?
Yes, there is. In this document I will describe Hev, a novel, nay, innovative, nay, radical, nay, revolutionary, nay, totally gnarly new programming language which provides the infix you love with an unlimited number of operator precedence levels and absolutely no need for parentheses or memorization!
Sound too good to be true...? Read on!
Hev's breathtaking syntactic slight-of-hand is accomplished by a synergistic combination of two features:
- Have an unbounded number of infix binary operators.
- Make precedence explicit.
To fit this bill, all we need is a single syntactic construct that can explicitly express an unbounded number of discrete operators, and at the same time, their precedence.
Well, I chose integers.
Positive integers, to be precise. So 3 is an infix operator. So is
15, and it has a higher precedence than 3. So is 514229, and it
has an even higher precedence than 15, but lower than
25852016738884976640000. See how easy it is? I can just name two
operators at random, and you can tell me which one has the higher
precedence without a second thought!
Oh, but what good are operators if they don't have anything to operate on? We need values, too. And since we have an unbounded number of operators, there's a certain sense to having only a bounded number of values.
Well, why not the logical extreme: no values at all? Well, OK, for the
sake of syntax we need to have one value, but since there's nothing it
can be differentiated against, it's effectively no values.
Syntactically, this value, or lack thereof, is denoted ,. (Yeah,
that's a comma.)
And, we'll probably need variables at some point, too, I'm guessing. We
should probably have a nice big supply of those, just so we don't run
into some artifical bound at some point that arbitrarily prevents Hev
from being Turing-complete. So, let's say that any string of consecutive
symbols drawn from +, -, * and / is an identifier for a
variable. That should do nicely.
There's still a bit of a problem, though -- those pesky parentheses. You
might need to nest a 5-expression into the LHS or the RHS of a
3-expression, and that would seemingly require parentheses. How do we
avoid this? Well -- if we're flexible on what 3 and 5 actually
mean, maybe we can just avoid this dilemma entirely! This brings us
to...
So we have all these infix binary operators, and this one value which I insist is essentially a non-value, and we need to be able to make something sensible out of this mess -- without using parentheses to do nesting.
Well, what can we build?
Trees.
Yep, binary trees. They're a bit unlike the "normal" trees of Computer Science, which almost universally have some sort of values stored at their leaves. These ones don't. They're just... you know, trees. But we can definately build them. And we don't need any parentheses. If you want to nest some expression inside another, you just pick operators with higher precedence levels for that expression.
So ,5,10,5, is a tree - a complete binary tree with 3 levels - a root
node (10), two intermediate nodes (both 5) and four leaves (,,,,)
with no values in them (or a single, meaningless value, repeated four
times, if you like.) And please realize that this is the same tree as
,1,3,2, -- it's just that different operators were used to construct
it. Those operators aren't "in" the tree in any sense, and their
magnitude is used only to determine their precedence.
But now for the splendid part. We can put variables in these trees! Which means, we can think of them as patterns that can match other trees. Which means, we can specify rules as pairs of patterns and substitutions, to be substituted in when the pattern matches. Which means, we can construct a rule-based language! A rewriting language, in fact. I think I'll call this approach valueless tree rewriting.
So, for example, the tree +10* matches that tree ,5,10,5, given
above. The variables + and * both unify with ,5,. But note that
this pattern matches ,41,76, too, where + unifies with ,41, and
* unifies with ,. And in fact it matches countless other possible
valueless trees.
A Hev program consists of a valueless binary tree. The left branch of
the root leads to a ruleset; the right branch leads to a valueless
binary tree which represents the data of the program: it is the state of
the program, the thing that is being rewritten. This data tree may not
contain any variables: the leaves must be entirely ,'s.
A ruleset consists of a node where the left branch leads to either a
ruleset or to a , and the right branch leads to a rule. A rule is a
node where the left branch is a pattern and the right branch is a
substitution. The pattern is a valueless binary tree which may contain
not only ,'s but also any variables at its leaves. The substitution
may contain both ,'s and variables, but it may not contain any
variables which do not appear in the corresponding pattern of the rule.
Each rule in the ruleset is considered in turn, starting with the rule nearest the root. The pattern of the rule is matched against the data tree. The structure of the tree must match some subtree of the data tree; a variable can match any structure of the data tree, but no variable can match two different structures. (The same variable identifier may appear multiple times in a pattern; all instances of that variable must match the same structure.) If there are multiple subtrees of the data tree that match, only the topmost one is considered. This is usually called "top-down rewriting".
When a match occurs, the substitution of the rule is instantiated. Any variables occuring in the substitution are replaced with the structures that those variables matched in the pattern. (This is why all the variables appearing in the substitution must also appear in the pattern.) The data tree is then modified: the subtree that was matched is removed and in its place the instantiated substitution is grafted. The process then repeats (starting over with the topmost rule.)
When a rule fails to match, the data tree is left alone and the next rule (one node lower down in the ruleset) is tried. When there are no more rules to try in the ruleset, the program ends.
You can leave out the , at the very beginning and very end of a Hev
program. It's implied. Also, whitespace is allowed, even between the
digits of an operator or the symbols of a variable... for whatever good
it'll do you.
hev.hs is a reference implementation of Hev in Haskell. It can be used
as something to check this language description against - any
discrepancy is either a bug in the implementation, or an error in this
document. hev.hs shouldn't be used as an official reference for Hev
behaviour that's not described in this document, but heck, it's better
than nothing, right?
It was sometime in November of 2005 when I came up with the idea to try to "break the precedence barrier" and started writing Hev. I continued to refine the idea and worked on it, on and off, after that. In October of 2006 I got a stubborn notion in my head that the parser should only make one pass over the program text, so I wasted a day trying to figure out how to code that in Haskell. In June of 2007 I finally got down to writing test cases and debugging it.
Happy ,!
-Chris Pressey
Cat's Eye Technologies
June 17, 2007
Vancouver, BC