generic-sequences

2015-07-09
GENERIC-SEQUENCES -- Generic sequences for Common Lisp

GENERIC-SEQUENCES-CONT -- Generic sequence comprehension for Common Lisp

GENERIC-SEQUENCES-ITERATE -- Generic sequence iteration for Common Lisp

GENERIC-SEQUENCES-STREAM -- Lazy streams for Common Lisp

GENERIC-SEQUENCES-TEST -- Unit tests for the generic sequences 

Generic Sequences is a library for Common Lisp. It introduces the generic sequences, which are a hybrid between the ordinary lists, lazy streams and iterable sequences that can be found in other programming languages such as C#, F#, Java and Scala. 

Each sequence returns an enumerator or NIL. The NIL value means that the sequence is empty. The enumerator is a cons cell, which CAR part has the ordinary meaning for Common Lisp, i.e. it returns the current element, while the CDR-part is different. That part is already a function that returns either the next enumerator or NIL in case of reaching the end of the sequence. In other words, there is a delay before receiving the next element of the sequence, which actually makes many sequences lazy.

Unlike the lazy streams, the enumerator always returns a new continuation of the sequence through the CDR part. It recalculates the next element anew, while the stream would memoize it. When iterating, this makes the enumerator more efficient computationally as the memoization would require some kind of locking in the multi-threaded environment.

At the same time, unlike the C# enumerators, our enumerator is like a list cell, which allows defining the sequence in a more easy and declarative way as if we defined an ordinary list. Macros introduced below simplify this process. There exists even the sequence comprehension similar to the F# sequence expression syntax and the yield construction from C#.

Unfortunately, the approach has a drawback. When iterating the sequence, it allocates a lot of small short-term objects on the heap. But the tests show that the modern List-machines have efficient garbage collectors and sometimes the consing is relatively fast, at least in comparison with calling the generic functions. Along with simplicity of defining the sequences, it was the second reason why I decided to apply the described representation to the enumerators. They are not just as slow as they might seem!

Please read the Generic Sequences Manual in the doc directory for more information.
Author
David Sorokin
License
MIT