19

I've been interested in uniqueness types as an alternative to monads in pure functional languages for some time; unfortunately, this is kind of an esoteric area of CS research and online resources about programming with uniqueness types are few and far between.

It's obvious how uniqueness types may be used to implement stateful data structures like references ("boxes") and arrays, though it escapes me how you might implement other common stateful data structures with them.

Is it possible to implement, for example, locking with unique types? Can uniqueness types be used to share mutable data across threads? Is it possible to use unique types to build synchronization primitives (like mutexes), or is message passing necessary?

  • Can you make your question a little more specific? What, for example, do you already know about locking with unique types and where is your own knowledge insufficient? – Robert Harvey May 6 '14 at 22:40
  • > What, for example, do you already know about locking with unique types I don't know anything about locking with unique types -- I don't really know how safe parallelism works with unique types and I'd like to know if there are any resources on the topic. – Ricky Stewart May 6 '14 at 22:49
  • 4
  • 2
    @RickyStewart: You probably know Clean (wiki.clean.cs.ru.nl/Clean) already. I just wanted to add the link because you did not mention it. – Giorgio Aug 17 '14 at 10:32
  • I think you should look into linear types for parallelism. IIRC uniqueness types are built on linear types. Frank Pfenning has some interesting stuff on the subject – Daniel Gratzer Feb 9 '15 at 21:25
2

Is it possible to implement, for example, locking with unique types?

I followed the link that Robert Harvey provided and I did a quick read-up. I cannot say that I understood everything or that I have a high level of confidence that I really understood what I think I understood, but it appears to me that the whole point of external uniqueness and reference immutability is to have no need for locking.

Modern approaches to multithreading try to avoid locking because only highly experienced programmers can write code which uses locking, and even their code is highly prone to have bugs. If you add on top of that the fact that locking code is virtually untestable, it should be obvious that it is a highly undesirable way of doing things, and any solution aiming to free us from locking is promising to say the least.

The way we have been avoiding locking is with message passing, which requires that the messages must be immutable. Roughly, (at first glance,) reference immutability appears to be a technique that can help us guarantee immutability without having to actually construct immutable types, and external uniqueness appears to be a technique that can help us relax the strict immutability requirement locally.

Can uniqueness types be used to share mutable data across threads?

The paper did not clearly state it, but from what I understand, an externally unique cluster of objects is thread safe because somehow (really, how?) it is guaranteed that there exists only one outside reference into that cluster of objects, which means that a thread receiving such a reference can treat the referenced objects as mutable without having to worry that some other thread might also mutate them, because no other thread can possibly have another a reference. I would be curious to know how such a theoretical construct can be implemented and enforced.

Is it possible to use unique types to build synchronization primitives (like mutexes), or is message passing necessary?

Again, from what I understand, externally unique types and reference immutability are meant to render locks, mutexes, and the like unnecessary. Message passing appears to be the way to go, and that's good.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.