Lindsey Kuper - Two projects that came to fruition this week [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Two projects that came to fruition this week [Jul. 13th, 2012|06:32 pm]
Previous Entry Share Next Entry
[Tags|, ]

This has been a busy week. First, two days ago my advisor and I submitted a paper to POPL about what we've been up to for the last six months. Here's the abstract of our paper, which is called "A Lattice-Theoretical Approach to Deterministic Parallelism with Shared State":

We present a new model for deterministic-by-construction parallel programming that generalizes existing single-assignment models to allow multiple assignments that are monotonically increasing with respect to a user-specified partial order. Our model achieves determinism by using a novel shared data structure with an API that allows only monotonic writes and restricted reads. We give a proof of determinism for our model and show that it is expressive enough to subsume diverse existing deterministic parallel models, while providing a sound theoretical foundation for exploring controlled nondeterminism.

There's also a Redex model, and the tech report that accompanies the paper will be up within a week or so. Hooray!

Second, the Rust team released Rust 0.3 yesterday, including, among other things, the feature I worked on for the first part of the summer, suffix inference for integer literals. I'm proud of this, since having to write suffixes on int literals was one of the more annoying things about the language (we had it tagged with "papercut" in the issue tracker).

Next, I'll be working on traits for Rust, but first I head to Oregon for OPLSS!

LinkReply

Comments:
[User Picture]From: zacharyzsparks
2012-07-14 04:14 am (UTC)

(Link)

Okay, so I tried to implement the first example (with hash tables) from that github page in SML and found that I was actually entirely unable to get the described behavior, and now I'm kind of confused.

How are, um, things (objects, I guess?) implemented in Rust? Are they passed around as packages of their value and their methods? Because if so, that seems awfully...not-systemsy to me, but I don't currently see any other way of getting that behavior out of that code.

Specifically, when I write the SML version of that code and run it, I get a hash table with only (3, "ho") in it, because once I call Module2::bar (or in my version, S2.foo) it is doing everything in Module2 land, even when it hashes the key from Module1. The only way I can see to get this behavior would be to pass around all of the methods with the object itself so that it "knows" to call its version of hash instead of the new one. Am I wrong?

I think the Haskell solution to this (since it looks like interfaces in their current form are basically typeclasses) is to only allow one instance per class, probably to avoid exactly this problem; iirc, this also allows the correct methods to be inserted at compile time. I think there are extensions (or at least talk of extensions) that allow instantiation of typeclasses at multiple types, which result in more verbosity (and I think something exactly as expressive as ML functors, or at least closer than typeclasses).

The solution you describe seems pretty legit (just what you want, validation from someone who isn't on the team and who has only thought about this for like an hour!); just to be clear, you require that any implementation of a trait native to a different module must be with a new (local) abstract type, correct? I can't help but think that there's a better way, but I'm not sure what it is right now.

Here's my SML code that attempted to implement the same behavior: http://pastebin.com/4VbvBL5u

What I really want in SML is some way to say "these two structures both have Key.t = int, but they are not necessarily the same structure" (as opposed to "these two are the same structure", which I'd also like). I have no idea if this is feasible/decidable, though. I know sml/nj has the ability to declare structure equality (so "where Key = Key1" instead of "where type Key.t = int" or whatever), but type equality is enough to get the two to interoperate, so *shrug*. I was trying to find a way to make MainFn not compile, but still be able to use integers for the inputs. Maybe someone more clever than me (like you!) can tell me how to get this to work/why it doesn't work.

So yeah, anyway, this is kind of a long, rambly post, sorry. I guess it's time for a tldr?

tldr: the behavior of the example in the wiki page seems wonky and like an inherent problem with OO that an ML style module system would treat better, but it still doesn't solve the problem of multiple instantiation, which is pretty interesting, especially when trying to solve it at (separate)-compile time!
[User Picture]From: lindseykuper
2012-07-14 07:49 am (UTC)

(Link)

Just so no one else gets terribly confused (as I was for several seconds), by "that github page" Zach means this github page, the one with the Rust traits proposal, not the other github page I linked to, the one with the Redex model of lambdapar.

I think the Haskell solution to this (since it looks like interfaces in their current form are basically typeclasses) is to only allow one instance per class

Yes; that's exactly what we want. "One instance per class" is the Haskell counterpart of our "only one implementation of a trait per type" plan, except that Haskell enforces it at link time, and we want to enforce it earlier in the process.

Rust ifaces in their current form are indeed kind of like Haskell typeclasses. I would argue that they're getting more like Haskell typeclasses with this proposal, because they'll allow default implementations like Haskell typeclasses do, and they'll have instance coherence.
[User Picture]From: zacharyzsparks
2012-07-16 09:02 pm (UTC)

(Link)

itt: zach forgets how hash tables work >.<;
[User Picture]From: bubblingbeebles
2012-07-14 02:38 pm (UTC)

(Link)

E-hard I-completion