This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 contain all messages, not just those from before July 7th, 2015.
On Wed, Oct 29, 2003 at 09:58:39AM -0800, Tom Lord wrote: > > By the way, am I reading the reference implementation correctly > to conclude that: > > (define x (list 1 2 3) > > (collection->list x) > => (1 2 3) > > but > > (define x (list =? '(a . b) '(c . d))) > > (collection->list x) > => ((a . b) (c . d)) > > So, for lists, the behavior of COLLECTION->LIST changes depending on > the types of values stored in the list? No. The first list contains the values 1, 2, and 3, and the second contains the values (a . b) and (c . d). I don't see what the problem is. Scott > Mutation isn't mentioned there and "inter-datastructure cooperation" > doesn't mean much. > > Saying that "the API defines [...] a common protocol for value access > via a generic enumerator" is misleading: the proposal in fact defines > procedures (not protocols) which perform enumeration of the values in > any collection. I'm not sure how you use the word "protocol" but in > this context, I would take it to mean that the proposal defines a way > to extend the enumeration generics for new collection types -- > something that the srfi does _not_ define. The protocol I'm refering to is the specification of the enumerating procedures, and the expected behavior of fold functions, as well as the various behaviors of collection-fold-*. I'll think of ways to clear this up. Feel free to make suggestions. > Although I see later that some operations in the interface accept > multiple collection arguments of possibly different collection types, > when reading the abstract I have no idea what is meant by > "inter-datastructure cooperation". Primarily the various add and remove operators that take collections. > * unclear "need for" this SRFI and incomplete results > > Most importantly, the abstract doesn't mention the need for the > proposal: it doesn't say what problem it aims to solve. This concerns > me because while there are some common needs that I would hope a > collections srfi will address, the abstract doesn't suggest that this > srfi will. Can you elucidate those needs? > > We recognize that there are several abstract data types, all of > which are kinds of collections (unordered sets of value, sets of > values, dictionaries, and so forth). Each of these varieties of > collection permits many possible implementations, often > differentiated by distinct performance trade-offs. > > It is desirable to be able to write programs which manipulate > collections using only abstract interfaces: so that the programs can > operate on many different specific implementations of the > collections (even during a single run). > > Given such an abstract interface, it is then necessary to provide a > standard mechanism by which programs may provide new implementations [*] > of the abstract interfaces to collections. Right, it doesn't try to solve this becauses that requires standardizing on a dispatch mechanism. That is a whole different SRFI that would be far more controversial than this one. Even providing function calls to register new collections, say (which has been discussed), will invariably either constrain the dispatch type, or limit efficiency, or both. > > This SRFI defines abstract interfaces to a small variety of common > collection types and an interface for making new implementations > of that inteface available. > > Additionally, for each abstract collection type it defines, this > SRFI defines constructors for specific implementations which all [**] > implementations are required to provide. No, it definitely doesn't try to solve the last bit because thats shaky ground. I'm assuming you mean things like (make-dictionary) which returns an unspecified dictionary type. The problem is that there is too much variation as to what might be returned for this to be useful. Indeed, I don't recall any language surveyed having such a feature. This of course doesn't prevent a programmer from having a (define make-dictionary make-hashtable) in his initial Scheme source file. > to me that 44 does not attempt to solve that problem. > > 44 concerns me with respect to the paragraph maked [**]. It appears > to me that 44 does that job "half way". > > Because of those two problems it would be a practical impossibility > for someone to write a future srfi, defining a new collection type > implementation which extends the abstract interfaces of 44, and > provide a reference implementation which is portable to all systems > that support 44. That seems to me like quite a surprising property > for a fundamental data structures srfi to have. Not at all. New collections can be created that hook into the reference implementation of SRFI-44 (which uses Tiny-CLOS), or they can be implemented natively on Scheme systems. This is a similar problem with the homogeneous numeric vector SRFI for example, (albeit without the future extensibility issue), and the SRFI process specifically allows for this. Its much more important that the collection that is created 'just work' for the programmer than how it comes to work. > > Or, perhaps the intent of the SRFI is roughly this (loosely > following wording from the chapter "Sequences" in "Common Lisp" by > Guy L. Steele): > > The standard Scheme types list, vector, and string have very > different natures and uses, but they also have some aspects in > common. For example, each contains an ordered list of elements. > > Because of those common aspects, it is useful to provide a set of > operations which operate on data of any of those types > generically. This SRFI defines procedures which do so. > > I think it's unlikely that that's the actual intent: the srfi talks > about "dictionaries" for example. If the intent were revised so > that the above was the goal, it could then be made far smaller and > simpler, and more obviously implementable. Yes, but much less useful to future collections, which to me is 90% of the point. > > Issues > > > Several functions in this SRFI are required to take arbitrary > > collections or major collection subtypes as input. This > > requires that the function in question be able to determine > > the specific type of the collection and dispatch to an > > appropriate implementation. > > > As standard Scheme lacks the ability to automatically dispatch > > on different function behaviors based on the types of > > arguments, it is difficult to devise a portable implementation > > of this SRFI which allows arbitrary future collections. > > I don't think that that's a good description of the issue. > > Standard Scheme provides no means by which to create new types of > objects which are disjoint from those listed in section 3.2 of R5RS. > Among the disjoint types it does provide, it provides no reliably > efficient means to dispatch on the type of one of those objects. > True. > Furthermore, some "derived types" recognized by Scheme procedures and > of interest to a generic collections interface are not disjoint, > either from one and other or from the types of section 3.2 (example: > pairs, lists, and association lists). > > Together, those problems imply that it is _permanently_impossible_ to > write a standard Scheme procedure which discriminates its input based > on the type of that input if the notion of type being used for > discrimination would separate, for exaple, pairs, lists, and > association lists. No upwards compatable extension to Scheme can > change that fact. Thats not really true. You can in fact dispatch appropriately between pairs lists and association lists, assuming you check the types in an appropriate order. > Consequently, I think it is a profound mistake of this srfi to attempt > the impossible. As a particular example, the reference implementation > defines a procedure CLASS-OF whose definition begins: > > (set! class-of > (lambda (obj) > (cond > ((%instance? obj) (%instance-class obj)) > > ;; Get the right classes here -- previously, there was no <LIST> > ;; or <ALIST>. > ((null? obj) <null>) > ((alist? obj) <alist>) > ((list? obj) <list>) > ((pair? obj) <pair>) > ....))) > > The implication of this, given how ALIST? is defined, is that if I > create a sequence using the srfis LIST procedure, then update it by > storing certain elements in it at certain positions (a procedure as > the 0th element, pairs as the other elements), then my list will > change types and become and ALIST? and a DICTIONARY? Perhaps Taylor can comment on that. That would be a real issue. Its solvable in a number of ways (all of which make Scheme alists incompatible with SRFI-44 alist-dicts or what have you). > > What difference does that make? Here's an example: > > COLLECTION-FOLD-LEFT, on a LIST?, should enumerate every element of > the list. COLLECTION-FOLD-LEFT, on an ALIST?, should enumerate every > key-value pair. In the reference implementation, given a list which > contains the elements: > Collection-fold-keys-left on an alist will enumerate every key-value pair (passing key and value separately to the fold function). > =? (a . b) (c . d) > > the enumeration will produce: > > (a . b) (c . d) > > !!!! > > In short, the kind of genericity that this SRFI proposes to provide is > an incoherent notion. It simply can not work. It can't work if you're trying to actually some existing Scheme structures collections. You could, though, for example, implement alists as a list with a unique first value in order to maintain type distinctness. Scott
Attachment:
pgpHaBGEJOxMu.pgp
Description: PGP signature