Is definition of variable length array (VLA) / known constant size recursive?

Question

Issue: definition of variable length array (VLA) / known constant size seems to be recursive.

C11, 6.2.5 Types, 23 (emphases added):

A type has known constant size if the type is not incomplete and is not a variable length array type.

C11, 6.7.6.2 Array declarators, 4 (emphases added):

If the size is an integer constant expression and the element type has a known constant size, the array type is not a variable length array type; otherwise, the array type is a variable length array type.

These quotes can be pseudo-coded as:

is_KCS(T) = !is_INCOMPL(T) && !is_VLA(T)
is_VLA(T) = !(is_ICE(S(T)) && is_KCS(ET(T)))

Here we see that:

is_VLA depends on is_KCS, which depends on is_VLA (and so on)
is_KCS depends on is_VLA, which depends on is_KCS (and so on)

Questions:

Is definition of variable length array (VLA) / known constant size indeed recursive?
If yes, then is it a defect in the standard?

In C2X (n3299.pdf) the quotes above a bit changed, but the issue remains.

If A is not B and B is not A then it does not mean that there is a recursion. They are two different entities. — Vlad from Moscow
– Vlad from Moscow, Commented Nov 15, 2024 at 14:59
int arr[x][5] where x is not a constant. Then arr is an array of constant size 5 whose elements are of the variable-length type int[x]. — Nate Eldredge
– Nate Eldredge, Commented Nov 15, 2024 at 15:10
6.7.6.2 refers to the element type having a known constant size, not the type itself. So the recursive definition will terminate. So, no, it is not a defect in the standard. — Tom Karzes
– Tom Karzes, Commented Nov 15, 2024 at 15:35
One thing missing from your pseudocode is that in order for a type to be a variable-length array type, it must in particular be an array type. So is_VLA(T) = is_array(T) && !(is_ICE(S(T)) && is_KCS(ET(T))). When is_VLA is "called" recursively, it's not with the same original type T, but with its element type ET(T) which is necessarily different. The recursion could continue for a finite number of steps, but eventually either is_array() will return false or is_ICE will return true, and then the recursion terminates. — Nate Eldredge
– Nate Eldredge, Commented Nov 15, 2024 at 15:42
So, it makes sense for the definition to be recursive, because types in C can always be defined in terms of other types. But this dependency relation is well founded; a C program can only define a finite number of types (because a C program is of finite length), and a type cannot be defined in terms of itself, neither directly nor indirectly, so there are no cycles. As such, recursive definitions like this are well-defined. — Nate Eldredge
– Nate Eldredge, Commented Nov 15, 2024 at 15:46

ikegami · Accepted Answer · 2024-11-15 20:51:13Z

4

Sure, it's recursive. No, it's not a problem, because the recursion terminates.

First of all, there's an implicit check you're missing (since S(T) is only defined for arrays):

is_KCS(T) = !is_INCOMPL(T) && !is_VLA(T);
is_VLA(T) = !( isARRAY(T) && is_ICE(S(T)) && is_KCS(ET(T)) );

With this change, you'll reach a type that isn't an array type, a type that's an array type without an integer constant expression for size, or an incomplete type.

Not only is it not a defect, it's necessary. Take a look at the following example:

typedef int ET[n];

ET a[4];

aka

int a[4][n];

Is a a VLA? Yes, because its element type (ET/int [n]) is a VLA type. To determine if a is a VLA, we needed to (recursively) check if ET/int [n] is a VLA type.

edited Nov 15, 2024 at 20:51

answered Nov 15, 2024 at 18:53

ikegami

391k17 gold badges291 silver badges555 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Is definition of variable length array (VLA) / known constant size recursive?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related