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: Frank Buss on 30 Jul 2010 14:02 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_smalltalk/03_smalltalk.html 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? -- Frank Buss, fb(a)frank-buss.de http://www.frank-buss.de, http://www.it4-systems.de
From: Pascal Costanza on 30 Jul 2010 14:05 On 30/07/2010 19:43, Alessio Stalla wrote: > On 30 Lug, 17:27, Pascal Costanza<p...(a)p-cos.net> wrote: >> On 30/07/2010 17:10, Alessio Stalla wrote: >> >> >> >>> Some time ago I ported SBCL's extensible sequences protocol[1] to ABCL >>> and I'm now using it to make ABCL support Java collections natively. >>> While doing so, I realized that the sequences API has some >>> shortcomings I'd like to discuss here. >> >>> The first, perhaps more evident problem is that it assumes mutable >>> data structures - specifically, it provides (setf elt). This is not a >>> big deal per se - if you want an immutable sequence type, define (setf >>> elt) to signal an error for it. That's how Java lists work, too. >> >>> However, digging deeper you find a more substantial problem: there's >>> no generic way of extending a sequence, except by creating a new one, >>> copying the source sequence, and adding the new elements - all using >>> (setf elt). I.e. there's not a generic version of the CONS and APPEND >>> functions - what Clojure folks call "conj". This may make sense if all >>> existing sequences are lists and vectors; but it doesn't if you want >>> to implement multiple sequence types, some of which may be immutable. >> >> 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 > > (defgeneric scons (item sequence)) ;;Appends item at the head of > sequence > (defgeneric sappend (sequence&rest sequences)) ;;Appends sequences to > sequence, returning a an object of the same type as sequence > > they could be implemented by default as (untested): > > (defmethod scons (item (s sequence)) > (concatenate (type-of s) (list item) s)) > > (defmethod sappend ((s sequence)&rest sequences) > (apply #'concatenate (type-of s) s sequences)) > > while they could be specialized to behave more efficiently, for > example for lists they would call cons and append. I don't think that scons is a good function for vectors. In general, I'm quite skeptical about abstracted interfaces for different kinds of collections: Each of them has their own advantages and disadvantages, and you don't easily change from one to the other without considering performance and other implications. So what's the real use of an abstract interface, other that you _can_ abstract it? >>> 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 don't want to discourage you, but again, what's the real use of such abstractions? Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Pascal Costanza on 30 Jul 2010 14:11 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_smalltalk/03_smalltalk.html > > 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. Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Helmut Eller on 30 Jul 2010 14:53 * 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. [...] >> > 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. Helmut
From: Christophe Rhodes on 30 Jul 2010 15:36
Pascal Costanza <pc(a)p-cos.net> writes: > Did anybody look at Dylan? Well, I did, when I designed and implemented the sequence protocol for sbcl and wrote up the paper about it. Another source of inspiration was the sequence interface in Factor. Christophe |