Readable s-expressions and sweet-expressions home page: Infix and fewer parentheses in Lisp-like languages

This page is obsolete; see instead.

I've used Lisp my whole programming life and I still don't find prefix math expressions natural. - Paul Graham

I have more faith that you could convince the world to use esperanto than [to use] prefix notation. - Paul Prescod

Lisp has all the visual appeal of oatmeal with fingernail clippings mixed in. - Larry Wall

After 13 years of doing Lisp and 3 or 4 years of Python, I agree: I prefer writing Lisp, but Python is easier to read. - John Wiseman

LISP: ... mythically from ‘Lots of Irritating Superfluous Parentheses’ Jargon File

[If only] we could find characters or signs suited for expressing all our thoughts as clearly and as exactly as arithmetic expresses numbers... - Gottfried Wilhelm Leibniz, 1677.

"A language should be designed in terms of an abstract syntax and it should have perhaps, several forms of concrete syntax: one which is easy to write and maybe quite abbreviated; another which is good to look at and maybe quite fancy... and another, which is easy to make computers manipulate... all should be based on the same abstract syntax... the abstract syntax is what the theoreticians will use and one or more of the concrete syntaxes is what the practitioners will use. John McCarthy, creator of Lisp

The Problem

Many people find Lisp s-expressions hard to read as a programming notation. I've developed Lisp programs for decades, and though I can read s-expressions well, I remain dissatisfied with their syntactic limitations. Others, including Lisp luminary Paul Graham, feel the same way. ( Tim Bray loves Clojure, but not its syntax.) Yet s-expressions have a lot of benefits to them, and it turns out to be very hard to design a more readable notation that retains all the benefits of s-expressions. But I believe it is possible - so let's try!

This web page identifies some ways to extend/modify s-expressions so they can be more readable without losing their power (such as homoiconicity, generality, macros, quasiquoting, and easily-manipulated program fragments). A vast number of projects have tried to create "a more readable Lisp notation" and failed, including M-expressions, IACL2, and Dylan. In hindsight, it's clear that they failed because they didn't have some key advantages of S-expressions, in particular, that they are generic (they do not depend on some underlying semantic) and homoiconic (the underlying data structure is clear from the syntax). Since these old "readable Lisp" syntaxes weren't generic or homoiconic, they could not handle semantic change and metaprogramming - yet those are some of the very reasons someone would use a Lisp! Now that we know why those efforts failed, we can avoid their mistakes.

My goal is to spur work to create one or more readable, general-purpose, homoiconic notations for s-expressions that do a good job representing programs. A good way to measure that is to see that it should be easy to translate back and forth between arbitrary S-expressions and this other notation (by computer and in people’s heads).

If you are unwilling to consider that there might be a better approach, read my retort/rebuttal that Lisp can be readable. If you're still unwilling to consider alternatives, stop reading. But if you're interested in developing a better way, keep reading. After all, the quote operator ' did not fall from the sky - it was not in the original Lisps, and was added because that construct was so common that it was worth creating an abbreviation. We're just adding new abbreviations. On this page, I explain how to get involved, present my 3-layer approach (curly infix, modern-expressions, and sweet-expressions), and point to others' approaches to the problem.

How to discuss solutions

Interested? Please join the readable-discuss mailing list of SourceForge project "readable".

This project exists to discuss options for taming s-expressions, and then develop and distribute open source software to implement those ideas. See the mail-archive archives of the readable Lisp archive to see what we've discussed so far.

Curly Infix, Modern-expressions, and Sweet-expressions

I've developed a 3-layer approach to making Lisp more readable, which is all based on creating simple abbreviations that work on any S-expression:

  1. Curly infix: Any expression surrounded by {...} is merely an abbreviation for an infix expression. So {n <= 2} maps to (<= n 2), {2 * 3 * 4} maps to (* 2 3 4), and {2 + {3 * 4}} maps to (+ 2 (* 3 4)). By intent there is no precedence and embedded infix expressions must use another {...}.
  2. Modern-expressions: This takes curly infix, and adds special meanings to the prefixed grouping symbols (), [], and {}. Thus, f(1 2) maps to (f 1 2).
  3. Sweet-expressions: Includes modern-expressions, and adds the idea that indentation is meaningful (like Python, Haskell, and many other languages).

