Cairo’s Revoked Reference Exercise

Run the following code, with –steps=32 –print_memory and explain what happens.

func main():
    let x = [ap]
    [ap] = 1; ap++
    [ap] = 2; ap++

    [ap] = x; ap++
    jmp rel -1  # Jump to the previous instruction.
end

Solution

The output of the exercise is shown below:

$ cairo-compile exercise.cairo --output exercise.json
$ cairo-run --program=exercise.json --print_memory \
--relocate_prints --no_end --steps=32
>>>
Addr  Value
-----------
⋮
1     5189976364521848832
2     1
3     5189976364521848832
4     2
5     5193354051357474816
6     74168662805676031
7     -1
8     27
9     27
10    1
11    2
12    1
13    2
14    1
15    2
16    1
17    2
18    1
19    2
20    1
21    2
22    1
23    2
24    1
25    2
26    1

We can see that the memory area referenced by the ap pointer alternates between the values 1 and 2. To understand why we need to talk about how let works.

The keyword let creates a reference that is resolved by the compiler without creating a new instruction. This type of references are very useful at abstracting away the offset of the ap pointer to access a previous value. As an example, the two programs shown below are exactly the same.

func main():
    let x = [ap]
    [ap] = 1; ap++
    [ap] = 2; ap++

    [ap] = x; ap++
    ret
end

Which creates in both cases the following output:

Addr  Value
-----------
⋮
1     5189976364521848832
2     1
3     5189976364521848832
4     2
5     5193354051357474816
6     2345108766317314046
7     12
8     12
9     1
10    2
11    1

The problem with this type of references is that they can be revoked when having jumps between the moment they are set and the moment they are used. Even worse, they might not produce any compilation error and instead have unexpected behavior if an explicit jump is used as in our exercise.

In our exercise, the first time the value x is used, the reference is resolved correctly to the memory address ap – 2 but after the first jump, our reference stops working correctly. Instead of increasing the offset to keep up with changes to the ap pointer when doing ap++, it gets stuck in the same offset of ap – 2.

The code below shows how the compiler is incorrectly resolving the x reference by doing the substitution ourselves instead of the compiler.

func main():
    [ap] = 1; ap++
    [ap] = 2; ap++

    [ap] = [ap - 2]; ap++
    [ap] = [ap - 2]; ap++
    [ap] = [ap - 2]; ap++
    [ap] = [ap - 2]; ap++
    [ap] = [ap - 2]; ap++
    [ap] = [ap - 2]; ap++
    ret
end

Look how similar the output is compared to the output of the exercise.

Addr  Value
-----------
⋮
1     5189976364521848832
2     1
3     5189976364521848832
4     2
5     5193354051357474816
6     5193354051357474816
7     5193354051357474816
8     5193354051357474816
9     5193354051357474816
10    5193354051357474816
11    2345108766317314046
12    22
13    22
14    1
15    2
16    1
17    2
18    1
19    2
20    1
21    2

The moral of the story is to not use a reference when there are function calls or explicit jumps between the moment the reference is set and the moment is used.

Reference

The exercise in this article can be found in this section of the Cairo docs.