Consts and references

Consts

Cairo supports defining constant expressions (only integers). For example, one may write:

const value = 1234
[ap] = value

which is equivalent to

[ap] = 1234

The line const value = 1234 is not translated to a Cairo instruction; it is just used by the compiler to replace value with 1234 in the following instructions.

Python literals

Instead of specifying an explicit constant integer using its decimal representation, you can use the syntax %[ <python-code> %] which can contain any python code. This code is evaluated to a constant during the compilation of the program. This means that it cannot depend on the program input, and unlike hints, the soundness of the program may rely on the correct evaluation of those literals.

For example,

[ap] = %[ 0x123456 %]
const value = %[ 2 * 3 * 5 %] + 100

References

Sometimes it may be difficult to follow the progress of the ap register. Consider the following code, which computes \(x^{16}+x\) for \(x = 3\):

# Set value of x.
[ap] = 3; ap++

[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++

[ap] = [ap - 1] + [ap - 5]; ap++

The problem is that it’s difficult to say whether the offset 5 in the last line should indeed be 5 (rather than 4 or 6). Instead, we can write:

# Set value of x.
let x = ap
[x] = 3; ap++

[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++

[ap] = [ap - 1] + [x]; ap++

The let syntax defines a reference and this code compiles exactly to the same instructions as the previous code. In particular, the compiler replaces the first occurrence of [x] by [ap] and the second by [ap - 5]. In other words, the compiler tracks the progress of the ap register and substitute x accordingly.

References can hold any Cairo expression, for example:

let x = [[fp + 3] + 1]
[ap] = x  # This will compile to [ap] = [[fp + 3] + 1].

The assert statement and compound expressions

Often you’ll need to perform a computation which involves more than one operation. The polynomial in Exercise - A simple Cairo program is a good example. An expression that involves more than one operation (e.g., [ap] * [ap] * [ap], [[[ap]]] + [ap], …) is called a compound expression. The Cairo compiler supports the following syntax, which allows to assert the equality between the values of two compound expressions:

assert <compound-expr> = <compound-expr>

For example,

let x = [ap - 1]
let y = [ap - 2]
assert x * x = x + 5 * y

Note that such statements are usually compiled to more than one instruction and ap may advance an unknown number of steps (the exact number depends on the number of operations in the two compound expressions). Hence, you should avoid using ap and fp directly in such expressions and use the mechanisms presented in this section instead (references and temporary/local variables).

Revoked references

Note that if there is a label or a call instruction (call to another function. See Functions) between the definition of a reference that depends on ap and its usage, the reference may be revoked, since the compiler may not be able to compute the change of ap (as one may jump to the label from another place in the program, or call a function that might change ap in an unknown way).

In some cases, the compiler will not automatically detect that a jump may occur (for example, in an explicit relative jump, see the exercise below) and the reference will not be revoked. However, using this reference in such cases may result in an undefined behavior.

References which do not depend on ap (for example, let x = [[fp]]) are never revoked by the compiler, but the same rule applies – using those references outside of the scope of the function they were defined in, may result in an undefined behavior.

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

Typed references

Suppose that [fp] contains a pointer to a struct of three memory cells: x, y, z. To access the value of y, one may write [[fp] + 1]. However, this requires the programmer to maintain the offset of y.

A better way is to define a struct:

struct MyStruct:
    member x : felt
    member y : felt
    member z : felt
end

This creates a struct named MyStruct. The keyword felt stands for field element, which is the primitive type in Cairo. The Cairo compiler computes the offsets of the members from the beginning of the structs, and you can access those offsets using MyStruct.x, MyStruct.y and MyStruct.z (for example MyStruct.z = 2). In addition, the total size of the struct can be obtained using MyStruct.SIZE. Now we can replace [[fp] + 1] with [[fp] + MyStruct.y].

Since this pattern repeats itself quite a lot, Cairo supports defining typed references as follows:

let ptr : MyStruct* = cast([fp], MyStruct*)
assert ptr.y = 10
# This will compile to [ptr + MyStruct.y],
# which will subsequently compile to [[fp] + 1].

In general, the syntax refname.membername, where refname is a typed reference with value val and type T, and T.membername is a member definition, compiles to [val + T.membername].

You may omit the type and write (the Cairo compiler will deduce the type from the right-hand side):

let ptr = cast([fp], MyStruct*)

Casting

Every Cairo expression has an associated type. Cairo supports types such as field-element (represented by the keyword felt), pointers and structs. For example, the values of the registers ap and fp and any integer literal is felt.

You can change the type of an expression using cast(<expr>, <type>), where <type> can be felt (for a field-element), T (for a struct T, as explained above) or a pointer to another type (such as T* or felt**).

Temporary variables

Cairo supports the following syntactic sugar which allows defining temporary variables:

tempvar var_name = <expr>

For simple expressions, with at most one operation, this is equivalent to:

[ap] = <expr>; ap++
let var_name = [ap - 1]

Compound expressions are also supported, in which case the command may be compiled to more than one Cairo instruction.

Note that as the reference is based on ap, it may be revoked by some instructions (see Revoked references).

Exercise

Rewrite the solution to Exercise - A simple Cairo program using temporary variables.

Local variables

Another important feature is called “local variables”. Unlike Temporary variables which are based on the ap register, and thus are revoked by some instructions (see Revoked references), local variables are based on the fp register. In the scope of a function, the first local variable will be a reference to [fp + 0], the second one to [fp + 1] and so on. Unlike Temporary variables which take care of incrementing ap, this is not the case for local variables. You must take care to advance ap if you’re using local variables. The Cairo compiler auto-generates a constant SIZEOF_LOCALS which is equal to the accumulated size (of cells) of locals within the same scope. For example:

func main():
    ap += SIZEOF_LOCALS
    local x  # x will be a reference to [fp + 0].
    local y  # y will be a reference to [fp + 1].

    x = 5
    y = 7
    ret
end

Additionally, Cairo provides the instruction alloc_locals which is transformed to ap += SIZEOF_LOCALS.

You may also define a local and assign a value to it in a single line:

local x = <expr>

In fact, the expression may be a compound expression.

Note that unless the local variable is initialized in the same line, the local directive itself does not translate to a Cairo instruction (this is another difference from tempvar) – it simply translates to a reference definition. This is one of the reasons you must increase the value of ap manually.

A local variable may have a type, like a reference. In the current version of Cairo, the type of a local variable must be explicitly stated (otherwise, felt is used), and it is not deduced from the type of the initialization value.

Exercise

  1. What’s wrong with the following code? (Hint: try to replace ap += SIZEOF_LOCALS with alloc_locals and see what happens) Can you fix it without changing the order of the variable definitions in the code?

    func main():
        tempvar x = 0
    
        local y
        ap += SIZEOF_LOCALS
        y = 6
        ret
    end
    
  2. Can you spot an inefficiency in the following code? Hint: take a look here. Fix the inefficiency in two ways (implement each of the following fixes separately):

    1. Move the instruction alloc_locals.

    2. Use tempvar instead of local.

func pow4(n) -> (m):
    alloc_locals
    local x

    jmp body if n != 0
    [ap] = 0; ap++
    ret

    body:
    x = n * n
    [ap] = x * x; ap++
    ret
end

func main():
    pow4(n=5)
    ret
end

Typed local variables

You can specify a type for the local variable in two different ways:

local x : T* = <expr>
local y : T = <expr>

The first one allocates one cell, which will be considered a pointer to a struct of type T. Thus you can use x.a as an equivalent to [[fp + 0] + T.a] (assuming a is a member of T).

The second one allocates T.SIZE cells (starting from fp + 1 in the example above due to the definition of x), and in this case y.a is equivalent to [fp + 1 + T.a] rather than [[fp + 1] + T.a] (exercise: why?).

Moreover, y itself refers to the address of the struct (fp + 1 rather than [fp + 1]). This means you may get an error if you try to use y. For example:

tempvar z = y

will fail, since it should compile to [ap] = fp which is not a valid instruction in Cairo (see Basic instructions). Nevertheless, defining a variable called __fp__ will allow the code to compile, as you will see in Accessing the values of the registers.

Reference rebinding

Cairo allows you to define a reference with the name of an existing reference:

let x : T* = cast(ap, T*)
x.a = 1

# ...

# Rebind x to the address fp + 3 instead of ap.
let x : T* = cast(fp + 3, T*)
x.b = 2

References are not variables: the scope of each definition is defined according to a static analysis of the order in which the instructions will be executed. It will follow a basic flow from jumps and conditional jumps, but if there are colliding definitions for the same reference, the reference will be revoked.

Example

To stress this last point, consider the following code.

func foo(x):
    let y = 1
    jmp x_not_zero if x != 0

    x_is_zero:
    [ap] = y; ap++  # y == 1.
    let y = 2
    [ap] = y; ap++  # y == 2.
    jmp done

    x_not_zero:
    [ap] = y; ap++  # y == 1.
    let y = 3
    [ap] = y; ap++  # y == 3.

    done:
    # Here, y is revoked, and cannot be accessed.
    ret
end

This code will return either [1, 2], or [1, 3].

Tuples

Tuples allow convenient referencing of an ordered collection of elements. Tuples consist of any combination of valid types, including other tuples.

Tuples are represented as a comma-separated list of elements enclosed in parentheses. For example: (3, x).

Consider the following assert statement:

assert (x, y) = (1, 2)

The above statement compiles to:

assert x = 1
assert y = 2

Tuple elements are accessed with the tuple expression followed by brackets containing a zero-based index to the element. The index must be known at compile time.

let a = (7, 6, 5)[2]  # let a = 5

Cairo requires a trailing comma for single-element tuples, to distinguish them from regular parentheses. For example (5,) is a single-element tuple. Access to nested tuples is achieved by using additional indices starting with the outer-most tuple. For example, MyTuple[2][4][3][1] first accesses index 2 of MyTuple. This value is accessed at index 4, and so on.

Arrays

In order to represent an array (an ordered collection of homogeneous elements) in Cairo, one may use a pointer to the beginning of the array. The standard library function alloc() may be used to “dynamically” allocate a new array.

For example, let (local struct_array : MyStruct*) = alloc() allocates a new memory segment and treats it as a pointer to MyStruct.

The expression struct_array[n] is used to access the n-th element of the array, where n=0 is the first element. struct_array[index] is compiled to [struct_array + index * MyStruct.SIZE], and is of type MyStruct.