PhD position in computer science, Utrecht (The Netherlands)

Vacancy PhD student on Realizing Optimal Sharing in the Functional Language Implementations
Utrecht University,
The Netherlands.

---

Within the Software Technology group of the Information and Computing Sciences department of Utrecht University there is a vacancy for a PhD student to work on the efficient implementation of functional languages. The position is funded by NWO, the Netherlands Organization for Scientific Research.

Project summary:

Lambda-calculus and term rewriting are models of computation lying at the basis of functional programming languages. Both possess syntactic meta-theories based on analyzing rewrite steps. Unfortunately, naive implementations are inefficient, since subterms are frequently copied.

To overcome this problem in both theoretical systems and actual implementations, duplicate work is avoided by using graph-based term representations, in which identical subterms can be (but not always are) shared. The question arises whether graph-representations and their reductions that are optimal in a theoretical sense can also be practical from an implementer's point of view. However, so far it is unclear whether nice theoretical ideas combine well with existing implementation methods. The overall-goal of this project is to answer this question in a back-and-forth communication between theoretical concepts and practical realizations. Starting points are the recent work on the optimal Lambdascope implementation based on context sharing, and the Haskell implementation developed at Utrecht University.

One of the open problems is whether the Lambdascope framework can be extended to efficiently represent sets of mutually recursive definitions. Another, whether global program analysis can discover where Lambdascope-based approaches solve problems due to insufficient sharing. If both questions can be solved, we want to combine Lambdascope-based implementations with conventional frameworks, and investigate how efficient the resulting implementations become. The unique combination of the theoretical depth from the Logic department and the implementation skills and compiler infrastructure from the Computer Science department make Utrecht University the optimal surroundings for such a project.

Project leaders

Prof.dr. Doaitse Swierstra and dr. Vincent van Oostrom (principal investigator).

The project will be executed in close cooperation between
* the Software Technology group (http://www.cs.uu.nl/wiki/Center) of the Information and Computing Sciences department (http://www.cs.uu.nl/)
* and the Theoretical Philosophy group (http://www.uu.nl/EN/faculties/Humanities/research/researchinstitutes/zeno/) of the Philosophy department (http://www.phil.uu.nl/), and between
* the more practically oriented PhD student and
* the more theory oriented postdoc.

Requirements: Master degree in Computer Science, Logic, or equivalent. Good knowledge of functional programming, and several advanced computer science techniques. Knowledge of lambda-calculus implementations, Haskell, and compiler construction will be useful. Both theory and software development based on this should appeal to you.

Terms of employment: the PhD student should start as soon as possible, but no later than January 1, 2010. The position is for four years (after one year there will be an evaluation), full-time. Gross salary starts with € 2042,-- per month in the first year and increases to € 2612,-- in the fourth year of employment. The salary is supplemented with a holiday bonus of 8% and an end-of-year bonus of 3%. In addition we offer: a pension scheme, partially paid parental leave, facilities for child care, flexible employment conditions in which you may trade salary for vacation days or vice versa. Conditions are based on the Collective Employment Agreement of the Dutch Universities: http://www.vsnu.nl/Workstudy/Universities-as-employers-/

More information:
* about the project can be found on http://www.cs.uu.nl/wiki/bin/view/Center/OptimalSharing * about the Software Technology group on http://www.cs.uu.nl/wiki/Center * about the Information and Computing Sciences department on http://www.cs.uu.nl/ * about this vacancy can be obtained from Doaitse Swierstra (doaitse at cs.uu.nl, +31 6 4613 6929).

Send your application in pdf (or another non-proprietary format) to mailto :SciencePenO at uu.nl

with a cc to mailto:doaitse at cs.uu.nl. on or before Sept 31, 2009.

Mention vacancy nr 62910.