My areas of interest are programming and programming languages, in particular functional programming languages. I am interested in semantics and theoretical foundations of programming languages, links between the functional and object-oriented paradigm, type theory, program transformation, compiler construction, programming tools, and how to program effectively. For example, you could develop a library or a tool that assists the programmer, implement a small programming language, or the more mathematically inclined could formalise some aspects of a programming language.
In this project you implement a new backend for the C- compiler that performs liveness analysis and register allocation. Also the new backend shall produce assembly code for the x86 processor architecture, so that it can be run without a simulator. Because this backend shall be used for teaching in the CGO module in the future, the implementation should be concise and well documented and there should be options for displaying information of various intermediate phases. If time permits, you could also consider how the assembly output can be enriched so that a standard debugger such as gdb enables source code debugging of C- programs.
The implementation is in C, as the rest of the compiler is implemented in C. You are expected to either take or have taken the CGO module in the third year.
References:
The aim of this project is to develop software that simulates and graphically animates several garbage collection algorithms for the purpose of teaching these algorithms. The animation should stress the similarities and differences of the algorithms. The software should be modular so that an implementation of the animation of a new algorithm could mostly reuse existing modules.
The implementation language is your choice. The animation should run under both Linux and Windows.
References:
Because the trace file is written sequentially, it also records in which order expressions are evaluated by the computation. None of the current viewing tools makes use of this information. The aim of this project is the development of a new tool for visualising the evaluation process by showing an animation.
Inspiration may be gained from the tool GHood and an early version of the tool Hood (both unconnected with Hat). They animate Haskell computations, but they cannot show many intermediate steps of a computation and they rely on source code annotations. Also further features that enable concentrating on a particular part of a computation are desirable.
The project requires understanding of the evaluation of lazy functional programs, but the tool may be implemented in another language than Haskell.
References:
The downside of the type system's flexibility is that from a type error message for an ill-typed program it is often hard to deduce and understand the actual cause of the error. I have recently proposed a new method for helping the programmer to understand type errors. I built a simple prototype of a tool that enables the programmer to explore the types of arbitrary subexpressions of a program. The tool uses a type inference algorithm that is different from the usually employed one.
The aim of this project is to develop an improved tool that can read in a program of a subset of Haskell (without classes) and provides a nice user interface for exploring its types.
The project requires understanding of the Haskell type system (without classes), but the tool may be implemented in another language than Haskell.
References:
The aim of the project is to make the Clean compiler usable for Haskell programmers. A translator from Haskell to Clean is to be built. Its main component could be the Haskell parser of the nhc98 compiler, which is maintained in the department. Furthermore, the standard libraries of Haskell have to be translated into Clean; parts of these libraries are written in Haskell, parts are primitive and have to be implemented using the standard libraries of Clean. The main part of the evaluation of the Haskell to Clean translator should be a comparison of efficiency with several direct Haskell implementations.
The project requires programming in Haskell and some Clean. Hence you should take or have taken the optional module FUN - Functional Programming - in the third year.
References:
You write a small to medium sized program in Cayenne in which you try to express as many properties as possible in the type system. The program implements a simple bibliographic database for different types of publications and their publishers. The database keeps all data in main memory and provides insertion, modification and deletion operations and various search facilities. Alongside the implementation you evaluate the usefulness of Cayenne for practical programming by determining which kind of properties are easy to express, where there are problems, and you collect some practical advice on writing Cayenne programs.
Because Cayenne is a lazy Haskell-like functional language, you should take or have taken the optional module FUN - Functional Programming - in the third year.
References:
Currently all new or updated information reaches the editors of this web site (John Peterson at Yale University and me) by email and news. We then edit the pages by hand. In this project you should develop software and modify the pages so that part of the presented information can be added, updated and removed through web forms by users. Mechanisms to prevent misuse of this feature have to be implemented. It must be possible to easily make a backup of the current contents. The system should be flexible so that web pages can be restructured without loss of information. Editorial comments should be permitted in most places of web pages. Simplicity of use and administration is a central requirement. Note that the aim of the project is not to produce a "flashy" web site; the pages should be accessible to everyone with nearly any web browser.
Because the web site is for the language Haskell, obviously the software should be developed in Haskell. Hence you should take or have taken the optional module FUN - Functional Programming. The Web Authoring System Haskell (WASH) will provide a suitable basis.
References:
if True
then if True then True else True
else
if False
then False
else False
The aim of the project is to study static garbage collection. This term covers a number of memory management methods that perform an analysis of either source or object code (e.g. escape analysis, region analysis) to locate for a large number of memory allocation points the program point from which on the memory will no longer be used and hence the memory can be reclaimed.
In the project a tool will be implemented to perform such an analysis and to insert appropriate allocation and deallocation instructions in the program. Furthermore, an existing run-time system will be modified to support the new memory management instructions. Evaluation will include measurement of the effectiveness of the analysis (amount of memory managed by the new instructions instead of the general garbage collector) and measurement of the performance of the new run-time system compared to the old one.
It is planned to use the Java Virtual Machine as experimentation environment. The analysis will work on Java byte code instructions.
References: