Citation
Latendresse, M. (2007, April). Simple and efficient compilation of list comprehension in Common Lisp. In Proceedings of the 2007 International Lisp Conference (pp. 1-6).
Abstract
List Comprehension is a succinct syntactic form to describe lists in functional languages. It uses nested generators (i.e., iterators) and filters (i.e., Boolean expressions). The former generates lists, whereas the latter restricts the contents of these lists. List Comprehension translation is commonly based on Wadler’s rules that emit code based on recursive functions. This code often results either in stack overflow or in inefficient execution for many Common Lisp implementations.
We present a very simple technique to compile List Comprehension in the Loop Facility of Common Lisp, resulting in efficient code that avoids stack overflow. Our translation code is also very short, with an emitted code very close to the user-specified list comprehension.
We also present a translation into more fundamental constructs of Common Lisp that often results in even more efficient code, although this translation is more complex than using the Loop Facility.
The author has used the first translation technique for compiling a new language called Bio Velo, which is part of bioinformatics software called Pathway Tools.
