Karl J. Lieberherr
Riccardo Pucella, Rajmohan Rajaraman, Yannis Smaragdakis
Date of Award
Doctor of Philosophy
Department or Academic Unit
College of Computer and Information Science. Department of Computer Science.
Algorithms, Function Objects, Traversal, Type Systems
Functional programming (Computer science)
The development of complex software requires the implementation of operations over recursively defined data structures. Complex data structures lead to an increase of code dealing with structure access and navigation. This `boilerplate' code in turn makes programs tedious to develop, difficult to maintain, prone to errors, and separates important functionality, all of which result in the loss of clarity. Generic (or polytypic) programming and higher-order functions can resolve some of these issues, but are usually too general to be practically useful for large collections of data types. This dissertation proposes a new approach to developing structure-based functions and describes an implementation of these ideas in Java, called DemeterF. Our approach uses function-objects over an adaptive traversal to implement deep, fold-like functions over data structures. Function-classes (and objects) provide a useful and flexible form of generic programming that adapts to different data structures using a type-based multiple dispatch. We model DemeterF with function sets and structural recursion, and give it a type system that shows our function-objects, multiple dispatch, and traversals can be checked for safety. In order to show that our approach is efficient we present the results of several performance tests comparing DemeterF to handwrittenmethods and visitor implementations in Java.
Chadwick, Bryan, "Functional adaptive programming" (2010). Computer Science Dissertations. Paper 12. http://hdl.handle.net/2047/d20000638
Click button above to open, or right-click to save.