Memory-safe graphs without GC in ATS

[Vanessa McHale]

Hi all,

Is it possible to write memory-safe circular linked list in ATS?

Cheers,
Vanessa

[gmhwxi]

Certainly.

The following code is written is ATS1:

https://github.com/githwxi/ATS-Anairiats/blob/master/libats/ngc/SATS/slist.sats

slseg(l1, l2) is a singly-linked list segment from l1 to l2. So a circular one is just

a case where l1 = l2.

If you want a doubly-linked one, please see the following;

https://github.com/githwxi/ATS-Anairiats/blob/master/libats/ngc/SATS/dlist.sats

The caveat is that writing this kind of code often requires a lot of effort that may

not be easily justified in practice.

Another approach (which I would take) is to use reference-counted nodes; it makes

the resulting code a bit slower but can drastically simplify the implementation effort.