[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Functional datatypes in Guile

From: Philip McGrath
Subject: Re: Functional datatypes in Guile
Date: Tue, 28 Feb 2023 11:54:48 -0500
User-agent: Cyrus-JMAP/3.9.0-alpha0-183-gbf7d00f500-fm-20230220.001-gbf7d00f5


On Tue, Feb 28, 2023, at 11:04 AM, Thompson, David wrote:
> Hi pukkamustard,
> On Tue, Feb 28, 2023 at 3:34 AM pukkamustard <> wrote:
>> I've been using SRFI-146
>> ( for functional
>> mappings. There's a Guile port:
>> (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

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. 

There's Racket documentation for stencil vectors at 
<> 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!


reply via email to

[Prev in Thread] Current Thread [Next in Thread]