Why does List<T, N> hold a maximum of N-1 elements?

[ikripaka]

While implementing macros for Simplex, I noticed that the List<T, N> type can hold strictly fewer elements than its specified size bound.
For example, if we declare a list with a size limit of 16, it can only hold a maximum of 15 elements.

https://docs.simplicity-lang.org/simplicityhl-reference/type/

SimplicityHL/src/value.rs

Line 955 in aeeb37e

"There must be fewer list elements than the bound {bound}"

SimplicityHL/src/array.rs

Line 179 in aeeb37e

Partition::Parent { slice, bound } => slice.len() + 1 == bound.get(),

I'm curious about the technical reasoning behind this design choice. Are you inserting the head of the list as the 0th element, resulting in the truncated capacity?
Or a binary tree uses a recursive cutoff, by using 2^i elements in each leaf?
Or is this purely related to how lists are encoded for contract stack execution?

From a developer's perspective, it feels counterintuitive that a list bound of N forces an "off-by-one" capacity limit.

[stringhandler]

I also noticed this to be a bit odd. There is an explanation on the types documentation, under Lists:

Lists hold a variable number of elements of the same type. This is similar to Rust vectors, but SimplicityHL doesn't have a heap. In SimplicityHL, lists exist on the stack, which is why the maximum list length is bounded.

<2-lists hold fewer than 2 elements, so zero or one element. <4-lists hold fewer than 4 elements, so zero to three elements. <8-lists hold fewer than 8 elements, so zero to seven elements. And so on. For technical reasons, the list bound is always a power of two. The bound 1 is not supported, because it would only allow empty lists, which is useless.

Lists are different from arrays: List values hold a variable number of elements. Array values hold a fixed number of elements.

On the blockchain, you pay for every byte that you use. If you use an array, then you pay for every single element. For example, values of type [u8; 512] cost roughly as much as 512 many u8 values. However, if you use a list, then you only pay for the elements that you actually use. For example, the type List<u8, 512> allows for up to 511 elements. If you only use three elements list![1, 2, 3], then you pay for exactly three elements. You don't pay for the remaining 508 unused elements

This does explain it, but I also find the notation counter-intuitive

[ikripaka]

Alright, looks like we need more context here. Maybe Andrew may know the design details?

---

Hey, @apoelstra, may you please shed some light on that?

[apoelstra]

IIRC the actual underlying type is Option<u8> x Option<[u8; N]> x ... Option<[u8; 2^(N-1)>.

So the total number of values you can hold in this big thing is 1 + 2 + 4 + ... + 2^(N - 1) which equals 2^N - 1.

[apoelstra]

I would be happy changing the notation so that rather than writing a power of two, the user writes one less-than a power of two. But this would mean that existing code that writes List<T, 1> (which is an empty list) would change to mean a list that can hold one element.

I would suggest we make this change. Then lint List<T, 1> as being potentially wrong (before the change, the user should've used a null type, afterward they should've used an option). For every other power of 2, we can interpret it unambiguously as 2^n - 1, emitting a warning.

[stringhandler]

A quick check of usages of List on every-simplicity, which contrary to the name will not have every simplicity program out there, shows that the 4 programs use List<A, 64>, List<A, 512> and similar variants.

The question is whether the CMRs should change for these types.

[uncomputable]

For what it's worth, u32::MAX is 2^32 - 1.

[apoelstra]

I'm tempted to change N to one-less-than-2^n, and remove/disable List<T, 0> and List<T, 1> (easy to put them back if somebody complains at us).

Then if the user writes List<T, N> for an other power of two, we can issue a warning and just interpret N as N-1.

[stringhandler]

AFAIK List<T, 0> and List<T, 1> already do not exist

[stringhandler]

I suspect that the fold implementation may have a bug, I'll investigate tomorrow.

[ikripaka]

Thanks for the clarification, everyone!
To be clear, I'm comfortable with the bit algebra and notation used here.
I'm not requesting any changes to the codebase.

My interest is primarily in understanding the internal architecture and design decisions behind this.

List<A, 8> <8-list list![], …, list![a1, …, a7]
https://docs.simplicity-lang.org/simplicityhl-reference/type/

In the documentation, the indexing essentially spans 1..n-1, leaving the 0th element omitted.
I would love to understand how it works at the structural level.

If anyone could point me to the specific file or line of code where the list is constructed or saved to the stack during contract execution, I would greatly appreciate it.
So far, I have only been able to find the assertions that enforce the maximum length limit to N-1 elements.

I assume that the 0th element is reserved for the tree's root and held as a fat pointer in Rust, but maybe I'm wrong.

[stringhandler]

You should look at the fold built-in method. That is the only interaction with List that I am aware of

[stringhandler]

After digging into this today, I don't think we can change this. The fundamental problem is that Ctx8 is an alias for (List<u8, 64>, (u64, u256)), Basically, the block of up to 63 unwritten bytes, and the current state. Ctx8 is used in most programs.

[apoelstra]

We can change the notation though, right? Can't we make the change and then just re-alias Ctx8 to (List<u8, 63>, (u64, u256))?

[stringhandler]

One thing to note is that N is restricted to specific powers of 2, so we could change that to be powers of 2 minus 1.

This would change the names to:

List<T, 1>
List<T, 3>
List<T, 7>

This is possibly just as obscure though.

Alternatively, a bigger change is allowing any N. The generated simplicity from the fold method would change quite a lot to accommodate it. The code is complicated, so I won't pretend to understand it entirely, but it generates a tree structure which does some kind of check for the end of the list. This would have to be adjusted to check the end of the list as well.

[stringhandler]

Possibly an extra piece of information to consider here. There seems to be a bug in fold anyway, so fixing it will be a breaking change