Difference between revisions of "Publications/newton.17.els"
From LRDE
(6 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
{{Publication |
{{Publication |
||
− | | published = |
+ | | published = true |
| date = 2017-02-06 |
| date = 2017-02-06 |
||
| authors = Jim Newton, Didier Verna, Maximilien Colange |
| authors = Jim Newton, Didier Verna, Maximilien Colange |
||
Line 6: | Line 6: | ||
| booktitle = European Lisp Symposium |
| booktitle = European Lisp Symposium |
||
| lrdeinc = Publications/newton.17.els.inc |
| lrdeinc = Publications/newton.17.els.inc |
||
− | | lrdekeywords = |
+ | | lrdekeywords = Graph algorithms, typechecking, Boolean functions, Binary decision diagrams, data structures |
| lrdenewsdate = 2017-02-06 |
| lrdenewsdate = 2017-02-06 |
||
− | | lrdestatus = |
+ | | lrdestatus = accepted |
| lrdepaper = http://www.lrde.epita.fr/dload/papers/newton.17.els.pdf |
| lrdepaper = http://www.lrde.epita.fr/dload/papers/newton.17.els.pdf |
||
− | | |
+ | | lrdeslides = http://www.lrde.epita.fr/dload/papers/newton.17.els.slides.pdf |
| lrdeprojects = Climb |
| lrdeprojects = Climb |
||
| address = Brussels, Belgium |
| address = Brussels, Belgium |
||
| abstract = In this article we contrast the use of the s-expression with the BDD (Binary Decision Diagram) as a data structure for programmatically manipulating Common Lisp type specifiers. The s-expression is the de facto standard surface syntax and also programmatic representation of the type specifier, but the BDD data structure offers advantages: most notably, type equivalence checks using s-expressions can be computationally intensive, whereas the type equivalence check using BDDs is a check for object identity. As an implementation and performance experimentwe define the notion of maximal disjoint type decomposition, and discuss implementations of algorithms to compute it: a brute force iteration, and as a tree reduction. The experimental implementations represent type specifiers by both aforementioned data structures, and we compare the performance observed in each approach. |
| abstract = In this article we contrast the use of the s-expression with the BDD (Binary Decision Diagram) as a data structure for programmatically manipulating Common Lisp type specifiers. The s-expression is the de facto standard surface syntax and also programmatic representation of the type specifier, but the BDD data structure offers advantages: most notably, type equivalence checks using s-expressions can be computationally intensive, whereas the type equivalence check using BDDs is a check for object identity. As an implementation and performance experimentwe define the notion of maximal disjoint type decomposition, and discuss implementations of algorithms to compute it: a brute force iteration, and as a tree reduction. The experimental implementations represent type specifiers by both aforementioned data structures, and we compare the performance observed in each approach. |
||
− | | note = Submitted |
||
| type = inproceedings |
| type = inproceedings |
||
| id = newton.17.els |
| id = newton.17.els |
||
Line 24: | Line 23: | ||
booktitle = <nowiki>{</nowiki>European Lisp Symposium<nowiki>}</nowiki>, |
booktitle = <nowiki>{</nowiki>European Lisp Symposium<nowiki>}</nowiki>, |
||
year = 2017, |
year = 2017, |
||
− | lrdestatus = |
+ | lrdestatus = <nowiki>{</nowiki>accepted<nowiki>}</nowiki>, |
− | optlrdeslides = <nowiki>{</nowiki>http://www.lrde.epita.fr/dload/papers/newton.17.els.slides.pdf<nowiki>}</nowiki> |
||
− | , |
||
address = <nowiki>{</nowiki>Brussels, Belgium<nowiki>}</nowiki>, |
address = <nowiki>{</nowiki>Brussels, Belgium<nowiki>}</nowiki>, |
||
month = apr, |
month = apr, |
||
Line 44: | Line 41: | ||
reduction. The experimental implementations represent type |
reduction. The experimental implementations represent type |
||
specifiers by both aforementioned data structures, and we |
specifiers by both aforementioned data structures, and we |
||
− | compare the performance observed in each approach.<nowiki>}</nowiki> |
+ | compare the performance observed in each approach.<nowiki>}</nowiki> |
− | note = <nowiki>{</nowiki>Submitted<nowiki>}</nowiki> |
||
<nowiki>}</nowiki> |
<nowiki>}</nowiki> |
||
Latest revision as of 16:21, 5 February 2018
- Authors
- Jim Newton, Didier Verna, Maximilien Colange
- Where
- European Lisp Symposium
- Place
- Brussels, Belgium
- Type
- inproceedings
- Projects
- Climb
- Keywords
- Graph algorithms, typechecking, Boolean functions, Binary decision diagrams, data structures
- Date
- 2017-02-06
Abstract
In this article we contrast the use of the s-expression with the BDD (Binary Decision Diagram) as a data structure for programmatically manipulating Common Lisp type specifiers. The s-expression is the de facto standard surface syntax and also programmatic representation of the type specifier, but the BDD data structure offers advantages: most notably, type equivalence checks using s-expressions can be computationally intensive, whereas the type equivalence check using BDDs is a check for object identity. As an implementation and performance experimentwe define the notion of maximal disjoint type decomposition, and discuss implementations of algorithms to compute it: a brute force iteration, and as a tree reduction. The experimental implementations represent type specifiers by both aforementioned data structures, and we compare the performance observed in each approach.
Documents
See also the Technical Report with many more details.
Bibtex (lrde.bib)
@InProceedings{ newton.17.els, author = {Jim Newton and Didier Verna and Maximilien Colange}, title = {Programmatic Manipulation of {C}ommon {L}isp Type Specifiers}, booktitle = {European Lisp Symposium}, year = 2017, lrdestatus = {accepted}, address = {Brussels, Belgium}, month = apr, abstract = {In this article we contrast the use of the s-expression with the BDD (Binary Decision Diagram) as a data structure for programmatically manipulating Common Lisp type specifiers. The s-expression is the de facto standard surface syntax and also programmatic representation of the type specifier, but the BDD data structure offers advantages: most notably, type equivalence checks using s-expressions can be computationally intensive, whereas the type equivalence check using BDDs is a check for object identity. As an implementation and performance experiment, we define the notion of maximal disjoint type decomposition, and discuss implementations of algorithms to compute it: a brute force iteration, and as a tree reduction. The experimental implementations represent type specifiers by both aforementioned data structures, and we compare the performance observed in each approach.} }