Recognizing Heterogeneous Sequences by Rational Type Expression

From LRDE

Abstract

We summarize a technique for writing functions which recognize types of heterogeneous sequences in Common Lisp. The technique employs sequence recognition functionsgenerated at compile time, and evaluated at run-time. The technique we demonstrate extends the Common Lisp type system, exploiting the theory of rational languages, Binary Decision Diagrams, and the Turing complete macro facility of Common Lisp. The resulting system uses meta-programming to move an exponential complexity operation from run-time to a compile-time operation, leaving a highly optimized linear complexity operation for run-time.

Documents

Bibtex (lrde.bib)

@InProceedings{	  newton.18.meta,
  author	= {Jim Newton and Didier Verna},
  title		= {Recognizing Heterogeneous Sequences by Rational Type
		  Expression},
  booktitle	= {Proceedings of the Meta'18: Workshop on Meta-Programming
		  Techniques and Reflection},
  year		= 2018,
  address	= {Boston, MA USA},
  month		= nov,
  abstract	= { We summarize a technique for writing functions which
		  recognize types of heterogeneous sequences in Common Lisp.
		  The technique employs sequence recognition functions,
		  generated at compile time, and evaluated at run-time. The
		  technique we demonstrate extends the Common Lisp type
		  system, exploiting the theory of rational languages, Binary
		  Decision Diagrams, and the Turing complete macro facility
		  of Common Lisp. The resulting system uses meta-programming
		  to move an exponential complexity operation from run-time
		  to a compile-time operation, leaving a highly optimized
		  linear complexity operation for run-time.},
  lrdestatus	= {accepted},
  nodoi		= {}
}