r/ProgrammingLanguages • u/PhosXD • 10d ago
Discussion No GC, no ref-counting, no pointers, does it work?
I recently just dropped raw-pointers in my interpreted language in favor of a path-based reference type which always gives `none` if the path ever becomes invalid, unlike a pointer which would cause unexpected issues or crash the program.
Now my question is... am I missing out on anything by eventually removing the pointer type entirely? In a sand-boxed language like Ity where everything is tightly controlled & you cant really access the underlying memory of anything, does it make sense to keep pointers to values? Doesn't a path do everything you need it to? You can access storage cells just the same but it's just safer, or am I mistaken.
The idea here is to make a truly 100% memory safe design, so that you couldn't corrupt or mess with the memory even if you wanted to, but you also get to pass around references to values (which is rather required for a language that has a strict copy-everything rule).
Let me know how you would go about designing a system that can pass around references while maintaining an unbreakable wall between the program & it's memory. The way I handle it is very simple, you can only reference values that are stored as a variable somewhere or is a variable nested somewhere inside some container. This means things like temporary values cannot be referenced as they have no storage cell, which I believe is one difference between path-refs & pointers.
Another big part of my design is that everything is copied, everywhere. Passing an argument to a function copies the value, setting a variable to another one also copies the value, no matter the type. You must explicitly use a "ref" type if you want to avoid unnecessary copies. But acknowledging this, I made refs very convenient to work with. By this I mean assignment operators, arithmetic, & method calls all act on the referenced value, not the actual ref itself, making it seamless to use effectively. Of course you can still inspect properties of the ref using it's own type methods.
So yeah, that's how I went about the design of a memory safe language with simple & intuitive references. I am curious to see how your guys' *interpreted* languages went about solving references & memory safety, so do let me know of interesting alternative methods!
2
u/ghkbrew 10d ago
Can you describe your planned implementation better? I'm not sure I understand the exact behavior you're going for.
Is your reference object a pointer plus a list of offsets that represent each item in the path? Or do you not include the base pointer and have to specify a base every time you use your "path reference"?
1
u/PhosXD 10d ago
A pointer is just a memory address, the idea with a path-ref is the same, it's just an address to a location. The thing is, pointers tend to fail when the address gets taken up by something else, like an `int` when you expected there to be `char` or something.
A path-ref checks each node along a path of locations & if it fails to find something at the end of the path, we safely return a `none` value. A big difference between pointers & path-refs though is that the refs don't point to a memory address, but rather a storage cell, whether that be a variable which has a name in the scope, or a variable which has an index in a nested array/map.
You can visualize a path-ref by imagining chained access of an array like so: "some_array[0][0][123]", we are just following the path. & if we fail at any step of the way, safely return.
1
u/gwillen 10d ago
This is memory-safe, but doesn't really avoid the "address taken up by something else" problem at all, right? Or at least, it depends on whether the type of
foo[0]can ever change (or the type offoo.bar.) If that's not possible, you have memory safety / type safety, but you still have to worry about semantic confusion (did you get the object you were looking for, or did someone replace it with a different object? It's not fundamentally different from someone deallocating the object you had a pointer to, and then someone else allocating something there.)1
u/PhosXD 10d ago
You are right, it doesn't solve that problem.. But in reality, why are you overwriting something that you know needs to be a specific value at a later time? I think the biggest issue is solved, the program doesn't break when the container is deleted. Overwriting the contents of the container is the fault of the developer... Well then again, you could say the same thing about pointers & C, if it breaks or doesn't work as expected well then YOU are doing something wrong & it's not the fault of the language design, right?
But then how would you go about covering this? Some kind of unique identification for every variable, & a global lookup table so we can safely find it during dereference? For what gain though?
1
u/xpusostomos 9d ago
If everything is a path, essentially everything is a global variable and there is no algorithm that can auto free it when it's not needed. What is the point? It's interpreted, so it's not like you've got some performance aim. Why not do what everybody does and garbage collect it?
1
u/PhosXD 9d ago
It frees when you exit the scope. The same way any other language frees their variables. No need for garbage collection if everything is in scopes.
1
u/xpusostomos 8d ago
So you've reinvented the stack then?
1
u/PhosXD 8d ago
How do you mean?
1
u/xpusostomos 5d ago
You seem to be saying things are allocated in scope and deallocated when leaving scope, which describes the same thing as the stack.
14
u/funbike 10d ago
copy-on-write. You pass around references, but when you attempt to modify a structure, you get back a modified clone. This is usually more efficient and safer than pass-by-value everywhere.
Look into pure monads.
2
6
u/spisplatta 10d ago edited 10d ago
This sounds basically like ref-counting restricted to one strong reference, what you call the container, and you make all the other references weak.
Edit: Seeing it from this PoV raised a question for me about concurrent modification. Normally with a strong/weak ref system, whenever you actually want to use a weak ref you usually do something like a get call that either returns a strong reference if the object is still alive or null if it's not. Using a temporary strong reference makes sure it can't get deleted while you are processing it. This won't really be a problem in a single threaded setting I guess. But how will you handle multithreading? Taking out some kind of lock against the container?
5
u/sadesaapuu 10d ago
Yeah, I feel that removing usual features is a good way to get a minimalistic language that might be at least more memory safe than those "normal" languages.
Something along the lines of, forbidding references/pointers in structs should go a long way, with RAII memory management. And then on the practical side, using IDs instead of references.
1
u/Dan13l_N 10d ago edited 9d ago
Your language will get a bit slower, that's all.
A lot of programming language design comes from performance considerations.
1
u/PhosXD 10d ago
What will make it slower exactly?
1
u/Dan13l_N 9d ago
Every dereferencing will have to go, I guess, over a series of hashed lookup tables. If you have a raw address -- the CPU has an instruction that uses it directly, reads, writes, even some math.
1
u/marshaharsha 10d ago
If I understand you literally and you arenât going to optimize any checks away, then code like the following is going to have a high ratio of checks to actual useful computation:
  for idx in 1..1000*1000 {
   thedict[âfooâ][idx] := thearray[idx] + thestruct.thefield[idx]
  }
