Functional datatypes in Guile

Functional datatypes in Guile

[Jessica Tallon]

Hello,

I've been thinking how it'd be nice to have available in Guile a number of 
purely functional datatypes, these being hashmaps, vectors, and sets. I've 
been wondering what folks have been using for these with the idea that we 
could bring them into guile for ease of use.

I know of Andy Wingo's fash[0] and fector[1]. What do folks like to use?

Thanks,
Jessica.

[0] https://wingolog.org/pub/fash.scm
[1] https://wingolog.org/pub/fector.scm

Re: Functional datatypes in Guile

[Maxime Devos]

[-- Attachment #1.1.1: Type: text/plain, Size: 832 bytes --]



Op 27-02-2023 om 14:17 schreef Jessica Tallon:
> Hello,
> 
> I've been thinking how it'd be nice to have available in Guile a number of
> purely functional datatypes, these being hashmaps, vectors, and sets. I've
> been wondering what folks have been using for these with the idea that we
> could bring them into guile for ease of use.
> 
> I know of Andy Wingo's fash[0] and fector[1]. What do folks like to use?

I use <https://github.com/ijp/pfds/>.  It has queues, hash maps and tree 
maps (as in, sorted by key), heaps, deques and some list data type. 
More precisely, I have used (pfds bbtrees), (pfds queues) and (pfds hamts).

Guile also has (ice-9 vlist), which has a functional interface, but its 
implementation isn't purely functional and as a consequence isn't 
thread-safe.

greetings,
Maxime.

[-- Attachment #1.1.2: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 929 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 236 bytes --]

Re: Functional datatypes in Guile

[pukkamustard]

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).

It would be nice to also have a Guile port of SRFI-113 (Sets and bags -
https://srfi.schemers.org/srfi-113/srfi-113.html) and SRFI-217 (Integer
Sets - https://srfi.schemers.org/srfi-217/srfi-217.html). For the
integer sets, I believe there is some code already lurking deep down in
Guile ((language cps intset)).

These are all things that would be very nice to have distributed
directly with Guile and I'd offer my help in upstreaming ports to Guile.

I've previously used pfds (as mentioned by Maxime), but I've encountered
some nasty issues that are keeping me from using it again
(https://github.com/ijp/pfds/issues/5).

-pukkamustard


Jessica Tallon <tsyesika@tsyesika.se> writes:

> Hello,
>
> I've been thinking how it'd be nice to have available in Guile a number of 
> purely functional datatypes, these being hashmaps, vectors, and sets. I've 
> been wondering what folks have been using for these with the idea that we 
> could bring them into guile for ease of use.
>
> I know of Andy Wingo's fash[0] and fector[1]. What do folks like to use?
>
> Thanks,
> Jessica.
>
> [0] https://wingolog.org/pub/fash.scm
> [1] https://wingolog.org/pub/fector.scm

Re: Functional datatypes in Guile

[Thompson, David]

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)?  Andy's
fash implementation uses atomic boxes, for example.

Also, what are your thoughts on read syntax?  I find myself using
alists more often than I probably should because the syntax is
pleasant.  (hashmap comparator 'foo 1 'bar 2) is... okay, but terse
syntax for the common case of a hash with literal keys would be nice.
For example, #hq((foo 1) (bar 2)) for a hash with keys compared with
eq?  Scheme is kind of odd for not having hash literal syntax.

> I've previously used pfds (as mentioned by Maxime), but I've encountered
> some nasty issues that are keeping me from using it again
> (https://github.com/ijp/pfds/issues/5).

Good to know about this issue, thanks!

- Dave

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

Re: Functional datatypes in Guile

[pukkamustard]

Hi Dave,

"Thompson, David" <dthompson2@worcester.edu> writes:

[..]

> 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)?  Andy's
> fash implementation uses atomic boxes, for example.

I know very little about thread-safety, but the implementation is purely
functional, and thus should be thread-safe. By purely functional, I mean
that no state is mutated. Calls that update mapping return a new
mapping. The old mapping remains unchanged. I imagine that if multiple
threads want to access (and modify) the same mapping they would have to
agree on the current mapping by keeping a reference to the current
mapping in an atomic or similar.

Makes me wonder, are Andy Wingo's fash/fector purely functional? Why do
they need atomic boxes? Aren't they only necessary for destructive
updates?

> Also, what are your thoughts on read syntax?  I find myself using
> alists more often than I probably should because the syntax is
> pleasant.  (hashmap comparator 'foo 1 'bar 2) is... okay, but terse
> syntax for the common case of a hash with literal keys would be nice.
> For example, #hq((foo 1) (bar 2)) for a hash with keys compared with
> eq?  Scheme is kind of odd for not having hash literal syntax.

No strong opinions on a read syntax. But I welcome anything that might
increase adoption of purely functional data structures. I think they're
cool! :)

- pukkamustard

Re: Functional datatypes in Guile

[Linus Björnstam]

On Sat, 4 Mar 2023, at 17:38, pukkamustard wrote:
> Hi Dave,
>
> Makes me wonder, are Andy Wingo's fash/fector purely functional? Why do
> they need atomic boxes? Aren't they only necessary for destructive
> updates?

This is to make sure that transient-fectors/flashes (in-place mutation with some copying going on to not break the other copies of the sector being mutated) thread safe. They should only be mutated by the current thread. 

It is a nice trade off , since you get a lot less copying if you mutate many values in the same leaf. This is especially good when building a fector meaning you can fill every tail by just using vector-set! without copying. Let's just say that it becomes a lot faster:)

/Linus 

Re: Functional datatypes in Guile

[pukkamustard]

Linus Björnstam <linus.bjornstam@veryfast.biz> writes:

> On Sat, 4 Mar 2023, at 17:38, pukkamustard wrote:
>> Hi Dave,
>>
>> Makes me wonder, are Andy Wingo's fash/fector purely functional? Why do
>> they need atomic boxes? Aren't they only necessary for destructive
>> updates?
>
> This is to make sure that transient-fectors/flashes (in-place mutation
> with some copying going on to not break the other copies of the sector
> being mutated) thread safe. They should only be mutated by the current
> thread.
>
> It is a nice trade off , since you get a lot less copying if you
> mutate many values in the same leaf. This is especially good when
> building a fector meaning you can fill every tail by just using
> vector-set! without copying. Let's just say that it becomes a lot
> faster:)