All of these can be used in any Lisp-like language (Common Lisp, Scheme, Emacs Lisp, ACL2, BitC, CLIPS, etc.). Curly-infix is 100% compatible with existing code; modern-expressions and sweet-expressions are 100% compatible with well-formatted code.

Sweet-Expression Examples

Let's do two quick examples - we'll use sweet-expressions version 0.2 to represent calculating factorials and Fibonacci numbers, in both cases using Scheme:

(Ugly) S-expression Sweet-expression 0.2
(define (fibfast n)
  (if (< n 2)
    (fibup n 2 1 0)))
define fibfast(n)  ; Typical function notation
  if {n < 2}       ; Indentation, infix {...}
    n              ; Single expr = no new list
    fibup(n 2 1 0) ; Simple function calls
(define (fibup max count n-1 n-2)
  (if (= max count)
    (+ n-1 n-2)
    (fibup max (+ count 1) (+ n-1 n-2) n-1)))
define fibup(max count n-1 n-2)
  if {max = count}
    {n-1 + n-2}
    fibup max {count + 1} {n-1 + n-2} n-1
(define (factorial n)
  (if (<= n 1)
    (* n (factorial (- n 1)))))
define factorial(n)
  if {n <= 1}
    {n * factorial{n - 1}} ; f{...} => f({...})

Note that you can use traditional math notation for functions; fibfast(n) maps to (fibfast n). Infix processing is marked with {...}; {n <= 2} maps to (<= n 2), and f{n * 2} maps to (f (* n 2)). Indentation is significant, unless disabled by (...), [...], or {...}. This example uses variable names with embedded "-" characters; that's not a problem, because the infix operators must be surrounded by whitespace and are only used when {...} requests them.

It's actually quite common to have a function call pass one parameter, where the parameter is calculated using infix notation. Thus, there's a rule to simplify this common case (the prefix {} rule). So factorial{n - 1} maps to factorial({n - 1}) which maps to (factorial (- n 1)).

Credit where credit is due: The Fibonacci number code is loosely based on an example by Hanson Char.

It's a joy to use at the command line; with sweet-expressions, you can type in simple-to-read expressions and have the system immediately respond.

More information about Sweet-expressions

Interested? You can get:

From the SourceForge page (noted above) you can download implementations. There's a production-ready Common Lisp implementation of curly infix, and a reasonably complete (though work is still ongoing) Scheme implementation of Sweet-expressions.

Analysis of alternatives

If you want even more detail, look here:

Implementation approaches

