Thursday, September 12, 2013

Lisp Without Parentheses

Lisp is sometimes jokingly said to stand for "Lots of Irritating Superfluous Parentheses". Despite the joke, it turns out most of the parentheses in an average Lisp program are, in fact, superfluous. Let's examine the program for finding square roots by Newton's Method from SICP:

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      (sqrt-iter (improve guess x)

(define (improve guess x)
   (average guess (/ x guess)))
(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

This isn't as bad as some Lisp programs, but even so, three closing-parens in a row starts to get hard to keep track of without editor support. Admittedly, most programmers have editor support (if your text editor can't match parens for you in 2013, you need to get a new text editor); but if we don't need them we might as well get rid of them. Parentheses do 3 things in this program: they tell indicate where function/macro applications start and where the argument lists for those applications end, and they delimit lists. If we know the signature of each function or macro, then we don't need parentheses for that second purpose- telling us where argument lists end. We can restrict them to simply marking applications (as opposed to functions that are being used as values), and delimiting lists (in this case, the only lists we need to worry about are the argument lists in function definitions). That gives us a transformed program that looks like this:

(define) '(sqrt-iter guess x)
  (if) (good-enough?) guess x
      (sqrt-iter) (improve) guess x

(define) '(improve guess x)
   (average) guess (/) x guess
(define) '(average x y)
  (/) (+) x y 2

(define) '(good-enough? guess x)
  (<) (abs) (-) square guess x 0.001

(define) '(sqrt x)
  (sqrt-iter) 1.0 x

For clarity, I've explicitly quoted the lists to distinguish an application from a list of a single element. This is starting to look a lot like Polish Notation with all of the operators parenthesized. You might think "Polish Notation arithmetic doesn't need parentheses because arithmetic operators use distinct symbols from operands"; true, but that turns out not to matter. If we think of values as functions that take no arguments and return themselves, and variables as functions that take no arguments and apply their values, then we can assume that everything is always applied by default, and then we don't need those parentheses (or anything else) to mark applications, giving us this:

define '(sqrt-iter guess x)
  if good-enough? guess x
      sqrt-iter improve guess x

define '(improve guess x)
   average guess / x guess
define '(average x y)
  / + x y 2

define '(good-enough? guess x)
  < abs - square guess x 0.001

define '(sqrt x)
  sqrt-iter 1.0 x

This should look suspiciously like FORTH. If it doesn't, try capitalizing everything and reading it backwards (in Reverse Polish Notation, like old HP calculators use). I have a sneaking suspicion that FORTH variants have remained fairly niche languages largely because they put their arguments and function names backwards from everybody else (well, except for Assembly languages, but nobody really wants to program in assembly either). (Incidentally, this is very similar to how actual Lisps are compiled into concatenative languages like VM bytecode.)

As long as you have just enough static typing to keep track the arity of each function, all of the original parenthesization can be reconstructed automatically (which means that we can still implement things like lazy evaluation or automatic parallelization under the hood).

Now, we did lose something by eliminating parentheses are explicit delimiters of argument lists: you can't handle variadic functions anymore (well, unless you do crazy Haskell stuff). But, for the most part, you don't really need variadic functions. Lisps tend to map rest arguments to lists anyway, so just pass list. If you want, say, variadic add, just write a function to fold a list over binary add. Something like...

define '(\+ l) fold + 0 l, oops. Type error. That code will be automatically parenthesized as follows:

(define (\+ l) (fold (+ 0 l)))

+ needs two numbers, not a number and a list, and fold doesn't take a number as it's first argument (plus, it needs a couple more). What we need is some way to turn off the application of + and get its value instead. We only need this for passing first-class function values as arguments, and that happens far less often than function applications do in most programs, so we can bring back parentheses for that (the exact opposite of their original purpose) and still have a net gain in program concision (and reduced nesting):

define '(\+ l) fold (+) 0 l

We're using parentheses here rather than some other symbol (like, say, a prefixed # or something) to indicate non-application, because we can actually put more stuff in there- a whole list of stuff, in fact. Maybe something like

define '(list-double-plus l) map (+ 1 * 2) l

What's really going on here is not that parentheses are suppressing application- rather, parentheses delimit lists (just like they do when quoted), but now, instead of representing function applications, unquoted lists represent functions that return functions composed of the contents of the list. (+) isn't a binary operator that hasn't been applied, rather it's a new function that returns a function composed solely of that binary operator. It gets applied as normal (to zero arguments), but its return value is what fold needed as its first argument. (+ 1 * 2) returns a function that's the composition of +, 1, *, and 2, with automatic currying. With these semantics, we don't actually need a separate "lambda" construct in the language anymore, since lists produce anonymous functions- as long as you're willing to program in point-free style, anyway.
If we just imagine the whole program as wrapped in one big set of top-level, outside parentheses, we can see that all programs are still lists- just less deeply nested ones. The language is still homoiconic, so it's still pretty easy to do metaprogramming, and it still makes sense to call this a dialect of Lisp.

Addendum on String Formatting:

The canonical example of a variadic function is a string formatter (which is what that Haskell variadic craziness was developed for, too). Since it's horribly stupid to get format strings out of variables, though,  and you should always have them as literals in the program text, we can solve that problem by building string formatting/interpolation into the language as have the language implementation turn literal strings into functions that take a fixed number of arguments (for the interpolation slots) and return string values.