arXiv (Cornell University) · 2017 · 103 citations · 0 references
ComputingComputer ScienceLinguisticsCompilersProgramming LanguagesSyntaxAbstract Syntax TreesSyntactic AnalysisSyntax AnalysisType CheckingType ClassificationType SystemsType Parameterization
In this article we contrast the use of the s-expression with the BDD<br> (Binary Decision Diagram) as a data structure for programmatically<br> manipulating Common Lisp type specifiers. The s-expression is the<br> \textit{de facto} standard surface syntax and also programmatic<br> representation of the type specifier, but the BDD data structure<br> offers advantages: most notably, type equivalence checks using<br> s-expressions can be computationally intensive, whereas the type<br> equivalence check using BDDs is a check for object identity. As an<br> implementation and performance experiment, we define the notion of<br> maximal disjoint type decomposition, and discuss implementations of<br> algorithms to compute it: a brute force iteration, and as a tree<br> reduction. The experimental implementations represent type<br> specifiers by both aforementioned data structures, and we compare<br> the performance observed in each approach.