LISPy things you can do in 64K bytes of core

Code Grinding

"Code Grinding" is ancient slang for pretty-printing LISP programs. The grinder is a serious program: its source code is about 6K bytes in size and it allocates more than 2000 nodes! Hence it is advisable to package it in a separate image file for daily use, i.e.:

(load 'src//grind)
(suspend 'klgrind)

The interpreter can then be started with kl klgrind and the grinder will be available immediately! It was common to have different LISP images for different tasks back in the days of early LISP.

What the grinder does it to take an S-expression forming a LISP program and printing a nicely indented version of the expression:

* (grind '(let ((a '(a b c)) (b '(1 2 3))) (map
          (lambda (x y) (cons y x)) a b)))

would output

(let ((a '(a b c))
      (b '(1 2 3)))
  (map
    (lambda (x y)
      (cons y x))
    a
    b)))

Of course, a modern pretty-printer would align the application of map more beautifully:

(map (lambda (x y)
       (cons y x))
     a
     b))

but this is not possible in (early) purely symbolic LISP, because there is no way to measure the length of a symbol name. Doing so would require the EXPLODE function, which deconstructs a symbol name into a list of single-character names, or the FLATSIZE function, which directly returns the length of a symbol. Both probably appeared in 1967 [6].

Note that GRIND is able to indent the LET form beautifully, because the size of "LET" is known to be 3 characters without measuring it. Hence the grinder can indent predefined special forms more aesthetically pleasing than user-defined code.

The grinder keeps track of the current level of indentation by using a list to represent a base-1 number. Here is the code for zero-testing, decrementing, incrementing, and adding base-1 numbers:

(setq zerop null)
(setq dec   cdr)
 
(setq inc
  (lambda (x)
    (cons 'i x)))

(setq add
  (lambda (x y)
    (conc x y)))

Note that a list representing a base-1 number may contain any elements, only the number of elements is important. The following lists all represent the number 3:

'(i i i)
#iii
'(1 2 3)
#123
'(foo bar baz)

The notation #xyz is a Kilo LISP shortcut for (quote (x y z)). In the GRIND source code, base-1 numbers are often written as #1234567 instead of #iiiiiii, because it allows to identify the number more easily without having to count the i's first.

The SPACES function emits the desired number of leading blanks in intended code:

(setq spaces
  (lambda (n)
    (cond ((zerop n))
          (else (prin1 sp)
                (spaces (dec n))))))

To temporarily increase indentation, the global variable OFF ("offset") is changed using the WITH special form, which expands as follows:

(with (v a)      -->  ((lambda (G1)  ; Gx is a gensym
  do something)          (setq v a)
                         (let ((G2 (prog do something)))
                           (setq v G1)
                           G2)
                       v)

That is, it saves the original value of V, changes it to A, evaluates the body of the form, resets V to its original value and returns the value of the body. It implements dynamic scoping. The code that pretty-prints LAMBDA using WITH looks like this:

(setq pplam
  (lambda (x)
    (prin1 lp)          ; left paren
    (prin1 'lambda) 
    (prin1 sp)          ; space
    (pp (cadr x))
    (with (off (add #12 off))
      (terpri)
      (ppbody (cddr x))
      (prin1 rp))))     ; right paren

By adding the two-element list #12 to OFF, the indentation is increased by two blanks. With that additional indentation the body of the function is printed. The TERPRI function emits the desired leading white space after a line break. Because WITH restores the original value of OFF, there is not need for a function that subtracts numbers.

Because it cannot measure the length of symbols, the grinder makes various assumptions about the code, which may not always be accurate. For example, it assumes that OBPERLN ("objects per line") objects fit in a line when printing a list. This may be wrong, of course, but since the lengths of symbols cannot be measured, nothing can be done about it:

* (grind ''(a b c d e f g h i j k l m n o p q r s t u v w x y z))
'(a b c d e f g h i j k l
  m n o p q r s t u v w x
  y z))

* (grind ''(supercalifragilisticexpialidocious
            deoxyribonucleic
            Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch))
'(supercalifragilisticexpialidocious deoxyribonucleic Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch)

The grinder also assumes that function applications whose forms contain at least LONGLEN ("long length") atoms will not fit in a single line, which may be equally wrong. However, LISP being an interactive language, the values of OBPERLN or LONGLEN can be changed at any time when printing expression for which the heuristics fail:

* (with (obperln #1234567890123)
    (grind ''(a b c d e f g h i j k l m n o p q r s t u v w x y z)))
'(a b c d e f g h i j k l m
  n o p q r s t u v w x y z)

* (with (longlen #1234567890)
    (grind '(foo a (b c) (d e f))))
(foo a (b c) (d e f))

Grinding is not only a tool for formatting LISP code in a pleasing way, it can also be used for debugging. Have a look at the following program, which should print the atoms in A, but doesn't. Remember that typing in programs in this way was common in the age of paper TTYs!

(lambda (a) (loop next ((a a)) (cond ((null a))
((atom (car a))) (print (car a)) (next (cdr a))
(else (next (cdr a))))))

By grinding the program, the problem becomes apparent immediately:

(lambda (a)
  (loop next
        ((a a))
    (cond ((null a))
          ((atom (car a)))  ; <-- extra paren
          (print
            (car a))
          (next
            (cdr a))        ; <-- missing paren
          (else
            (next (cdr a))))))

Measured by modern standards GRIND is a simple program. Modern pretty-printers have multiple templates for all kinds of expressions and do backtracking to find the best fit. This cannot be done in GRIND, because EXPLODE and FLATSIZE are missing from early LISP.

Even if the lengths of symbols cannot be measured, some more intuitive form for numbers would be nice to have. Can this be done in purely symbolic LISP? (Spoiler: of course it can!)


contact  |  privacy