Composable language extensions for computational geometry: A case study

This paper demonstrates how two different sets of powerful domain specific language features can be specified and deployed as composable language extensions. These extensions in-corporate analyses and transformations that simplify the process of writing efficient and robust computational geometry programs and can be automatically added to a host language and used simultaneously. This is not possible in domain-specific language and library-based implementations of these features. One extension relies on characteristics of geometric algorithms to implement efficient exact-precision integers; the other employs a technique that symbolically perturbs geometric coordinates to safely and automatically handle degeneracies in the input data. These language extensions are implemented in an extensible language framework based on higher-order attribute grammars and forwarding. Attribute evaluation on the new language extension constructs is used to implement the static analysis and code transformations that enable the generation of efficient code.