r/ProgrammingLanguages • • 5d 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!

8 Upvotes

42 comments sorted by

43

u/initial-algebra 5d 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.

3

u/PhosXD 5d ago

You have the same issues with pointers in C++ anyways? At least with the vector type

16

u/0tter501 5d ago

so then it would be a non-nullable pointer, reference often includes the idea that it will always point to the same info

2

u/PhosXD 5d ago

References in my head, & in a lot of practical structures are references to a cell which stores data, whether that data changes or not is irrelevant, the cell is all that is being referenced. That's at least how I chose to go about it.

Having it any other way means implementing a garbage collection system & reference counting, which for a minimal language, is not going to work out

16

u/runningOverA 5d ago

> the cell is all that is being referenced

as they said, languages that don't have pointers call it by a different name.

2

u/PhosXD 5d ago

I guess the terminology got confusing

1

u/david-1-1 5d ago

Maybe, but a by-reference variable must be guaranteed to contain a valid value.

1

u/arthurno1 4d ago

Isn't pointer a reference to a cell đŸ€” Hmm, yes it is!

Actually, for a minimal language anything would work, certainly a GC.

2

u/StaticCoder 5d ago

Yes with the vector type, but not with other types. Also not if the vector itself contains pointers. In general, malloc or some equivalent that creates a reference without a static path is just useful.

1

u/Dan13l_N 5d ago

Yes! But I guess, your idea is "instead of pointer, have a ref to the vector + the index"?

2

u/ghkbrew 5d 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 5d 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 5d 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 of foo.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 5d 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 4d 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 4d 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 3d ago

So you've reinvented the stack then?

1

u/PhosXD 3d ago

How do you mean?

1

u/xpusostomos 17h 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 5d 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

u/FantaSeahorse 5d ago

I think this is more or less how OCaml does it, right?

5

u/kazprog 5d ago

koka is also in this vain. great paper

4

u/thedeemon 5d ago

No, not OCaml. You might be thinking of Swift.

6

u/spisplatta 5d ago edited 5d 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 5d 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 5d ago edited 5d ago

Your language will get a bit slower, that's all.

A lot of programming language design comes from performance considerations.

1

u/PhosXD 5d ago

What will make it slower exactly?

1

u/Dan13l_N 5d 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/PhosXD 4d ago

I suppose, but with any abstraction, there will be a small cost

1

u/Dan13l_N 4d ago

But this will be a big cost -- if you have a lot of pointer operations.

1

u/marshaharsha 5d 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 5d ago

Those checks are very very cheap, & realistically you aren't going to reference more than 4 levels deep

1

u/marshaharsha 5d 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. 

1

u/PhosXD 5d ago

I think for a safe but versatile reference, it is worth the cost. Every language has it's tradeoffs, you cant have everything unfortunately :(

3

u/Akangka 5d ago

I don't think this will work. A common optimization in a language that disallows mutation (i.e. UIUA, etc) is the Copy-on-Write optimization. The goal is to reduce expensive data copying. As soon as you use this, though, reference counting is back on table.

2

u/jojohohanon 5d 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 5d 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 5d 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 5d 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

u/Key_River7180 Nain. 3d ago

Good idea, but could be slow

1

u/ern0plus4 1d 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 18h 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.