The Heading Level Problem

Headings have a problem that lisp’s S-expressions do not: that s-expressions explicitly close.

Consider the lisp expression

Admittedly, goto was considered harmful by Dijkstra.

• (setq inferior-lisp-program "sbcl") ; my setup
• (slime)
• (setq eepitch-buffer-name "*slime-repl sbcl*")
(progn
  (do ((x '(1 (0) 3) (prog1 x (incf (caadr x)))))
      (nil)
    (case (random 3)
      (0 (go decrease))
      (1 (go exit))
      (2 (go continue)))
   decrease
    (decf (caadr x))
    (go continue)
   exit
    (return x)
   continue))

Pointless in this case but a conceivable use of do’s implicit tagbody.

Heights

(defun atom-heights (form &optional (height 0))
  (loop
    :for item :in form
    :if (atom item) :collect
      height :into heights
    :else
      :nconc (atom-heights item (1+ height)) :into heights
    :if (atom item) :collect
      item :into items
    :else
      :nconc (nth-value 1 (atom-heights item)) :into items
    :finally
       (return (values heights items))))

it is going to haunt me how to write that atom-heights using do.

Another aside

I loaded and use-packaged my gnuplot from here.

A plot of atom height in a common lisp form

(multiple-value-bind
      (heights items)
    (atom-heights
     '(progn
       (do ((x '(1 (0) 3) (prog1 x (incf (caadr x)))))
	   (nil)
	 (case (random 3)
	   (0 (go decrease))
	   (1 (go exit))
	   (2 (go continue)))
	decrease
	 (decf (caadr x))
	 (go continue)
	exit
	 (return x)
	continue)))

  (let* ((ys (mapcar 'list heights))
	 (xs (loop :for x from 0 :below (length ys)
		   :collect x)))
    (gnuplot "a common lisp form height"
	     (pairlis xs ys)))
  (mapc 'print
	(reverse (pairlis heights items)))
  nil)

i.e. `(height . atom)

(0 . PROGN) 
(1 . DO) 
(3 . X) 
(4 . QUOTE) 
(5 . 1) 
(6 . 0) 
(5 . 3) 
(4 . PROG1) 
(4 . X) 
(5 . INCF) 
(6 . CAADR) 
(6 . X) 
(2) 
(2 . CASE) 
(3 . RANDOM) 
(3 . 3) 
(3 . 0) 
(4 . GO) 
(4 . DECREASE) 
(3 . 1) 
(4 . GO) 
(4 . EXIT) 
(3 . 2) 
(4 . GO) 
(4 . CONTINUE) 
(1 . DECREASE) 
(2 . DECF) 
(3 . CAADR) 
(3 . X) 
(2 . GO) 
(2 . CONTINUE) 
(1 . EXIT) 
(2 . RETURN) 
(2 . X) 
(1 . CONTINUE)  

We can see that DECREASE, EXIT and CONTINUE are atoms at the same height as DO, occuring after higher heading forms.

The ambiguity is whether they be the beginning of a new expression of that level, or they be atoms in a continuing list of that level.

Otherwise requires an s-expression like structure with both begin and end tokens to allow

1. Chapter 2
2. Chapter 2 section ω
3. back to regular Chapter 2 for a while
4. Chapter 3

which appears not to be allowed.

Conclusions

I kind of lost confidence in my thesis that this is a significant problem while writing this, though I think ambiguity does occur in a variety of practical scenarios.

It was kind of fun to gnuplot the height of a lisp form (it would be interesting to do that for each package in a large lisp project).

Directly figuring out the height of a tree’s leaves iteratively escaped me for the moment.

Out of interest, I believe org-mind-map construes equal (in the sense of string=, as dot(1) would) org headings to be the same node, so one would get back to the level above by nesting the a next-level heading with the same name as the parent inside the child node, since a digraph only goes forward. This then at least renders sanely in graphviz dot.

Fin.

Obviously this thought was wandering after interviewing Karl Voit about orgdown and markdown yesterday, though this does not constitute my additional write-up of that. Look at the description of that downloadable recording for Karl’s own notes and links. The quality of the audio fixes after Karl turns off his video in the call ten minutes in.

Still, see you on the Mastodon. I should get back to NicCLIM next.

Nonsense

(defun atom-heights (form &optional (height 0))
  (loop
    :for item :in form
    :if (atom item) :collect
      height :into heights
    :else
      :nconc (atom-heights item (1+ height)) :into heights
    :if (atom item) :collect
      item :into items
    :else
      :nconc (nth-value 1 (atom-heights item)) :into items
    :finally
       (return (values heights items))))

(multiple-value-bind
      (heights items)
    (atom-heights
     '(progn
       (do ((x '(1 (0) 3) (prog1 x (incf (caadr x)))))
	   (nil)
	 (case (random 3)
	   (0 (go decrease))
	   (1 (go exit))
	   (2 (go continue)))
	decrease
	 (decf (caadr x))
	 (go continue)
	exit
	 (return x)
	continue)))

  (let* ((ys (mapcar 'list heights))
	 (xs (loop :for x from 0 :below (length ys)
		   :collect x)))
    (gnuplot "a common lisp form height"
	     (pairlis xs ys)))
  (mapc 'print
	(reverse (pairlis heights items)))
  nil)

Heh.