Re: [rust-dev] Persistent data structures
On 12/3/13 11:28 PM, Isaac Dupree wrote: Is Rc the best smart pointer for persistent data structures? I would think so, for non-thread safe ones. Is it possible for the structure to be parametrized on smart pointer? Not without higher kinded types (which eventually we do want--so the answer is not yet). Rc requires the contained data to be Freeze or Send or risk reference cycles. I want to lift this restriction, BTW. Trying to prevent cycles through the type system has never really worked for us. Gc requires T:'static (which means no borrowed pointers besides 'static ones within the type). Yes, but I wouldn't worry about this restriction biting users of your structure too much. Rust data structures rarely ever store non-static references in them, as the stack discipline that references must follow is fairly limited. (I can probably count the number of times I've put a non-static `` reference into a dynamic vector on one hand, and I don't think I've ever put references into a hash map.) Every Send type is 'static, but not every Freeze type is 'static, so neither Rc nor Gc is strictly more flexible. Arc is Send, unlike either Rc or Gc, but has more overhead and can only contain Freeze+Send data; someone wanting to share persistence between tasks (conceivably for the sake of memory-use or asymptotic time) would want it. Really what you want here for maximum flexibility is higher-kinded types and an implementation parameterized over RcT or ArcT. That doesn't work in today's Rust, so you'll have to implement the data structure separately for non-thread-safe and thread-safe applications, unless you use macros. (Though often times you may want separate logic either way, necessitating a separate implementation. I'm not sure about the particular data structure you had in mind though.) Is it possible to implement FromIteratorT for ListT without using O(n) temporary space or unsafe code? The problem is that the list comes out reversed in an obvious implementation. (O(n) stack space via recursion, or an O(n) intermediate data structure, or unsafely constructing a cons cell before constructing its tail.) I think it should be possible to reverse the list after it's constructed, but then of course it has to be mutable (at least temporarily). Or you could carry around a pointer to the end of the list (which, again, requires mutation). I don't think this is solvable without mutation in a strict (non-lazy) language, unless I'm missing something. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] method overloading and generic
thanks for explanation, it all makes sense now. so I will stick to manually
implement the overloading for every float type until #8075 is fixed, which
is fine for now.
cheers,
Rémi
On Tue, Dec 3, 2013 at 11:50 PM, Eric Reed ecr...@cs.washington.edu wrote:
I think you're running into issue
#8075https://github.com/mozilla/rust/issues/8075which has to do with
generic impls conflicting with all the other impls
present.
The typechecker tries to ensure that impls are coherent, i.e. that impls
do not overlap (otherwise the compiler wouldn't know which one to use).
Unfortunately, the coherence check isn't very smart right now and if
there's a generic impl around then it assumes it could conflict with
everything (and consequently forbids any other impls).
The specific problem here is that the coherence checker doesn't realize
that SomeData does not impl Float. Without knowing that, the checker sees
two possible impls for SomeData and rejects the code.
If you replace implT: Float SomeDataRhs for T with impl SomeDataRhs
for f64, then it'll work fine. You can add an impl for f32 as well (FYI
float is already removed in HEAD).
Unfortunately, I don't know of a good general solution that will support
all types implementing Float (i.e. what the generic impl is doing).
On Tue, Dec 3, 2013 at 1:09 AM, Rémi Fontan remifon...@yahoo.fr wrote:
Hi,
I think I already asked this question in the past and I'm not very sure
what was the answer and whether it is still applicable wirh rust 0.8.
I'm implementing the double dispatch method overloading such that I can
add 2 struct together and a float to a struct.
let data = SomeData{a:1.0} + 2.0;
let data2 = SomeData{a:100.0} + data;
I would like to implement the add for every type of float. I asked
whether I could write something like this:
implT:Float SomeDataRhs for T {
fn add_to(self, lhs:SomeData) - SomeData {
SomeData{a:lhs.a + cast(*self)}
}
}
it does not compile right now with rust 0.8
I get error messages as follow
test2.rs:39:0: 43:1 error: conflicting implementations for trait
`SomeDataRhs`
test2.rs:39 impl SomeDataRhs for SomeData {
test2.rs:40 fn add_to(self, lhs:SomeData) - SomeData {
test2.rs:41 SomeData{a:lhs.a + self.a}
test2.rs:42 }
test2.rs:43 }
test2.rs:33:0: 37:1 note: note conflicting implementation here
test2.rs:33 implT:Float SomeDataRhs for T {
test2.rs:34 fn add_to(self, lhs:SomeData) - SomeData {
test2.rs:35 SomeData{a:lhs.a + cast(*self)}
test2.rs:36 }
Would you know whether what I try to do is possible. I was recommended to
use macro for that, I don't mind to eventually go this way but I would
rather do it the proper way if there is one.
here's the full code of my test:
extern mod std;
use std::num::cast;
struct SomeData { a:float }
trait SomeDataRhs {
fn add_to(self, lhs:SomeData) - SomeData;
}
implT:SomeDataRhs AddT, SomeData for SomeData {
fn add(self, rhs:T) - SomeData {
rhs.add_to(self)
}
}
// ---
// implementations
// impl SomeDataRhs for float {
// fn add_to(self, lhs:SomeData) - SomeData {
// SomeData{a:lhs.a + *self}
// }
// }
// impl SomeDataRhs for f64 {
// fn add_to(self, lhs:SomeData) - SomeData {
// SomeData{a:lhs.a + cast(*self)}
// }
// }
implT:Float SomeDataRhs for T {
fn add_to(self, lhs:SomeData) - SomeData {
SomeData{a:lhs.a + cast(*self)}
}
}
impl SomeDataRhs for SomeData {
fn add_to(self, lhs:SomeData) - SomeData {
SomeData{a:lhs.a + self.a}
}
}
#[test]
fn test_sandbox() {
let mut data = SomeData{a:1.0} + 2.0;
println!(result: {}, data.a);
let mut data2 = SomeData{a:100.0} + data;
data = data + data2;
println!(result: {}, data.a);
}
cheers,
Rémi
--
Rémi Fontan : remifon...@yahoo.fr
mobile: +64 21 855 351
93 Otaki Street, Miramar 6022
Wellington, New Zealand
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
--
Rémi Fontan : remifon...@yahoo.fr
mobile: +64 21 855 351
93 Otaki Street, Miramar 6022
Wellington, New Zealand
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Practical usage of rustpkg
On Tue, Dec 3, 2013 at 8:44 PM, SiegeLord slab...@aim.com wrote: I don't think any of these options are ideal. I don't want to suggest solutions to these issues because I'm not sure how things are supposed to be used/what the planned design is. Does anybody use rustpkg seriously today? Is everybody making workspaces with a github.com/user directory where they develop their software? I usually (i.e. in other languages I work with) develop dependencies in-line as they were cloned by the package manager, at least if they need deep integration with the surrounding project and can not be easily tested/developed in isolation. It's not such a horrible situation as long as the package manager is smart enough to avoid wiping your stuff on its own. That said, a pretty good option I think is to have a command like npm link [1] that would allow you to tell rustpkg to set up a symlink to another dir on the disk, yet without interfering/polluting the project's source itself. [1] https://npmjs.org/doc/cli/npm-link.html Cheers -- Jordi Boggiano @seldaek - http://nelm.io/jordi ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
On Dec 4, 2013, at 12:23 AM, Patrick Walton pcwal...@mozilla.com wrote:
Yes, but I wouldn't worry about this restriction biting users of your
structure too much. Rust data structures rarely ever store non-static
references in them, as the stack discipline that references must follow is
fairly limited. (I can probably count the number of times I've put a
non-static `` reference into a dynamic vector on one hand, and I don't think
I've ever put references into a hash map.)
I've put non-static [u8]s into a map. Specifically, I have a function in one
of my sources that looks vaguely like
pub fn process_input'a(input: 'a [u8]) - int {
let mut map: HashMap'a [u8], int = HashMap::new();
// .. process the input using the map, then throw away the map
return result;
}
-Kevin
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Problem to use Encodable as fn parameter
I reply to my questions. It can be helpful to somebody.
First the error: wrong number of lifetime parameters
The struct encoder is declared pub struct Encoder'self so the 'self
lifetime is part of the type and must be keep.
The good declaration is pub fn
buffer_encodeT:EncodableEncoder'self(to_encode_object: T) - ~[u8]
The call to the function is : Encoder::buffer_encode(to_encode_object)
For the other questions.
The lifetime has been added to init (pub fn init'a(wr: 'a mut
io::Writer) - Encoder'a) because the borrowed specified parameter
(wr) is returning in the Encoder and must be keep borrower after the
call and during all the Encoder use. Fn Init borrow the wr and give it
to the Encoder. After the 'init' call, returned Encoder is use to encode
object and wr must still be borrowed. The call to init and encode are
put inside a scoped block to manage the Encoder lifetime:
ex:
let mut m = MemWriter::new();
{
let mut encoder = Encoder::init(mut m as mut Writer);
to_encode_object.encode(mut encoder);
}
m.inner()
Why the type is declared with a 'self lifetime (pub struct
Encoder'self). It's not so clear. What I think, It's because the
struct contains an attribute (priv wr: 'self mut io::Writer) that have
a variable lifetime (depend on the use) , so to be configurable the
lifetime must be declared as a generic in the struct. The variable
lifetime is needed because, it allow the Encoder to borrow the writer
during a lifetime longer that the function call (lifetime of normal
borrowing) needed in the init function.
For more informations:
http://static.rust-lang.org/doc/master/tutorial-borrowed-ptr.html : to
understand borrowing mechanism
https://www.mail-archive.com/rust-dev@mozilla.org/msg05811.html : for
the 'self
Hope my explication is clear.
I have remark about the list and the thread 'Rust Forum', I think it
become important to have a user mailing list or forum. It's the second
time I answer to my trivial questions and I fell that I'm annoying
everybody with these.
Philippe Delrieu
Le 01/12/2013 18:28, Philippe Delrieu a écrit :
I see the PR has been approved to I try to implements the method 'pub
fn buffer_encodeT:EncodableEncoder(to_encode_object: T) - ~[u8]'
and I have this error : error: wrong number of lifetime parameters:
expected 1 but found 0 and indicate the Encoder type.
I have another question. I try to understand the modification on
json.rs and function declaration has changed from :
impl serialize::Encoder for Encoder
to:
impl'self serialize::Encoder for Encoder'self
or
pub fn init'a(wr: 'a mut io::Writer) - Encoder'a
instead of
pub fn new(wr: mut io::Writer) - Encoder
Could you explain me the difference if you don't mind.
Philippe
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
I've implemented a persistent HAMT [1] a while back: https://github.com/michaelwoerister/rs-persistent-datastructures/blob/master/hamt.rs It's the data structure used for persistent maps in Clojure (and Scala, I think). It's not too hard to implement and it's pretty nifty. I'm not sure about the performance with atomic reference counting being used for memory management. It will definitely be worse than with a stop-the-world garbage collector. Although, it's noteworthy that look ups in the data structure only have to copy one `Arc` for returning the result, so the high fan-out of the data structure should not hurt if you mostly read from it. I'd be very interested in a performance comparison to other persistent map implementations in Rust (e.g. a red-black tree or splay tree). Here are some things I came across during implementing this: * I too discovered that I couldn't parametrize on the type of reference being used without higher kinded types. I did the implementation with regular @ pointers at first and later switched to `Arc`, since concurrent contexts are where persistent data structures really shine. Switching the implementation from @ to Arc was pretty straight forward. * I found there is no standardized trait for persistent maps in libstd or libextra. It would be nice to have one! * It's probably a very good idea to provide a non-persistent builder that avoids the excessive copying during the insertion phase. In Clojure one can switch between transient and persistent mode for a data structure instance which also allows for optimized batch modifications. An `insert_from(iterator)` method might also do the trick. There's quite a bit of design space here. * I would have liked to avoid some allocations and pointer chasing by using fixed size vectors directly within nodes but I could not get that to work without a lot of unsafe code that I was not sure would be correct in all cases. So I just used owned vectors in the end. Looking forward to seeing more in this area :) -Michael [1] https://en.wikipedia.org/wiki/Hash_array_mapped_trie On 04.12.2013 08:28, Isaac Dupree wrote: I'm interested in having persistent data structures[1] in Rust. To start, I implemented the simplest one, the cons/nil list (it looks like extra::list::List has another implementation of it). Am I using Rust conventions properly? My persistent list code: https://github.com/idupree/rust-code/blob/master/persistent.rs My next goal is a persistent tree-map, probably cribbing from Haskell's Data.Map. Is Rc the best smart pointer for persistent data structures? Is it possible for the structure to be parametrized on smart pointer? Rc requires the contained data to be Freeze or Send or risk reference cycles. Gc requires T:'static (which means no borrowed pointers besides 'static ones within the type). Every Send type is 'static, but not every Freeze type is 'static, so neither Rc nor Gc is strictly more flexible. Arc is Send, unlike either Rc or Gc, but has more overhead and can only contain Freeze+Send data; someone wanting to share persistence between tasks (conceivably for the sake of memory-use or asymptotic time) would want it. Is it possible to implement FromIteratorT for ListT without using O(n) temporary space or unsafe code? The problem is that the list comes out reversed in an obvious implementation. (O(n) stack space via recursion, or an O(n) intermediate data structure, or unsafely constructing a cons cell before constructing its tail.) [1] https://en.wikipedia.org/wiki/Persistent_data_structure , like every data structure in Haskell -Isaac ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Ideas of small projects or improvements
There is a tag on GitHub specifically for easy issues: https://github.com/mozilla/rust/issues?labels=E-easymilestone=13state=open ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
On 04/12/13 20:51, Michael Woerister wrote: I've implemented a persistent HAMT [1] a while back: https://github.com/michaelwoerister/rs-persistent-datastructures/blob/master/hamt.rs It's the data structure used for persistent maps in Clojure (and Scala, I think). It's not too hard to implement and it's pretty nifty. I'm not sure about the performance with atomic reference counting being used for memory management. It will definitely be worse than with a stop-the-world garbage collector. Although, it's noteworthy that look ups in the data structure only have to copy one `Arc` for returning the result, so the high fan-out of the data structure should not hurt if you mostly read from it. I'd be very interested in a performance comparison to other persistent map implementations in Rust (e.g. a red-black tree or splay tree). Here are some things I came across during implementing this: * I too discovered that I couldn't parametrize on the type of reference being used without higher kinded types. I did the implementation with regular @ pointers at first and later switched to `Arc`, since concurrent contexts are where persistent data structures really shine. Switching the implementation from @ to Arc was pretty straight forward. * I found there is no standardized trait for persistent maps in libstd or libextra. It would be nice to have one! * It's probably a very good idea to provide a non-persistent builder that avoids the excessive copying during the insertion phase. In Clojure one can switch between transient and persistent mode for a data structure instance which also allows for optimized batch modifications. An `insert_from(iterator)` method might also do the trick. There's quite a bit of design space here. For reference, the FromIterator Extendable traits are the things to implement if one has a structure that can be constructed from/extended with an iterator and wishes to share the behaviour. http://static.rust-lang.org/doc/master/std/iter/trait.FromIterator.html http://static.rust-lang.org/doc/master/std/iter/trait.Extendable.html Huon * I would have liked to avoid some allocations and pointer chasing by using fixed size vectors directly within nodes but I could not get that to work without a lot of unsafe code that I was not sure would be correct in all cases. So I just used owned vectors in the end. Looking forward to seeing more in this area :) -Michael [1] https://en.wikipedia.org/wiki/Hash_array_mapped_trie ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Distilled essence of placement new
What's the current plan for the implementation of placement new as you envision it? In particular what would the trait used by Gc etc. to hook into it look like? How does it do the thing where expressions are constructed directly into place? I agree with many parts of your analysis (different argument evaluation orders implicitly would indeed be unfortunate), but I want to have a clearer picture of the other alternative before discussing it further. On Wed, Dec 4, 2013 at 5:57 AM, Patrick Walton pwal...@mozilla.com wrote: I should elaborate: I think you've successfully formulated placement new in terms of unboxed closures as monomorphized traits whose call method takes self by value. That is, something like (in Rust of the future): fn GCT,F:OnceFuncT(f: F) - GCT The difference, though, is that the construction of the closure is implicit at the call site in this proposal. This is what I'm uncomfortable with. Rust is a strict language, not a lazy one, and the order of evaluation of function arguments is one of the things that one has heretofore been unable to change. I would prefer that a different argument evaluation order would necessitate some sort of annotation at the call site (e.g. ocaml's lazy). But once you've done that you've essentially recreated something equivalent to placement new, but more verbose since you have to name a method when you allocate into an object (e.g. instead of box(my_arena) foo you'd have to write my_arena.alloc(lazy foo). I think we would end up wanting the sugar. Patrick Gábor Lehel illiss...@gmail.com wrote: Yes, that was one of the things that passed through my mind as well. One difference is that those are passed at runtime, whereas here everything happens at compile time. I remember LLVM had difficulty reliably optimizing runtime closure passing code, like with the old iterators. On Wed, Dec 4, 2013 at 5:05 AM, Daniel Micay danielmi...@gmail.comwrote: This looks a lot like what stack once functions would provide. -- Your ship was destroyed in a monadic eruption. -- Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev -- Sent from my Android phone with K-9 Mail. Please excuse my brevity. -- Your ship was destroyed in a monadic eruption. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
For reference, the FromIterator Extendable traits are the things to
implement if one has a structure that can be constructed from/extended
with an iterator and wishes to share the behaviour.
http://static.rust-lang.org/doc/master/std/iter/trait.FromIterator.html
http://static.rust-lang.org/doc/master/std/iter/trait.Extendable.html
Thanks for pointing that out :)
Implementing FromIterator should work out fine. Extendable would need a
persistent version returning the newly created instance, something like:
mod persistent {
pub trait ExtendableA: FromIterator
http://static.rust-lang.org/doc/master/std/iter/trait.FromIterator.htmlA
{
fn extend
http://static.rust-lang.org/doc/master/std/iter/trait.Extendable.html#tymethod.extendT:
Iterator
http://static.rust-lang.org/doc/master/std/iter/trait.Iterator.htmlA(self,
iterator: mut T) - Self;
}
}
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Type system thoughts
On Mon, Dec 2, 2013 at 7:18 PM, Niko Matsakis n...@alum.mit.edu wrote: OK, I read a bit more. I've been working on a blog post about HKR (higher-kinded Rust) and you've been elaborating on some of the same themes as I was thinking about (naturally enough). All makes sense. ...which was part of the impetus for finally getting my thoughts down on paper. :) In the absence of an erased keyword, I think that higher-kinded traits and objects are simply incompatible. The situation is not as simple as you made it out, as the trait may itself have generic parameters of higher-kind. Without having thought about very deeply about whether it's true (can you provide an example?), wouldn't this be more accurately phrased as: (higher-kinded?) traits with higher-kinded generic parameters and objects are simply incompatible? In other words, if the problem is with the higher-kinded generic parameters, then why not forbid objects only in that case, and support them in their absence? The other is the potential to abstract over traits. GHC does this with the `ConstraintKinds` extension. (According to people who have implemented Haskell compilers, it's actually easier to implement it than not to![1] Which is pretty crazy.) I'm not sure this would be true for Rust, but perhaps. I have no idea either - it's astonishing enough that it's true for Haskell. :) There's two further issues that higher-kinded generics raise... This is as far as I got in this round. More later. :) OK. :) (I also still have yet to find serious time for DST parts [2..4]...) Niko -- Your ship was destroyed in a monadic eruption. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Rust forum
On 12/03/2013 11:01 PM, Martin DeMello wrote: keeping up with email is a lot easier than pretty much everything else, though. the solution to keeping old messages around is mirroring the mailing list to a searchable archive, not moving to a forum en masse and sacrificing ease-of-conversation for ease-of-recall. Agreed. Plus, with emails everyone can *also* filter / categorise / search according to their own preferred rules on their preferret email client. [I have always hated forums for such reasons, plus they force one to explore, search, navigate, online, without any control.] Denis ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Meeting-weekly-2013-12-03, str.from_utf8
Hi, In response to: https://github.com/mozilla/rust/wiki/Meeting-weekly-2013-12-03#strfrom_utf8 Yes, error handling other than strict/fail requires allocation. I suggest taking the pull request for the special case of non-allocating strict UTF-8, and keeping error handling for a future, larger API that also handles other encodings (and incremental processing): https://github.com/mozilla/rust/pull/10701 https://github.com/mozilla/rust/wiki/Proposal-for-character-encoding-API [On invalid UTF-8 bytes] brson: One has a condition that lets you replace a bad character I believe this is not implemented. The current not_utf8 condition lets you do the entire decoding yourself. acrichto: We could truncate by default. I am very much opposed to this. Truncating silently loses data (potentially lots of it!) It should not be implemented, let alone be the default. jack: In python, you have to specify how you want it transformed. Truncate vs. replace with '?', etc. Maybe there should be an alternate version that takes the transform. pnkfelix: But doesn't work with slices... jack: There's truncate, replace, and fail. Python does not have truncate. It has ignore (skip invalid byte sequences but continue with the rest of the input), strict (fail), and replace (with � U+FFFD REPLACEMENT CHARACTER). You don’t have to specify an error handling, strict is the default. Ignore is bad IMO as it silently loses data (although it’s not as bad as truncate) though it could have uses I’m not thinking of right now. Side note: Regarding failing vs. returning an Option or Result: I’d be in favor of only having the latter. Having two versions of the same API (foo() and foo_opt()) is ugly, and it’s easy to get value or fail from an Option with .unwrap() -- Simon Sapin ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] How to search the mailing list archives
Actually, you do not have to change the article to thread...instead, just CLICK on the Subject and you get the full thread discussion view. Thanks for the tip Benjamin ! (search at the bottom ? whatever. everyone is copying Firefox these days. :-) ) On Tue, Dec 3, 2013 at 9:11 PM, Benjamin Striegel ben.strie...@gmail.comwrote: Apparently even Brian doesn't know how to do this, so I figured I'd share this tip. The rust-dev mailing list is archived here: http://thread.gmane.org/gmane.comp.lang.rust.devel/ Use the search box at the bottom to search through the mailing list's archives since the beginning of time. When you click on a result, you will end up on a page like this: http://article.gmane.org/gmane.comp.lang.rust.devel/6778/match=dst ...which is pretty terrible from a navigation standpoint. But in that URL you can manually change the article bit on the front to thread, to yield this: http://thread.gmane.org/gmane.comp.lang.rust.devel/6778/match=dst ...which will let you easily browse a full conversation. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev -- -Thad +ThadGuidry https://www.google.com/+ThadGuidry Thad on LinkedIn http://www.linkedin.com/in/thadguidry/ ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Practical usage of rustpkg
FYI, there's a related bug open: https://github.com/mozilla/rust/issues/8673 (this is about the problem of repeating the same package ID#revision string in different files and not having a way to abstract it out) The preferred way to work on a dependency and the package that depends on it at the same time is to make a local copy and put it in your RUST_PATH; this copy will be found before rustpkg looks for the upstream copy and/or for an automatically-cached copy of that. The local copy has to have the same package ID, of course, so for a package like github.com/foo/bar, you would have to have a github.com/foo/bar directory in your RUST_PATH. Hope that helps! Cheers, Tim On Tue, Dec 3, 2013 at 11:44 AM, SiegeLord slab...@aim.com wrote: So I've been thinking for awhile about how one would actually use rustpkg. Let me first outline my use case. I have a library and a program that uses that library, both of which I host on GitHub. One of the features of the rustpkg system is that I should be able to write this to refer to the library in my program: extern mod lib = package_id; Unfortunately, there is no obvious thing to put into the 'package_id' slot. There are two options: First, I could use github.com/SiegeLord/library as my package_id. This is problematic, as it would require one of these sub-optimal courses of action: - Stick the source of the library into workspace/src/library where I would actually develop and then use a duplicate package in the workspace/src/github.com/SiegeLord/library that would be created by rustpkg (the program is located in workspace/src/program). Somehow this duplicate package will be synced to the actual package: either through pushing to GitHub and then pulling somehow via rustpkg (this is less than ideal, as I may want to test WIP changes without committing them elsewhere/I may have no internet connection e.g. when traveling), or some manual, local git operation. - Stick the source of the library into workspace/src/github.com/SiegeLord/library and develop the library there. There is no duplication, but it really seems bizarre to me to locate a project in a directory named like that. Also, I'd be a bit paranoid about rustpkg not realizing that I never want to communicate with GitHub and having it accidentally overwriting my local changes. The second option is to use library as the package id. This allows me to locate my library in a logical location (workspace/src/library), but it prevents other users of my program from building it automatically. Essentially what they'll have to do is to manually check out the library repository inside their workspaces so as to create the workspace/src/library directory on their system: the `extern mod` syntax will not work otherwise. I don't think any of these options are ideal. I don't want to suggest solutions to these issues because I'm not sure how things are supposed to be used/what the planned design is. Does anybody use rustpkg seriously today? Is everybody making workspaces with a github.com/user directory where they develop their software? -SL ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev -- Tim Chevalier * http://catamorphism.org/ * Often in error, never in doubt If you are silent about your pain, they'll kill you and say you enjoyed it. -- Zora Neale Hurston ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
On Wed, Dec 04, 2013 at 12:23:35AM -0800, Patrick Walton wrote: Not without higher kinded types (which eventually we do want--so the answer is not yet). This. That said, I imagine that if we do it right, it'll be possible to write one persistent map implementation that can be used with GC, ARC, and also an arena. The latter would -- at least in principle -- make it possible to store references. I haven't thought hard about this though and it may be that complications arise. Niko ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
Is it
possible for the structure to be parametrized on smart pointer?
Not without higher kinded types (which eventually we do want--so the
answer is not yet).
I've been thinking about that a bit more and I think it might be
possible to support different reference types without higher-kinded
types. We can define a `Reference` trait that is then implemented for
`Rc`, `Arc` and what have you. Something like:
trait ReferenceT : Clone {
fn borrow'a('a self) - 'a T;
}
If we also want to create references without knowing their concrete
type, we also need a trait for creating them:
trait ReferenceFactoryT, TRef: ReferenceT {
fn create_reference(self, val: T) - TRef;
}
And then we can define a container type, using the generic reference type:
struct ContainerT, TRef, TRefFactory {
items: ~[TRef],
reference_factory: TRefFactory
}
It contains a `ReferenceFactory` value that is used to create
`Reference` instances when the container needs one (see the `add` method
below):
impl
T,
TRef: ReferenceT,
TRefFactory: ReferenceFactoryT, TRef
ContainerT, TRef, TRefFactory {
pub fn create(factory: TRefFactory) - ContainerT, TRef,
TRefFactory {
Container {
reference_factory: factory,
items: ~[]
}
}
pub fn add(mut self, val: T) {
self.items.push(self.reference_factory.create_reference(val));
}
}
This setup is a bit roundabout but it should get the job done. Of
course, I may have overlooked something but at least rustc swallows the
above code without complaint ;)
If we could call static methods on type parameters, the factory
functionality could be moved to the `Reference` trait:
trait ReferenceT : Clone {
fn borrow'a('a self) - 'a T;
fn new(value: T) - Self;
}
// Now using the static `new` method instead of the `ReferenceFactory` trait
pub fn add(mut self, val: T) {
self.items.push(TRef::new(val));
}
With this, the code would actually be of acceptable complexity in my eyes.
-Michael
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Meeting-weekly-2013-12-03, str.from_utf8
On 12/04/2013 06:01 AM, Simon Sapin wrote: Hi, In response to: https://github.com/mozilla/rust/wiki/Meeting-weekly-2013-12-03#strfrom_utf8 Yes, error handling other than strict/fail requires allocation. I suggest taking the pull request for the special case of non-allocating strict UTF-8, and keeping error handling for a future, larger API that also handles other encodings (and incremental processing): OK. https://github.com/mozilla/rust/pull/10701 https://github.com/mozilla/rust/wiki/Proposal-for-character-encoding-API [On invalid UTF-8 bytes] brson: One has a condition that lets you replace a bad character I believe this is not implemented. The current not_utf8 condition lets you do the entire decoding yourself. You're right! I guess I was forshadowing. acrichto: We could truncate by default. I am very much opposed to this. Truncating silently loses data (potentially lots of it!) It should not be implemented, let alone be the default. I agree. jack: In python, you have to specify how you want it transformed. Truncate vs. replace with '?', etc. Maybe there should be an alternate version that takes the transform. pnkfelix: But doesn't work with slices... jack: There's truncate, replace, and fail. Python does not have truncate. It has ignore (skip invalid byte sequences but continue with the rest of the input), strict (fail), and replace (with � U+FFFD REPLACEMENT CHARACTER). You don’t have to specify an error handling, strict is the default. Ignore is bad IMO as it silently loses data (although it’s not as bad as truncate) though it could have uses I’m not thinking of right now. Side note: Regarding failing vs. returning an Option or Result: I’d be in favor of only having the latter. Having two versions of the same API (foo() and foo_opt()) is ugly, and it’s easy to get value or fail from an Option with .unwrap() Thanks for your always valuable feedback, Simon! ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Rust front-end to GCC
Hi,
fn fib1 (n:int) - int {
if (n = 1) { 1 }
else { n * fib1 (n - 1) }
}
Wrong function name. That's fac. ;-)
fib is
...
else { fib1 (n - 1) + fib1 (n - 2) }
-- Matthias Urlichs
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Rust front-end to GCC
On 12/03/2013 09:22 AM, Philip Herron wrote: Hey all Some of you may have noticed the gccrs branch on the git mirror. Since PyCon IE 2013 i gave a talk on my Python Front-end pet project and heard about rust by a few people and i never really looked at it before until then but i've kind of been hooked since. So to learn the language i've been writing this front-end to GCC. Only really a a month or so on and off work in between work. Currently it compiles alot of rust already in fairly little effort on my side GCC is doing loads of the heavy lifting. Currently it compiles most of the basic stuff such as a struct an impl block while loop, functions expressions calling methods passing arguments etc. Currently focusing on getting the typing working correctly to support and ~ and look at how templates might work as well as need to implement break and return. There is still a lot of work but i would really like to share it and see what people think. Personally i think rust will target GCC very well and be a good addition (if / when it works). I really want to try and give back to this community who have been very good to me in learning over the last few years with GSOC. This is very exciting work. I'm looking forward to following your progress. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Please welcome the Rust and Servo GNOME/OPW interns for December 2013-March 2014
So much awesome! On Wed, Dec 4, 2013 at 2:43 PM, Brian Anderson bander...@mozilla.comwrote: Welcome aboard, Nif and Isabelle. I'm looking forward to working with you. And thanks for setting this up, Tim and Lars. On 12/04/2013 08:18 AM, Tim Chevalier wrote: Hello, I'm pleased to announce that the winter/spring Rust and Servo interns through the GNOME Outreach Program for Women ( https://wiki.gnome.org/OutreachProgramForWomen ) have been chosen. The program starts December 10 and runs until March 10. Nif Ward (IRC nick: nif) will be interning on Rust, working to develop a full-fledged B-tree library. Nif is a senior graduating this fall in computer science from Oberlin College in Ohio, USA. I will be her mentor. Isabelle Carter (IRC nick: ibnc) will be interning on Servo, working to add support for fixed positioning. Isabelle is on leave from her undergraduate degree in mathematics, and will be working from Springfield, Missouri, USA. Lars Bergstrom will be her mentor. We had many qualified applicants for Rust and Servo's first foray into OPW, so it's an honor to be chosen for this program. Please be friendly to nif and ibnc if you see them on #rust! Depending how this round of OPW goes, Rust and/or Servo may participate in a future iteration, so if you're interested in applying, then keep watching for more announcements. In addition, internships at Mozilla working on Rust and Servo (look for the Research Engineering listing; paid, on-site in the Bay Area) are open to all graduate students (undergraduate students with research experience have been considered in the past): http://careers.mozilla.org/ . Thanks are due to the Rust and Servo teams -- particularly Lars Bergstrom, Brian Anderson, and Jack Moffitt -- for helping many people apply for the program, and to the Mozilla coordinator for OPW, Larissa Shapiro, for their efforts. Cheers, Tim ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Separated/Incremential compilation
On Fri, Nov 29, 2013 at 9:09 AM, Patrick Walton pcwal...@mozilla.com wrote: I shouldn't say that Rust has no problems with build times--it could always be faster, and in particular the memory representations are inefficient, particularly around ASTs--but when you actually run with `-Z time-passes`, you'll see that the vast majority of the time for any reasonably-sized crate is spent in LLVM. There isn't much we can do to make that faster by an order of magnitude, other than to try to push on the parallel per-function optimization and codegen work that is happening in some upstream branches. Mergefunc, disabling exceptions, and the no-zeroing-out stuff that Niko is doing would be nice, but they won't improve build times by an order of magnitude. What about caching LLVM bitcode for individual Rust functions / items (using workcache, for example) and only recompiling those items whose dependencies have changed? Obviously this would be a lot of design and implementation work, and one would want to do the math to make sure it's likely to improve build performance, but offhand I can't see why it's not feasible. The scenario I'm thinking of is add a debug! statement to one function, and only recompile the code for that function since its interface hasn't changed. In that case, only regenerating code for the changed function and not the entire crate should make a big difference. Cheers, Tim Patrick [1]: https://groups.google.com/forum/#!topic/mozilla.dev.platform/WjcCfckml4A ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev -- Tim Chevalier * http://catamorphism.org/ * Often in error, never in doubt If you are silent about your pain, they'll kill you and say you enjoyed it. -- Zora Neale Hurston ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Separated/Incremential compilation
On 11/29/2013 03:01 AM, Léo Testard wrote: Hello, I think everyone here will agree to say that compilation times in Rust are problematic. Recently, there was an argument on IRC about reducing compilation times by reducing the use of GC and failures. Although I agree it's good to reduce Rustc's overhead, I think there are more important problems. The total duration of a build matters only because you have to recompile the whole crate on each modification. In C++, the duration of the complete build of a project matters less because when you compile incrementally, you only have to rebuild a couple of files - those you modified. I know the 1 crate = 1 compilation unit is the model chosen by Rust, but this is a major issue for production. Nobody will ever use Rust in production if they have to recompile thousands of lines of code on each modification. On some of my personal projects, I solved this problem by splitting the codebase into several crates, that I compile statically, and then link together using extern mod. This is not really a solution, because this implies that there is no cyclic dependency between each of the small crates, or I end up with issues trying to compile it, because using extern mod requires that the library corresponding to that mod exists before compiling the crate that depends on it. But strictly speaking, a compiled crate is nothing more than a module hierarchy, and so is a single Rust source file, so we should be able to compile a single file to some sort of .o and then link all together to form a crate. References to modules outside of this file just require the first passes of the build, not the code generation, so it should be ok regarding to cyclic dependencies, and if not, we could still introduce some kind of auto-generated interface file, like Caml does. I know it's quite a big work, and that the current system is quite good, but having this is very important if we want Rust to be used in production. I agree that incremental recompilation would be a good thing to pursue, and I'd be happy to see someone work on it, but as you say it is a very difficult problem, and it's frankly a low priority. Some other compilition performance wins to pursue are removing metadata compression (causes dynamic linker crashes on linux), improving llvm perf, and improving linker perf. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Plz separate mail threads for separated compilation [was Re: Separated/Incremential compilation]
Thanks Felix. I added this to https://github.com/mozilla/rust/issues/4047 On 11/29/2013 05:46 AM, Felix S. Klock II wrote: First off, the topic of rustc slowness and long bootstrap times has indeed been discussed many times. If you have not yet tried skimming the archives, I recommend doing so, e.g. via http://lmgtfy.com/?q=+site%3Amail.mozilla.org+rust+crate+compilation+speed (I provide a (surely incomplete) list of previous-post links below.) Now, a request: when discussing this topic, please try to avoid conflating: 1. librustc+libstd bootstrap time, from the somewhat separate issues of 2. models for incremental compilation, and 3. compilation times when running rustc on projects other than rustc itself. In particular, incremental compilation alone is not going to solve (1). (At least, not as long as one is using the default make rule that rebuilds all of librustc+libstd atop the newly built rustc, and rustc itself draws upon a (large) libstd. Under the latter two constraints, you *have* to redo the build for all of librustc+libstd: the compiler itself was changed. Incremental compilation does not solve this.) I am concerned that we will waste time debating tasks/designs related to (2) and then people will be disappointed when it does not provide the gains that they were expecting for issues like (1). In case its not clear from the comments above: the team is well aware that rustc itself runs more slowly than it should; it is a common topic of discussion. The team is also well aware that the time to bootstrap librustc+libstd is longer than many developers can cope with. I am not sure I agree with the assertion that the approach of breaking a project into multiple crates is not a solution. Yes, we may need better tools here (though I don't know how much rustpkg could help with this problem). As promised, here are some relevant links to previous posts. In *all* of the cases below, the *whole thread* is often worth review. * A great overview from pcwalton Thread subject: Why does Rust compile slowly? https://mail.mozilla.org/pipermail/rust-dev/2012-October/002462.html * In early 2013 there was discussion of easing crate decomposition: Thread subject: Plans for improving compiler performance https://mail.mozilla.org/pipermail/rust-dev/2013-January/002878.html * strcat and graydon each had good points in this discussion: Thread subject: Please tell me about making rustc faster https://mail.mozilla.org/pipermail/rust-dev/2013-May/004326.html https://mail.mozilla.org/pipermail/rust-dev/2013-May/004328.html * The team internally discussed whether to break lubrustc into multiple subcrates here: Thread subject: code generation and rustc speed https://mail.mozilla.org/pipermail/rust-dev/2013-June/004493.html Cheers, -Felix On 29/11/2013 12:22, Guillaume HERVIER wrote: +1 for this issue. I think that compilation time is really important if we want Rust to be used as production language. For example, I think that if we can reduce significantly the Rust compiler's compilation time, it could allow more developers to contribute to the Rust language (as they won't have to wait 30min for each small modifications in the compiler). Personally, it's the only thing which blocks me when I want to contribute to Rust, because I like to often compile code when I do small modifications to test each of these small modifications, partly because I don't know the language very well. On 11/29/2013 12:01 PM, Léo Testard wrote: Hello, I think everyone here will agree to say that compilation times in Rust are problematic. Recently, there was an argument on IRC about reducing compilation times by reducing the use of GC and failures. Although I agree it's good to reduce Rustc's overhead, I think there are more important problems. The total duration of a build matters only because you have to recompile the whole crate on each modification. In C++, the duration of the complete build of a project matters less because when you compile incrementally, you only have to rebuild a couple of files - those you modified. I know the 1 crate = 1 compilation unit is the model chosen by Rust, but this is a major issue for production. Nobody will ever use Rust in production if they have to recompile thousands of lines of code on each modification. On some of my personal projects, I solved this problem by splitting the codebase into several crates, that I compile statically, and then link together using extern mod. This is not really a solution, because this implies that there is no cyclic dependency between each of the small crates, or I end up with issues trying to compile it, because using extern mod requires that the library corresponding to that mod exists before compiling the crate that depends on it. But strictly speaking, a compiled crate is nothing more than a module hierarchy, and so is a single Rust
Re: [rust-dev] Separated/Incremential compilation
Maybe this should be done upstream in LLVM, actually. Seems like work that would be applicable to e.g. clang with LTO as well. Tim Chevalier catamorph...@gmail.com wrote: On Fri, Nov 29, 2013 at 9:09 AM, Patrick Walton pcwal...@mozilla.com wrote: I shouldn't say that Rust has no problems with build times--it could always be faster, and in particular the memory representations are inefficient, particularly around ASTs--but when you actually run with `-Z time-passes`, you'll see that the vast majority of the time for any reasonably-sized crate is spent in LLVM. There isn't much we can do to make that faster by an order of magnitude, other than to try to push on the parallel per-function optimization and codegen work that is happening in some upstream branches. Mergefunc, disabling exceptions, and the no-zeroing-out stuff that Niko is doing would be nice, but they won't improve build times by an order of magnitude. What about caching LLVM bitcode for individual Rust functions / items (using workcache, for example) and only recompiling those items whose dependencies have changed? Obviously this would be a lot of design and implementation work, and one would want to do the math to make sure it's likely to improve build performance, but offhand I can't see why it's not feasible. The scenario I'm thinking of is add a debug! statement to one function, and only recompile the code for that function since its interface hasn't changed. In that case, only regenerating code for the changed function and not the entire crate should make a big difference. Cheers, Tim Patrick [1]: https://groups.google.com/forum/#!topic/mozilla.dev.platform/WjcCfckml4A ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev -- Tim Chevalier * http://catamorphism.org/ * Often in error, never in doubt If you are silent about your pain, they'll kill you and say you enjoyed it. -- Zora Neale Hurston -- Sent from my Android phone with K-9 Mail. Please excuse my brevity.___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
Hello, I already implemented a persistent tree-map called SnapMap: you can find the source code at https://github.com/mozilla/rust/pull/9816 I stopped working on it before I made a serious effort to push it into the Rust codebase and don't have time to work further on it, so it would be awesome if you were interested in continuing that effort. It's pretty much finished, but pretty much completely untested (however, it was derived from the existing treemap, so the amount of bugs should not be as high as something written from scratch and untested). The first thing that needs to be done is to run the existing tests inherited from treemap, fix any bug that shows up, and then write more tests to test SnapMap specific usage patterns and features. Then, one should look at the mutable/handle-based iterators in the code and decide whether they should be removed, kept as is, or improved, possibly after changing the iterator interface to return an object with the lifetime of the function call instead of the iterator. The rest of the code should be fine (except for bugs due to no testing), but there might be places where unnecessary copy-on-write is performed. My code used an improved version of Rc that supports copy-on-write by cloning only when reference count 1. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Please welcome the Rust and Servo GNOME/OPW interns for December 2013-March 2014
Hooray, welcome to our new contributors! :) And thanks to our mentors and coordinators as well! On Wed, Dec 4, 2013 at 11:18 AM, Tim Chevalier catamorph...@gmail.comwrote: Hello, I'm pleased to announce that the winter/spring Rust and Servo interns through the GNOME Outreach Program for Women ( https://wiki.gnome.org/OutreachProgramForWomen ) have been chosen. The program starts December 10 and runs until March 10. Nif Ward (IRC nick: nif) will be interning on Rust, working to develop a full-fledged B-tree library. Nif is a senior graduating this fall in computer science from Oberlin College in Ohio, USA. I will be her mentor. Isabelle Carter (IRC nick: ibnc) will be interning on Servo, working to add support for fixed positioning. Isabelle is on leave from her undergraduate degree in mathematics, and will be working from Springfield, Missouri, USA. Lars Bergstrom will be her mentor. We had many qualified applicants for Rust and Servo's first foray into OPW, so it's an honor to be chosen for this program. Please be friendly to nif and ibnc if you see them on #rust! Depending how this round of OPW goes, Rust and/or Servo may participate in a future iteration, so if you're interested in applying, then keep watching for more announcements. In addition, internships at Mozilla working on Rust and Servo (look for the Research Engineering listing; paid, on-site in the Bay Area) are open to all graduate students (undergraduate students with research experience have been considered in the past): http://careers.mozilla.org/ . Thanks are due to the Rust and Servo teams -- particularly Lars Bergstrom, Brian Anderson, and Jack Moffitt -- for helping many people apply for the program, and to the Mozilla coordinator for OPW, Larissa Shapiro, for their efforts. Cheers, Tim -- Tim Chevalier * http://catamorphism.org/ * Often in error, never in doubt If you are silent about your pain, they'll kill you and say you enjoyed it. -- Zora Neale Hurston ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
On 12/04/2013 02:09 PM, Michael Woerister wrote:
Is it
possible for the structure to be parametrized on smart pointer?
Not without higher kinded types (which eventually we do want--so the
answer is not yet).
And then we can define a container type, using the generic reference type:
struct ContainerT, TRef, TRefFactory {
items: ~[TRef],
reference_factory: TRefFactory
}
Clever solution! In the cons list, it needs to be a reference to
NodeT, not to T. Every persistent container library would have to
expose its node type and take as a parameter an allocator for its
NodeT. Simplified example:
enum NodeT, TNodeRef {
Nil,
Cons(T, TNodeRef)
}
type IntList = RcNodeint, IntList;
But that is an infinite type and, as such, does not compile. Instead using
struct IntList(RcNodeint, IntList);
works and could implement the necessary traits. Or better,
struct RcListT(RcNodeT, RcListT);
Ooh, this is within the realm of maybe being reasonable. A persistent
data structure module could provide RcList and ArcList versions. Is
performance affected by the use of traits for this strategy, or does the
way Rust generics are compiled make that a non-issue? Are there other
reasons this is a terrible idea? :)
-Isaac
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
On Wed, Dec 4, 2013 at 4:17 PM, Isaac Dupree
m...@isaac.cedarswampstudios.org wrote:
On 12/04/2013 02:09 PM, Michael Woerister wrote:
Is it
possible for the structure to be parametrized on smart pointer?
Not without higher kinded types (which eventually we do want--so the
answer is not yet).
And then we can define a container type, using the generic reference type:
struct ContainerT, TRef, TRefFactory {
items: ~[TRef],
reference_factory: TRefFactory
}
Clever solution! In the cons list, it needs to be a reference to NodeT,
not to T. Every persistent container library would have to expose its node
type and take as a parameter an allocator for its NodeT. Simplified
example:
enum NodeT, TNodeRef {
Nil,
Cons(T, TNodeRef)
}
type IntList = RcNodeint, IntList;
But that is an infinite type and, as such, does not compile. Instead using
struct IntList(RcNodeint, IntList);
works and could implement the necessary traits. Or better,
struct RcListT(RcNodeT, RcListT);
Ooh, this is within the realm of maybe being reasonable. A persistent data
structure module could provide RcList and ArcList versions. Is performance
affected by the use of traits for this strategy, or does the way Rust
generics are compiled make that a non-issue? Are there other reasons this
is a terrible idea? :)
-Isaac
Generics are equivalent to substituting all of the type parameters
with the concrete type by hand. Specialized code is generated for each
set of type parameters with removing the duplication left up to LLVM
(`mergefunc` is close to being completely stable).
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
On 12/04/2013 03:36 PM, Bill Myers wrote: Hello, I already implemented a persistent tree-map called SnapMap: you can find the source code at https://github.com/mozilla/rust/pull/9816 I stopped working on it before I made a serious effort to push it into the Rust codebase and don't have time to work further on it, so it would be awesome if you were interested in continuing that effort. It's pretty much finished, but pretty much completely untested (however, it was derived from the existing treemap, so the amount of bugs should not be as high as something written from scratch and untested). The first thing that needs to be done is to run the existing tests inherited from treemap, fix any bug that shows up, and then write more tests to test SnapMap specific usage patterns and features. Yay! Looks like I should start by collecting the various existing persistent structures (your SnapMap, Michael's HAMT, extra::list) and polishing them up. Then, one should look at the mutable/handle-based iterators in the code and decide whether they should be removed, kept as is, or improved, possibly after changing the iterator interface to return an object with the lifetime of the function call instead of the iterator. The rest of the code should be fine (except for bugs due to no testing), but there might be places where unnecessary copy-on-write is performed. My code used an improved version of Rc that supports copy-on-write by cloning only when reference count 1. Did COW improve performance? What's a good way to do performance testing of Rust code? Should I try to get your patches to Rc and Arc merged? They look generally useful, if folks think they fit the design of Rc. You also have a patch that adds OwnT to std which is equivalent to ~T but has methods that look like Rc's. You use this, and putting most of your treemap.rs inside macro definitions, to get a sort of reference-type-polymorphism in your treemap. Shall I continue with this approach and try to get OwnT merged too? (Opinions from anybody are welcome.) (I used https://github.com/mozilla/rust/pull/9816/files + click Show Diff Stats to look through the changes) -Isaac ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
[rust-dev] Interesting talk about (scala) language/compiler complexity
To be taken with a grain of salt, naturally: https://www.youtube.com/watch?v=TS1lpKBMkgg -- Ziad ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
Did COW improve performance? What's a good way to do performance testing of Rust code? The reason I introduced COW when RC 1 is that it allows persistent data structures to be mutated in place if there aren't extra references, just like non-persistent data structures. Lots of languages with persistent data structures can't do that because they use garbage collection (and thus they can't tell whether there are other references due to lack of a reference count), but it seems an essential feature to have if one is using reference counting in a language like Rust that is supposed to be a systems language producing optimal code. Should I try to get your patches to Rc and Arc merged? They look generally useful, if folks think they fit the design of Rc. You also have a patch that adds OwnT to std which is equivalent to ~T but has methods that look like Rc's. You use this, and putting most of your treemap.rs inside macro definitions, to get a sort of reference-type-polymorphism in your treemap. Shall I continue with this approach and try to get OwnT merged too? (Opinions from anybody are welcome.) I did it because I realized that having two different balanced tree implementations would have imposed a significant maintenance burden, and thus the macro and OwnT approach would have allowed to avoid that by replacing the current treemap code completely with the new optionally-persistent version. Also, having both Rc and Arc versions seems quite useful anyway, and currently I think macros are the best way to have both, until Rust starts supporting higher-kinded types (which would allow to pass Rc as a parameter), or at least recursive types (which would allow to express RcTreeNodeT, RcTreeNode, T, ... and pass it as a parameter). I don't have much more input on what the best names for the methods are, whether to have OwnT instead of ~T and so on; I guess someone on the Rust core team will have to decide on that, and there's already some discussion on that on https://github.com/mozilla/rust/pull/9786 ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Interesting talk about (scala) language/compiler complexity
There are a couple parts of the Rust compiler about which I've heard people say if I knew how that worked, I'd fix it so that we could do ... So I definitely thought of Rust when watching that. I think it is very encouraging to see so how many components Rust has pushed out of the core and into libraries in the last year or so, though. Rust seems a long way from ossification. Considering Scala, count me pre-emptively as a fan of rustz. Hopefully we can avoid that kind of apparent community split, though... Kevin On Wed, Dec 4, 2013 at 5:07 PM, Ziad Hatahet hata...@gmail.com wrote: To be taken with a grain of salt, naturally: https://www.youtube.com/watch?v=TS1lpKBMkgg -- Ziad ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Interesting talk about (scala) language/compiler complexity
On 12/4/13 7:36 PM, Kevin Cantu wrote: There are a couple parts of the Rust compiler about which I've heard people say if I knew how that worked, I'd fix it so that we could do ... So I definitely thought of Rust when watching that. The Rust compiler is not that bad. Niko and I, as well as several others I'm sure, know how basically all of it works, at least at a high level. I think it's true that in any large piece of software, it's never true that everyone knows precisely how all of it works. The biggest problem with the Rust compiler, I think, is much of it is written in an old Rust style, and modernizing its style would not take too long. (Unfortunately we're all racing to 1.0 and on the core team such modernization will have to take a back seat to the 1.0-incompatible language changes... but that said we should not allow our technical debt to garner too much interest.) The particular criticisms of the Scala compiler, that the front-end does too much desugaring and that code is a string, are definitely not true for the Rust compiler. (Well, OK, `for` is desugared too early, but that has to be fixed before 1.0 anyway because this desugaring is actually incorrect.) Niko and Jed, just to name two, have done a lot of work to improve the state of the Rust compiler, for example by rewriting type unification, rewriting ad-hoc passes to use the CFG produced by liveness analysis, introducing `Datum`, and creating a universal ADT type to represent data types. There is more work to be done, of course, and I think we should very much hold the line against additional cruft being added to the compiler at this point, but I think we're OK as long as we keep moving in the right direction. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Interesting talk about (scala) language/compiler complexity
On 12/4/13 5:07 PM, Ziad Hatahet wrote: To be taken with a grain of salt, naturally: https://www.youtube.com/watch?v=TS1lpKBMkgg I watched some of this. Some notes on specific criticisms follow. (Many of the criticisms are too abstract to really confront head-on though--for example, correctness versus performance.) 1. *The compiler is too hard to modify.* See my other message in the thread. 2. *Universal equality is bad.* Rust doesn't do it. 3. *Using inheritance for collection mutability is bad.* Rust doesn't do it. 4. *The argument to functions such as filter should be pure to allow for stream fusion.* Purity is hard in Rust. We tried it and the annotation burden was too high. At least our iterators allow for more stream fusion than creating intermediate data structures would. 5. *Forbid reference equality.* Incompatible with the systems language nature of Rust. 6. *Silent coercion between primitives is bad.* Rust doesn't do it. 7. *Don't try to be too general purpose.* Rust is explicitly not designed to be a language for all use cases. 8. *Unnecessary expressiveness is the enemy.* I think we've been holding the line on language complexity quite well, even for features that are popular like `once fn`. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
My next goal is a persistent tree-map, probably cribbing from Haskell's Data.Map. I look forward to hearing how that goes! I've been meaning to make a data structure in Rust too, but it's hard to find the time, so how's about I tell you guys about it instead. I call my data structure an optionally-persistent hashtable or hashset. In C# I implemented this optionally-persistent hashtable and hashset with mutable and immutable variants of each (the term semi-persistent was already taken and means something else). I've been meaning to write an article about this, but didn't get around to it yet. Optionally-persistent means that it's structured as if it were persistent, but each node can be either mutable (locally) or immutable (recursively). Each node has a frozen flag which implicitly applies recursively to all children. Converting the tree from immutable to mutable, or mutable to immutable takes O(1) time. Immutable to mutable is essentially a no-op (the mutable copy has copy-on-write behavior), while mutable-to-immutable simply requires marking the root node as frozen. The hashtable is really a tree that is up to 8 levels deep, with each level representing 4 bits of the hashcode (not sure if this is the best approach). Lots more details in the doc comment: https://sourceforge.net/p/loyc/code/HEAD/tree/Src/Loyc.Collections/Sets/InternalSet.cs My benchmarks show that mutating such a set/map is dramatically faster than immutable editing (which requires copying multiple nodes for each change), and not that much slower than a traditional hashtable, so I think it's hands down superior to a traditional persistent hash tree. In my version, from the end-user's perspective, there's a separate data type for immutable and mutable versions of the data structure (MMapT and MSetT are mutable, MapT and SetT are immutable). Both data types encapsulate an instance of InternalSetT which is the real data structure. InternalSetT manages a tree of nodes, where each node has 16 entries and represents 4 bits of the hashcode. There's also an interesting variation called InvertibleSetT; an invertible set can represent a negative set such as all integers except 0 and 1. -- - David http://loyc-etc.blogspot.com ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Interesting talk about (scala) language/compiler complexity
On 5 Dec 2013, at 1:46 pm, Patrick Walton pcwal...@mozilla.com wrote: The particular criticisms of the Scala compiler, that the front-end does too much desugaring and that code is a string, are definitely not true for the Rust compiler. (Well, OK, `for` is desugared too early, but that has to be fixed before 1.0 anyway because this desugaring is actually incorrect.) Whilst desugaring too early is indeed an issue for creating a robust compiler, would it still make sense to think of how these language features desugar on a design/theoretical level? Then once these are set in stone for 1.0, document these transformations? ~Brendan ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Interesting talk about (scala) language/compiler complexity
3. *Using inheritance for collection mutability is bad.* Rust doesn't do it. Is this an argument against generalizing over mutability at all (as I believe has been proposed in the past)? On Wed, Dec 4, 2013 at 10:53 PM, Patrick Walton pcwal...@mozilla.comwrote: On 12/4/13 5:07 PM, Ziad Hatahet wrote: To be taken with a grain of salt, naturally: https://www.youtube.com/watch?v=TS1lpKBMkgg I watched some of this. Some notes on specific criticisms follow. (Many of the criticisms are too abstract to really confront head-on though--for example, correctness versus performance.) 1. *The compiler is too hard to modify.* See my other message in the thread. 2. *Universal equality is bad.* Rust doesn't do it. 3. *Using inheritance for collection mutability is bad.* Rust doesn't do it. 4. *The argument to functions such as filter should be pure to allow for stream fusion.* Purity is hard in Rust. We tried it and the annotation burden was too high. At least our iterators allow for more stream fusion than creating intermediate data structures would. 5. *Forbid reference equality.* Incompatible with the systems language nature of Rust. 6. *Silent coercion between primitives is bad.* Rust doesn't do it. 7. *Don't try to be too general purpose.* Rust is explicitly not designed to be a language for all use cases. 8. *Unnecessary expressiveness is the enemy.* I think we've been holding the line on language complexity quite well, even for features that are popular like `once fn`. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Error casting to trait: value may contain borrowed pointers
I see, thanks for the explanation. Looks like a compiler bug, then.
I'll work around it with an unsafe transmute for now.
Thanks,
Christian.
On Mon, Dec 2, 2013 at 5:49 AM, Felix S. Klock II pnkfe...@mozilla.com wrote:
rust-dev-
In general, we need to ensure that for an expression `source as target`
that any borrowed pointers in the type of source are not obscured [1] by
the cast.
A collection of conditions sufficient to enforce this are listed in a
comment in librustc/middle/kind.rs that I think is apropos here:
https://github.com/mozilla/rust/blob/master/src/librustc/middle/kind.rs#L488
However, there are probably other conditions that would also suffice that we
might add to that set.
In particular, I do not see anything immediately wrong with your example;
the type-expression `'a V` should ensure that `V` does not contain any
lifetimes that are shorter than 'a, and therefore it should be safe to cast
`v: 'a V` to a `'a T`.
I have filed this as issue #10766 [2].
Cheers,
-Felix
[1] https://github.com/mozilla/rust/issues/5723
[2] https://github.com/mozilla/rust/issues/10766
On 30/11/2013 23:22, Christian Ohler wrote:
Hi all,
I'm trying to learn rust and ran into an error message I don't
understand, and would appreciate some help. This code:
trait T {}
fn f'a, V: T(v: 'a V) - 'a T {
v as 'a T
}
is rejected with this error message:
trait-cast.rs:4:4: 4:5 error: value may contain borrowed pointers; add
`'static` bound
trait-cast.rs:4 v as 'a T
I'm trying to upcast from V to T so that I can put v in a container of
element type T (in code not shown here). The suggestion to add a
'static bound doesn't sound like what I'm looking for.
What is the concern about borrowed pointers here? What would an
implementation of T and a caller of f look like to lead to a safety
problem?
I'm using a version of rust that is a few days old.
Thanks,
Christian.
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
--
irc: pnkfelix on irc.mozilla.org
email: {fklock, pnkfelix}@mozilla.com
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Persistent data structures
Please disregard this message; I hadn't seen Bill Myers' solution (copy-on-write by cloning only when reference count 1), which sounds like it's probably perfect for Rust. On Wed, Dec 4, 2013 at 9:03 PM, David Piepgrass qwertie...@gmail.comwrote: My next goal is a persistent tree-map, probably cribbing from Haskell's Data.Map. I look forward to hearing how that goes! I've been meaning to make a data structure in Rust too, but it's hard to find the time, so how's about I tell you guys about it instead. I call my data structure an optionally-persistent hashtable or hashset. In C# I implemented this optionally-persistent hashtable and hashset with mutable and immutable variants of each (the term semi-persistent was already taken and means something else). I've been meaning to write an article about this, but didn't get around to it yet. Optionally-persistent means that it's structured as if it were persistent, but each node can be either mutable (locally) or immutable (recursively). Each node has a frozen flag which implicitly applies recursively to all children. Converting the tree from immutable to mutable, or mutable to immutable takes O(1) time. Immutable to mutable is essentially a no-op (the mutable copy has copy-on-write behavior), while mutable-to-immutable simply requires marking the root node as frozen. The hashtable is really a tree that is up to 8 levels deep, with each level representing 4 bits of the hashcode (not sure if this is the best approach). Lots more details in the doc comment: https://sourceforge.net/p/loyc/code/HEAD/tree/Src/Loyc.Collections/Sets/InternalSet.cs My benchmarks show that mutating such a set/map is dramatically faster than immutable editing (which requires copying multiple nodes for each change), and not that much slower than a traditional hashtable, so I think it's hands down superior to a traditional persistent hash tree. In my version, from the end-user's perspective, there's a separate data type for immutable and mutable versions of the data structure (MMapT and MSetT are mutable, MapT and SetT are immutable). Both data types encapsulate an instance of InternalSetT which is the real data structure. InternalSetT manages a tree of nodes, where each node has 16 entries and represents 4 bits of the hashcode. There's also an interesting variation called InvertibleSetT; an invertible set can represent a negative set such as all integers except 0 and 1. -- - David http://loyc-etc.blogspot.com -- - David http://qism.blogspot.com ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
