The FrankenSort Experiment

The FrankenSort Experiment: Progress on FrankenSort; Decomposition of sort.c

The FrankenSort experiment is a early investigation into the use of Compositional Program Synthesis for real-world applications. In this experiment, the POSIX sort applications is being rewritten with Hyper/J. The original version (sort.c from the GNU Project) is being re-implemented as a set of composable, evolutionary components. The early work demonstrated the large number of evolutionary enhancements that are present in a real-world application. The more recent synthesis work has demonstrated that most interactions can be categorized with a limited vocabulary of behaviors.

Progress on FrankenSort

The construction of FrankenSort currently supports a general-purpose Application Framework, a flexible File Manager package, and several Record Ordering options. A more complete implementation should be finished shortly.

This work formed the basis of Mr. Carver's Masters Thesis. This thesis and related papers are available online.

L. Carver, Building a Real-World Application with Aspect-Oriented Modules and Hyper/J, Master's thesis, Univeristy of Califorina, San Diego, Department of Computer Science and Engineering, June 2002.
L. Carver, Composition Behaviors for Application Construction, Workshop on Aspect Oriented Design, First International Conference on Aspect Oriented Software Development (AOSD'02), 2002

This project has also lead to some simple tools to help with Hyper/J software development. Use and enjoy, and send me any recommendations for future improvements.

Decomposition of sort.c

An important question when one constructs software is the number and type of components that are needed to defined the desired result. Traditional imperative languages provide branches, loops, and functions as the major components. Unfortunately, these components are not stable in the face of incremental enhancements. Adding a new capability typically requires invasive changes to a large number of components.

One alternative is to find different set of components that is stable in the face of changes. The definition of such a set is an important open question for software composistion. What are the components and what are the composition rules?

One way to discover a components set is to analyze the structure of a an existing program. In this experiment, the Gnu implementaion of sort.c is being analyzed to expose composable component that are present in real, production quality code.

This is a work in progress. The preliminary analysis results are available here.

Preliminary results of the decomposition have been presented at several recent workshops. The papers and presentations are available online:

L. Carver, Combining Selector-Guarded Blocks: Difficulties From the Option-Processing Task, Workshop on Aspects and Dimensions of Concerns, European Conference on Object-Oriented Programming (ECOOP'2K), 2000
L. Carver, A Practical Hyperspace Application: Lessons From the Option-Processing Task,Workshop on Multi-Dimensional Separation of Concerns in Software Engineering, International Conference on Software Engineering (ICSE'2K), 2000
L. Carver and W. G. Griswold, Sorting Out Concerns, Workshop on Multi-Dimensional Separation of Concerns, Conference on Object-Oriented Programming, Systems, and Languages (OOPSLA'99), 1999

The Workshop on Multi-Dimensional Separation of Concerns during OOPSLA'99 requested a summary presentation. The presentation is also available online.

Page design by Pnambic Computing.