A Collections Framework?
in [Lisp]
|
Prev: scheme problem
Next: lisp student job offer
From: D Herring on 10 May 2010 19:47 On 05/10/2010 04:53 PM, Pascal Costanza wrote: > I'm concerned about this because using stateful iterators adds > unnecessary dependencies, which can hurt if you want to parallelize your > code. I think in the future we have to pay a lot more attention to such > issues. Is there a reason that stateful iterators couldn't be split? In particular, Java-style iterators (with an internal end) or Alexandrescu's Range objects might be able to split into two halves. Even C++'s iterators could do in a pinch. Relevant LtU thread: http://lambda-the-ultimate.org/node/3520 One promising design pattern to automatically parallelize code I heard from someone on the Sun Fortress design crew: While the input vector is "big", split it in half and push half on a queue; then recurse with the other half. Other threads can then pop jobs off the queue. I forget the exact name they used to describe this. Given an efficient API for splitting an iterator, it seems similar patterns could be layered on top of iterators. Even splitting a CONS-list into pieces may be cost effective depending the cost of processing each cell. - Daniel
From: Alessio Stalla on 11 May 2010 04:04 On May 10, 3:35 pm, Pascal Costanza <p...(a)p-cos.net> wrote: > On 10/05/2010 10:43, Alessio Stalla wrote: > > > > > On May 9, 2:27 am, "Scott L. Burson"<g...(a)zeta-soft.com> wrote: > >> Oh yes -- Christophe Rhodes published a proposal for genericizing the > >> CL sequence interface. I believe his proposal is implemented in SBCL, > >> but I'm not aware that any other implementation has picked up on it. > > > I recently ported it on ABCL, with the intent of adapting Java > > collections to the Lisp sequence interface (not done yet). > > >> My recollection is that it doesn't quite work for functional > >> collections, which is partly why I didn't try to use it, but for > >> imperative collections it might be useful. > > > Indeed, the CL sequence API in some parts assumes mutable collections. > > I think you should be able to avoid all such parts and still have a > > fully usable API, but I haven't investigated deeply. Note also that > > the Java Collections API referred to by the OP also has some > > operations that involve mutation which are specified to be optional, > > while having a core set of operations that is designed to also work on > > immutable collections. > > The Java collection API inherently builds on mutability: It's very hard > to create collections without having to "add" elements one by one, and > as soon as you want to iterate over a collection, you get a data > structure that keeps track of the iteration state by way of side > effects. I hope that Lisp collection frameworks don't copy such "features". It's not entirely true that it builds on mutability: the core set of operations (those specified in java.util.Collection) distinguish between mandatory operations, which work on any collection, and optional operations, which assume mutable collections and can be implemented to throw an exception in case of immutable data structures. It's true that you cannot incrementally build a collection without using add() to destructively modify the sequence (and that's hard to fix in a general way given Java's type system restrictions); but the CL sequence API is very similar in that regard: the generic equivalent of CONS does not exist. One can use CONCATENATE, but it's not really the same thing. About iterators: the CL sequence API per se does not say anything about iterators. The SBCL extensible sequences provide a concept of an iterator represented as several functions and three values representing the state of the iterator (current position, limit, from- end-p). AFAIK the iterators specified by SBCL are not stateful; all the functions are pure and it's the user's responsibility to advance the iterator state. It's also easy (API-wise, not necessarily implementation-wise) to have an iterator start from the middle of a sequence, so that you can have several iterators going in parallel. Regards, Alessio
From: Scott L. Burson on 11 May 2010 15:57 On May 11, 1:04 am, Alessio Stalla <alessiosta...(a)gmail.com> wrote: > On May 10, 3:35 pm, Pascal Costanza <p...(a)p-cos.net> wrote: > > The Java collection API inherently builds on mutability: It's very hard > > to create collections without having to "add" elements one by one, and > > as soon as you want to iterate over a collection, you get a data > > structure that keeps track of the iteration state by way of side > > effects. I hope that Lisp collection frameworks don't copy such "features". > > It's not entirely true that it builds on mutability: the core set of > operations (those specified in java.util.Collection) distinguish > between mandatory operations, which work on any collection, and > optional operations, which assume mutable collections and can be > implemented to throw an exception in case of immutable data > structures. Perhaps it bears pointing out here that functional collections are not merely immutable: they also have functional versions of the common imperative operations. For example, there needs to be an operation to construct a set as an existing set with a new value added. The Java collection API doesn't define such operations. > It's true that you cannot incrementally build a collection > without using add() to destructively modify the sequence (and that's > hard to fix in a general way given Java's type system restrictions); Please explain. What is it about Java's type system that makes this hard to fix? -- Scott
From: samantha on 11 May 2010 17:22 On May 5, 2:06 am, "Captain Obvious" <udode...(a)users.sourceforge.net> wrote: > NP> Is there something Comparable ($\ddot\smile$) to the > NP> Java Collections Framework in LISP. > > Unfortunately, no. > Closest I was able to find is cl-containers, but it is half-assed, to say it > lightly. > > NP> productive with huge data sets I will need things like > NP> balanced-trees etc. and I don't want to re-invent > NP> the wheel. > > There are some implementations of balanced trees available, but all of them > have some deficiencies. > (At least at time I was checking it.) > > NP> What I like in particular in Javas Collections is > NP> the separation of semantics (via "Interfaces") and > NP> implementation. There should be a similar standard in > NP> LISP. > > That would be nice, but I'd start with good underlying data structure > implementations. In what way do CL generic functions and CLOS fail to be many times more powerful and better at expressing interfaces than Java interfaces?
From: Alessio Stalla on 11 May 2010 17:45
On 11 Mag, 21:57, "Scott L. Burson" <g...(a)zeta-soft.com> wrote: > On May 11, 1:04 am, Alessio Stalla <alessiosta...(a)gmail.com> wrote: > > > On May 10, 3:35 pm, Pascal Costanza <p...(a)p-cos.net> wrote: > > > The Java collection API inherently builds on mutability: It's very hard > > > to create collections without having to "add" elements one by one, and > > > as soon as you want to iterate over a collection, you get a data > > > structure that keeps track of the iteration state by way of side > > > effects. I hope that Lisp collection frameworks don't copy such "features". > > > It's not entirely true that it builds on mutability: the core set of > > operations (those specified in java.util.Collection) distinguish > > between mandatory operations, which work on any collection, and > > optional operations, which assume mutable collections and can be > > implemented to throw an exception in case of immutable data > > structures. > > Perhaps it bears pointing out here that functional collections are not > merely immutable: they also have functional versions of the common > imperative operations. For example, there needs to be an operation to > construct a set as an existing set with a new value added. The Java > collection API doesn't define such operations. Fair enough. Concrete Collection implementations might add their own methods, but that's out of the scope of the generic API. But then, the CL sequence API is not much better in that regard. > > It's true that you cannot incrementally build a collection > > without using add() to destructively modify the sequence (and that's > > hard to fix in a general way given Java's type system restrictions); > > Please explain. What is it about Java's type system that makes this > hard to fix? Suppose I want to add a new method called "cons" which, when called on a Collection C and an object O, will return a new Collection with O appended in front of C. What would the signature of that method be? Collection.cons(T obj) : Collection -> loses type information, needs a cast (e.g. to ImmutableLinkedList), also casts in Java are dynamic type checks so an inefficiency (though small) is introduced Collection<COLLTYPE>.cons(T obj) : COLLTYPE -> ugly, every concrete collection class C must implement Collection<C> <COLLTYPE> Collection.cons(T obj) : COLLTYPE -> probably the best, it's unsafe (caller decides the type), but we're Lispers so we don't care ;) - but fits badly with the rest of Java others? I can't come up with any. Alessio |