Create an array with the values 1, 2 and 3, and print the last value to the terminal.
Solution
Arrays are stored using continuous memory addresses that need to be previously allocated. If all the elements of an array are known beforehand, one could simply create an array by directly storing its values in the execution segment using the ap register and creating a reference for its first memory address.
%builtins output
from starkware.cairo.common.serialize import serialize_word
func main{output_ptr : felt*}():
let my_array = ap
[ap] = 1; ap++
[ap] = 2; ap++
[ap] = 3; ap++
serialize_word([my_array + 2])
return ()
end
Compiling and executing this program we get the following output:
$ cairo-compile exercise.cairo --output exercise.json
$ cairo-run --program=exercise.json --print_output --layout=small
>>>
Program output:
3
This approach has two problems. First, we will not always know the size of an array beforehand so directly interacting with the ap register to create a continuous chunk of memory for our data might not be possible if we have other operations in between array assignments. Second, the syntax [array + index] is awkward and we would much prefer to use the syntax array[index] for the same purpose.
To solve both issues, we can use alloc, a function that allows for the creation of a memory segment of dynamic size that is used to store the values of an array. The return value of alloc is a pointer to the beginning of the newly allocated memory segment.
Using alloc we can rewrite our code to create an array of dynamic size.
%builtins output
from starkware.cairo.common.serialize import serialize_word
from starkware.cairo.common.alloc import alloc
func main{output_ptr : felt*}():
let (my_array : felt*) = alloc()
assert [my_array] = 1
assert [my_array + 1] = 2
assert [my_array + 2] = 3
serialize_word(my_array[2])
return ()
end
Compiling and executing this code we get the same result as before. To reduce clutter I’ve removed the output of the program memory segment.
$ cairo-compile exercise.cairo --output exercise.json
$ cairo-run --program=exercise.json \
--print_memory --print_output --layout=small
>>>
Addr Value
-----------
⋮
1:0 2:0
1:1 3:0
1:2 4:0
1:3 1:3
1:4 0:9
1:5 5:0
1:6 1
1:7 2
1:8 3
1:9 2:0
1:10 3
1:11 1:3
1:12 0:22
1:13 2:1
⋮
2:0 3
⋮
5:0 1
5:1 2
5:2 3
Program output:
3
In the memory address 1:5 (memory segment 1, offset 5) we can see the return value of the alloc function, a pointer to the first address (offset 0) of a newly created memory segment 5 or 5:0. In this segment we can see the values of our array being stored (1, 2, 3).
We have succeeded at creating an array of dynamic size whose internal elements can be accessed with the usual syntax array[index] but why do we need to use assert to add values to the array? To understand why we need to take a couple of steps back.
When a function returns, its return value (or values) is available at [ap – 1]. In our example, when alloc() returns, the address of the newly created memory segment available at [ap – 1]. We then create a reference called my_array that is bound to [ap – 1] for convenience. This means that when we assign our first value to our array doing [my_array] = 1 this would be equivalent to [[ap – 1]] = 1.
from starkware.cairo.common.alloc import alloc
func main():
alloc()
[[ap - 1]] = 1
return ()
end
$ cairo-compile exercise.cairo --output exercise.json
>>>
exercise.cairo:17:6: Expected a register. Found: [ap + (-1)].
[[ap - 1]] = 1
^******^
Preprocessed instruction:
[[ap + (-1)]] = 1
As you can see we can’t perform an assignment of a double dereference [[]]. For that we have to use assert that allows for complex expressions on either side of the = symbol and acts as an assignment if the left expression doesn’t have a value yet.
assert <complex_exp> = <complex_exp>
From the docs we are warned that when using assert we should avoid using any of the built in registers directly.
assert [[ap - 1]] = 1 # invalid
assert [my_array] = 1 # valid
This is why we end up using assert for adding new values to an array.