(Previous discussion continued)
Re: Too much of a good thing? Taylor Campbell 17 Apr 2003 01:57 UTC

Re: Too much of a good thing? Taylor Campbell 17 Apr 2003 01:57 UTC

On Tuesday, April 15, 2003, at 01:35 AM, Sergei Egorov wrote:
> I'd rather cut it to one third, but then Olin will come out of
> his lair and add the rest and then some :)


> The question is not whether LIST->VECTOR and VECTOR->LIST are
> actually used in the implementation, but whether vector-specific
> algorithms
> you propose are better than just list operations followed by a
> conversion
> or the same operations on lists with no conversion at all. Did you
> turn any
> SRFI-1 algorithms into something more effective (from linear- to
> constant-time,
> from quadratic to linear etc.)?

Oh, I see what you mean.  (I missed the 'the performance is the same
as' bit)

In that case, I'm not really sure...it's been a while since I wrote the
implementation, and my memory isn't that great.

> For example, both vector search and list search are linear by number of
> elements.
> This means that there is no big insentive to use vectors if what you
> want is
> linear search. On the other hand, you can sort vectors and use binary
> search: this is where vectors are much more effective. Thus, I would
> expect vector SRFI to include BINARY-SEARCH and SORT! operations
> (real benefits), but can easily do without linear search (writing one
> more
> DO loop is no big deal).

I deliberately avoided writing anything involving sorting vectors,
since SRFI 32
will provide that.  However, I may later include a VECTOR-BINARY-SEARCH
-- it
merely didn't occur to me to do so previously.

> Can you give me any pointers to drafts or notes on his project?


I'm in the process of writing the reference implementation.

> Turns N-ary procedure into M-ary (M < K) by "fixing" or "binding"
> values of some arguments.

Hmm.  Could you show me a definition of it, or an example of using it?

> I wrote a draft myself long ago, but had no time to finish it. May be
> this
> discussion will move it up on my priority list...

I'd love to see it.  Where can I find a copy?

> I guess it is fine too.
> By the way, you forgot to mention VECTOR-COPY!'s behavior in case of
> intra-vector copy (target and vec are the same). Does it copy to the
> left,
> to the right, or does it chose the "correct" direction automatically?

If they are the same in terms of EQ?, or EQUAL? ?  I assume the former.

> True, but this somehow ligitimizes restrictive implementations.
> I just consider them broken :)

Unfortunately, some of the major ones, like CHICKEN, have this sort of
restriction.  But if you insist upon having VECTOR-APPEND instead of
VECTOR-CONCATENATE[*] (please, someone: think up a better name than
VECTOR-CONCATENATE*), then I'll agree.

> Which everybody can easily define by composition (especially when
> given a suitable high-order primitive).

OK, then, show me your functional-ish SRFI thing!

>  More, if you take this road,
> nothing prevents you from making VECTOR-APPEND-REVERSE,
> VECTOR-REVERSE-CONCATENATE and dozens of others.

No, that's the C++ road, where you continue to add whatever you can
think of, even if it could never be useful in any situation whatsoëver.

Of course, at first, I shamefully admit that this was the road taken,
but I did
certainly intend to make great cuts to the thing.

> Personally, I dislike REDUCEs because while giving you certain
> performance benefits in some imaginary cases (the dreadful database
> queries!),
> they allow you to "cheat" (or make an honest mistake) by giving an
> inconsistent
> KONS/ RIDENTITY pair. Try to copy a list with REDUCE and you will
> see that it's not only a performance hack - it is a *broken*
> performance
> hack!

Very well -- no VECTOR-REDUCE[-RIGHT].

> On the second thought, NO, unfolds are not very useful (no benefits
> for vectors).


> Just compositions with VECTOR-COPY...


> Yes, with start and end; When there is only one vector argument,
> they are easy to remember.

Good, good.

> That's your only option if you don't want to reallocate the vector
> for performance reasons, but can afford the loss of some "old"
> elements. Some "history" stacks, circular buffers of fixed size etc.
> work this way.

OK, I was just wondering if you had found them useful ever.

> Start and End arguments are trouble... I'd prefer to have abstract
> operations
> that can work with "windows" over sequences as first-class objects.
> I don't care much about operations taking any number of vectors, except
> for the cases where people may expect them (MAP, FOR-EACH).

What about other cases like VECTOR-FOLD[-RIGHT], VECTOR=, et cetera?

(and that's another thing: should there be vector comparisons in this
SRFI? -- and, if so, I don't like the name VECTOR= -- I'd personally
VECTOR-EQUAL? or VECTOR=? or something.  Has anyone else an opinion on