Uniqueness Typing

Date: 2006-09-28

Time: 13:30

Room: AARD-C008

Speaker: Arie Middelkoop

Title: MastersThesisDefence = UniquenessTyping

Reasons why you should attend this talk:

• If you want an example of a master's thesis project that took place at the university itself
• If you heard something about uniqueness typing (or the name Clean) and what to know what it is all about. [Note that I talk about my own approach, not about that of Clean]
• To learn a technique that can make value updates in functional languages more efficient
• To learn a technique that can serve as alternative to IO/ST monads
• For those who are more involved with the imperative/object oriented paradigm: to learn about a typing technique that may be of use in those fields too
• I tailored the talk for ST students specifically, so I hope you can all understand it...
• To increase your attendance count... you'll need it if you want to beat mine

Master's Thesis

Master's Thesis [28 Sept 2006]. Slides [27 Sept 2006].

Abstract

Functional languages like Haskell treat values as atomic. When a portion of a value is updated, the update actually is made on a copy of the entire value, keeping the original value intact. For example, to update an element of an array, a copy is made of the entire array. Likewise, to change a key in a hashtable requires a copy of the entire hashtable. The result is that so much copying is involved that a Haskell program cannot use mutable arrays or hashtables efficiently. This is a pity because these are very efficient data structures for imperative languages.

One solution is to monadify all the code. For example, the ST-monad provides functionality to update an array without making a copy. The monad code can only access the most recent version of the array, which guarantees that there is no need to keep track of older versions, which in turn means that no copy needs to be made when updating the array. This is an effective solution, but the effect is that the code tends to look like ugly C-programs (i.e. check The Computer Language Shootout Benchmarks). So, the question is: if we use a value in such a way that we are not interested in older version of a value anymore, why not let the compiler infer that this is the case, such that these values can be updated without making a copy.

This is where my master's thesis subject comes into the picture. With uniqueness typing, the type inferencer of the compiler determines which values are used at most once. Suppose we update a value that is used at most once. Since updating counts as a use of the value, it means that the old value is not used anymore after the update. Instead of updating a copy of the old value, the old value can be updated instead. No copy is made, thus removing the inefficency without affecting the code.

Uniqueness typing is originally designed for the language Clean. We show how this can be done in combination with Haskell.

-- ArieMiddelkoop - 28 Sep 2006