Commits

Anonymous committed 2f7c70c

Convert documentation to Markdown.

  • Participants
  • Parent commits c4812ab

Comments (0)

Files changed (2)

File README.markdown

+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

File doc/hev.html

-<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
-<head>
-<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
-<title>The Hev Programming Language</title>
-  <!-- begin html doc dynamic markup -->
-  <script type="text/javascript" src="/contrib/jquery-1.6.4.min.js"></script>
-  <script type="text/javascript" src="/scripts/documentation.js"></script>
-  <!-- end html doc dynamic markup -->
-</head>
-<body>
-
-<h1>The Hev Programming Language</h1>
-
-<h2>Introduction</h2>
-
-<p>Hey, does this thing look at all familiar?</p>
-
-<pre>()  []  -&gt;  .  ++  --                        Left to right
-++  --  +  -  !  ~  *  &amp;  (type)  sizeof     Right to left
-*  /  %                                      Left to right
-+  -                                         Left to right
-&lt;&lt;  &gt;&gt;                                       Left to right
-&lt;  &lt;=  &gt;  &gt;=                                 Left to right
-==  !=                                       Left to right
-&amp;                                            Left to right
-^                                            Left to right
-|                                            Left to right
-&amp;&amp;                                           Left to right
-||                                           Left to right
-?:                                           Left to right
-=  +=  -=  *=  /=  %=  &amp;=  ^=  |=  &lt;&lt;=  &gt;&gt;=  Right to left
-,                                            Left to right</pre>
-
-<p>That's right: it's the precedence table for operators in the C language.
-OK, some of them (like <code>()</code>) are pretty easy to remember, I guess,
-but the logic behind most of these choices escapes me.
-Really, can you give me a <em>good</em> reason for why <code>&amp;</code>
-should have a higher precedence than <code>|</code>?  And why is <code>^</code> in-between?
-And why in the world are <code>-&gt;</code> and <code>++</code> 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?</p>
-
-<p>And hey, you think that's bad?  Perl 5 has like 129 operators at like 24 levels of
-precedence.</p>
-
-<p>You may well ask: is there something that can save us from this insanity?</p>
-
-<p>Yes, there is.  In this document I will describe Hev, a <del>novel</del> <del>innovative</del>
-<del>radical</del> <del>revolutionary</del> totally gnarly new programming
-language which provides <strong>the infix you love</strong>
-with <strong>an unlimited number of operator precedence levels</strong>
-and <strong>absolutely no need for parentheses or memorization!</strong></p>
-
-<p>Sound too good to be true...?  Read on!</p>
-
-<h2>Syntax</h2>
-
-<p>Hev's breathtaking syntactic slight-of-hand is accomplished by a
-synergistic combination of two features:</p>
-
-<ul>
-<li>Have an unbounded number of infix binary operators.</li>
-<li>Make precedence explicit.</li>
-</ul>
-
-<p>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.</p>
-
-<p>Well, I chose integers.</p>
-
-<p>Positive integers, to be precise.  So <code>3</code> is an infix operator.
-So is <code>15</code>, and it has a higher precedence than <code>3</code>.
-So is <code>514229</code>, and it has an even higher precedence
-than <code>15</code>, but lower than <code>25852016738884976640000</code>.
-<em>See</em> 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!</p>
-
-<p>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.</p>
-
-<p>Well, why not the logical extreme: <em>no values at all</em>?  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 <code>,</code>.  (Yeah, that's a comma.)</p>
-
-<p>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 <code>+</code>, <code>-</code>, <code>*</code> and <code>/</code>
-is an identifier for a variable.  That should do nicely.</p>
-
-<p>There's still a bit of a problem, though -- those pesky parentheses.
-You might need to nest a <code>5</code>-expression into the LHS or the RHS
-of a <code>3</code>-expression, and that would seemingly require parentheses.
-How do we avoid this?  Well -- if we're
-flexible on what <code>3</code> and <code>5</code> actually <em>mean</em>,
-maybe we can just avoid this dilemma entirely!  This brings us to...</p>
-
-<h2>Semantics</h2>
-
-<p>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 --
-<em>without</em> using parentheses to do nesting.</p>
-
-<p>Well, what can we build?</p>
-
-<p>Trees.</p>
-
-<p>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.</p>
-
-<p>So <code>,5,10,5,</code> is a tree - a complete binary tree with 3 levels -
-a root node (<code>10</code>), two intermediate nodes (both <code>5</code>)
-and four leaves (<code>,,,,</code>) with no values in them (or a single,
-meaningless value, repeated four times, if you like.)  And please realize that
-this is the <em>same</em> tree as <code>,1,3,2,</code> -- 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.</p>
-
-<p>But now for the splendid part.
-We can put <em>variables</em> in these trees!  Which means, we can think of them
-as <em>patterns</em> that can match other trees.  Which means, we can specify <em>rules</em>
-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 <dfn>valueless tree rewriting</dfn>.</p>
-
-<p>So, for example, the tree <code>+10*</code> matches that tree
-<code>,5,10,5,</code> given above.  The variables <code>+</code>
-and <code>*</code> both unify with <code>,5,</code>.
-But note that this pattern matches <code>,41,76,</code> too,
-where <code>+</code> unifies with <code>,41,</code> and
-<code>*</code> unifies with <code>,</code>.
-And in fact it matches countless other possible valueless trees.</p>
-
-<h2>Execution Model</h2>
-
-<p>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 <code>,</code>'s.</p>
-
-<p>A ruleset consists of a node where the left branch leads to either a ruleset
-or to a <code>,</code> 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 <code>,</code>'s
-but also any variables at its leaves.  The substitution may contain both
-<code>,</code>'s and variables, but it may not contain any variables which do
-not appear in the corresponding pattern of the rule.</p>
-
-<p>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 <strong>topmost</strong> one is considered.  This is usually called
-"top-down rewriting".</p>
-
-<p>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.)</p>
-
-<p>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.</p>
-
-<h2>Miscellaneous Notes</h2>
-
-<p>You can leave out the <code>,</code> 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.</p>
-
-<h2>Implementation</h2>
-
-<p><code>hev.hs</code> 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.  <code>hev.hs</code> 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?</p>
-
-<h2>History</h2>
-
-<p>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.</p>
-
-<p>Happy <code>,</code>!</p>
-
-<p>-Chris Pressey
-<br />Cat's Eye Technologies
-<br />June 17, 2007
-<br />Vancouver, BC</p>
-
-</body>
-</html>