I understand what you're getting at. A more restrictive language allows you to exclude a lot of things that cannot possibly happen and thefore you don't have to think about them any longer, which means less complexity.
But I'm still not sure whether this idea is sufficient to explain away the situation where you have to write a far longer program in order to work around those restrictions.
For instance, safe Rust cannot express linked lists in the usual way, i.e using pointers. So in order to write a linked list in safe Rust, you would have to reimplement some of the functionality that pointers provide using array indices (or similar).
This program would be very long indeed, plus it would cause many of the same safety issues that safe Rust was supposed to avoid. Essentially, what this program would do is create an unsafe memory management system in safe Rust.
I believe that the dominant factor for complexity of a program is its length. If you have two programs that produce the same output for the same input and one is 10 tokens long while the other one is 10,000 tokens long then the first program will always be less complex.
I say "I believe" because I'm a bit out of my depth here. These claims (mine and yours) clearly need formal proofs and some formal definition of complexity.
I actually don't think it's as difficult as people often suggest to write a doubly linked list in Rust (yes, I have done it and read Learning Rust by Implementing Entirely Too Many Linked Lists.). I think it's just surprising to people that something that's a CS101 data structure takes some advanced features to implement without locks.
But the thing is, you don't write C programs in Rust and you don't generally use doubly linked lists. (Linked lists turn out to be a very niche data structure that doesn't work well with modern CPUs anyway, but I digress.) You'd probably use a Vec or a BTree from the stdlib anywhere you're thinking of using a linked list.
So I don't think it's really the case that programs are significantly longer in Rust. Rust is more explicit, so you'll end up moving some things that existed as comments or documentation or just in your own head into code - that's a win that doesn't increase complexity, only exposes it. That program may look larger, but it's only because you can see it better.
It really depends on what those 10 tokens are doing. If I have a token that creates a new universe, seeds it with life, and creates the conditions for life to develop an optimal linked list - it might solve the problem in one step, but our atomic unit here is absolutely massive.
Similarly, if I compile a program to assembly I'll generally get many more tokens. But I can't really buy that I've increased the complexity of the program here.
I'm pretty satisfied with this understanding but I understand your desire for greater rigor.
>But the thing is, you don't write C programs in Rust and you don't generally use doubly linked lists.
The usefulness of linked lists is entirely beside the point. They just serve as an example for situations where additional restrictions can cause a program to be longer or more difficult to understand.
>It really depends on what those 10 tokens are doing. If I have a token that creates a new universe, seeds it with life, and creates the conditions for life to develop an optimal linked list - it might solve the problem in one step, but our atomic unit here is absolutely massive.
This example shows why I think that your claims lack a definition of complexity. You're now saying that the output of a program determines its complexity. I don't think that's a useful measure of complexity because it doesn't allow us to compare the complexity of two programs that produce the same output.
Not the particular output, no. It was how much was going on inside that hypothetical instruction, how massive of an abstraction it was, the unpredictability of the output. If you like you can think of it was a giant decision tree and imagine counting the branches to measure the complexity.
But I'm still not sure whether this idea is sufficient to explain away the situation where you have to write a far longer program in order to work around those restrictions.
For instance, safe Rust cannot express linked lists in the usual way, i.e using pointers. So in order to write a linked list in safe Rust, you would have to reimplement some of the functionality that pointers provide using array indices (or similar).
This program would be very long indeed, plus it would cause many of the same safety issues that safe Rust was supposed to avoid. Essentially, what this program would do is create an unsafe memory management system in safe Rust.
I believe that the dominant factor for complexity of a program is its length. If you have two programs that produce the same output for the same input and one is 10 tokens long while the other one is 10,000 tokens long then the first program will always be less complex.
I say "I believe" because I'm a bit out of my depth here. These claims (mine and yours) clearly need formal proofs and some formal definition of complexity.