cl-series graphs declarations and optimizes
Table of Contents
The classic package cl-series was "80% of Haskell made by one graduate student" in the 1970s. I would argue that missing the other 20% typing baloney of Haskell is actually an improvement as well.
https://github.com/rtoy/cl-series/
Consider this cl-series macro form.
1. Change symbols from old to new in sequence
(defun change-sym
(old new sequence)
(let* ((series
(scan sequence))
(olds
(series old))
(bools
(#Meq olds series))
(news
(series new))
(choice
(choose bools series)))
(alter choice news)))
being six declarations, five of which sequentially define series, and the last alter declaration.
2. Seeing that working
CL-USER> (require :series)
("SERIES")
CL-USER> (series::install)
CL-USER> (defun change-sym (old new sequence)
(let* ((series (scan sequence))
(olds (series old))
(bools (#Meq olds series))
(news (series new))
(choice (choose bools series)))
(alter choice news)))
CHANGE-SYM
CL-USER> #(foo bar baz)
#(FOO BAR BAZ)
CL-USER> (change-sym 'foo 'frob *)
NIL
CL-USER> **
#(FROB BAR BAZ)
As we can see, those series declarations result in the destructive modification of an input array.
3. cl-series' mechanism
All of series' magic happens at macroexpansion time (lisp programs that run when lisp expressions are read), so after reading, series can be uninstalled and the series program is still there (it ends up as pure common lisp).
The only thing series does is construct a tight in-order traversal reflecting the declarations. Since this is the only thing cl-series does, we never have to declare that what we want a tight in-order traversal.
The series objects themselves are never really real. They are a stand-in for identifiable steps in the in-order traversal of a the scanned sequence.
Series does this by constructing a graph and performing prolog-like processing of its declarations.
While series is exceptionally clear and powerful to use itself, one must not miss the implication of cl-series' approach for knowledge-based graph processing as a general principle.
4. What Series Actually Built appendix
CL-USER> *last-series-loop*
(COMMON-LISP:LET* ((#:OUT-10 SEQUENCE) (#:OUT-12 OLD) (#:OUT-19 NEW))
(COMMON-LISP:LET (SERIES
#:PARENT-3
#:LISTPTR-4
#:TEMP-5
(#:LIMIT-6 0)
(#:INDEX-7 -1)
#:LSTP-8
BOOLS)
(DECLARE (TYPE LIST #:PARENT-3)
(TYPE LIST #:LISTPTR-4)
(TYPE SERIES::VECTOR-INDEX+ #:LIMIT-6)
(TYPE SERIES::-VECTOR-INDEX #:INDEX-7)
(TYPE BOOLEAN #:LSTP-8))
(LOCALLY
(DECLARE (TYPE ARRAY #:TEMP-5))
(IF (SETQ #:LSTP-8 (LISTP #:OUT-10))
(SETQ #:LISTPTR-4 #:OUT-10
#:TEMP-5 #())
(LOCALLY
(DECLARE (TYPE ARRAY #:OUT-10))
(SETQ #:TEMP-5 #:OUT-10)
(SETQ #:LIMIT-6
(SERIES::ARRAY-FILL-POINTER-OR-TOTAL-SIZE #:OUT-10))))
(TAGBODY
#:LL-27
(IF #:LSTP-8
(PROGN
(IF (ENDP #:LISTPTR-4)
(GO SERIES::END))
(SETQ #:PARENT-3 #:LISTPTR-4)
(SETQ SERIES (CAR #:LISTPTR-4))
(SETQ #:LISTPTR-4 (CDR #:LISTPTR-4)))
(PROGN
(INCF #:INDEX-7)
(LOCALLY
(DECLARE (TYPE ARRAY #:OUT-10)
(TYPE SERIES::VECTOR-INDEX #:INDEX-7))
(IF (>= #:INDEX-7 #:LIMIT-6)
(GO SERIES::END))
(SETQ SERIES
(THE SERIES::*TYPE*
(ROW-MAJOR-AREF #:OUT-10 #:INDEX-7))))))
(SETQ BOOLS
((LAMBDA (#:V-14 #:V-13) (EQ #:V-14 #:V-13)) #:OUT-12 SERIES))
(IF (NOT BOOLS)
(GO #:F-20))
(IF #:LSTP-8
(SETF (CAR #:PARENT-3) #:OUT-19)
(SETF (ROW-MAJOR-AREF #:TEMP-5 (THE SERIES::VECTOR-INDEX #:INDEX-7))
#:OUT-19))
#:F-20
(GO #:LL-27)
SERIES::END)
NIL)))