Write a program poly.cairo that computes the expression x^3 + 23*(x^2) + 45*x + 67 where x = 100
func main():
[ap] = 100; ap++
# << Your code here >>
ret
end
1) After the program ends, the value should be at [ap – 1]
2) For this exercise, you may assume that the fp register is constant and initialized to the same value as ap
3) Your code shouldn’t depend on the value of x.
4) Compile with cairo-compile and inspect the output. The output should be in poly_compiled.json.
5) Run the program (this will invoke the Cairo VM):
$ cairo-run --program=exercise.json
--print_memory --print_info --relocate_prints
6) Take a look at the output: You should see the memory values (the last cell should be 1234567). Verify that you understand what’s going on there.
Solution
Given that this is the first exercise in the “How Cairo Works” section, there’s an expectation that we will have to rely only on built-in pointers like the allocation pointer (ap) and the function pointer (fp) along with simple expressions instead of variables and compound expressions.
Simple expressions consist of a maximum of two operands, an optional operator and an assignment. The following are examples of simple expressions:
[ap] = 100; ap++ # no operator
[ap] = [ap - 1] + [ap - 2]; ap++ # addition operator
[ap] = [fp] * 10; ap++ # multiplication operator
Compound expressions (more than one operator) are not allowed when using only built-in pointers.
[ap] = [ap - 1] + [ap - 2] + [ap - 3] # invalid
[ap] = [ap - 1] + [ap - 2] + 100 # invalid
Cairo imposes an additional restriction on the use of integers when dealing directly with built-in pointers. Integers that are part of an operation must be placed on the right hand side of the operator, never on the left. The reason for this restriction is still unclear to me.
[ap] = [fp] * 10; ap++ # valid expression
[ap] = 10 * [fp]; ap++ # invalid expression
Finally, the docs state that at the beginning of any function the fp and the ap pointer always start pointing to the same memory address but while ap changes, fp remains fixed during the execution of the function. This fact about the built in pointers makes the following comment on the exercise redundant in my opinion.
“For this exercise, you may assume that the fp register is constant and initialized to the same value as ap.”
We can now start coding the solution to the problem. We already know that the value of x is 100 so the first challenge is to calculate the value of x^2.
func main():
[ap] = 100; ap++
[ap] = [ap - 1] * [ap - 1]; ap++ # x^2
ret
end
Because the ap pointer moves to the next contiguous memory address everytime we do ap++ to refer to the value of x on the second instruction we have to read the previous memory address [ap – 1] (100).
Next we calculate the value of x^3 using a similar trick.
func main():
[ap] = 100; ap++
[ap] = [ap - 1] * [ap - 1]; ap++ # x^2
[ap] = [ap - 1] * [ap - 2]; ap++ # x^3
ret
end
The memory address at [ap – 1] holds the recently calculated value of x^2 (1,000) while the memory address at [ap – 2] holds the value of x (100).
Next we calculate the value of 23*(x^2) remembering that when using integers they must appear to the right hand side of the operator.
func main():
[ap] = 100; ap++
[ap] = [ap - 1] * [ap - 1]; ap++ # x * x (x^2)
[ap] = [ap - 1] * [ap - 2]; ap++ # x^2 * x (x^3)
[ap] = [ap - 2] * 23; ap++ # x^2 * 23
ret
end
The rest of the expressions are very similar so I’ll add them all at once with comments.
func main():
[ap] = 100; ap++
[ap] = [ap - 1] * [ap - 1]; ap++ # x * x (x^2)
[ap] = [ap - 1] * [ap - 2]; ap++ # x^2 * x (x^3)
[ap] = [ap - 2] * 23; ap++ # x^2 * 23
[ap] = [ap - 4] * 45; ap++ # x * 45
[ap] = [ap - 3] + [ap - 2]; ap++ # x^3 + x^2 * 23
[ap] = [ap - 1] + [ap - 2]; ap++ # x^3 + x^2 * 23 + x * 45
[ap] = [ap - 1] + 67; ap++ # x^3 + x^2 * 23 + x * 45 + 67
ret
end
To execute our code we need to compile it first.
$ cairo-compile poly.cairo --output poly_compiled.json
We can now execute our code as the exercise suggests.
$ cairo-run --program=poly_compiled.json
--print_memory --print_info --relocate_prints
And we get the following output:
Addr Value
-----------
⋮
1 5189976364521848832
2 100
3 5210805504208502784
4 5210805499913535488
5 5207427813077843968
6 23
7 5207427813077712896
8 45
9 5201798300658663424
10 5201798300658794496
11 5198420613823168512
12 67
13 2345108766317314046
14 24
15 24
16 100
17 10000
18 1000000
19 230000
20 4500
21 1230000
22 1234500
23 1234567
Number of steps: 9 (originally, 9)
Used memory cells: 23
Register values after execution:
pc = 24
ap = 24
fp = 24
According to the exercise we have found the right answer (1234567) stored on the last memory address of our program (23).
Improving Readability Using the fp Pointer
In our program we referenced the value of x multiple times using different offsets from the current ap pointer to access the same memory address. This is cumbersome as we have to remember what’s the right offset depending on where the ap pointer is at any given time. An alternative approach is to use the fp register whenever we want to access the value of x as both registers point to the same address at the beginning of a function and fp remains unchanged during the function execution.
func main():
[ap] = 100; ap++
[ap] = [fp] * [fp]; ap++ # x * x (x^2)
[ap] = [ap - 1] * [fp]; ap++ # x^2 * x (x^3)
[ap] = [ap - 2] * 23; ap++ # x^2 * 23
[ap] = [fp] * 45; ap++ # x * 45
[ap] = [ap - 3] + [ap - 2]; ap++ # x^3 + x^2 * 23
[ap] = [ap - 1] + [ap - 2]; ap++ # x^3 + x^2 * 23 + x * 45
[ap] = [ap - 1] + 67; ap++ # x^3 + x^2 * 23 + x * 45 + 67
ret
end
Compiling and executing our modified code we get the exact same output.
Analyzing the Memory Trace
One of the challenges of the exercise is to understand what the memory trace is showing us when we run the program.
When I first saw the memory trace of the solution it didn’t make much sense to me so I went back and started to debug the code to infer its meaning. The first debugging was to execute a single expression and observe the output.
func main():
[ap] = 100; ap++
ret
end
Running this program we get the following output:
Addr Value
-----------
⋮
1 5189976364521848832
2 100
3 2345108766317314046
4 7
5 7
6 100
Number of steps: 2 (originally, 2)
Used memory cells: 6
Register values after execution:
pc = 7
ap = 7
fp = 7
There are two numbers that I recognize from the trace, one is the number 100 as it represents the value of x and the other is 7 as it represents how many memory cells were needed to execute the program and the final value of the pointers pc, ap and fp.
Let’s make a small change to the code and see how it affects the output:
func main():
[ap] = 100; ap++
[ap] = 200; ap++
ret
end
The output of this program is:
Addr Value
-----------
⋮
1 5189976364521848832
2 100
3 5189976364521848832
4 200
5 2345108766317314046
6 10
7 10
8 100
9 200
Number of steps: 3 (originally, 3)
Used memory cells: 9
Register values after execution:
pc = 10
ap = 10
fp = 10
We can see that the same number is present for the memory cell 1 and 3 but followed by the two numbers we use in the assignments. This makes me believe that this number is in fact the opcode of a simple assignment operation. With this realization, the number shown on the cell 5 might represent the opcode of the return statement. It’s important to keep in mind that some instructions might require more than one opcode for its execution and that these opcodes are generated when the program is compiled.
The values stored on the memory address 6 and 7 are still unclear to me. They could represent how many memory cells are required to execute the program as this is something the compiler would know ahead of time or the last value stored in the registers pc, ap or fp.
The memory cells 8 and 9 represent the execution of the program or in other words, the values referenced by the ap pointer as the calculation progresses.
So there you go, the first part of the memory trace is the program itself while the second part shows the execution of the program.
In the following article we will tackle the bonus question of solving the same exercise by using no more than 5 instructions as this will require the introduction of temporary variables.
Reference
The exercise in this article can be found in this section of the Cairo docs.