[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [oleg@xxxxxxxxx: Interface view of dictionaries]

This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 contain all messages, not just those from before July 7th, 2015.

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?


> 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

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