Summary

Functional languages are a great medium for expressing algorithms and solving problems. Many ideas and technologies from the functional language community are migrating into mainstream software engineering. This connection means that the field of applied functional programming is an exciting place to be doing research. There is significant scope for new ideas and contributions, yet the area allows for quantitative assessments of merit and influence as well as providing examples of external contribution which facilitate grant proposals and other sources of funding.

My research focuses on enabling technologies which supports the transfer of technology from functional language theory to engineering practices. I use the underlying theoretical framework of functional languages as a means to an end, not the end itself – the ability to reason about a specific idiom or style of programming is useful in as much as how it can be applied. I have a track record of taking ideas from theory to practice, and have successfully done this in a number of different disciplines inside functional programming, both inside academia and inside industry.

Research Contributions

• Short Cut Deforestation is widely recognized as the first practical deforestation system, has been cited over 200 times, and this contribution remains the basis for the implementation of deforestation inside the premier Haskell compiler. This deforestation system is based on a simple rewrite rule for eliminating lists, and required quite careful setup to enable its effective use. Specifically, the full scale implementation demonstrated the need to include a new analysis inside the compiler, and also facilitated the invention of a generalization of the original simple rule. Since publishing my deforestation results many extensions, improvements and generalizations have been suggested and implemented. Making the system effective for real Haskell programs was critical to the success of this research.
• Debuggers for Lazy Functional Languages are challenging to write because the order of evaluation obfuscates the intent of the program being debugged. The Haskell Object Observation Debugger provides a simple but robust mechanism for observing intermediate data structures and in-context functions, and has been cited over 60 times. The published algorithm has been re-implemented in four independent debugging systems.
• Haskell Equational Reasoning Assistant (HERA) is a long-running effort to provide a simple tool that allows a user both a graphical and programatic interface into a general rewrite engine for Haskell. The programatic interface of HERA has been used to code up a correct-by-construction pattern matching compiler which applies only trivially correct rewrites to reach an efficient match implementation. The graphical interface reused some algorithms from the HERA prototype, but is now rendered using modern Ajax-based web technologies.
• Code Coverage is an important technique for assessing the quality of code. In a lazy functional language like Haskell the usual tradeoffs used by code coverage implementations do not neatly transliterate. In Haskell Program Coverage, Colin Runciman and I pushed the idiom of coverage down to the sub-expression level – that is every expression and sub-expression had an independent coverage counter. The tool itself is both complete and useful; it operated on any Haskell program and has a small overhead price for the information gleaned.

The common thread throughout all my contributions listed here is that they involved pragmatic solutions to open problems and needs, and all these contributions are supported with full-scale implementations that work on real Haskell programs.

Research Ideas and Work in Progress

In the following sections I elaborate my current research interests and ideas. In general I am interested in any applied research using functional languages; this list is just a sample of what immediate opportunities are open for exploration.

• The Optimization of Functional Languages has been a personal driving motivator for many years. If we can write clear programs and rely on compilers to generate efficient implementations, then applied functional programmers can focus on clarity without sacrificing performance – a long-standing dream of many compiler writers. Profile Based Optimizations (PBOs) is a new frontier for optimizing functional languages. Optimization systems for functional languages have many (sometimes costly) options for improving code quality, so compilers use heuristics to keep compile time and code size acceptable. Using information gleaned from previous executions of a program to inform optimization choices during recompilation of imperative languages is an well understood discipline, but there are many interesting conceptual problems to address when applying PBOs to functional languages.
  • Functional languages offer more dimensions of freedom than imperative languages; how can we take advantage of these freedoms?
  • Function inlining and function unrolling appears to be the analog to basic block ordering and loop unrolling in imperative PBOs. Will functional languages see the same benefits, and are other optimization technologies required?
  • Do invasive translations like deforestation or CPS change the effectiveness of PBOs?
  • Can we choose alternative low-level data-type representations based on PBO information?
  Intentionally, the code coverage implementation generated by our coverage tool gives exactly the information required to construct the first full scale profile based optimization system for Haskell.