Thank you for explaining. That makes a lot of sense!

-pukkamustard

Re: Functional datatypes in Guile

[Ludovic Courtès]

Hello,

pukkamustard <pukkamustard@posteo.net> skribis:

> 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).

I’m late to the party, but I think it’d be nice to integrate this in
Guile proper, and possibly other implementations like fash/fector.

These data structures are crucial and the code is very much “write
once”, so cheap in terms of maintenance, so I’m all for getting them in
Guile.

WDYT?

Thanks,
Ludo’.

Re: Functional datatypes in Guile

[Dr. Arne Babenhauserheide]

[-- Attachment #1: Type: text/plain, Size: 1005 bytes --]


Ludovic Courtès <ludo@gnu.org> writes:

> pukkamustard <pukkamustard@posteo.net> skribis:
>
>> 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).
>
> I’m late to the party, but I think it’d be nice to integrate this in
> Guile proper, and possibly other implementations like fash/fector.
>
> These data structures are crucial and the code is very much “write
> once”, so cheap in terms of maintenance, so I’m all for getting them in
> Guile.
>
> WDYT?

I would like that very much!

Having more powerful datastructures directly usable in Guile without
installing additional packages makes it much easier to use Guile for
teaching and for quick scripting.

Also it makes it much easier to write tutorials.

Best wishes,
Arne
-- 
Unpolitisch sein
heißt politisch sein,
ohne es zu merken.
draketo.de

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 1125 bytes --]

Re: Functional datatypes in Guile

[pukkamustard]

Ludovic Courtès <ludo@gnu.org> writes:

> Hello,
>
> pukkamustard <pukkamustard@posteo.net> skribis:
>
>> 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).
>
> I’m late to the party, but I think it’d be nice to integrate this in
> Guile proper, and possibly other implementations like fash/fector.
>
> These data structures are crucial and the code is very much “write
> once”, so cheap in terms of maintenance, so I’m all for getting them in
> Guile.
>
> WDYT?

I'm all for including SRFI-146 in Guile proper!

If nobody else is up for it, I'll try and prepare some patches.

-pukkamustard

Re: Functional datatypes in Guile

[Ludovic Courtès]

Hello!

pukkamustard <pukkamustard@posteo.net> skribis:

> I'm all for including SRFI-146 in Guile proper!
>
> If nobody else is up for it, I'll try and prepare some patches.

Yay, awesome!

