Finite Automata Theory Based Optimization of Conditional Variable Binding
Type
Event
Date
Apr 1, 2019 — Apr 2, 2019
Abstract
We present an efficient and highly optimized implementation of
destructuring-case in Common Lisp. This macro allows the selection of the
most appropriate destructuring lambda list of several given based on
structure and types of data at run-time and thereafter dispatches to the
corresponding code branch. We examine an optimization technique, based on
finite automata theory applied to conditional variable binding and
execution, and type-based pattern matching on Common Lisp sequences. A risk
of inefficiency associated with a naive implementation of destructuring-case
is that the candidate expression being examined may be traversed multiple
times, once for each clause whose format fails to match, and finally once
for the successful match. We have implemented destructuring-case in such a
way to avoid multiple traversals of the candidate expression. This article
explains how this optimization has been implemented.