On 24 Sep 2009, at 3:50 am, Michael Lenaghan wrote: >>> One is homogeneous vectors; the other is growable vectors. >> >> We have very different ideas about "fundamental." Both of your >> candidates >> are efficiency hacks; from an expressiveness standpoint, "growable >> vector" >> is just another name for "list." > > No, they're abstraction boundaries. As abstraction boundaries they > enable optimizations. In this particular case the optimizations could > benefit a very wide range of algorithms. Perfect! > > How far do you want to go with the "efficiency hack" thing? All the > way back to lambda calculus and Peano arithmetic? Or maybe just dump > strings in favor of vectors? Good heavens--vectors? Lists are all we > need! :-)
I think there's an important point here. I feel that vectors are OK to have in Thing 1 because they have fundamentally different semantics to lists in that the big-O behaviour of operations changes. So at that level of detail, you can't implement vectors with lists (or lambdas). Now, I do see your argument for giving Scheme just a very low-level data storage abstraction and letting things be built on top of it - but that's an implementation technique, not a specification issue. Scheme reports will mandate certain fundamental data structures, so that programmers can assume they exist with the given semantics from the access procedures, in order to make code portable (including porting between programmers that can all read it). Providing a low-level (in implementation terms, not in mathematical terms) data structure still means you'd need to standardise how strings, bignums, etc work, so that people don't end up rolling their own incompatible string libraries all the time, and endless conversions between them. In which case, what counts as a fundamental minimal core becomes the smallest set of common data structures: list, vector, hashmap. I'd be quite happy for the spec to state (for exmaple) that the vector operations are defined on cons cells, which must report a length of two and return the car and cdr when dereferenced, and for car and cdr to accept vectors of any length and return the first two elements; that has a certain elegance (and would let us create annotated lists by having some of the cons cells carry extra elements), and does not actually mandate that specifications implement pairs as vectors of length two. ABS -- Alaric Snell-Pym Work: http://www.snell-systems.co.uk/ Play: http://www.snell-pym.org.uk/alaric/ Blog: http://www.snell-pym.org.uk/archives/author/alaric/ _______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
