Advisor(s)

Karl J. Lieberherr

Contributor(s)

Riccardo Pucella, Rajmohan Rajaraman, Yannis Smaragdakis

Date of Award

2010

Date Accepted

9-2010

Degree Grantor

Northeastern University

Degree Level

Ph.D.

Degree Name

Doctor of Philosophy

Department or Academic Unit

College of Computer and Information Science. Department of Computer Science.

Keywords

Algorithms, Function Objects, Traversal, Type Systems

Subject Categories

Functional programming (Computer science)

Disciplines

Computer Sciences

Abstract

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.

Document Type

Dissertation

Rights Holder

Bryan Chadwick


View Full Text

Click button above to open, or right-click to save.

Share

COinS