• Rewriting Haskell Programs from clear specifications to efficient implementations is an alternative to the direct application of compiler optimization technology, and has a different set of application areas. Offline tools and techniques can be used to help the refinement and refactoring of well-engineered code. Jointly with Graham Hutton I have been exploring the worker/wrapper transformation, formalizing how a recursive function can be systematically translated into a new function that performs the same operations more efficiently. A number of well-known and seemingly unrelated translations can be unified in this framework, including accumulation, memoization, CPS translation and lambda-lifting. (invited submission for Journal of Functional Programming, draft completed and available on web page, submitting in January 2008).
  • Can we use the unifying nature of the worker/wrapper framework to reduce the number of significant decision points during program transformation?
  • Can we use the worker/wrapper refactoring framework to help with the generation of solutions for embedded devices? For example, can we translate out some dynamic allocation requirements?
  • Can we use the worker/wrapper transformation to automate the discovery of improved opportunities for parallel execution?
• Strictness inside Lazy Functional Languages is a difficult engineering and research issue.
  • What is a good way of expressing a value, vs. a computation that will result in a value?
  Based on my engineering experiences, I propose the introduction of a deep seq primitive to Haskell, which will simplify the higher fidelity control over strictness needed by some applications. There are important conceptual problems and a design space to be explored with any such solution.
• Strict Pure Functional Languages are a completely different approach to the unevaluated values problem. A consequence of having the evaluation order strict by default is that we lose much of the declarative nature of Haskell.
  • Can we create a strict language without compromising the feel and attractive semantics of Haskell?
  Towards this aim, I propose the maturation of the language Timber , a strict pure functional language based on Haskell, in parallel with other Haskell efforts. Timber is better suited than Haskell as a mechanism for expressing solutions to problems where time and space usage are a significant part of the user experience – for example real time applications – because deadlines are built into the operational semantics of the language. In collaboration with Johan Nordlander, I have been developing a Timber compiler which explores a specific design for such a strict, pure language. One novel feature of our implementation is that it allows for strict, recursive data-structures without using any assignment.
• Automated Debugging is a growing research field, where tools are used to cut down a problem space to locate which part of the codebase a bug is located in. The Haskell Program Coverage framework has already been extended to allow dynamic monitoring of Haskell programs, allowing programmers to script up some debugging idioms. A successful project here would allow many typically bug-prone coding patterns to be thoroughly tested.
  • Can we check for interference between threads, detecting possibly latent race conditions that have not been tested?
• API Design is rarely taught for functional languages. Haskell provides a unique and under appreciated tool, the ST monad. Inside the Galois Trusted Services Engine, I designed and implemented a filesystem cache which by the design of the API can never be corrupted by a user, due to the properties of the ST monad. (write-up for Journal of Functional Programming pending)
  • Can we automate the transformation of existing APIs into ST monad style APIs, turning a specific class of run time violations into compile time errors?

Application Areas for Functional Languages

All of these ideas and research interests need applications to drive and inform them. I am always looking for new ways of deploying functional languages. Galois was started with the conviction that there are unexplored application areas for functional languages, and people will pay for the benefits that these languages can provide. But significant unsolved issues remain.

• Functional languages work well in the domain of translation. Compilers, web-mashups, version control and other data transformation problems are straightforward to implement in functional languages using well-understood techniques. These implementations would automatically benefit from stronger compiler technology, like profile based optimizations. The goal of my research applied to this application area is to allow clearer programs because the programmer can depend on specific optimizations.
• Functional languages have been successfully deployed in the domain of service providers, like web servers, and window managers. Any similar long-running applications would benefit from more accurate space-usage control and runtime behavior inside critical components. The goal of my research applied to this application area is to give implementers tools and techniques to be able to address issues like space leaks in systematic and precise ways.
• Functional languages have huge unrealized potential in the domain of embedded and real-time systems. There are many interesting, open problems, including the managing of garbage collected executable specifications in time critical, space critical situations. The goal of my research applied to this application area is to provide new languages, compiler technologies, and offline translation technologies that allow functional languages to be useful and relevant to the generation of software for embedded and real-time systems.