Simple and Efficient Compilation of List Comprehension in Common Lisp

摘要

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.rnWe 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.rnWe 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.rnThe author has used the first translation technique for compiling a new language called BioVelo, which is part of bioinformatics software called Pathway Tools [2].