An indentation-based homoiconic infix-operator syntax for Lisp

The marvellous syntactic flexibility and extensibility of the Lisp languages finds its roots in the fact that the lexical syntax of the language can be fully parsed into a tree structure without reference to any special rules for particular operators.¹ This makes it possible to expose the types used to represent this tree into program code, and for the program code to use the provided operations on these types to generate more code directly in the form of a syntax tree.

This property has often been referred to as homoiconicity, although finding a satisfactory formal definition of this term has proven tricky. In its original form in McCarthy’s ‘pure Lisp’, it referred to code built out of structures of pairs (used to form linked lists representing operator applications) and symbols (used to represent the names of variables). Within the Lisp language itself, pairs could be constructed (cons) and deconstructed (car, cdr), while symbols could be identified (atom) and compared with one another (eq). Subsequent Lisps in the direct lineage of this original version added machine representations of numbers, strings, and other data types with corresponding lexical syntax (datums), but kept the basic idea. The most distinctive operator in this view of homoiconicity was quote, which, surrounding any expression, evaluated to that expression’s representation as pairs, symbols, and other datums, rather than finding the value of the expression itself; paired with eval, which took a tree of pairs and symbols and found its value as an expression, code could be generated dynamically. Since original Lisp was dynamically scoped, running the code (eval (quote e)) was equivalent to running e for any expression value of e. Lisp macro technology was developed to allow manipulations to the pair-and-symbol structure of a program before evaluation even began, allowing programmers to create new syntactic abstractions at no run-time cost.²

Apart from the obvious desire to represent richer and more hardware-efficient data types than only pairs and symbols, other factors which have necessitated a break from this traditional view are the adoption of lexical scope instead of dynamic scope, and the subsequent development of macro hygiene which extends lexical scope to the domain of syntactic abstraction. Hygienic macro technologies demand, at the very least, that the symbol data type be replaced by an identifier type which is aware of the lexical scope in which it appears. In practice, for efficiency reasons the pair data type is also converted to a ‘wrapped’ form which likewise has awareness of its scoping context.³

Thus homoiconicity has developed from the representation of code in types which otherwise happen to be used for any other domain-specific data to its representation in more specific abstract types. This can also be seen as an opportunity to correct other infelicities in the design of traditional Lisp. One such infelicity is that programming in Lisp requires directly writing the abstract syntax tree of one’s program in fully-parenthesized prefix notation. Whether this is a great disadvantage or not is fiercely fought over by Lisp programmers, but even the most experienced Lisp programmer with the most advanced text editor will acknowledge that occasionally, while editing, the structure of the parentheses becomes accidentally detached from the intended structure (usually shown by indentation). This is a minor but regular frustration for every Lisp programmer. It is a simple but frustrating bug to find and fix, checking that each individual parenthesis in a section of code is balanced with the correct corresponding opposite parenthesis.

Traditional Lisp’s uniformly parenthesized prefix notation extends also to mathematical expressions, which must be written in forms such as (+ x 1) rather than the more familiar x + 1. The hierarchy of expressions cannot be inferred based on operator precedence. Like other aspects of Lisp’s traditional notation, the benefits (or otherwise) of this are intensely debated: writing a macro which converts an infix expression into nested prefix expressions is virtually a rite of passage for budding Lisp macrologists; but Lisp programmers generally claim to grow to like writing mathematical expressions this way, and point out advantages such as the ability to use more than one operand per mathematical operator.

In a seminal paper of 1966, Peter Landin introduced the proposed programming language ISWIM (‘If You See What I Mean’), which he described as ‘an attempt to deliver Lisp from its eponymous commitment to lists’. This remark can be understood all the better if one considers that there were still no ‘functional’ programming languages other than Lisp at this time – and Lisp as she was spoke, at the time, was very far from functional in practice!⁴ Landin’s proposed language used indentation to denote the structure of programs, rather than parenthesization, and supported infix notation for arithmetic expressions. Using indentation directly as the machine-readable construct for expressing syntactic hierarchy, instead as merely as the human-readable expression of the actually semantically significant machine-readable hierarchy expressed through (various kinds of) brackets, completely eliminates the possibility of the programmer wasting time trying to work out how the two kinds of hierarchy are out of synch with one another.⁵

