Shrubbery Notation

General
1

Shrubbery Notation (see also the rhombus paper) is a general syntax for domain-specific languages that is being pitched as an alternative to s-expressions for the next iteration of Racket. A lot of careful thought has been put into problems like allowing for binary infix operators without specifying the global precedence of those operators, as different DSLs might want different precedence.

In AlgebraicJulia, we get a lot of mileage out of not having to write parsers for our DSLs, because we just use the Julia parser and then manipulate Julia expressions. However, we end up having to re-parenthesize when Julia wants to parse in a different way than makes sense for the DSL. As we look toward “leveling up” our DSL-building tools, it might be good to learn from the Racket community and benefit from the work they’ve put into shrubbery.

Here’s an example of shrubbery notation followed by how it is parsed. Note that, for instance, in the let statements in the fourth function, we just parse a flat list of identifiers. Also note that fun, let, def, match, etc. are not reserved keywords from the perspective of shrubbery. It is up to another program to “enforest” the shrubbery, and turn the flat lists of identifiers into actual syntax trees. Which is a non-trivial step, but shrubbery notation means that you don’t have to spend your life writing and rewriting the regex to recognize floating point numbers or deal with unicode character classes every time you make a new DSL.

def pi = 3.14

(group def pi (op =) 3.14)

fun fourth(n :: Int):
  let m = n*n
  let v = m*m
  println(n +& "^4 = " +& v)
  v

(group fun fourth (parens (group n (op ::) Int))
       (block
        (group let m (op =) n (op *) n)
        (group let v (op =) m (op *) m)
        (group println (parens (group n (op +&) "^4 = " (op +&) v)))
        (group v)))

if x == y
| #'same
| #'different

(group if x (op ==) y
       (alts (block (group (op |#'|) same))
             (block (group (op |#'|) different))))

fun fib(n):
  match n
  | 0: 0
  | 1: 1
  | n: fib(n-1) + fib(n-2)

(group fun fib (parens (group n))
       (block
        (group match n
               (alts
                (block (group 0 (block (group 0))))
                (block (group 1 (block (group 1))))
                (block (group n (block
                                 (group fib (parens (group n (op -) 1))
                                        (op +)
                                        fib (parens (group n (op -) 2))))))))))))
1 Like