[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)

	(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?

Here's a detailed review of the first two sections:



> Abstract

> 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
  "inter-datastructure cooperation".


* 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.  


** 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 
     "Scheme collections"


** 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.



>       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.

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:

  (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?

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.

-t