2018 001 Addition of monomorphic buffers

Proposal 2018-001

Addition of MONO_BUFFER signature

Author: John Reppy
Last revised: May 17, 2018
Status: proposed
Discussion: issue #24

---

This proposal is a revision of 2015-004 Addition of Buffer module, which generalizes the interface to any element type that has monomorphic vectors, arrays, and slices.

Synopsis

signature MONO_BUFFER

structure Word8Buffer : MONO_BUFFER
                          where type elem = Word8.word
                            and type vector = Word8Vector.vector
                            and type slice = Word8VectorSlice.slice
                            and type array = Word8Array.array
                            and type array_slice = Word8ArraySlice.slice
structure CharBuffer : MONO_BUFFER
                          where type elem = Char.char
                            and type vector = CharVector.vector
                            and type slice = CharVectorSlice.slice
                            and type array = CharArray.array
                            and type array_slice = CharArraySlice.slice

Interface

type buf

type elem
type vector
type slice
type array
type array_slice

val maxLen : int

val new : int -> buf

val contents : buf -> vector

val copy : {src : buf, dst : array, di : int} -> unit

val length : buf -> int

val sub : but * int -> elem

val clear : buf -> unit

val reset : buf -> unit

val reserve : buf * int -> unit

val add1 : buf * elem -> unit
val addVec : buf * vector -> unit
val addSlice : buf * slice -> unit
val addArr : buf * array -> unit
val addArrSlice : buf * array_slice -> unit

Description

• type buf

  A type of mutable buffers that allows efficient addition of elements at the end and then extraction as a monomorphic vector. It provides accumulative concatenation of strings in quasi-linear time (instead of quadratic time when vector are concatenated pairwise).

• type elem

  The type of buffer elements.

• type vector

  The type of vectors of elements.

• type slice

  The type of vector-slices of elements.

• type array

  The type of arrays of elements.

• type array_slice

  The type of array-slices of elements.

• maxLen

  is the maximum number of elements that a buffer can hold.

• new hint

  creates a new empty buffer. The argument hint is used as the initial internal storage capacity for the buffer contents. A hint of 0 causes the implementation to use an implementation-dependent default size.

  Raises Size if hint < 0 or hint > maxLen.

  An implementation should guarantee that if no more than hint elements are added to the buffer, then the internal storage should not need to be reallocated.

• contents buf

  returns the current contents of buf as a vector value.

• copy {src, dst, di}

  copies the contents of the buffer into the array dst with the buffer element at position i being copied to the position (di + i) in dst. If the contents of the buffer overflows the array, then the Subscript exception is raised and dst is not modified.

• length buf

  returns the length of the contents of buf.

• sub (buf, i)

  returns the buffer element at position i. If i < 0 or length buf <= i, then the Subscript exception is raised.

• clear buf

  emptys the buffer buf (i.e., sets the length of the contents to zero).

• reset buf

  emptys the buffer buf and resets its internal storage to the initial size.

• reserve (buf, amount)

  extends the capacity of the buffer by the specified amount. Note that the total capacity cannot exceed maxLen.

  Raises the Size exception if amount < 0.

• add1 (buf, elem)

  appends the element elem to the buffer buf.

  This function raises Subscript if adding the element causes the buffer contents to exceed maxLen elements.

• addVec (buf, vec)

  appends the vector vec to the buffer buf.

  This function raises Subscript if adding the vector causes the buffer contents to exceed maxLen elements.

• addSlice (buf, slice)

  appends the vector-slice slice to the buffer buf.

  This function raises Subscript if adding the slice causes the buffer contents to exceed maxLen elements.

• addArr (buf, arr)

  appends the contents of the array arr to the buffer buf.

  This function raises Subscript if adding the array's elements causes the buffer contents to exceed maxLen elements.

• addArrSlice (buf, slice)

  appends the contents of the array-slice slice to the buffer buf.

  This function raises Subscript if adding the slice's elements causes the buffer contents to exceed maxLen elements.

Discussion

This abstraction allows one to efficiently build up vectors of values (e.g., strings for text output or bytevectors for object serialization). While it is possible to implement this abstraction using the existing Basis Library mechanisms (e.g., see the sample implementation), implementations may be able to take advantage of internal features to maximize performace.

Impact

Adopting this proposal should not affect existing programs.

Rationale

This module is a natural candidate for inclusion in the Basis Library. Similar structures have been found to be useful in other programming languages, for instance StringBuilder in Java and the Buffer module in O'Caml.

---

History

• [2018-05-17] Added copy and sub functions.

• [2018-05-10] Revised proposal.

• [2015-08-11] Original string-buffer proposal by Ken Friis Larsen (2015-004 Addition of Buffer module).

---