I want to have final sweet-expression readers that work on Scheme, Common Lisp, emacs Lisp, and ACL2 at least, without having to implement it multiple times. Scheme is in some ways the most strict of the these, e.g., it's picky about the meaning of a boolean value, what is at the end of a list, and the legal names of parameters. Thus, I've been implementing sweet-expressions in a small subset of "easily translatable" Scheme, so that it can eventually be auto-translated to other Lisps. (It's easier to translate from more-picky Scheme to others than vice-versa.) ACL2 has a very short list of built-ins, which are similar to Scheme's, so this seems plausible. Perhaps I could use Dorai Sitaram's Scmxlate Scheme translate tool (LGPL license) so that I could write a single implementation and have it be useful in Common Lisp (CL) and ACL2 as well. The final program will be so small that a specialized program to do the translation might be enough.

One nastiness about this technique: In Scheme, recursion is how you do everything. In Common Lisp, tail recursion isn't guaranteed. However, tail recursion is a very common optimization in simple cases, e.g., where a function tail recurses into itself. In ACL2, mutually-recursive functions have to be declared, which is annoying - but they can occur. In fact, ACL2's only iteration technique is recursion. Emacs lisp doesn't optimize tail recursion at all, but since code doesn't require a deep stack that should be okay. Scheme for Common Lispers discusses differences between Scheme and CL, as does the Wikipedia article on Common Lisp. Here's a convenient table of Common Lisp/Scheme function "equivalences". DrACuLa combines ACL2 with DrScheme, and this page discusses combining ACL2 with DrScheme (basically, ACL2 builds on just a few primitives, so DrScheme just implemented those and ACL2 showed up!).

Ideally, an implementation should go both ways (translate text to S-expressions, and pretty-print S-expressions as indented with infix format). It should be absolutely rock-solid (maybe even proved). It should also provide a "check for change" tool, e.g., read in some text using the 'regular' read and the indented, and make sure there's no change.

Why am I bothering?

I'm very interested in improving the security and safety of programs. Doing that well requires good program analysis tools. S-expressions have proven themselves, over many decades, to be a very good tool for creating programs to transform or analyze programs (or other symbolic systems). Many proving tools such as ACL2 and PVS are based on s-expressions, as well as existing computer alegebra tools like Axiom and Maxima.

Sadly, traditional s-expressions are nearly unreadable to most people, making them difficult to use, and a notoriously poor way to communicate with a wider world. Its inability to properly support infix notation directly - a basic starting point for symbolic manipulation of mathematics - is laughable in the 2000s. By having a readable notation for s-expressions, I hope to be able to spur on better abilities for programs that analyze programs... resulting (perhaps) in more secure and safe programs.

Besides, I'm drawn like a moth to the flame of "impossible" problems. For more proof of this character flaw, see my trusting trust web page.

Other resources

There are many programs available to aid s-expression readability; You can use the Subversion SCM tool to quickly extract the latest versions of the whole set. This README (local copy) explains more.

Other files on this web page that can improve s-expression readability are here:

  1. gloria-infix.lisp - an infix macro for Common Lisp, MIT license
  2. gloria-infixdemo.lisp - demo of above
  3. - an I-expression formatter in Common Lisp
  4. sugar-original.scm - Original Scheme implementation of I-expressions, from SRFI-40.
  5. sugar.scm - Scheme implementation of I-expressions, modified from SRFI-49.

Other web pages that might be of interest include:

  1. Darius Bacon's page (code to implement indenting and infix).
  2. SRFI-49, I-expressions are an alternative method for presenting s-expressions (either program or data), using indentation. I-expressions have no special cases for semantic constructs of the language. SRFI 49 includes a sample implementation with an MIT-style license.
  3. Peter Norvig’s book, “Artificial Intelligence: A Modern Approach.” includes a simple Lisp program that converts infix to s-expression format. It appears to be open source software.
  4. Infpre is A Common Lisp infix utility (LGPL license). It converts between prefix and infix. "The intended use is for CL programs with long math formulas", and it contains the functions "infix->prefix" and "prefix->infix", as well as the macros "math" and "!!". It supports precedence.
  5. Guile's ice-9 infix module. Infix expressions are surrounded by #[...]; precedence, infix, and prefix functions are supported (though you must declare each one before use); name-prefixed functions are used with comma-separated parameters. However, you can't mix ordinary Lisp code inside them (e.g., there doesn't seem to be support for quasiquotations); it switches to a completely different and incompatible language inside.
  6. GEE/Infix and Guile-reader, part of GNU Guile's projects.
  7. XKCD's cartoon about LISP and parentheses.
  8. comp.lang.lisp discussion/flamefest about this
  9. OCaml's "The Whitespace Thing" (twt)
  10. "An infix syntax for Forth (and its compiler)" by Andrew Haley (Red Hat) (2008) . Traditional Forth is exclusively postfix, and has many of the same readability problems as Lisp... so Haley is trying to fix that, by creating a reader that supports a more-readable syntax.
  11. Lisp is not perfect. Those who think it is may want to look at essays like Lisp is not an Acceptable Lisp.

To use this, of course you'll need a Lisp implementation. The Road To Lisp comments on some implementations. Common Lisp Implementations is a great comparison of Common Lisp implementations. Other sources of information on Lisp include Practical Common Lisp by Peter Seibel (here's Practical Common Lisp (video of Peter Seibel)) and Paul Graham's Lisp page. Humility about Lisp is good, though.

There's probably room for a few different approaches, but in the end, I hope there will be a short list of useful approaches and freely-available tools to make Lisp-like systems easier to use.

You can view the readable-discuss mailing list or my home page.