Transcript distil2
DiSTiL : A Transformation Library for Data Structures Yannis Smaragdakis 1 Overview DiSTiL is a project to add GenVoca Components to Microsoft’s IP Domain: container data structures 2 Overview (Continued) Goal: increase productivity by programming in high-level data structure abstractions cursor container 3 Overview (Continued) Create complex container data structures by composing DiSTiL components Design rule checking to ensure validity of component compositions Automatic selection of data structures according to retrieval predicates 4 Implementation Platform IP Transformation System (Microsoft Research) Handling of code with tree primitives User can define new language primitives (intentions) and write code to transform them at compilation (reduction) time 5 DiSTiL Library (Realms) Data Structures (arrays, linked lists, redblack trees, hash-tables) Storage (Persistent and Transient storage) Architectural (create code in functions) Special purpose layers (LRUTree) Various data-structure related layers (garbage collection, bound checks) Hidden layers (out-of-bounds, predicate, order) 6 DiSTiL Type Expressions Typex construct: the composition of components (layers) that defines the target container data structure Huge number of distinct container data structures can be generated from compositions of DiSTiL components 7 Cursors Cursors define retrieval predicates over containers cursor(emp_cont, name < “An” && name > “Akers”, no_order) Predicates used to generate efficient code for retrievals The “smart” part of the library 8 A Composite Data Structure typex Example = malloc[transient] Keen 4789711 Jones Lam 4719711 Guy 4769711 Ajit 4759711 4709711 Koch Mann 4749711 4799711 Land 4739711 Smith 4729711 9 A Composite Data Structure key=name typex Example = tree[malloc[transient]] Keen 4789711 Jones Lam 4719711 Guy 4769711 Ajit 4759711 4709711 Koch Mann 4749711 4799711 Land 4739711 Smith 4729711 10 A Composite Data Structure key=phone key=name typex Example = hash [ tree [ malloc [ transient]]] Keen 4789711 Jones Lam 4719711 Guy 4769711 Ajit 4759711 4709711 Koch Mann 4749711 4799711 Land 4739711 Smith 4729711 11 How to Use 12 What to Notice Programming abstractions in domain-specific makes code easier to understand makes code more reliable (simpler and checked at a higher level) makes code easier to evolve (can modify typex without modifying program) should result in very good code 13 What to Notice DiSTiL actually can increase programmer productivity (simpler/shorter programs) removes burden of coding & debugging data structures can accommodate architectural styles 14 Example Application LRU memory policy simulation 3 2 1 0 1 0 1 0 0 15 What is different about DiSTil? Different from static libraries (e.g. STL): meta-level optimizations (retrieval structure selection, updates) more advanced static checking (design-rule checking) level of programming significantly raised (“what” vs “how”) more general, powerful approach larger selection of structures/mechanisms 16 What is different about DiSTil? Even at the usual level of abstraction static libraries suffer from performance loss not easy to integrate such a variety of components example: templates and memory allocation would have the added cost of a virtual dispatch static consistency checking is a domainspecific mechanism (type checking) 17 Internal organization Quote Package Predicate engine Generated Application Static Library Components Transformatio n engine Exported Symbols User Application 18 Next Steps Improve design-rule checking Clarify design, possibly develop tools for writing generators Explore ideas (explicit, generation-time scoping) examined in the Quote package Broaden applications 19 Contributions of DiSTiL Example of factored libraries (Biggerstaff 1994) Primitive data structures factored in new ways (out-of-bounds checking, predicates on retrievals, inlined/functional implementation etc.) Extensive background for software generator development in non-scoped environments (Quote package) 20 Contributions (cont’d) Layered generator: analysis of layer interaction possible mechanisms to facilitate construction determining pattern of information flow among layers 21