Common Lisp + cl-series Leaves of a tree

This week on the mastodon lisp people were writing ground-up Structure-and-interpretation-of-computer-programs investigations of leaves of a tree. In the case of common lisp, I prefer to use the modern and historical static analysis into lazy evaluation macro package, cl-series. Raymond Toy recently updated its online (still current!) documentation for us. Series are also described in an appendix of the book, Common Lisp The Language 2. cl-series does static analysis to your declarations at macroexpansion time and creates a tight, efficient in-order loop meeting your series declarative specifications. Note that series objects never really exist after complete compilation (the usual case) - they are a mnemonic for things that the static analysis will build a lazy traversal of. We are going to look at traversing the leaves of a tree, efficiently and in Series’ declarative manner.

eepitch sbcl and series

Using emacs eev and its eepitch of course.

 (eepitch-sbcl)
(require "asdf")
(asdf:load-system :series)

Installing series

One of the more modern and uncommon things about the advanced way cl-series works is that since it does its graph building static analysis and work at ansi common lisp’s macroexpansion time which happens after reading and before evaluation, series needs to be added before a form is read and macroexpanded, the results of which end up pure common lisp,

(series::install)

which has lots of knobs and dials but probably does the thing you want on its own. However, if you are loading or compiling a lisp file or package, you need to let lisp know that the common lisp form to install series’ consequences need to be available before compilation or loading happen, so we often see:

(eval-when
    (:compile-toplevel :load-toplevel)
  (series::install))

; whenever you need it to specifically happen.

Series useages

Interactive, hand-typed series

Especially useful when exploratively building your series expression, when series cannot see a graph to the end-result of what you are trying to do, it has performatively series-like but unoptimized series package objects. We can just type one of these on its own, for example.

#Z(1 2 3)

On the other half of our screen, tapping <F8> we see:

* #Z(1 2 3)
#Z(1 2 3)

we can complete a series graph by bringing it back to lisp list with collect declarations:

(collect *)

here, series is letting us know that we were not truly using series’ to its proper potential:

* (collect *)
WARNING: Warning 28 in series expression:
(COLLECT *)
Non-series to series data flow from:
*
to:
(COLLECT *)
(1 2 3)
* 

the number of things that can stop series from building a graph properly are quite finite and tractable- and it is always eventually possible to realise a compileable series expression. The documentation has explanations of and hints about resolving its warnings and violations.

series::let*…scan…choose…collect

More usually, we bit by bit build our series expression in terms of declarations building on earlier declarations. As an entry point to its macroexpand time static analysis, series shadows common lisp entrypoints like let and let*.

(let* ((list '(1 2 3))
       (z (scan list))
       (choice (choose (#Moddp z) z)))
  (collect choice))

You can see I snuck in choose and the #M≝make-series::mapping-out-of-function macro to keep things interesting.

A weird function demo

(defun pick-len-leaves-less-than
    (tree len limit)
  (let* ((fringe (scan-lists-of-lists-fringe tree))
	 (infinite-series-of-limit (series limit))
	 (numbers (choose
		   (#Mnumberp fringe)
		   fringe))
	 (small-leaves (choose
			(#M< numbers
			     infinite-series-of-limit)
			numbers))
	 (mask (scan-range :below len)))
    (collect (choose mask small-leaves))))
	 

Removing series after our function definition using it

(series::install :remove t)

See our tight, efficient fringe traversal function example working

* '((1 (2)) (3 (4 (5) 6)) (7) 8)
((1 (2)) (3 (4 (5) 6)) (7) 8)
* (pick-len-leaves-less-than * 5 6)
(1 2 3 4 5)
* (reverse **)
(8 (7) (3 (4 (5) 6)) (1 (2)))
* (pick-len-leaves-less-than * 5 6)
(3 4 5 1 2)

Concluding

cl-series is a good fundamental building block that uses macroexpansion-time static analysis to build tight, efficient in-order traversals of arbitrary sequences with excellent cooked in functionalities and extensibility. Because the only thing series does is build tight, efficient, in-order traversals, our declarations for it are clear and terse. We never have to state that we want a tight, efficient in-order traversal: there is no other option.

We also found that its lazy evaluation is relevant to traversing the fringe of a list of lists by limiting the type and number of leaves being collected.

Fin

See you on the Mastodon thread. In particular, if there is a lazy, tight, declarative series traversal you would like to see, please let me know there. So far as concerns my plans for this week, series fits in because I would like to use the native lisp it generates via parenscript with my kittens.