Please make sure to add a section to the manual, tests, and then see
<https://lists.gnu.org/archive/html/guile-devel/2022-10/msg00008.html>
regarding copyright.

Thanks,
Ludo’.

Clojure support

[Lassi Kortela]

> I've been thinking how it'd be nice to have available in Guile a number of
> purely functional datatypes, these being hashmaps, vectors, and sets.

Those are core data types of Clojure. It'd be nice if the canonical 
Scheme versions of these types have Clojure-compatible semantics. This 
will make it easy to turn Scheme implementations into partial 
implementations of Clojure. This is already being attempted in Lokke 
(https://github.com/lokke-org/lokke).

Re: Clojure support

[Linus Björnstam]

Regarding data structures, there are some additions that should be made to the standard clojure versions. There would be no reason to implement a regular leftwise-dense persistent vector when there is something like RRB-trees available, which provide no slowdown compared to the leftwise dense vectors when used as such, but can "degrade" to RRB-trees when needed as a means to support amortized O(1) concatenation, insertion, and splitting. 

If a C library is to be used, C-rrb is a very high quality implementation. I tried to implement RRB-trees in guile, but I never quite got the merge algorithm to work as it should. Scalas functional vectors are RRB-trees with some really cool additions to the tail optimization.

Andy already has a fast implementation of functional hashtables ("fash") which are of a particular high quality. They do not support element removal which should be trivial to add.  Other than that it has all the basic functionality needed to build a complex library on top. 

-- 
  Linus Björnstam

On Tue, 28 Feb 2023, at 18:03, Lassi Kortela wrote:
>> I've been thinking how it'd be nice to have available in Guile a number of
>> purely functional datatypes, these being hashmaps, vectors, and sets.
>
> Those are core data types of Clojure. It'd be nice if the canonical 
> Scheme versions of these types have Clojure-compatible semantics. This 
> will make it easy to turn Scheme implementations into partial 
> implementations of Clojure. This is already being attempted in Lokke 
> (https://github.com/lokke-org/lokke).

Re: Clojure support

[Philip McGrath]

On Sat, Mar 4, 2023, at 5:28 AM, Linus Björnstam wrote:
> Andy already has a fast implementation of functional hashtables 
> ("fash") which are of a particular high quality. They do not support 
> element removal which should be trivial to add.  Other than that it has 
> all the basic functionality needed to build a complex library on top. 

I’ve heard a few people mention “fash”, but I haven’t managed to find the code: could you give a link?

-Philip

Re: Clojure support

[Linus Björnstam]

http://wingolog.org/pub/fash.scm

-- 
  Linus Björnstam

On Sat, 4 Mar 2023, at 12:22, Philip McGrath wrote:
> On Sat, Mar 4, 2023, at 5:28 AM, Linus Björnstam wrote:
>> Andy already has a fast implementation of functional hashtables 
>> ("fash") which are of a particular high quality. They do not support 
>> element removal which should be trivial to add.  Other than that it has 
>> all the basic functionality needed to build a complex library on top. 
>
> I’ve heard a few people mention “fash”, but I haven’t managed to find 
> the code: could you give a link?
>
> -Philip

Re: Clojure support

[Rob Browning]

Lassi Kortela <lassi@lassi.io> writes:

> Those are core data types of Clojure. It'd be nice if the canonical 
> Scheme versions of these types have Clojure-compatible semantics. This 
> will make it easy to turn Scheme implementations into partial 
> implementations of Clojure. This is already being attempted in Lokke 
> (https://github.com/lokke-org/lokke).

Not sure if it helps, but lokke should include all the basics, and in
some cases, I've tried to implement things in a scheme-compatible way,
then build the clojure support on that.  For example (lokke scm vector)
provides a scheme-style lokke-vector-length/ref/append interface, and
then (lokke vector) builds on it to provide the clojure generics like
conj, nth, count, etc.

The current vectors are intended to be a fairly close translation of
clojure's persistent vectors to C:

  https://hypirion.com/musings/understanding-persistent-vector-pt-1

via

  https://codeberg.org/lokke/lokke/src/branch/main/lib/lokke-vector.c

including the tail optimization, etc.  That code's standalone, fairly
compact, and should be reasonably easy to use elsewhere (well for a C
module, anyway).

In addition, (lokke scm edn) provides a configurable edn parser that can
build purely scheme data structures if you like, and then it's used by
(lokke ns clojure edn), which implements lokke's clojure.edn namespace,
to build clojure hash-maps, hash-sets, etc.

Generally speaking, I'd be more than happy to rework and contribute
anything in lokke that ends up being interesting to guile, and I've
tried to keep everything arranged so that could happen, i.e. licensing,
etc.  Personally, I'd love to see guile provide edn support.

Regarding hash-maps and hash-sets, I initially used pfds, but after
having trouble with bugs, I switched to fash:

  https://codeberg.org/lokke/lokke/commits/branch/main/search?q=pfds

Regarding fash, unless http://wingolog.org/pub/fash.scm has changed
(haven't checked recently), there were some bugs that you'd want fixed.
There was also a brief discussion about setting up a "common" repo
somewhere that incorporated various improvements (iirc, someone else may
have some too?), but nothing has happened on that front yet that I know
of.  I might do something eventually.

For now, this version should work fine, and adds a fash-set
function:

  https://github.com/lokke-org/lokke/blob/main/mod/lokke/fash.scm
  https://codeberg.org/lokke/lokke/src/branch/main/mod/lokke/fash.scm

One thing that's missing if lokke's going to stick with fash, is a
"fash-delete" (i.e. dissoc).  Right now lokke just does something
somewhat terrible whereby "deletion" changes the key to refer to a
"tombstone" value.

Unrelated to the persistent data structures, there's also a fairly
standalone interface to libpcre2 in (lokke pcre2) and the corresponding
lokke-pcre2.c.  Lokke uses and requires pcre because I wanted it to have
a standard regex syntax/behavior across platforms.

I've also thought I might like to see that as a (presumably optional)
guile feature, though it'll make more sense if I ever finish the work
I've started to migrate guile to utf-8 (or if someone else beats me to
it) because pcre doesn't support latin-1.  Right now, that code has to
do some undesirable conversions in some cases.

Hope this helps
-- 
Rob Browning
rlb @defaultvalue.org and @debian.org
GPG as of 2011-07-10 E6A9 DA3C C9FD 1FF8 C676 D2C4 C0F0 39E9 ED1B 597A
GPG as of 2002-11-03 14DD 432F AE39 534D B592 F9A0 25C8 D377 8C7E 73A4

Re: Clojure support

[Maxime Devos]

[-- Attachment #1.1.1: Type: text/plain, Size: 1009 bytes --]



Op 14-05-2023 om 00:10 schreef Rob Browning:
> Regarding hash-maps and hash-sets, I initially used pfds, but after
> having trouble with bugs, I switched to fash:
> 
>    https://codeberg.org/lokke/lokke/commits/branch/main/search?q=pfds

Guix has included a fix tor the hamts bug:

        #:phases (modify-phases %standard-phases
                   (add-after 'unpack 'patch-sources
                     ;; Initially reported here:
                     ;; https://github.com/ijp/pfds/pull/6, and merged into
                     ;; other projects such as IronScheme (see:
                     ;; https://github.com/IronScheme/pfds/pull/1).
                     (lambda _
                       (substitute* "hamts.sls"
                         (("subtrie-vector vector")
                          "subtrie-vector trie"))))

(which has been merged upstream.)
(Or perhaps you encountered some other bug.)

Possibly your version of pfds is simply out-of-date.

Greetings,
Maxime.

[-- Attachment #1.1.2: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 929 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 236 bytes --]

Re: Clojure support

[Rob Browning]

Maxime Devos <maximedevos@telenet.be> writes:

> Guix has included a fix tor the hamts bug:
>
>         #:phases (modify-phases %standard-phases
>                    (add-after 'unpack 'patch-sources
>                      ;; Initially reported here:
>                      ;; https://github.com/ijp/pfds/pull/6, and merged into
>                      ;; other projects such as IronScheme (see:
>                      ;; https://github.com/IronScheme/pfds/pull/1).
>                      (lambda _
>                        (substitute* "hamts.sls"
>                          (("subtrie-vector vector")
>                           "subtrie-vector trie"))))
>
> (which has been merged upstream.)
> (Or perhaps you encountered some other bug.)
>
> Possibly your version of pfds is simply out-of-date.

Oh thanks, though lokke's not using pfds now, switched to fash a bit
back.

-- 
Rob Browning
rlb @defaultvalue.org and @debian.org
GPG as of 2011-07-10 E6A9 DA3C C9FD 1FF8 C676 D2C4 C0F0 39E9 ED1B 597A
GPG as of 2002-11-03 14DD 432F AE39 534D B592 F9A0 25C8 D377 8C7E 73A4