[oleg@pobox.com: Interface view of dictionaries] scgmille@xxxxxx (28 Oct 2003 01:28 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] Bradd W. Szonye (28 Oct 2003 04:25 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] scgmille@xxxxxx (28 Oct 2003 04:54 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] Bradd W. Szonye (28 Oct 2003 05:33 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] scgmille@xxxxxx (28 Oct 2003 14:10 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] scgmille@xxxxxx (28 Oct 2003 15:11 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] Bradd W. Szonye (28 Oct 2003 18:01 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] scgmille@xxxxxx (28 Oct 2003 18:29 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] Bradd W. Szonye (28 Oct 2003 19:05 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] scgmille@xxxxxx (28 Oct 2003 19:42 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] Bradd W. Szonye (28 Oct 2003 19:59 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] Tom Lord (28 Oct 2003 19:59 UTC)
Re: [oleg@pobox.com: Interface view of dictionaries] Tom Lord (28 Oct 2003 20:02 UTC)

Re: [oleg@pobox.com: Interface view of dictionaries] Bradd W. Szonye 28 Oct 2003 04:25 UTC

This is Oleg's response, correct?

> Ray Dillinger wrote:
>> And when joe code writer is looking at the API going, I want
>> something that applies a function to each mapping, "foreach" is going
>> to attract his attention.

