[rust-dev] Uniqueness and Reference Immutability for Safe Parallelism

Niko Matsakis niko at alum.mit.edu
Wed Dec 5 18:20:04 PST 2012


Yes, I loved that paper and I did find the techniques they used very 
interesting.  For those who did not read the paper, they have a rule in 
their type system which says approximately:

"Given a function that takes one unique value and any number of deeply 
read-only values as input, the unique value will still be unique after 
the function even if it is aliased during the function."

The reasoning here is that in order to be aliased after the function 
terminates, the value must have been stored somewhere, but all of the 
inputs to the function were deeply read-only, so it cannot have been 
stored anywhere.  We could potentially apply similar reasoning, but I'm 
not sure how much it would buy us, given the borrowed pointer system, 
which is ultimately more flexible.  They of course use this rule to 
avoid having a borrowed pointer system at all.

pcwalton and I have kicked around similar ideas as a replacement for 
purity.  Basically pure functions would be removed, but the borrow 
checker would consider functions that do not have access to mutable 
state as being pure.  Another place I had thought of using similar 
reasoning was to build a library for fork-join parallelism [1, 2], where 
the closures that are being executed in parallel only have access to 
immutable/read-only state. I think this would be very cool, but there 
are a few things standing in the way  (ref-counted @ boxes, const bounds 
on closures).  But in that last case the reasoning wouldn't be part of 
the type system but more an argument why the library is sound.


Niko

[1] 
https://www.usenix.org/conference/hotpar12/parallel-closures-new-twist-old-idea
[2] https://github.com/RiverTrail/RiverTrail/

Elliott Slaughter wrote:
> Hi there,
>
> I wonder if the Rust borrowing experts here (Niko especially, but 
> maybe others) have seen this paper from MSR? The interesting aspect of 
> this paper is that they can "recover" uniqueness of pointers without 
> needing to limit the scope of (what are effectively) borrows. I'm not 
> actually sufficiently familiar with Rust's borrowing to know if this 
> would be useful to you or not.
>
> http://research.microsoft.com/pubs/170528/msr-tr-2012-79.pdf
>
> -- 
> Elliott Slaughter
>
> "Don't worry about what anybody else is going to do. The best way to 
> predict the future is to invent it." - Alan Kay
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev


More information about the Rust-dev mailing list