Re: Functional datatypes in Guile

[Philip McGrath]

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