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

From LRDE
Line 18: Line 18:
 
| id = newton.17.els
  
| id = newton.17.els
 
| bibtex =
 
| bibtex =
  +
@InProceedings<nowiki>{</nowiki> newton.17.els,
  +
author = <nowiki>{</nowiki>Jim Newton and Didier Verna and Maximilien Colange<nowiki>}</nowiki>,
  +
title = <nowiki>{</nowiki>Programmatic Manipulation of <nowiki>{</nowiki>C<nowiki>}</nowiki>ommon <nowiki>{</nowiki>L<nowiki>}</nowiki>isp Type
  +
Specifiers<nowiki>}</nowiki>,
  +
booktitle = <nowiki>{</nowiki>European Lisp Symposium<nowiki>}</nowiki>,
  +
year = 2017,
  +
lrdestatus = submitted,
  +
optlrdeslides = <nowiki>{</nowiki>http://www.lrde.epita.fr/dload/papers/newton.17.els.slides.pdf<nowiki>}</nowiki>
  +
,
  +
address = <nowiki>{</nowiki>Brussels, Belgium<nowiki>}</nowiki>,
  +
month = apr,
  +
abstract = <nowiki>{</nowiki>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.<nowiki>}</nowiki>,
  +
note = <nowiki>{</nowiki>Submitted<nowiki>}</nowiki>
  +
<nowiki>}</nowiki>
  +
 
}}
  
}}

Revision as of 17:39, 13 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.

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	= submitted,
  optlrdeslides	= {http://www.lrde.epita.fr/dload/papers/newton.17.els.slides.pdf}
		  ,
  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.},
  note		= {Submitted}
}






Retrieved from "https://www.lrde.epita.fr/index.php?title=Publications/newton.17.els&oldid=107232"