Before you can add the two numbers and write the result to a slot, you will have to check thedict, thedict at âfoo,â that array at idx, thearray, thearray at idx, thestruct, thestruct at thefield, and that array at idx. Do that a million times and kiss performance good-bye.Â
1
u/PhosXD 10d ago
Those checks are very very cheap, & realistically you aren't going to reference more than 4 levels deep
1
u/marshaharsha 10d ago
Itâs your language, so you get to decide how much overhead is acceptable. Your users also get to decide. For many uses, it would not be acceptable to pay eight branches just to read two numbers (usually in cache), add them, and write them to a slot that is usually in cache. On the other hand, Python became very popular while doing lots of checks inside loops. On yet another hand, some of the popular Python libraries depend on C code to get acceptable performance.Â
2
u/jojohohanon 10d ago
Siskindâs stalin compiler (for a very large subset of r4rs) used region allocation.
ITA software did flight low fare search for many airlines and orbitz. For a sizable part of that time, it did not gc. It just bumped the alloc pointer through the query computation and then reset the heap pointer at end of query.
Both of these had very specific runtime behaviors, tho.
1
u/its-been-a-decade 10d ago
My experience is not in interpreted languages, but in grad school I worked on a language called Resolve that did away with pointers, aliasing, and references entirely (everything was just its value). It was designed initially to make reasoning (and automated formal verification) tractable but the limitations they ran into were at least in part handled by something they called âUltimately Void Referencing Templateâ (âTemplateâ in this language, is essentially an âInterfaceâ in other OO langs). I canât at the moment find the publication(s) about it (if indeed there were any) or any references to it, no pun intended. If memory serves it is essentially a formally specified DAG component with limitations on what can go where and how. If I come across it again Iâll drop back here to update.
1
u/binaryfireball 10d ago
References/pointers are just something essential imo at least in some form or fashion. O always found python's binding kinda interesting
1
u/Difficult-Value-3145 10d ago
One path-refs here is just an abstraction for pointers what if you put another var at the end of that path or null out what's at the end same boat. I think you just need a default return and flexible types you can abstract away pointers by making a pointer to garbage return garbage idk .
1
1
u/ern0plus4 6d ago
Just an idea, probably not the best one:
instead of not using pointers, just hide it: provide lot of containers, so the language user has not to write their own
copy everything
1
u/gio_vs 5d ago
Acho que funciona sim e vocĂȘ nĂŁo perde muita coisa. Linguagens como Swift, Hylo e atĂ© Rust jĂĄ usam ideias parecidas. O maior problema seria o desempenho, jĂĄ que resolver um caminho pode ser mais custoso do que acessar um ponteiro direto. TambĂ©m teria cuidado com a identidade dos elementos: se vocĂȘ usa lista[2] e alguĂ©m remove um item anterior, a referĂȘncia pode acabar apontando para outro valor sem retornar none.
43
u/initial-algebra 10d ago
If you take a "reference" to an object inside a list, and then insert or remove an entry before that object in the list...suddenly, your "reference" is pointing to a completely different object.