[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Fundamental design flaws
By the way, am I reading the reference implementation correctly
to conclude that:
(define x (list 1 2 3)
=> (1 2 3)
(define x (list =? '(a . b) '(c . d)))
=> ((a . b) (c . d))
So, for lists, the behavior of COLLECTION->LIST changes depending on
the types of values stored in the list?
Here's a detailed review of the first two sections:
> A Collections API which defines a common naming scheme and set of
> operations for creating, accessing, and manipulating common
> datastructures in Scheme. The API defines accessors, a common
> protocol for value access via a generic enumerator, and functions for
> inter-datastructure cooperation.
> Finally, a concrete specification of a compliant set of operators
> for the standard Scheme heterogenous datastructures (lists and
> vectors) and for the homogeneous Scheme string is provided.
* confusing wording
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.
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
* 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
** is it an extensible, abstract API for collections?
I _think_ that the intent of the SRFI is roughly this (but see below
for an alternative):
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.
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.
44 concerns me with respect to the paragraph marked [*]. It appears
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.
Similarly, and also because of those two problems, it would be a
practical impossibility for someone to write a program, portable to
all systems that provide 44, which adds new collection types.
In effect, then, 44 gives us only:
1) a large abstract interface to collections parts of which are
neither required by the srfi to be useful or to be portably
implementable on systems providing 44
2) a not-portably-extensible interface to a small set of
** or is it a non-extensible API for certain implementations of collections?
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.
> 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.
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.
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:
((%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?
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:
=? (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.