Abstractions
in [Lisp]
|
From: Pascal J. Bourguignon on 3 Aug 2010 10:22 Alessio Stalla <alessiostalla(a)gmail.com> writes: > We use them because we don't care about the low-level details of how > arithmetic operations are implemented on the CPU; we only care about > summing numbers together. Similarly, at a higher level, there are > cases when we don't care whether a sequence is a list or a vector; we > just want to append an element to it, or change the value of the nth > element, and so on. > If there were no abstractions - and by that I mean no generic > operations that abstract over several data types - then all the > benefits of dynamic typing would be gone. If I have to write list-nth, > vector-nth, int+, float+, ..., type-operation for each (type, > operation) pair, I'm basically writing a statically-typed program that > is just not checked for correctness at compile-time - i.e. the worst > case possible :) I can agree with that. Nonetheless, depending on the operation and the types of collections, it may make sense or not to have a generic API. aref, nth -> elt -- ok, it's provided by CL. push, vector-push -> ? -- here you already have a problem, that vector-push doesn't work on all vectors, but only on vectors with a fill-pointer. And you'd really want vector-push-extend, and therefore adjustable vectors. Or you would have to provide a vector pushing function (that would copy the vector into a 1-bigger one to insert the new element, which would be awfully slow). So, my point is that CL data types are two low level to provide a consistent generic collection API. If you want collections with different classes of time or space complexities, including some looking like lists and some looking like vectors, you will have to implement them, using CL data types, but more sophisticated. Said otherwise, use FSet, or some similar library. -- __Pascal Bourguignon__ http://www.informatimago.com/
From: =?iso-8859-1?Q?Bj=F6rn?= Lindberg on 3 Aug 2010 10:42 Alessio Stalla <alessiostalla(a)gmail.com> writes: > On Aug 3, 2:02�pm, bj...(a)runa.se (Bj�rn Lindberg) wrote: >> No, these are two completely different topics. We do not use generic >> arithmetic operators to delay an implementation choice of which number >> type to use. > > We use them because we don't care about the low-level details of how > arithmetic operations are implemented on the CPU; we only care about > summing numbers together. Similarly, at a higher level, there are > cases when we don't care whether a sequence is a list or a vector; we > just want to append an element to it, or change the value of the nth > element, and so on. I would claim that it is comparatively rare that you don't care if something is a list or vector. In particular, this discussion is about how to factor code so that you can change the underlying implementation after the fact, i.e. we are _very_ concerned with whether it is a list or a vector. > If there were no abstractions - and by that I mean no generic > operations that abstract over several data types - then all the > benefits of dynamic typing would be gone. First of all, no one has disputed the usefulness of abstractions. In fact, if you re-read my posts you will see that I advocate application- specific abstractions in favour of generic framework abstractions. Secondly, the kind of abstraction we are discussing here, namely one to allow changing the implementation of some data type in a later version of the program, _has_ no dynamic properties. In version X of the program, a particular call site (ref ...) will mean ASSOC, in version Y GETHASH. No dynamicity involved. In contrast, your straw man the arithmetic operators are very likely to accept different number types at run-time. > If I have to write list-nth, vector-nth, int+, float+, ..., > type-operation for each (type, operation) pair, I'm basically writing > a statically-typed program that is just not checked for correctness at > compile-time - i.e. the worst case possible :) Yeah, I wouldn't do that. Bj�rn Lindberg
From: Alessio Stalla on 3 Aug 2010 10:59 On Aug 3, 4:22 pm, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > Alessio Stalla <alessiosta...(a)gmail.com> writes: > > We use them because we don't care about the low-level details of how > > arithmetic operations are implemented on the CPU; we only care about > > summing numbers together. Similarly, at a higher level, there are > > cases when we don't care whether a sequence is a list or a vector; we > > just want to append an element to it, or change the value of the nth > > element, and so on. > > If there were no abstractions - and by that I mean no generic > > operations that abstract over several data types - then all the > > benefits of dynamic typing would be gone. If I have to write list-nth, > > vector-nth, int+, float+, ..., type-operation for each (type, > > operation) pair, I'm basically writing a statically-typed program that > > is just not checked for correctness at compile-time - i.e. the worst > > case possible :) > > I can agree with that. > > Nonetheless, depending on the operation and the types of collections, > it may make sense or not to have a generic API. > > aref, nth -> elt -- ok, it's provided by CL. > > push, vector-push -> ? -- here you already have a problem, that > vector-push doesn't work on all vectors, but only on vectors with a > fill-pointer. And you'd really want vector-push-extend, and therefore > adjustable vectors. > > Or you would have to provide a vector pushing function (that would > copy the vector into a 1-bigger one to insert the new element, which > would be awfully slow). The vector pushing function could be more intelligent than that. For example, if the vector has a fill pointer, use it, otherwise create a new vector with a fill pointer, copy the original into it, and return it. And even if the function was naive it would still do fine as long as performance doesn't matter much. If it turns out it does, you have the option to change data structure (without changing the code) or to use more specialized operators (losing the advantages of abstraction in return of better performance) or to use a different algorithm. The same argument could be constructed for ELT and LENGTH too, which are O(1) on vectors but O(n) on lists. A higher-level list data type could make LENGTH be O(1) by incrementing a counter for every element pushed onto the list and decrementing it for every element popped off it. Still, ELT and LENGTH are useful even on the low-level CL sequences. > So, my point is that CL data types are two low level to provide a > consistent generic collection API. If you want collections with > different classes of time or space complexities, including some > looking like lists and some looking like vectors, you will have to > implement them, using CL data types, but more sophisticated. > > Said otherwise, use FSet, or some similar library. I believe FSet would be used much more if there were a de facto standard API for sequences that worked reasonably well with both CL sequences and FSet. One of my original points was that the sequence API proposed by Christophe Rhodes for SBCL, while great in many aspects, doesn't take into account functional data structures (nor does the CL sequence API, of course). Alessio
From: Alessio Stalla on 3 Aug 2010 11:31 On Aug 3, 4:42 pm, bj...(a)runa.se (Björn Lindberg) wrote: > Alessio Stalla <alessiosta...(a)gmail.com> writes: > > On Aug 3, 2:02 pm, bj...(a)runa.se (Björn Lindberg) wrote: > >> No, these are two completely different topics. We do not use generic > >> arithmetic operators to delay an implementation choice of which number > >> type to use. > > > We use them because we don't care about the low-level details of how > > arithmetic operations are implemented on the CPU; we only care about > > summing numbers together. Similarly, at a higher level, there are > > cases when we don't care whether a sequence is a list or a vector; we > > just want to append an element to it, or change the value of the nth > > element, and so on. > > I would claim that it is comparatively rare that you don't care if > something is a list or vector. In particular, this discussion is about > how to factor code so that you can change the underlying implementation > after the fact, i.e. we are _very_ concerned with whether it is a list > or a vector. > > > If there were no abstractions - and by that I mean no generic > > operations that abstract over several data types - then all the > > benefits of dynamic typing would be gone. > > First of all, no one has disputed the usefulness of abstractions. In > fact, if you re-read my posts you will see that I advocate application- > specific abstractions in favour of generic framework abstractions. What I want to say is that it's not application-specific vs generic abstractions. You should build application-specific abstractions on top of generic ones, except when serious considerations force you to do otherwise. > Secondly, the kind of abstraction we are discussing here, namely one to > allow changing the implementation of some data type in a later version > of the program, _has_ no dynamic properties. In version X of the > program, a particular call site (ref ...) will mean ASSOC, in version Y > GETHASH. No dynamicity involved. In contrast, your straw man the > arithmetic operators are very likely to accept different number types at > run-time. Is this kind of abstraction forbidden to have dynamic properties? Clearly not. Given (defun add-foo-to-bar (foo bar) (sequence-push foo (foos-of bar)) then I will be able to deal with bars which store foos in sequences of any type. Otherwise I would have either to constrain bars to only store foos in, say, lists, or to manually dispatch on the type of (foos-of bar) to handle at least lists and vectors. There are also possible uses of custom collection types whose reason to exist is not in the realm of data types & algorithms. For example, a CLOS persistence library might provide a persistent-sequence type and require the user to use it for storing persistent collections of objects. Alessio
From: RG on 3 Aug 2010 14:02
In article <9mpsk2vkb9o.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) wrote: > Alessio Stalla <alessiostalla(a)gmail.com> writes: > > > On Aug 3, 2:02 pm, bj...(a)runa.se (Björn Lindberg) wrote: > > >> No, these are two completely different topics. We do not use generic > >> arithmetic operators to delay an implementation choice of which number > >> type to use. > > > > We use them because we don't care about the low-level details of how > > arithmetic operations are implemented on the CPU; we only care about > > summing numbers together. Similarly, at a higher level, there are > > cases when we don't care whether a sequence is a list or a vector; we > > just want to append an element to it, or change the value of the nth > > element, and so on. > > I would claim that it is comparatively rare that you don't care if > something is a list or vector. That's true. But it's relatively common not to realize that you care until long after you've already made the choice. > Secondly, the kind of abstraction we are discussing here, namely one to > allow changing the implementation of some data type in a later version > of the program, _has_ no dynamic properties. It could. My version of dictionaries, for example, allows the underlying implementation of a dictionary (a.k.a. an abstract associative map) to be dynamically changed at run time. rg |