Re: Functional datatypes in Guile

[Ludovic Courtès]

Hello!

pukkamustard  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

regarding copyright.

Thanks,
Ludo’.

Re: Functional datatypes in Guile

[pukkamustard]

Ludovic Courtès  writes:

> Hello,
>
> pukkamustard  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

[Dr. Arne Babenhauserheide]

Ludovic Courtès  writes:

> pukkamustard  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


signature.asc
Description: PGP signature

Re: Functional datatypes in Guile

[Ludovic Courtès]

Hello,

pukkamustard  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

[pukkamustard]

Linus Björnstam  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

[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]

Hi Dave,

"Thompson, David"  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

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


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!

-Philip

Re: Functional datatypes in Guile

[Thompson, David]

Hi pukkamustard,

On Tue, Feb 28, 2023 at 3:34 AM pukkamustard  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

[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  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

[Maxime Devos]

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


OpenPGP_0x49E3EE22191725EE.asc
Description: OpenPGP public key


OpenPGP_signature
Description: OpenPGP digital signature