At the time of Landin’s paper, there were still no widely-used standard techniques for syntactic abstraction using Lisp’s homoiconicity.⁶ As history turned out, ISWIM had no immediate noticeable impact on its parent language; instead it became the last common ancestor of a new family of functional programming languages, whose most well-known members include the MLs and Haskell. These languages have no built-in idea of homoiconicity nor syntactic abstraction. More notably in the eyes of their inventors and proponents, they also have static type systems based on algebraic data types, which seem anecdotally to compose poorly with macro-based syntactic abstraction.⁷

What if, say, the part of the Lisp community that took note of Landin’s idea and, in our timeline, developed it into new non-Lisp languages, had observed the rump Lisp community’s development of macro-based syntactic abstraction and determined to incorporate these new features into their languages which had been liberated from Lisp’s commitment to lists? The abandonment (or at least sidelining) of pair-and-symbol representations with the move to hygienic macros suggests that we should take more seriously the possibilities presented to us by using other data types. This paper suggests that by abandoning certain shibboleths of traditional Lisp notation, a comparably simple notation which nonetheless supports indentation sensitivity and infix operators is possible.

Prior art

Attempts to reskin existing Lisps to use indentation-sensitive syntax and/or infix mathematical notation are numerous. In Scheme alone, there are Egil Möller’s I-expressions,⁸ David A. Wheeler and Alan Manuel K. Gloria’s sweet-expressions, and Arne Babenhauserheide’s wisp. The latter two both incorporate curly-infix-expressions, also by Wheeler and Gloria.

Guy L. Steele and Richard P. Gabriel’s ‘Evolution of Lisp’ paper at HOPL II (1993) contains further information on some historical attempts to bring what they call ‘Algol-Style Syntax’ to Scheme (section ‘Some Notable Failures’). Will Clinger and Mitch Wand’s ‘Hygienic Macro Technology’ paper at HOPL IV (2020) also contains a section on attempts to implement Lisp-style macros in languages with more conventional syntax. Generally, those languages (which include Rust) do not consider themselves Lisps.

The most recent development in this area, and the direct inspiration and point of comparison for this proposal, is the Shrubbery notation used in the Racket project’s new Rhombus language. I believe the Shrubbery notation was largely developed by Matthew Flatt. If the attempts considered by Steele and Gabriel could be called ‘Algol-style’, Shrubbery might fairly be called ‘Python/ML-style’. The notation I propose in this paper might be called ‘ML/Haskell-style’.

Unlike the notation I propose, it does not appear to have been a goal of Shrubbery to find a minimal possible set of rules for expressing a homoiconic/macro-compatible syntax with the features of indentation-sensitivity and infix operators. The practical considerations which seem to have motivated many of Shrubbery’s features are worthwhile goals in and of themselves, but I would like to find something which is, at its core, a worthy successor to the sheer minimalism of McCarthy’s original Lisp. In particular, Rhombus supports not only infix but also prefix, postfix, and circumfix operators; I consider only infix operators. Shrubbery notation defines very many expression types; my notation attempts to maintain the principle of maximal lexical uniformity among syntactic operators.

Difficulties

Adding optional indentation-sensitivity to an existing Lisp language is not especially challenging. Maximizing the interchangeability of whitespace- and parenthesis-based notations is, however, difficult because in Lisp, every parenthesis is meaningful: no parenthesis is redundant. While x, (x), and ((x)) are equivalent expressions in mathematical notation and the parentheses in the latter two would likely never be written in practice, in traditional Lisp notation these are quite distinct. It is tricky to express this in pure indentation style. The notation proposed here resolves this problem by simply banning the equivalent of traditional Lisp function applications with no arguments. This is no great restriction since the equivalent functionalty can be provided by having ‘thunks’ (the Scheme term for a zero-argument procedure whose result is not memoized) and other procedures as types which are distinct from one another; in a system which encourages a functional programming style, this might even be seen as a benefit. It is, however, a major factor which makes the notation proposed in this paper incompatible with existing Lisp languages.

