2.1 S-Expressions as Inspiration🔗

Rhombus syntax is like Lisp syntax in that it’s bicameral: there are two layers to the specification, and both layers must be satisfied to write a valid expression. In Lisp, the first layer is S-expression notation; the second layer is the grammar of definitions, conditionals, function calls, etc. That second layer is expressed in terms of the first layer. Rhombus is similarly layered, where the first layer is shrubbery notation.

S-expression notation has an especially simple grammar: The grammars here mingle abstract-syntax notation with concrete-syntax literals like ( and ). The literals are meant to stand in place of constructor tags while suggesting the relevant concrete syntax.

	‹term›	::=	‹atom›
		|	( ‹term›* )

We’re simplifying a little bit here, as the ‹atom› nonterminal hides a lot of complexity and we’re ignoring the distinction between pairs and (improper) lists.

Still, this abstract syntax is simple, and the concrete version mimics the abstract version’s simplicity: a ‹term› sequence is combined into a single using ( and ) around the sequence, and whitespace appears between the ‹term›s in the sequence. This simplicity is a great strength of the language design, but it also extracts a price from programmers, requiring them to write lots of parentheses.

The value of this simple, underlying S-expression layer in the syntax is that it lets us factor the definition of the syntax of the language. This first layer’s parsed form serves itself as the concrete syntax for the second layer. The second layer parses into an AST, i.e., abstract syntax as we normally mean it, that a compiler or interpreter can understand. The advantage of this split for a language like Lisp or Rhombus is in the way that the S-expression or shrubbery notation layer is defined once and for all, applying both inside and outside of quoted forms. Then, we can build a second, extensible layer on top; because the first S-expression or shrubbery layer is fixed, the macro writer needs to consider only forms that have the first layer’s basic structure.

2.2 Shrubbery Goals🔗

Shrubbery notation is design to look conventional and lightweight, particularly relative to S-expressions. This goal is realized in two ways:

• Shrubbery notation is provides most tree structure, but it leaves some tree structure to a second layer of parsing, as in 1 + x * 3.

  Individual elements like 1, +, and x are called terms. A sequence of terms where extra parsing will be needed is called a group. Groups, meanwhile, are typically separated by newlines or commas.

  Forms written with (…), […], {…}, or '…' are also terms on the outside, but they contain multiple groups on the inside. For example, f(1 + x) is a group of two terms, where the first term is f and the second term is (1 + x). The term (1 + x) contains a single group that has three terms. Similarly, f(3 * x, 4 * y) is also two terms, but the group that is surrounded by parentheses contains two groups, 3 * x and 4 * y, and those two groups each consist of three terms (a number, the asterisk, and a variable).

• Large-scale block structure relies on newlines and indentation, instead of relying on closing )s or }s that look noisy and redundant in code that is otherwise formatted in a reasonable way.

  For example, the end of a function body is determined by outdenting.

  fun f(x):

  println(x)

  x + 1

  f(0)

  A block, like the function body above, contains a sequence of groups. Roughly, a group spans one line of text within a block, but there are various ways for a group to span multiple lines. For example, an opening ( to create a term within a group might be closed with ) on a later line.

  fun f(x):

  println(

  x

  ) // of the first group in the function body's block

  x + 1

2.3 Shrubbery Abstract Syntax🔗

Many previous attempts to make the abstract structure of S-expressions look less noisy also use newlines and whitespace. Shrubbery notation differs from previous efforts by intentionally adding complexity in the abstract structure. Shrubbery notation enables a second layer of syntax to make distinctions among forms that used (…), […], {…}, : or |, instead making distinctions only based on a leading identifier. Still, the shrubbery abstract grammar is still far simpler than the AST of any realistic programming language.

Here’s the abstract syntax that a shrubbery form describes:

	‹document›	::=	‹group›*
	‹group›	::=	‹item›* [‹block›] [‹alts›]    — must be nonempty
	‹term›	::=	‹item›  |  ‹block›  |  ‹alts›
	‹item›	::=	‹atom›
		|	( ‹group›* )     — comma-separated groups
		|	[ ‹group›* ]     — comma-separated groups
		|	{ ‹group›* }     — comma-separated groups
		|	' ‹group›* '     — newline-separated groups
	‹block›	::=	: ‹group›*       — newline-separated groups
	‹alts›	::=	{| ‹group›*}+    — newline-separated groups

Why these particular textual elements?

• Distinguishing (…), […], and {…} has clear advantages, and even some S-expression dialects (e.g., Clojure) make that distinction.

• Quoting code is important for our goals, so we add '…' to the sets of bracketing forms, which both makes it distinct and highlights its “quoting” nature.

• Using : plus indentation for block structure reads and writes well.

• Using | to generalize : for multi-block forms helps highlight alternatives, such the cases of an if, match, or algebraic-datatype declaration.

Although a ‹group› can end with both a ‹block› and an ‹alts›, usually only one of those (or neither) appears in a ‹group›. A block created with : is itself a ‹term› within an enclosing ‹group›, just like (…), […], {…}, and '…' create ‹term›s. Each individual | form within ‹alts› is conceptually a block, since it has the same shape as ‹block›—but a ‹term› created with | encompasses a sequence of one or more | blocks, not each individual | block.

The ‹atom›s of shrubbery notation are mostly straightforward, and we’ll leave them to the documentation. Note that shrubbery distinguishes identifiers, such as x or to_string, from operators, such as + and ->. The tokens : and | are not operators, and neither are (, ), [, ], {, }, or '.

2.4 Shrubbery Syntax Details🔗

Shrubbery notation is designed to look simple and natural, but as we all know, natural language can be surprisingly complex. For shrubbery notation, the complexities mostly involve ‹group› formation: where exactly newlines are required and where they are allowed.

This section offers a compact summary the key rules, but it’s still too much for a short tutorial. Rhombus programmers are mostly expected to infer sensible rules, anyway. We advise skipping to the exercise.

2.5 Exercise🔗

The shrubbery language permits any shrubbery form in a module body as a sequence of ‹group›s, and it prints the shrubbery’s abstract form using an S-expression encoding that is described in the documentation.

For example,

#lang shrubbery

start:

"hello"

"world"

end:

"bye"

prints

(multi

(group start (block (group "hello") (group "world")))

(group end (block (group "bye"))))

where multi is used to combine a top-level sequence of groups in a module.

Experiment with #lang shrubbery, then reverse-engineer the following outputs by writing a shrubbery form that produces it. Note that if you make the DrRacket window narrower, the parenthesized output will contain more newlines, making it easier to see if you got the answer right.

• (multi

  (group fun

  f

  (parens (group x))

  (block (group x (op +) 1)))

  (group f

  (parens (group 2))))

• (multi

  (group

  (quotes

  (group math

  (op |.|)

  max

  (parens (group (op $) x) (group (op ...))))

  (group (op ...)))))

• (multi

  (group

  match

  x

  (alts

  (block (group 1 (block (group "one"))))

  (block (group 2 (block (group "two")))))))