Re: Multiple-values SRFI Marc Nieper-Wißkirchen 11 May 2020 09:41 UTC

Thank you for your encouraging response!

Am Mo., 11. Mai 2020 um 11:09 Uhr schrieb Lassi Kortela <xxxxxx@lassi.io>:

> > I am not so sure about the naming; in view of SRFI 8, it could make
> > sense to use names like `receive-list`, `receive-vector`. I am open to
> > suggestions!
>
> To me, the word "receive" connotes that it's a macro (a very nice macro,
> to be sure); not sure how common this association is.

The point is that values->list (or receive-list or however we are
going to name it) has to be syntax (e.g. implemented as a macro)
because of the limitations of Schemes applicative syntax.

> "Values" is a simpler, shorter word and since the term for the concept
> is "multiple values", it's probably more obvious if the operator names
> talk about "values" as well.

That's a fair point. I have to think about it a bit more, though,
because "multiple values" are no first-class concept (unless you reify
them with multiple value boxes). A procedure named `foo->bar` should
transform objects of type `foo` into objects of type `bar`. This
reading does not work if `bar` is replaced by the word `values`.

> > Again, there may be better names, like `unpack-list` or `explode-vector`.
>
> I really like the names you chose. They are symmetrical among themselves
> and with the rest of Scheme, and use common words that are familiar to
> every Schemer.

See my remark above why I am still at odds with own suggestion. Maybe,
replacing "->" by "-" helps here. So `list-values` and
`vector-values`.

> > Racket has `set!-values`
> > (https://docs.racket-lang.org/reference/set_.html#%28form._%28%28lib._racket%2Fprivate%2Fmore-scheme..rkt%29._set%21-values%29%29),
>
> Nice. `define-values` is already in the standard so `set!-values` is a
> natural complement. In Common Lisp, MULTIPLE-VALUE-SETQ.
>
> > which can slightly be generalized to also take formals with a rest
> > argument, and which also should go into such a multiple-values SRFI.
>
> Even nicer. Would this be best done using the consing dot?

Yes. And there should be a reference to SRFI 17 for Schemes that
implement it. (NB: But we should remember that there are also reasons
for not promoting the idea of SRFI 17:
https://srfi-email.schemers.org/srfi-17/msg/2778583/)

> > However, there is no obvious generalization of `fold` and friends to
> > multiple values (which implies multiple seeds). The problem is the
> > calling convention of the procedure that is being called in each step.
> > Currently, it takes the accumulator and an arbitrary number of values
> > corresponding to the number of lists (vectors, generators, gadgets,
> > ...) being iterated or recursed over. A multiple-value version `fold*`
> > would have to apply an arbitrary number of accumulator values and an
> > arbitrary number of values corresponding to the number of lists
> > present but there is only one rest argument.
>
> IMHO the most obviously useful is (fold* step list init...) where N init
> values mean `step` takes N accumulators and returns N values to use as
> the next accumulators. At the end, `fold*` returns N values.

We should see whether this protocol can be implemented efficiently.
However, I don't think that the number of values passed in each
iteration step should be forced to be fixed. The next iteration should
receive as many values as the previous one produced. (BTW, this
requirement rules out my simplest syntax proposal.)

The `fold*` you describe cannot handle more than one list, though.

> Using multiple-value boxes, we could also do (fold* step init list...)
> where `init` is a box. `step` would then be called with M lists and N
> accumulators (in either order) and return N accumulators as values.

An interesting use case for mv boxes; I should add this to SRFI 195's rationale.

This proposal has the advantage that it can copy with more than one
list. More than with your previous suggestion, we have to take care of
the efficiency.

> Multiple-value boxes would work for an even more general fold* if we
> pass the accumulators to `step` as boxes. This may actually be less
> crazy than it sounds :)
>
> Perhaps instead of the most generic values-fold there should be a
> box-fold. In Scheme implementations with multiple-value boxes, box-fold
> could take advantage of them.

So you mean that the iteration/recursion procedure has to unbox the
seed by hand and the multiple values it returns will be auto-boxed for
the next iteration by `fold*`?

> M-v boxes a nice generalization that doesn't make the existing
> single-value boxes any more difficult for users. If they are easy to
> implement efficiently, they will hopefully be widely adopted.

I will add a system-specific implementation (for Chibi) to show how to
implement them efficiently when the system already packages multiple
values into some internal structure.

> > One solution would be to make `fold*` into syntax, say:
> >
> > (fold* (<list-formals> <seed-formals> <body>) (<seed> ...) (<list> ...)),
> >
> > which would work unless anyone would want to use `fold*` itself in any
> > higher-order context (are there any use cases for that?).

The problem I have just seen here is that <seed-formals> is fixed in
size, forcing the same number of values passed in each step (which is
a bit of an unnatural requirement).

> > Alternatively, `fold*` is an ordinary higher-order procedure receiving
> > a procedure that evaluates into another procedure first, e.g. like the
> > following or similarly:
> >
> > (fold* (lambda <list-formals> (lambda <seed-formals> body)) (lambda ()
> > (values <seed> ...)) <list> ...)
>
> Would it work to use m-v boxes instead (as an abstraction built
> specifically for the purpose)?

The syntax may be simplified. Boxing, however, adds another level of
indirection, so boxing both seeds and lists may be a bit too much.

>
> > Or we could restrict `fold*` to a single list, but this would restrict
> > its usefulness.
>
> We should probably have that one in any case.
>
> (fold* (lambda (elem acc1 acc2) ... (values new-acc1 new-acc2))
>         list init1 init2)

Indeed; this will be used often and should be simple. For hash-tables,
this is all we would need (it does not make sense to process unordered
lists in parallel).

In order to keep the dependencies of this planned SRFI below a certain
limit, I would propose that procedures like

hash-table-fold*, generator-fold*, stream-fold*, ifold*, ...

go into their respective SRFI libraries (taking the same approach as
SRFI 162, which amended the SRFI 128 library) once we have agreed on
the signature.

We also want to talk about `unfold*` and friends. For example, there
is currently no idiomatic way to create a SRFI 125 hash table from a
list of keys and a list of values (values not in the mv sense :)).
While `alist->hash-table` can be defined through `hash-table-unfold`,
this doesn't work with separate lists of keys and values because
`hash-table-unfold` is restricted to a single seed.

Marc