Adding limited infix notation is also not a particular difficulty per se, as demonstrated by curly-infix-expressions. The problem comes from accommodating the (reasonable!) cultural expectation of Lisp programmers. Since nothing about the syntax of anything in Lisp is fixed by the language itself, except for the parenthesized prefix notation, almost everything a programmer could write in the language can be made to look and work the same as if it were something that came with the language itself. It is unnatural to a Lisp programmer to have a feature, like infix expressions, which cannot be extended to support new constructs (infix operators) which look indistinguishable from those provided by the language itself. This includes being able to customize the precedence of custom operators relative to one another and to those included in the language, and their associativity (left or right). These properties are collectively referred to here as the fixity of the operator.

The desire to have this level of customizability of infix operators is problematic for implementation, because traditional implementations of infix operator parsing have worked entirely within the initial lexical processing phase of evaluation; i.e. before the semantics of any declarations within the programming language assigning fixity to operators have been processed. Haskell and ML do support custom infix operators with custom fixity, but declaring such a custom operator amounts to a monkey-patch of the parser on-the-fly during ongoing parsing of a file. Since custom operators are also imported and exported from libraries, which are also semantic-level constructs typically beyond the ken of a typical parser, the interaction of these features is quite hairy.

This notation solves the problem by adopting two rules familiar from Haskell and marrying them to an idea pioneered by Rhombus. The two rules from Haskell are: that the infix adjacency operator (i.e. whitespace, in various forms) which creates function applications has a higher precedence than any other infix operator; and that all infix operators must be lexically identifiable as infix operators (e.g. by consisting only of punctuation characters), even though their relative precedence and associativity cannot be known only from their lexical appearance.

With these two rules, infix expressions can be identified by the lexical parser as infix expressions without having to resolve precedence and associativity. Instead, the lexical parser leaves infix expressions as a flat list alternating between the operators themselves and the expressions which will form their operands. Identifying the correct order of operations is left to a later stage of evaluation: macro expansion. Since the implementation already knows about imported identifiers, locally-defined identifiers, and some of their semantics during this stage, it can resolve operator precedence itself using this expand-time information. Moreover, this process can be entirely invisible to implementers of macros and other operators, infix or otherwise.

The concrete syntax

Here I consider the design of only three types of expressions in the concrete syntax tree: identifiers, I-expressions, and S-expressions. In particular, the lexical syntax of other datum types (including numbers, strings, and even compound structures like literal lists and vectors) is not considered.⁹ More or less any obvious lexical syntax for these types will be compatible with the proposed notation.

The only thing about identifiers’ lexical syntax that may be slightly surprising to non-Lispers is that the names of identifiers may freely mix alphabetic, numeric, and punctuation characters. Identifiers therefore generally have to be separated from one another by whitespace. (x+y is a a single identifier; x + y is a compound expression.)

