Abstractions
in [Lisp]
|
From: RG on 3 Aug 2010 14:21 In article <9mpwrs7kipq.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) wrote: > > It all boils down to some common sense. Just like we use + rather than > > fixnum+, bignum+, float+, double+, it's often convenient to use ELT > > rather than AREF or NTH. > > 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. Huh?!? This seems to me to be the *only* reason to use generic arithmetic. What else is it good for? rg
From: Pascal J. Bourguignon on 3 Aug 2010 15:48 Alessio Stalla <alessiostalla(a)gmail.com> writes: > 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). Then, since pushing on a simple vector would imply copying it, while pushing on an adjustable vector would not, you would have to wrap it in your own high level data structure, therefore what you want to do is not possible. QED. > 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). This is my point, that CL data types are too low level. You cannot have a homogeneous API over them or in conjunction with other higher level data structure. -- __Pascal Bourguignon__ http://www.informatimago.com/
From: George Neuner on 3 Aug 2010 17:33 On Tue, 03 Aug 2010 16:42:59 +0200, bjorn(a)runa.se (Bj�rn Lindberg) wrote: >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. Interface abstraction frequently hides dynamic changes. It's not at all uncommon, for example, for collections to change data structures depending on the number of elements involved. Similarly, functions may need to choose different algorithms and data structures depending on how much or what kind of data they need to operate on. I'm not talking about compiler overloading here but rather functions that use intelligent dispatch to optimize some aspect of their performance. George
From: D Herring on 3 Aug 2010 19:54 On 08/03/2010 03:25 AM, Bj�rn Lindberg wrote: > RG<rNOSPAMon(a)flownet.com> writes: > >> But that is exactly what puzzles me. You see the value in latent >> typing, but not in abstraction. And yet the value in those two things >> is exactly the same, namely, the ability to write code in a way that >> lets you defer decisions. So I don't understand how you can value one >> and not the other. > > If I may interject, I do see value in abstraction, but it will usually > take a different form than what you propose. > > Let's say that we in our program have objects of the kind foo, indexed > by bar, stored in collections bork. You do not want to prematurely > select the implementation of bork to be either hash tables, alists or > something else. You now write accessors like ADD-FOO, FIND-FOO, and the > like, essentially creating an ADT specific to the program. This ADT > encapsulates whatever implementation is chosen for bork, making change > later easy. The advantages of this approach are plenty: The accessors > can be written to fit the semantics of foo, bar and bork, rather than > shoe-horning the behaviour of those into some generic collections > framework. It makes the code much more descriptive of what it is doing > than if it is sprinkled with "generic" REF calls, which from a > documentation perspective is even worse than having it filled with calls > to GETHASH. [slightly exaggerating to make a point] The disadvantages are also plenty: Without access to the underlying, standard API, I can't use the set of tools already developed for iterating over lists, etc. I am at your mercy to implement the whole API, I have to learn a new API, and your data structures are opaque to MAP, LOOP, etc. I really wish CL had the tools to use a generic REF for indexing into arrays, retrieving hashtable values, etc. and then using a few DECLAREs to tell the compiler how to optimize these numerous REFs into efficient code (possibly even changing the underlying choice of data structure). This ties into a bigger framework I'd like to have... - Daniel
From: =?iso-8859-1?Q?Bj=F6rn?= Lindberg on 4 Aug 2010 03:36
RG <rNOSPAMon(a)flownet.com> writes: > In article <9mpwrs7kipq.fsf(a)runa.se>, bjorn(a)runa.se (Bj�rn Lindberg) > wrote: > >> > It all boils down to some common sense. Just like we use + rather than >> > fixnum+, bignum+, float+, double+, it's often convenient to use ELT >> > rather than AREF or NTH. >> >> 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. > > Huh?!? This seems to me to be the *only* reason to use generic > arithmetic. What else is it good for? To write code that can accept differing types of numbers at run-time. As you know, + takes a variable number of arguments, which among themselves can have different types. Alessio would need an awfully high number of operators with his approach (admittedly a straw man). Bj�rn Lindberg |