How to Balance Parentheses in Lisp or Scheme

One thing that was very interesting in the classic Structure and Interpretation of Computer Program lectures by Jay Sussman and Hal Abelson was the effortlessness that Mr. Sussman was able to balance parentheses while writing code on a chalk board. One of the biggest complaints from new Lisp or Scheme programmers is the difficulty of balancing parens. In fact, my major advisor joked that Lisp stood for Lots of Irritating Single Parentheses.

From what I can tell, the best way to balance parens in a LISP-like language is to not balance the parens directly, instead balance parens by using the identifiers after the parens as guide posts. If you watch the videos (which I highly recommend) you will see Mr. Sussman calling out the identifiers as he is balancing them. Take as an example the following bit of code:

(define (sum-of-squares x y)
  (+ (square x) (square y

After he had written everything up to the ‘y’, you would hear him say, “’square’ ‘plus’ ‘define’”. Each time he called out an identifier he would add a closing paren to arrive at:

(define (sum-of-squares x y)
  (+ (square x) (square y)))

Here is a second example:

(define (div-interval x y)
  (mul-interval x
  (make-interval (/ 1.0 (upper-bound y))
  (/ 1.0 (lower-bound y

He would call it out as “‘lower-bound’ ‘divides’ ‘make-interval’ ‘mul-interval’ ‘define’” to arrive, effortlessly, at:

(define (div-interval x y)
  (mul-interval x
  (make-interval (/ 1.0 (upper-bound y))
  (/ 1.0 (lower-bound y)))))

Unfortunately, it is not quite as simple as this. On occasion, you may have add multiple parens for each identifier. For example:

(define (dismiss lst x k)
  (cond ((null? lst) ())
    ((= (remainder x k) 0) (dismiss (cdr lst) (+ 1 x) k))
    ((cons (car lst) (dismiss (cdr lst) (+ 1 x) k)))))

The closing parens are called out as “‘dismiss’ ‘cons’ ‘cond’ ‘define’”, but you’re one paren short. When calling out ‘cons’, two parens should have been added. It is fairly easy to recognize the sitautions where two parens should be added. Fortunately, with practice this gets easy very quickly.

September 10, 2009   Posted in: Programming

One Response

  1. Justin Deltener - October 19, 2009

    What I like about this post is that if I ever want to take up a ridiculously absurd language that whores out its parenths to any passers-by, I can use this for reference. Aaaand, bookmarked.

Leave a Reply