Some thoughts on extensible sequences
in [Lisp]
|
Prev: introductory texts for new Lispers
Next: trace of Thermite (tm) at WTC, almost no asbestos: if the main beams had been clad, they mightn't have weakened enough to collapse!
From: Alessio Stalla on 30 Jul 2010 17:10 On 30 Lug, 20:53, Helmut Eller <eller.hel...(a)gmail.com> wrote: > * Alessio Stalla [2010-07-30 17:43] writes: > > >> This is incorrect: There is 'concatenate. > > > Concatenate requires all sequences to be copied. Also, it is > > inconvenient to use as a replacement for APPEND since it requires to > > specify the target sequence type. What I'd like to have is something > > like > > There's also ADJOIN. At least that would be the closest to Clojures's > conj. But there's nothing like that for java.util.List and it wouldn't > be efficient. Sounds like you want need something like PUSH. ADJOIN is specified to work on lists only, so it cannot be made generic. As for java.util.List, you're right, probably I'd need to have destructive counterparts to "scons" and "sappend" (whoah, I chose really bad names!). However, the main use case I want to support is to iterate over lists returned by some Java API, not constructing those lists efficiently in Lisp. For that, I plan to make our Cons class implement the java.util.List interface, or, if I find that to not work, to create a tiny wrapper for that, say ConsList. > > [...] > > >> > The third design issue I found is less important and can be worked > >> > around by stretching the protocol a bit: there's no account for > >> > objects which can be iterated, but not accessed by index, like a hash- > >> > based set. Those aren't strictly speaking sequences, but still they > >> > would benefit from having some of the generic functions specialized on > >> > sequences be specialized on them as well. > > >> Could be interesting. > > > I think so too, especially given that SBCL's protocol adds support for > > iterators. However, if this was being designed from scratch, it would > > make sense to have a type/system class ITERABLE and have SEQUENCE as a > > subtype of it. Since CL can't be retrofitted like that, iterable will > > have to be a type disjoint from sequence. > > I think the SERIES package could deal quite naturally with iterators. > In fact, SERIES's generators are almost iterators. Nice, I never gave SERIES too much attention, it sounds like it's time to study it :) Thanks for the advice, Alessio
From: Alessio Stalla on 30 Jul 2010 17:17 On 30 Lug, 20:11, Pascal Costanza <p...(a)p-cos.net> wrote: > On 30/07/2010 20:02, Frank Buss wrote: > > > > > Pascal Costanza wrote: > > >> The Java Collections API is just bad. It's better to look at something > >> that is not designed for a toy language. :-P > > > What is bad of the Java Collection Framework (JCF)? I hope you don't think > > of the first try, with Vector and Hashtable. Since Java 2 it is much > > better: > > >http://download.oracle.com/javase/tutorial/collections/ > > > Abstracting implementations with interfaces and separate algorithms is a > > good idea and would be even easier when implementing in Common Lisp. > > > Maybe more natural for Lisp would be Smalltalk collections: > > >http://www.ifi.uzh.ch/richter/Classes/oose2/01_Collections/03_smallta... > > > No wonder that it is a bit similar to the JCF, because the author knows it. > > > Another useful resource is STL of C++. Without the need for templates and > > the horrible template syntax, it would be even fun to use it :-) > > >> Did anybody look at Dylan? > > > No, what are the advantages compared to other collection frameworks? > > When the JCF was introduced, there was already a widely used collection > framework for Java, the Java Generic Library. The JGL had a couple of > very cool features, but they were just ignored by the JCF. No idea why, > but it was probably a political issue. As most elements in Java. > > Just because something is in Java doesn't make it good. I have never > encountered anything that was built in Java that didn't suffer from > artificial limitations because of artificial restrictions of the > Java/JVM infrastructure. So please don't make it the first reference > point, and at least not the only reference point. > > If I understand correctly, a lot of thought was put into Dylan's > collections, and would have the advantage that, because Dylan is > dynamically typed and based on a variation of CLOS (generic functions > instead of message sending), it is probably much closer to what we need > in Common Lisp. I think that as far as API goes, and by that I mean interfaces, the JCF is nice. I admittedly don't know about Dylan's collections, or Smalltalk's, or even the STL, but I use the JCF regularly and it works nice (in the context of a language without any support for functional programming, that is). It lacks a Bag type, which is a shame, and due to the Java type system quirks it doesn't allow efficient collections of primitive types, which can be a huge limitation in certain applications. But the latter is a problem with Java as a whole, the poor collections can't do anything about it. Anyway, what I'm interested in is just to make those collections be first-class citizens in ABCL, certainly not to make ABCL's sequences implementation rely on them. Thanks for the input! Cheers, Alessio
From: Norbert_Paul on 31 Jul 2010 08:46 Frank Buss wrote: > Pascal Costanza wrote: [...] > Maybe more natural for Lisp would be Smalltalk collections: > > http://www.ifi.uzh.ch/richter/Classes/oose2/01_Collections/03_smalltalk/03_smalltalk.html Funny. Looking there at 5 Hashed Collections gives me the impression that JCF was inspired by Smalltalk's collections.
From: Scott L. Burson on 31 Jul 2010 23:48 Norbert_Paul wrote: > > I am missing something similar to Java Collections in Lisp, too. > Therefore on May 05-th I started a similar discussion here titled > > "A Collections Framework?" > > where I just asked if such framework existed in Lisp. > The result was like a verbose "No, it doesn't" but there seems to be a > library FSet which could be worthwhile having a closer look at. Could be :) > Currently I restrict myself to what Lisp offers to make my program run > first and optimize later. If you are using what Lisp offers, you are already optimizing prematurely. Use FSet and you can pessimize prematurely instead :) Ha ha, just kidding :) Seriously -- the design of FSet is such that every operation is within a log n factor of the best possible time complexity for that operation. So you can use the FSet types without worrying that there will be some operation whose time complexity will be problematic (e.g., linear-time list indexing) and so will force you to a different data structure. Also, FSet is quite space-efficient for small collections (unlike hash tables). Plus, you get the stylistic benefits of functional collections. So what I'm suggesting is to use the FSet collections by default. They are easy to use and packed with featureful goodness. Admittedly, it's still possible when using FSet that there will be some inner loop that updates a collection such that the time and garbage overhead of a functional collection will prove to be excessive. In that case one will eventually want to change that loop to use a different data structure. But since this is just a linear-factor problem rather than a time complexity problem, the change won't be so urgent. E.g., the loop might run half as fast as you want for any size input, but it won't blow up for large inputs. -- Scott
From: Norbert_Paul on 1 Aug 2010 08:59
Hi Schott, nice to meet you again. Scott L. Burson wrote: > If you are using what Lisp offers, you are already optimizing > prematurely. Use FSet and you can pessimize prematurely instead :) > > Ha ha, just kidding :) I don't get the joke? (knowing the difference "optimize" vs. "pessimize"). > So what I'm suggesting is to use the FSet collections by default. They > are easy to use and packed with featureful goodness. OKAY, OKAY! I'll give them a try next week. :) > [...] But since this is just a linear-factor problem rather > than a time complexity problem, the change won't be so urgent. E.g., the > loop might run half as fast as you want for any size input, but it won't > blow up for large inputs. Good point. I don't care much for linear factors, either. Norbert |