5 ms·

> I want a language that can check at compile/check time that none of my pointers will have invalid addresses. This is incompatible with pointer arithmetic, as

> I want a language that can check at compile/check time that none of my pointers will have invalid addresses. This is incompatible with pointer arithmetic, as it would require to solve the halting problem. You could, still, verify it at run time.

AgentME 7y ago
Right, but another option is to eschew pointer arithmetic. Iterators in many languages address many usages of pointer arithmetic, and can be designed to compile to the same sort of code as pointer arithmetic-using C compiles to. C wouldn't ever be able to take out pointer arithmetic, so I worry anyone envisioning a new language as some diff from C is probably going to get stuck on that sort of thing too. I'm a big fan of the original referenced article by Eevee for bringing this sort of thing up.
- jstimpfle 7y ago
  Pointers and pointer arithmetic are a physical reality. If you forbid them you are necessarily limiting yourself. It's a tradeoff. Iterators may work only very locally, or require garbage collection, for example. Static option types add complexity to the typesystem and require many typecasts in practice (which can me made safe with runtime checks and panics, but they are a hassle).
  - int_19h 7y ago
    The problem with pointer arithmetic in C is that it's the default. Every pointer implicitly supports it, even though the vast majority of them point to a single object of a given type, and so it doesn't really make sense for them. So it's much easier to get an invalid pointer than it ought to be. The obvious fix, as seen in e.g. Zig, is to have different types for pointers to objects and pointers to arrays. But once you have that, you can relegate the latter to the "unsafe" opt-in subset of the language.
    - jstimpfle 7y ago
      I've worked on a hobby programming language where I've made that design decision, too. But it makes pointers less general. Single "Objects" are arrays of length 1, but not in the type system. And in practice it often happens that I want to treat an object as an array of length 1. On the other hand I can't remember that I've ever given a pointer to an object that was treated as an array. I figure it happens about as often, and is about as easy or hard to debug, as swapped function call arguments. Which is pretty rare in my experience. And my philosophy is that making separate types for things that are structurally the same is usually a bad idea. Because it splits your world in two.
kragen 7y ago
It's entirely possible for a compiler to reject all programs that it can't verify as safe at compile time, including for array bounds checking, including pointer arithmetic. It's true that the uncomputability of the halting problem means that the compiler must reject some safe programs to achieve this. Doing this in practice probably requires using dependent types.
- enriquto 7y ago
  What you say is certainly possible but it does not seem that it would lead to a beautiful language with a beautiful specification.
  - pjc50 7y ago
    If you consider the C specification beautiful it can only be because anything ugly is simply left unspecified. Large parts are simply missing. It only seems straightforward because so many of the weird architectures and platforms have failed and we're left with 32/64 Intel/Arm as the only ones most authors consider. The C spec allows one's complement arithmetic, but how many programs would break horribly on such a machine?
    - jstimpfle 7y ago
      I neither consider the C specification beautiful, nor do I think that large parts are missing. In fact, the specification goes to great lengths to allow implementations on a wide range of computers. I will claim that most other languages specifications only seem so straightforward because they have a simpler execution model, where some of the things you can do in C are simply not possible, or where the spec is exclusively targeted at more modern machines. (And that's a good thing for most applications).
  - dependenttypes 7y ago
    You would be incorrect. Languages with proper type systems tend to have a much simpler specification when compared to C.

AgentME 7y ago

Right, but another option is to eschew pointer arithmetic. Iterators in many languages address many usages of pointer arithmetic, and can be designed to compile to the same sort of code as pointer arithmetic-using C compiles to. C wouldn't ever be able to take out pointer arithmetic, so I worry anyone envisioning a new language as some diff from C is probably going to get stuck on that sort of thing too. I'm a big fan of the original referenced article by Eevee for bringing this sort of thing up.

jstimpfle 7y ago
Pointers and pointer arithmetic are a physical reality. If you forbid them you are necessarily limiting yourself. It's a tradeoff. Iterators may work only very locally, or require garbage collection, for example. Static option types add complexity to the typesystem and require many typecasts in practice (which can me made safe with runtime checks and panics, but they are a hassle).
- int_19h 7y ago
  The problem with pointer arithmetic in C is that it's the default. Every pointer implicitly supports it, even though the vast majority of them point to a single object of a given type, and so it doesn't really make sense for them. So it's much easier to get an invalid pointer than it ought to be. The obvious fix, as seen in e.g. Zig, is to have different types for pointers to objects and pointers to arrays. But once you have that, you can relegate the latter to the "unsafe" opt-in subset of the language.
  - jstimpfle 7y ago
    I've worked on a hobby programming language where I've made that design decision, too. But it makes pointers less general. Single "Objects" are arrays of length 1, but not in the type system. And in practice it often happens that I want to treat an object as an array of length 1. On the other hand I can't remember that I've ever given a pointer to an object that was treated as an array. I figure it happens about as often, and is about as easy or hard to debug, as swapped function call arguments. Which is pretty rare in my experience. And my philosophy is that making separate types for things that are structurally the same is usually a bad idea. Because it splits your world in two.

kragen 7y ago

It's entirely possible for a compiler to reject all programs that it can't verify as safe at compile time, including for array bounds checking, including pointer arithmetic. It's true that the uncomputability of the halting problem means that the compiler must reject some safe programs to achieve this. Doing this in practice probably requires using dependent types.

enriquto 7y ago
What you say is certainly possible but it does not seem that it would lead to a beautiful language with a beautiful specification.
- pjc50 7y ago
  If you consider the C specification beautiful it can only be because anything ugly is simply left unspecified. Large parts are simply missing. It only seems straightforward because so many of the weird architectures and platforms have failed and we're left with 32/64 Intel/Arm as the only ones most authors consider. The C spec allows one's complement arithmetic, but how many programs would break horribly on such a machine?
  - jstimpfle 7y ago
    I neither consider the C specification beautiful, nor do I think that large parts are missing. In fact, the specification goes to great lengths to allow implementations on a wide range of computers. I will claim that most other languages specifications only seem so straightforward because they have a simpler execution model, where some of the things you can do in C are simply not possible, or where the spec is exclusively targeted at more modern machines. (And that's a good thing for most applications).
- dependenttypes 7y ago
  You would be incorrect. Languages with proper type systems tend to have a much simpler specification when compared to C.