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 11:10 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. 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. What do you think? Cheers, Alessio [1] http://www.doc.gold.ac.uk/~mas01cr/papers/ilc2007/sequences-20070301.pdf
From: Pascal Costanza on 30 Jul 2010 11:27 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. > 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. 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: Norbert_Paul on 30 Jul 2010 12:20 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. > > 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. > > What do you think? 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. Some expressed interest in such a framework, so maybe it would be worthwhile to start writing one. Currently I restrict myself to what Lisp offers to make my program run first and optimize later. That is not so bad because with that restriction I can concentrate better on my actual proplems. The Java Collections API is a bit seductive :) . Norbert
From: Pascal Costanza on 30 Jul 2010 12:41 On 30/07/2010 18:20, Norbert_Paul wrote: > 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. >> >> 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. >> >> What do you think? > > 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. > > Some expressed interest in such a framework, so maybe it would be > worthwhile > to start writing one. > > Currently I restrict myself to what Lisp offers to make my program run > first and optimize later. That is not so bad because with that restriction > I can concentrate better on my actual proplems. The Java Collections API is > a bit seductive :) . The Java Collections API is just bad. It's better to look at something that is not designed for a toy language. :-P Did anybody look at Dylan? 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: Alessio Stalla on 30 Jul 2010 13:43
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. > > 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. Alessio |