Difference between revisions of "Publications/newton.19.els"

From LRDE

(Created page with "{{Publication | published = true | date = 2019-01-14 | authors = Jim Newton, Didier Verna | title = Finite Automata Theory Based Optimization of Conditional Variable Binding |...")
 
 
(4 intermediate revisions by the same user not shown)
Line 5: Line 5:
 
| title = Finite Automata Theory Based Optimization of Conditional Variable Binding
 
| title = Finite Automata Theory Based Optimization of Conditional Variable Binding
 
| booktitle = European Lisp Symposium
 
| booktitle = European Lisp Symposium
| lrdestatus = submitted
 
 
| lrdekeywords = finite automata, infinite alphabets, type systems, Common Lisp, meta programming
 
| lrdekeywords = finite automata, infinite alphabets, type systems, Common Lisp, meta programming
 
| lrdenewsdate = 2019-01-14
 
| lrdenewsdate = 2019-01-14
 
| lrdepaper = http://www.lrde.epita.fr/dload/papers/newton.19.els.pdf
 
| lrdepaper = http://www.lrde.epita.fr/dload/papers/newton.19.els.pdf
  +
| lrdeslides = http://www.lrde.epita.fr/dload/papers/newton.19.els.slides.pdf
 
| lrdeprojects = Climb
 
| lrdeprojects = Climb
 
| address = Genova, Italy
 
| address = Genova, Italy
Line 14: Line 14:
 
| type = inproceedings
 
| type = inproceedings
 
| id = newton.19.els
 
| id = newton.19.els
  +
| identifier = doi:10.5281/zenodo.2635412
 
| bibtex =
 
| bibtex =
 
@InProceedings<nowiki>{</nowiki> newton.19.els,
 
@InProceedings<nowiki>{</nowiki> newton.19.els,
Line 21: Line 22:
 
booktitle = <nowiki>{</nowiki>European Lisp Symposium<nowiki>}</nowiki>,
 
booktitle = <nowiki>{</nowiki>European Lisp Symposium<nowiki>}</nowiki>,
 
year = 2019,
 
year = 2019,
lrdestatus = <nowiki>{</nowiki>submitted<nowiki>}</nowiki>,
 
 
address = <nowiki>{</nowiki>Genova, Italy<nowiki>}</nowiki>,
 
address = <nowiki>{</nowiki>Genova, Italy<nowiki>}</nowiki>,
 
month = apr,
 
month = apr,
Line 40: Line 40:
 
destructuring-case in such a way to avoid multiple
 
destructuring-case in such a way to avoid multiple
 
traversals of the candidate expression. This article
 
traversals of the candidate expression. This article
explains how this optimization has been implemented.<nowiki>}</nowiki>
+
explains how this optimization has been implemented.<nowiki>}</nowiki>,
 
doi = <nowiki>{</nowiki>10.5281/zenodo.2635412<nowiki>}</nowiki>
 
<nowiki>}</nowiki>
 
<nowiki>}</nowiki>
   

Latest revision as of 18:08, 7 April 2023

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.

Documents

Bibtex (lrde.bib)

@InProceedings{	  newton.19.els,
  author	= {Jim Newton and Didier Verna},
  title		= {Finite Automata Theory Based Optimization of Conditional
		  Variable Binding},
  booktitle	= {European Lisp Symposium},
  year		= 2019,
  address	= {Genova, Italy},
  month		= apr,
  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.},
  doi		= {10.5281/zenodo.2635412}
}