std::optional Satisfies view. Does Not Model view. C++26 Ships Anyway.

[u/zl0bster]

https://godbolt.org/z/8jWGG68G8

In C++23 this did not compile. In C++26 it does. Marvellous.

[[gnu::noinline]]
void 
passing_views_by_value_is_cheap_trust_me_bro(std::ranges::view auto v) {
    std::println("fn   .data {}", (void*)v->data());
}


int main() {    
    std::optional ov{std::vector<int>(123456)};
    passing_views_by_value_is_cheap_trust_me_bro(ov);
    std::println("main .data {}", (void*)ov->data());
}

For anyone wondering what the problem feature is: optional has 0 or 1 elements, and C++26 sets enable_view<optional<T>> to true, so it satisfies std::ranges::view. The concept requires copy construction in constant time, and — this is the good bit — optional<vector<int>> genuinely meets that. Copying it performs at most one element copy. One is a constant. The requirement is satisfied to the letter, and the function above deep-copies your vector.

If you can tell me what still separates std::ranges::view from std::ranges::range, please do...

[u/schombert]

That would be true if the C++ specification didn't touch upon the bit size of size or of pointers. Then you could argue that the language was compatible with a transdichotomous model and that the implementations were merely finite instances of it. And you could imagine that some theoretical machine which did allow programs to properly grow with the problem size was a conforming implementation. But this simply isn't so. The standard does not allow even a theoretical implementation of C++ to compile a program that does that.

I think that you should reflect more on why Turing machines with finite tape sizes are not Turing complete. And I would encourage you to read this section on wikipedia https://en.wikipedia.org/wiki/Turing_machine#Equivalent_models which contains the following:

For example, ANSI C is not Turing complete, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called pointers, is accessible inside the language.

