Re: Functional datatypes in Guile

["Philip McGrath" <philip@philipmcgrath.com>]

Hi,

On Tue, Feb 28, 2023, at 11:04 AM, Thompson, David wrote:
> Hi pukkamustard,
>
> On Tue, Feb 28, 2023 at 3:34 AM pukkamustard <pukkamustard@posteo.net> wrote:
>>
>>
>> I've been using SRFI-146
>> (https://srfi.schemers.org/srfi-146/srfi-146.html) for functional
>> mappings. There's a Guile port:
>> https://inqlab.net/git/guile-srfi-146.git/ (also in Guix -
>> guile-srfi-146).
>
> Your Guile port of (srfi srfi-146 hash) looks really nice!  A
> functional hash is the most important data structure for our needs at
> Spritely. Do you know if it's thread-safe (unlike vhashes)?

Another issue with vhashes is that vhash-cons works like cons with an alist: if the vhash already had an entry for the given key, the returned vhash will retain a reference to both the new value and the old value, potentially preventing the old value from being garbage-collected.

>  Andy's
> fash implementation uses atomic boxes, for example.
>

I have a work-in-progress port of the three immutable hash-table implementations from Racket CS. The two portable backends, Patricia tries and vector-based hash array mapped tries, offer a time-space tradeoff. There's commentary in  https://github.com/racket/racket/blob/master/racket/src/cs/rumble/intmap.ss

The backend actually used now by Racket CS is a variant of the HAMT implementation backed by a new primitive type, "stencil vectors", a kind of sparse array. They need a little cooperation from the runtime system, but they're designed to distill the essence of what functional data structure implementations need from the runtime and GC into a minimal primitive type. There's a paper with details and more benchmarks: it reports that Racket's stencil-vector HAMTs "perform in the same neighborhood as" Clojure's PersistentHashMap and Java's CHAMP. <https://www-old.cs.utah.edu/plt/publications/dls21-tzf.pdf>

There's Racket documentation for stencil vectors at <https://docs.racket-lang.org/reference/stencil_vectors.html> or the Guix package "racket", and the corresponding Chez Scheme documentation is in the Guix package "chez-scheme-for-racket:doc".

Even the non–stencil-vector backends should be serviceable, though!

-Philip