If I understand correctly, Oleg wrote:
> Allow me to paraphrase your argument: "When Joe the coder looks at
> Scheme for a non-local-exit, he would probably look for something like
> GOTO, BREAK, or RETURN. But he finds none of that. He might come
> across call-with-current-continuation (because it's such a long name),
> but it probably will not attract his attention as GOTO would have." Is
> it a reasonable paraphrase?

Sure.

> Should R5RS authors have added BREAK, RETURN and GOTO to Scheme, as CL
> has done?

Whoah, hold on? When did Bear suggest that Scott should do this? He was
suggesting a name that he felt was more intuitive, not proposing a bunch
of aliases.

> The analogy between fold and call/cc is actually deep.

I agree. You can do some cool stuff with fold. But what does that have
to do with a discussion of whether it's the best name for the procedure?

>> If you provide fold-left and fold-right, the first thing joe coder is
>> going to do with them is implement iterators, because iterators are
>> simpler to use.

> If that Joe finds cursors are the right tool for him, he can get them.
> Let me quote the conversion function: [snip implementation]

I'm not sure, but it looks like that cursor doesn't support
bidirectionality or random access, both of which are important for
generic programming. Now, I'm sure that you *can* write those cursors if
you really need them, although it's much easier if the implementor
provides them for you. I'm not sure how to do that in a way that avoids
the disadvantages of cursors, but I haven't given it much thought yet.

> I don't think the argument about efficiency of implementing
> *-fetchfirst via a collection-fold-left is productive. If a particular
> collection permits an efficient implementation of *-fetchfirst, and if
> a programmer writes an application that truly needs an efficient
> *-fetchfirst, then the programmer can go ahead an write that efficient
> *-fetchfirst for his particular collection.

Thing is, there are a few functions like this which have superior
performance characteristics for *many* collections, if you limit the
interface somewhat. As you say, there are trade-offs between performance
and generality. However, there's a significant class of collections --
any tree-based dictionary, for example -- where you can improve from
O(N) performance to O(lg N + K) performance for sequential access to
keys. That's both efficient and generic.

> If I read the intent of SRFI-44 correctly, its goal is not to provide
> all things for all people. Rather, the goal is to define the framework
> and to describe a _minimal_ set of core functions plus a _limited_ set
> of very common extensions.

And Bear is trying to establish that some of these functions are not
only common but important extensions. For most dictionary-type
collections, primitives aren't sufficient. There's a convenience
argument *and* a performance argument for extending the set.

> The intent is not to make it unnecessary to add more API in future
> SRFIs. Rather, the intent is to make it unnecessary to remove SRFI-44
> features in future SRFIs.

Why would you need to remove a function that is more convenient and more
efficient?

Also, speaking of things which might need to be removed, I'm concerned
about the object-oriented nature of the containers. Polymorphism is
good, but I suspect that the SRFI's design may be tied too closely to
the specific object system used in the reference implementation. For
example, the hierarchy looks like it's based on a traditional "objects
as references" class-based system, when an "objects as values"
prototype-based system may fit better into Scheme. (Especially given the
way such a system incorporates primitive data structures according to
content rather than type).

> People who want rich APIs have stated their preference. Probably I
> should be allowed to state mine: I do not like rich APIs, both as a
> user and an implementor.

That's fine. Personally, I don't like APIs which are quietly
inconsistent with the core language they're supposed to extend.

> About experience using SRFI-44. I can see how to change my
> implementation of treaps to fit SRFI-44.

That's good. Present the implementations as support for the design. The
author hasn't done so, however -- indeed, he keeps making excuses for
why he shouldn't have to. That reduces my confidence in the proposal.
Furthermore, the SRFI Process Document recommends against exactly that
kind of thing.

I think SRFI-44 could become a good SRFI. However, first it should
actually become an implementation of everything it proposes.

> About fold-right. I'd rather wish to see fold-right gone ....
> Reversible collections is another thing that I'm uneasy about. A
> concept of views has received quite a lot of attention recently.

I was thinking the same thing -- container views and enumeration
adapters would be a much better way to provide some of this stuff. I
think I mentioned it earlier in the discussion, but I dropped it because
of the attitude that it's best not to change the SRFI at this point.

Now I've changed my mind. That was when I felt that the SRFI was
basically ready to go, and I didn't want to hold it up for an
experimental change. Now, my opinion has changed. There's enough missing
and enough major issues that I think the SRFI needs to go back for major
work anyway.

> If we take the advantage of an OO system, reverse can be a wrapper
> that creates a different (sub)type ....

Yes, that's what I was thinking.

> I'm uneasy to submit this approach for consideration into SRFI-44.  I
> have not used it. I don't know how well it works.

That's why I didn't pursue it very far either. I do know that C++ has
made good use of container and iterator adapters, though -- there is
prior art for that kind of thing.

> I'd prefer the reverse view approach, if it is feasible at all,
> explained in a separate SRFI, after we have implemented and used it.

Personally, I don't feel that there's enough implementation or use of
*this* SRFI.

> Bradd W. Szonye wrote:
>> And, most importantly, can you show how to implement a
>> multiple-collection fold without cursors?
>>
>>     (nfold f seed c1 c2 c3 ...)

> First of all, who said that we should ban cursors completely?

Have you read the author's replies to our review comments? He dismisses
them immediately, with a handwave in the general direction of your
earlier article.

> When traversing multiple collections, cursors are actually useful and
> should be used, in my opinion.

OK, thanks. I've been wondering about that.

> In contrast, folds over multiple collections don't seem to be useful.
> For one thing, a fold over two collections traverses the collections
> in a "lock-step". However, we often need to enumerate each collection
> at its own pace (especially when computing a join).

You can do that with enumeration adapters. I've been working with a
prototype. An enumeration adapter can modify or filter collection values
before they get to the main fold. It's nice.

> Furthermore, the great benefit of an enumerator is that it is privy to
> collection's internals and therefore can do traversal efficiently.
> It's hard to make an enumerator that is privy to details of two
> different collections.

You don't need to. Each collection can provide the values with a "raw
enumerator," a coroutine designed to traverse the collection efficiently
(and without any special coding! just a straightforward traversal that
supplies every value with YIELD). The main FOLD function creates the
coroutines, grabs a value from each, and calls the folding-function.
I've already got this implemented. It was almost trivial, once I
understood how coroutines work.

> Given the calls for vote, I vote for finalizing. I see the benefit of
> a stable API, which I can look up to when writing new collections or
> updating the old ones.

Yes, a stable API would be good. My objection is that the SRFI is not a
stable API. Parts of it are unimplemented, and major sections have
changed recently. And what's there doesn't take advantage of prior art
like SRFI-1 and SRFI-13 very well; it reinvents the wheel too much IMO.
Some elements it did take from SRFI (like linear update functions) are a
bit controversial -- see the beginner's discussion on c.l.s.

So while I agree that there is value in a stable API, I don't think
there's any value in rushing an immature API to finalization just so
that we can call it "stable." It'd be much better to propose a concrete
collection or three, get some experience with their use, and it they're
successful, factor out the interface and publish that as a SRFI.

Actually, if they're successful, there's less need to publish the
interface separately. Future developers will imitate it like they
already imitate SRFI-1. That's a much more desirable outcome: We get
useful collection types *and* a de facto standard interface that way.

By rushing an unused and partially-implemented interface, you get less
benefit and more risk. And I still don't feel that it meets the
requirements for a SRFI.

> Are you going to LL3?

No, sorry. I only just heard about it, and I don't have the budget for
it anyway.

> I'll have a poster presentation at LL3 -- about enumerators, cursors.
> I also touch upon generators and iteration inversion in languages
> without first-class continuations (such as Haskell).

Sounds interesting! Wish I could be there.
--
Bradd W. Szonye
http://www.szonye.com/bradd