195: Multiple-value boxes

by Marc Nieper-Wißkirchen

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-195@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

• Received: 2020-05-04
• Draft #1 published: 2020-05-14
• Draft #2 published: 2020-08-19
• Finalized: 2020-08-28

Abstract

This SRFI extends the specification of the boxes of SRFI 111 so that they are multiple-values aware. Whereas a SRFI 111 box is limited in that it can only box a single value, multiple values can be boxed with this SRFI.

Rationale

At its core, Scheme's evaluation semantics is multiple-value based. Continuations can accept an arbitrary number of values and expressions can yield an arbitrary number of values. This is in contrast to the functional languages ML and Haskell.

Despite this fact, programming with multiple values is more cumbersome than programming with single values. This is mostly due to the fact that Scheme's application syntax does not deal directly with operands returning multiple values so that the programmer has to fall back on things like call-with-values. It is, however, also partly due to the fact that a lot of Scheme's procedures have been modelled on a language that does not have multiple values.

One example for this are the procedures exported by SRFI 111. In an ongoing attempt to make Scheme more uniform (and therefore also simpler) and so that multiple values feel less like a second-class citizen, this SRFI extends SRFI 111 so that it becomes multiple-values-aware in a natural way. The naturalness of the extension is a proof that it is the right extension.

The boxes of this SRFI can be used to reify the concept of multiple values into a first-class single value. This can be used in the implementation of SRFIs like SRFI 189.

Multiple-value-aware boxes as described in this SRFI form a natural Scheme monad as much as the monads defined in SRFI 165 and SRFI 189 do. However, it is left to a future SRFI to describe a monadic interface to boxes. (The monadic pure would be the box procedure; the monadic join would be unbox when restricted to boxes whose values consist of a single box).

In a number of use cases, the multiple-valued boxes of this SRFI may be used interchangeably with vectors or lists. In general, however, they are different things:

• The constructors (list) and (vector) do not have to return a newly allocated object each time, but the constructor (box) does.
• Vectors are optimized for random access of single elements. Boxes, on the other hand, are supposed to be implemented in a way such that setting all values at once and passing all values at once to a continuation are efficient. For example, the boxes of this SRFI are the natural candidate to implement the Justs, Lefts, and Rights of SRFI 189.
• Lists and vectors are usually viewed as sequences (of single values) whose lengths are the length of the underlying list or vector. A box, however, shall be viewed as a sequence (of multiple values) of length one much like the Justs, Lefts, and Rights of SRFI 189.
• Contrary to vectors and lists, a box shall convey the meaning of multiple value reified as a single value, whereas packing and unpacking (i.e. boxing and unboxing) from and into multiple values shall be as efficient as possible.

Example

Unlike writing explicit iterations, the use of higher-order functions like fold of SRFI is often simpler and clearer. While one can pass an arbitrary number of values from one step to the next in an iteration, the fold procedure only allows one, initially called knil in SRFI 1. The reason is that fold and the folding procedure kons are already of variable arity in the number of lists to fold over.

By reifying the concept of multiple values as a single value, a variant of fold, dubbed fold*, can be specified that allows passing an arbitrary (but fixed) number of values from one step to the next of the iteration. The following is an implementation written for clarity and not speed:

(define (fold* kons* knil* clist . clist*)
  (unbox (apply fold
                (lambda args
                  (call-with-values (lambda () (apply kons* args)) box))
                knil*
                clist
                clist*)))

Here, knil* is a box reifying the seed states and kons* is a procedure taking n + 1 parameters, one element from each list, and the fold states reified into a box, and returns the next seed states as multiple values.

Example:

(fold* (lambda (e b)
         (receive (lis n) (unbox b)
           (values (cons e lis) (+ 1 n))))
       (box '() 0) '(1 2 3 4 5))

evaluates to two values, '(5 4 3 2 1) and 5.

Specification

In a Scheme system supporting both SRFI 111 and this SRFI, the bindings that are exported by both SRFIs have to be the same.

Boxes

The following procedures implement the box type (which is disjoint from all other Scheme types) and are exported by the (srfi 111) and (srfi 195) libraries.

(box value …)

Constructor. Returns a newly allocated box initialized to the values.

(box? object)

Predicate. Returns #t if object is a box, and #f otherwise.

(unbox box)

Accessor. Returns the values currently in box.

(set-box! box value …)

Mutator. Changes box to hold values. It is an error if set-box! is called with a number of values that differs from the number of values in the box being set. (In other words, set-box! does not allocate memory.)

The behavior of boxes with the equivalence predicates eq?, eqv?, and equal? is the same as if they were implemented with records. That is, two boxes are both eq? and eqv? iff they are the product of the same call to box and not otherwise, and while they must be equal? if they are eqv?, the converse is implementation-dependent.

Introspection

The following procedures are exported by the (srfi 195) library.

(box-arity box)

Accessor. Returns the number of values in box.

(unbox-value box i)

Accessor. Returns the ith value of box. It is an error if i is not an exact integer between 0 and n - 1, when n is the number of values in box.

(set-box-value! box i obj)

Mutator. Changes the ith value of box to obj. It is an error if i is not an exact integer between 0 and n - 1, when n is the number of values in box.

Implementation

A simple, portable R7RS-implementation of (srfi 195) and a compatible (srfi 111) are given in the repository of this SRFI.

Scheme implementers are encouraged to provide fast specialized implementations of preferences of the SRFI 111 procedures.

By way of an example, the implementation in the repository of this SRFI contains specialized code for Chibi-Scheme.

Acknowledgements

This SRFI is based on SRFI 111, written by John Cowan. In the specification section, I stole its language.

Copyright

© 2020 Marc Nieper-Wißkirchen.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.