Identifiers may be infix or non-infix. The rule for this is familiar from Haskell: an identifier whose name consists entirely of punctuation is understood as an infix operator; an identifier whose name contains any non-punctuation character is non-infix. Haskell’s rules to use a non-infix operator in infix position with ` stropping, or to use an infix operator in prefix position or as a value with a single pair of surrounding parentheses, can also be used without problem. The latter convention will be used in subsequent sections showing the equivalence between infix and prefix expressions.

S-expressions are prefix expressions. They have at least two subexpressions. The requirement to have at least two subexpressions is the main restriction that makes this notation incompatible with existing dialects of Lisp; however, it is also what makes it simple and intuitive to freely interchange indentation and parenthesization in ways which previous indentation-based Lisp notations have made awkward. An S-expression is formed by the adjacency of two or more expressions which are not infix identifiers. The simplest form of adjacency is horizontal adjacency, i.e. separation by ordinary horizontal space characters. The cases for adjacency involving vertical space will be explained later. Examples of S-expressions are f x, f x y, …

I-expressions are infix expressions. They have at least three subexpressions, and always an odd number of subexpressions. The subexpressions alternate between subexpressions of any kind (in positions 0, 2, etc.) and identifiers which denote infix operations (in positions 1, 3, etc.) Like S-expressions, I-expressions are formed by adjacency. When an expression which is not an infix identifier is left-adjacent to an infix identifier, which in turn is left adjacent to another expression other than an infix identifier, an I-expression of those three expressions is formed. If additional pairs of infix identifiers and expressions other than infix identifiers follow to the right, they form part of the same I-expression. Examples of I-expressions are x + y, x + y + z (a single I-expression with five subexpressions), x + y * z (likewise), …

As in ML and Haskell, the adjacency rule for building S-expressions has higher precedence than any infix identifier. Parentheses around either an S-expression or an I-expression serve to group that compound expression. f x + y z will parse as an I-expression with two S-expression sub-expressions and could also be written (f x) + (y z); based on the variable names, probably the programmer intended to write f (x + y) z, an S-expression of three subexpressions, the middle subexpression being an I-expression. Likewise, the defined operator fixity in an expression such as x * (y + z) is irrelevant, because the precedence of expressions is entirely specified by the parentheses: this example is an I-expression of three subexpressions whose rightmost subexpression is also an I-expression of three-subexpressions; it is not a single I-expression of five subexpressions.

Redundant parentheses do not appear in the concrete syntax tree, so f x + g y and (f x) + (g y) form identical CSTs. Parentheses around a single non-infix identifier are redundant. As mentioned above, in the presentation here, the rule is used that parentheses around a single infix identifier denote that identifier in a non-infix context (and do not build an I-expression), but whether this double meaning for parentheses is actually a good idea in practice is debatable.

Any expression which can be written only with horizontal adjacency and parentheses can also be written using vertical adjacency without parentheses. This is the layout rule based on Landin’s offside rule. The principles of the rule are simple:

• each new line begins a new expression (whether S- or I-expression or simply a non-infix identifier);
• if the new line is less indented than a previous line, everything between the beginning of the new line and that previous line is grouped as if by parentheses;
• if the new line is identically indented to a previous line, the expression is a rightward sibling of the expression on the previous line;
• if the new line is more indented than a previous line, its expression is simply adjacent to the expressions on the previous line;
• an open parenthesis overrides this rule with respect to things outside the parenthesized expression, until the corresponding closing parenthesis.

The only small difficulty here is when a line ends with an infix identifier. In this case, only a single more-indented expression can follow. In fact, it would be possible to eliminate the requirement for additional indentation, but this might lead to surprising parses of strange layouts, so it would probably be better to require it for practical reasons.

The horizontal S-expression f x y could be written:

f
  x
  y

or:

f x
  y

The example f (x + y) z could be rewritten without parentheses:

f
  x + y
  z

or if the parse (f x) + (y z) were actually intended, as:

f x +
  y z

The abstract syntax

In the transition from the concrete syntax tree to the abstract syntax tree, I-expressions are simply eliminated and replaced by equivalent S-expressions, taking account of the fixity of the infix identifiers within them.

The task of converting I-expressions to S-expressions falls to the macro expander. In a traditional Scheme hygienic macro system, macros are implemented by example – a simple parser is paired with a corresponding unparser which use identical syntax to do inverse tasks: first to identify the form of a macro use and extract its relevant subforms, then to re-arrange those subforms into an expansion. I will take a brief detour into the implementation details of hygiene and of ‘macros by example’ in order to explain how this remains possible for macros in a system built on this notation, while the expander still shields users from having to worry about the distinction between S-expressions and I-expressions and the macro user’s precise layout choices.

S-expressions and I-expressions are, as implied above, not pairs but opaque syntax objects. Syntax objects are both the input to and output of macro expansion procedures (called transformers). When a syntax object is passed into a macro expansion procedure, it contains information about the identifiers which are bound in the scope of the macro use.

The fundamental inspection operation on opaque syntax objects is the primitive unwrap-syntax.¹⁰ In Scheme implementations as well as in implementations of this notation, unwrap-syntax is called internally within the macro-by-example parser according to the specification given to the parser by the macro’s implementation. For example, consider this basic Scheme example:

(define-syntax foo-macro
  (syntax-rules ()
    ((_ (x . y)) (list 'the-input-was x 'and y))))

The clause (_ (x . y)) represents the grammar which the parser is tasked with parsing. The parser will call unwrap-syntax on a correct input macro use four times. Given a real use of this macro such as (foo-macro (2 . 4)), it will first call unwrap-syntax on the syntax object representing the macro use as a whole. This will yield a pair of two further syntax objects, one (the car) representing the identifier foo-macro and the other (the cdr) a syntax object representing only the part ((2 . 4)). (Note the extra parentheses! This syntax object wraps a 1-list, not the 1-list’s contents directly.) The macro implementation is uninterested in the foo-macro part, so the parser unwraps the cdr of this pair to yield another pair. The components of this pair are again syntax objects: the car directly represents the pair (2 . 4), and the cdr represents the empty list. The parser will call unwrap-syntax once more on each of these, because the grammar has declared that it is interested in knowing the car and cdr of the pair (x . y) separately, so it will make those available to the unparser under the respective names of x and y (still as syntax objects); it will also unwrap the final cdr of the list to make sure that it is, in fact, the empty list. If any of these unwrap-syntax operations does not yield a value of the expected type, the parser knows (without the macro author having to write an explicit syntax check) that the macro user has not used the macro in the correct way, and will signal an error. The parser only calls unwrap-syntax as much as it actually needs in order to verify that the structure of the macro use is correct and bind the terminals specified by the grammar: if the macro use were (foo-macro ((1 . 2) . 3)), the parser does not call unwrap-syntax on the syntax object representing (1 . 2).

The trick employed to implement this notation is to embed the I-expression to S-expression conversion inside the operation unwrap-syntax. For example, given the input I-expression x + y, the unwrap-syntax operation will notice that it is an I-expression and convert it to the S-expression (+) x y before passing the unwrapped form of that syntax object back to the parser. The implementation of the parser also has to unwrap the syntax objects representing the grammar in order to interpret the grammar, so I-expresisons can be used freely on both sides of a macro-by-example clause.

This raises the question of how the unwrap-syntax operation deals with I-expressions with multiple operators, such as a * b + c * d. The expander must identify which of the operators has lowest precedence and, respecting that operator’s associativity, convert it to an S-expression of three subforms, leaving the higher-precedence operations on either side as unmodified I-expressions. In this case + has the lowest precedence, so this I-expression will appear to a macro implementer to be the S-expression (+) (a * b) (c * d).

How does the macro expander know about the fixity of operators? Recall that syntax objects contain compile-time information about bindings. Typically this compile-time information includes the procedures which have been defined as transformers for macros, or the information that an identifier such as lambda is bound to a primitive syntactic construct (the procedure creation syntax) so it can correctly process primitive constructs and their subforms. Besides this, though, the expander can carry metadata about each identifier and its binding – including its fixity information. In order to create the procedure objects which are used as the transformers for macros, a macro expander already has to evaluate code during expand time: an operator’s fixity can therefore be calculated using any code, most usefully by copying the fixity of some other related operator or deriving a different fixity entirely relative to it.

This means that operator semantics and fixity are both fully lexically-scoped, and the fixity of an operator will always be correct for the locally-defined semantics of that operator. The same project can, for example, import a third-party library whose author (Cy D. Fect?) has internally defined >>= to be a destructive right arithmetic shift with the very low precedence of an assignment operator; another part of the same project (by Mona D.?) can safely use >>= for the ‘bind’ operation on a monoid in the category of endofunctors, with the much higher operator precedence implied. The two uses will not interfere with one another, any more than two distinct libraries using the same variable or procedure name would in any other situation in a language with proper namespacing.

Operator fixity could even be specified within local scopes: an implementation of a hash-based purely functional data structure might prefer the monadic bind interpretation of >>= in most of a file; but in part of the file which actually defines a hash function, it might be desirable for that implementation to be maximally visually similar to a corresponding C implementation of the hash function, so that it can be verified that the two versions actually do the same thing. That particular procedure could rebind >>= to the ‘Cy’ defectual form within itself with a correspondingly correct fixity rule.

Examples

In this section I present fully-bracketed CSTs and sometimes their corresponding ASTs. CSTs use a special notation where round brackets denote S-expressions, and square brackets I-expressions. ASTs are presented as S-expressions in fully-horizontal, maximally parenthesized form.

A basic function definition with an infix := definition syntax might look and parse like this:

hypot a b := sqrt (a ** 2 + b ** 2)

CST:

[(hypot a b) := (sqrt [a ** 2 + b ** 2])]

A pattern matching macro can be naturally expressed in this notation:

match xs
  Cons x xs* =>
    Cons (f x) (map f xs*)
  Null => Null

CST:

(match xs [(Cons x xs*) => (Cons (f x) (map f xs*))] [Null => Null])

Expressing a multi-test McCarthy conditional is considerably more awkward. A very Lispy single-test if where the alternate clause is not syntactically labeled is unproblematic:

if (x < y)
   invert y x
   x / y

CST:

(if [x < y] (invert y x) [x / y])

But multiple clauses à la Lisp’s cond are more awkward:

cond
  (x < y) =>
    invert y x
  (x > y) =>
    x / y
  else =>
    1

This is a case where Shrubbery notation’s larger number of lexical expression types, in particular the ‘alternatives’ feature, provides a clear benefit over the notation proposed in this paper (although Rhombus chooses to continue historical Lisp’s dissociation of single-test if from multi-test cond).

The Haskell $ operator is a parentheses-reducing device: f x $ g y is equivalent to f x (g y). It could be implemented in this notation as a hygienic macro. The CST of that example would be:

[(f x) $ (g y)]

and the AST:

(($) (f x) (g y))

and an implementation of the $ macro could simply append its right-hand expression to the operands of its left-hand S-expression. An implementation of this macro ‘by example’ might look like this:

syntax ($)
  ((left-expr ...) $ right-expr) => (left-expr ... right-expr)

where the left-hand side of the => is the grammar and the right-hand side the template for an expansion, as in Scheme’s syntax-rules. It could equivalently be written:

syntax ($)
  (($) (left-expr ...) right-expr) => (left-expr ... right-expr)

because whether an S-expression or I-expression is used in the implementation is invisible to the macro user, just as whether a macro use is an S-expression or I-expression is invisible to the macro implementer. (In theory, a form for unpacking I-expressions in macro uses could also be made available to advanced macrologists.)

A block-based binding structure like Lisp’s let might look like this:

let ((x = 1)
     (y = 2))
  x + y

CST:

(let ([x = 1] [y = 2]) [x + y])

Potential implementation:

syntax let
  (let ((var = expr) ...) body_0 body_1 ...) =>
    (λ (var ...) body_0 body_1 ...) expr ...

(Somehow the parser for the let implementation also needs to be told to treat = specially, like the literals list in Scheme syntax-rules, but this detail is omitted here.)

Miscellaneous concerns

A name for the notation

A bonsai is a more minimal shrubbery.

Further development

There is a long way between doodling a potential syntax, as this paper has done, and developing a working programming language with an indentation-based syntax which proves intuitive for programmers in practice and not only in the imagination.