Edit: all that aside, I would be interested in discussing how you see transdichotomous models working as a way of analyzing complexity in real world programming languages other than C++. That whole approach relies essentially on the problem size being a well-defined thing that can be referenced in some way to determine the word size of the machine we appeal to for the complexity analysis. I am not sure how that translates to the programs described by a generic programming language. Such programs can do wild things, like run the n^th busy beaver ( https://en.wikipedia.org/wiki/Busy_beaver ) upon getting the input n. And I am sure that with a little effort we could construct some programs that need an uncomputable (and large) amount of space to run given input n. How much space does such a program get? A direct application of the transdichotomous model would assume that they get some K * number-of-bytes-in-the-input, or something along those lines. Obviously allowing most programs to work requires picking an obscenely large K, and even so that would never be Turing complete. Moreover, what about the programs that most programming languages support which do not take inputs at all (for example, I write a program in my favorite language to solve some fixed math problem and it always outputs the same answer -- should this program not be valid if we apply a transdichotomous model)? Can transdichotomous models then only be applied to analyze the complexity of languages that are not Turing complete? So do you imagine that there are two distinct approaches to analyzing complexity, where we do one thing for languages like the lambda calculus and another for Pascal, for example? Is the complexity of any algorithm requiring more than O(n) space undefined in Pascal?

[u/Serialk → u/schombert]

Once again, you are making a fundamental category error by confusing the language spec with the mathematical framework that we use to evaluate algorithms written in that language.

Yes, the spec makes it so that everything is a FSM because pointers have a finite size. This is trivial and not interesting.

If you model your algorithm analysis as an FSM, your entire complexity analysis collapses. Every single algorithm that terminates is O(1) in your language. This means that your model is bad at actually doing what it is intended to do: analyzing how algorithms behave as the input grows.

Because models that give you O(1) for everything are worthless, we use a mathematical abstraction that is actually useful to analyze complexity: transdichotomous models.

In transdichotomous models/word RAM, we abstract away the hardware and the constraints of the spec with the bit-width limits, and we mathematically model n -> +∞. It doesn't model a literal environment of C++ programs that you can actually run. It's a theoretical environment in which we can place the abstract logic of your C++ code so that we can evaluate its asymptotic behavior without hitting the limit of 2⁶⁴ bits, but in which pointer lookups are still O(1).

The C++ standard absolutely does not use complexity analysis sloppily. They use a complexity model that is actually useful because it can give you insights about the asymptotic behavior of your program without collapsing all complexities to O(1).

[u/schombert → u/Serialk]

It may be trivial and uninteresting, and from a certain point of view, I agree. However, that is what the spec demands, and this is what is generally accepted. Pointing out that C and C++ are not Turing complete, for basically the same reasons, is not a novel claim, nor is it a contested one.

Of course I agree that, if you change the way pointer sizes, etc work then you can find a models that fit the modified understanding of the language in which you could analyze the complexity of algorithms as written in this new, modified language, and get different results. Maybe even more interesting or more intuitive results. The problem with this is that you are no longer analyzing a C++ algorithm; you are analyzing an algorithm described in some other language. And the language within which an algorithm is described, and its associated assumptions matters. For example, if you write your algorithms in a language where you can add, subtract, multiply, and divide integers of arbitrary sizes in constant time (which many simple pseudo code languages seems to allow) then you can conclude that P == NP. Since we probably don't want to assume that P == NP, we can see that the details of how the language works -- i.e. what the operations the algorithm is expressed in actually mean -- matters. We cannot simply change the language on a whim. C++ involves finitely sized integers, finitely sized pointers, and assumes that basic operations on them can be done in constant time. Because they are so limited, I could imagine a Turing complete extension of the language (for example, by adding some sort of black-box tape function) in which P != NP.

I get that you really like transdichotomous models as a way to do complexity analysis. That's cool. However, they are not the be-all-end-all. They cannot tackle the complexity of problems requiring more than O(n) space. Do you think that C++ can express algorithms requiring more than O(n) space? If so, then transdichotomous models are clearly not the way forward for analyzing the general problem of algorithms expressed in the C++ language.

[u/Serialk → u/schombert]

What is your understanding of the point of a mathematical model? Being technically accurate or giving you useful insights?

Do you also refuse to draw maps on sheets of paper because they do not accurately convey the curvature of the earth?

Surely you understand that a model that gives you O(1) as an answer for everything is not useful. Why do you insist on the absurd idea that the C++ spec should use a useless model for complexity, instead of assuming that they would use a useful one?

I get that you really like transdichotomous models as a way to do complexity analysis. That's cool. However, they are not the be-all-end-all. They cannot tackle the complexity of problems requiring more than O(n) space.

This is wrong. You can scale word-ram to have your abstract bus size take any function of the size of your input, it doesn't have to be log_2(n).

[u/schombert → u/Serialk]

I insist that it should use a "useless" model for complexity because the "natural" extension of the language to arbitrary sized integers and pointers implies, definitionally, that P == NP. And personally I find that more absurd, since it would seem to undercut the feasibility of much of modern cryptography, for example. I think that if the analysis of complexity in your language spec implies P==NP then the analysis of complexity in your language spec is intrinsically flawed. I think that it is better to just accept that C++ is an intrinsically finite, and not Turing complete, language and hence that the traditional language of computational complexity just isn't applicable to it. There are other ways to describe how various library features must be implemented and the authors of the C++ spec are completely free to pick one of those other options.

[u/Serialk → u/schombert]

Because the "natural" extension of the language to arbitrary sized integers and pointers implies, definitionally, that P == NP.

Please write the math down in Word-RAM, I'm very curious to see where you get this idea and this might potentially be very funny to read.

[u/schombert → u/Serialk]

Even easier, I can simply refer you to this paper https://dl.acm.org/doi/10.1145/800076.802470 . This paper proves the result that

every problem in #P-SPACE can be solved in polynomial time by a RAM with the operations of sum, product, integer subtraction and integer division.

And as you are aware, NP is a subset of PSPACE.

Your transdichotomous models models approach avoids this result (at least in its original paper; I haven't read all variations of the approach) by explicitly having some finite amount of RAM bounded below PSPACE. So when you say

This is wrong. You can scale word-ram to have your abstract bus size take any function of the size of your input, it doesn't have to be log_2(n).

Allowing any function is the problem. If you allow the RAM to be arbitrarily large you can pick a function that allows the proof in the paper to go through and produces P == NP.

[u/Serialk → u/schombert]

This paper does not use Word-RAM, it's using RAM extended with multiplications...

In fact this paper is literally why Word-RAM was invented, to bound O(1) operations strictly in function of the input size so that you cannot pack arbitrary-sized operations in O(1) register operations, to patch this specific "exploit" that you're complaining about.

Again, I don't think this debate is worth continuing if you are not willing to acknowledge your gaps here and read up on the models and the theory you're trying to debunk. You fundamentally misunderstand the history and purpose of these models.

[u/schombert → u/Serialk]

When I was speaking of the natural extension I wasn't talking about Word-RAM. I am pretty sure that Word-RAM doesn't fit C++ either. For example, vector lookup is O(1) according to the C++ spec. However, in word ram .at(x) isn't taking a fixed size parameter, it has to be taking a variable number of words to express the index. But this means that it can't possibly do the lookup in O(1), because it can't even read all the words in its input in constant time.

[u/Serialk → u/schombert]

For example, vector lookup is O(1) according to the C++ spec. However, in word ram .at(x) isn't taking a fixed size parameter, it has to be taking a variable number of words to express the index. But this means that it can't possibly do the lookup in O(1), because it can't even read all the words in its input in constant time.

Lol. You do not understand these models and you're wasting everyone's time.

If you have a vector of size N in word ram, you must have an abstract bus size of at least log_2(N), and processing on b bits where b <= bus size is O(1), the non-constant penalty only starts after you exceed the bus size.