Fast Sequence Iteration in Common Lisp

Summary

Fast SEQUENCE iteration in Common LispIf you don't know what sequences are in CL, here's the gist of it: either a linked list or a vector. The main idea being that some operations like element search, comparison or deletion should have the same interface for both those types.Basically, sequences are a band-aid over the lack of real iterator protocol (yes, even considering the mildy supported extensible sequences thing). But well, that's what we have to work with and it's not so bad really; we could be in barren C-ountry after all.One of the problems of sequences is that if you want to iterate over these while supporting the conventional keywords (:start, :end, :key) without writing entirely separate (and gnarly) versions, there are only two unified interfaces provided by ANSI:elt+length+loop (or do): naïve and simple, what's actually used under the hood by iterate's in-sequence driver. No free keyword forwarding and quadratic (thus extremely slow) on lists.reduce: way more practical as it handles all the keywords for you (even :from-end) and much faster since any non-toy implementation internally dispatches over the actual sequence type. Still not ideal as it has the overhead of repeat funcall of your closure and you don't have access to the often needed internal raw element (without :key applied) or iteration index.So when I made a naïve max-elt (for this years' Advent of Code) then was forced to rewrite it to use reduce, I said to myself I must build that Lovecraftian macro to handle the required nested monomorphization/specialization… so here's the beast: (defmacro do-sequence ((var seq &key (start 0) end key with-index with-raw-elt) &body body) "Iterate on a sequence with the usual keywords available. :WITH-INDEX (resp. :WITH-RAW-ELT) takes an unevaluated symbol to use as index (resp. element without :KEY applied). NB: since iteration is done via `(LOOP ... :DO (LOCALLY ,@BODY)), said body can use RETURN and contain declarations." (once-only (seq start end key) ...