The Hev Programming Language

Introduction

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!

Syntax

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...

Semantics

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.

Execution Model

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.

Miscellaneous Notes

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.

Implementation

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?

History

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