Difference between revisions of "Publications/newton.17.els"
From LRDE
| Line 1: | Line 1: | ||
{{Publication |
{{Publication |
||
| − | | published = |
+ | | published = false |
| date = 2017-02-06 |
| date = 2017-02-06 |
||
| authors = Jim Newton, Didier Verna, Maximilien Colange |
| authors = Jim Newton, Didier Verna, Maximilien Colange |
||
| Line 10: | Line 10: | ||
| lrdestatus = submitted |
| lrdestatus = submitted |
||
| lrdepaper = http://www.lrde.epita.fr/dload/papers/newton.17.els.pdf |
| lrdepaper = http://www.lrde.epita.fr/dload/papers/newton.17.els.pdf |
||
| − | | |
+ | | optlrdeslides = 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 experiment, we define the notion of maximal disjoint type |
+ | | 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 decompositionand 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 |
||
Revision as of 16:07, 9 February 2017
- Authors
- Jim Newton, Didier Verna, Maximilien Colange
- Where
- European Lisp Symposium
- Place
- Brussels, Belgium
- Type
- inproceedings
- Projects
- Climb
- Keywords
- Rational languages, typechecking, finite automata
- 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 experiment, we define the notion of maximal disjoint type decompositionand 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.