Recent

Author Topic: Immutable types  (Read 227 times)

circular

  • Hero Member
  • *****
  • Posts: 2954
    • Personal webpage
Immutable types
« on: August 19, 2019, 02:59:14 pm »
I am not sure this subject has already been discussed, but I am wondering about immutable types in FreePascal. Basically the idea is that except locally, variables are constant. For a list, it means that a function that change an item in fact would return a copy. To avoid using much memory, a tree structure is used, and only the branches that change are reallocated to make the copy, and reference counters are used to indicate that a branch is used in multiple trees.

I found this hashmap there:
https://github.com/benibela/hamt

That looks promising. Though I am looking for something simple like a list. Also it seems to me that allocating takes time, and that it would be more efficient to have pre-allocating memory and to use "sectors" for each leaf or branch. For example I was thinking of something like blocks of either 32 pointers or otherwise raw data of the corresponding size (32x8 = 256 bytes on a 64 bit processor). So for example a list of 200 kilobytes could be stored in 200x1024/256 = 800 blocks of raw data.

Of course ideally, the tree depth would be limited. There are more technical questions like how to store the number of elements, what if an element is bigger than the block size, etc. Also is there a way to have reference counting like strings, without having to call some function when a variable gets out of scope? It can be done with interface type but that would be an class instance, and I am trying to avoid allocating on the heap. I would rather have a record with some magic.

I find this topic interesting because it could help solve some complex errors that we can get when unexpected changes happen to an object. And of course avoiding to duplicate data when passing it to a function or an object or to have to handle ownership to know who is supposed to free the memory.
Conscience is the debugger of the mind

jamie

  • Hero Member
  • *****
  • Posts: 1899
Re: Immutable types
« Reply #1 on: August 24, 2019, 08:35:17 pm »
Sounds like a lot of over head..

managed strings in Fpc and Delphi are much that way, if you make multiple copies of a string they simply make references to the original string. If you make a change to one of the referenced strings then it decrements the reference count to the original string and now makes the remote string an entity of its own..

 As for your talk about variables being copied I think smart coding can work just as well, if not better.

 Sounds like you must be referring to languages like Rust and so on.