A function is a reusable unit of code that receives arguments and returns a value.
To facilitate this in Cairo, we introduce two low-level instructions:
call addr, and
In addition, the Cairo compiler supports high-level syntax for those instructions:
return (...) respectively.
A function is declared as follows:
func function_name(): # Your code here. return () end
func function_name(): and
end are not translated to Cairo instructions –
they are just used by the compiler to name the function and create a corresponding scope.
To call the function, simply use the call instruction:
or the high-level syntax:
The full syntax of
call is similar to
you can call a label (a function is also considered a label),
and make a relative call (
call rel ...) (
call abs is not supported).
The fp register¶
When a function starts the frame pointer register (
fp) is initialized to the current value
ap. During the entire scope of the function (excluding inner function calls)
the value of
fp remains constant.
In particular, when a function,
foo, calls an inner function,
bar, the value of
bar starts but is restored when
The idea is that
ap may change in an unknown way when an inner function is called,
so it cannot reliably be used to access the original function’s local variables and arguments
anymore after that. Thus,
fp serves as an anchor to access these values.
Compile and run (with at least 10 steps) the following code:
func main(): call foo call foo call foo ret end func foo(): [ap] = 1000; ap++ ret end
We will analyze the memory generated by this program in the example below.
For now, try to think what happens when the cpu gets to the
(which of the registers
pc should change when
ret is executed
and to what values?).
Under the hood¶
call addr is roughly equivalent to the following set of instructions:
# Stores the value of the current fp, which will be # restored once the called function ends using ret. [ap] <-- fp # Stores the address of the next instruction, to run # once the called function ends. This will be # assigned to pc when ret is invoked. [ap + 1] <-- return_pc # Increase ap by 2, to account for the last two writes. ap += 2 # Updates fp to be the new ap, so it points to the start # of the new frame within the called function's scope. fp <-- ap jmp addr
ret is roughly equivalent to the following set of instructions:
# Jumps to return_pc (stored on the stack). jmp [fp - 1] # Restores the value of the previous fp. fp <-- [fp - 2]
We can summarize it thusly:
call “pushes” the current frame pointer and return-address to a (virtual) stack of pairs
(fp, pc) and jumps to the given address.
ret “pops” the previous
fp and jumps to
return_pc that were pushed during the call.
Schematically, after a call instruction the memory looks as follows:
| ... | +--------------+ | old_fp | +--------------+ | return_pc | +--------------+ | | <-- ap, fp +--------------+ | ... |
Look at the memory values after running the program above:
Address Value 13 13 14 3 15 1000 16 13 17 5 18 1000 19 13 20 7 21 1000
When main starts, the value of
fp is 13, and the program calls the first invocation of
writing the current value of
fp (13) and value of the program counter to return to (3).
foo writes 1000 to the memory.
ret restores the value of
fp back to 13 and then jumps to
pc = 3.
foo is called a second time.
Make sure you understand the rest of the memory values.
Use the information given in the last section, in order to write a piece of code that
when executed puts the current values of
pc in memory
[ap + 1] and
[ap + 2]).
Accessing the values of the registers¶
Cairo’s standard library has two functions that allow to retrieve the values of the three registers (in fact, they are implemented similarly to the solution of the last exercise). You may use them as follows:
from starkware.cairo.common.registers import get_ap from starkware.cairo.common.registers import get_fp_and_pc let get_ap_res = get_ap() tempvar my_ap = get_ap_res.ap_val let fp_and_pc = get_fp_and_pc() tempvar my_fp = fp_and_pc.fp_val tempvar my_pc = fp_and_pc.pc_val
(You will learn more about this syntax in the sections below.)
When Cairo needs to use the address fp in a compound expression
it will try to replace it with a variable named
__fp__, which is assumed to contain the value
fp. Note that dereferences with respect to
fp (such as
[fp + 3]) are always OK.
For example, line B in the following code requires line A in order to compile,
while line C does not.
local __fp__ = fp_and_pc.fp_val # A. tempvar x = fp # B. tempvar y = [fp] # C.
Function arguments and return values¶
The following is an example of a function which gets two values
and returns their sum
z and product
func foo(x, y) -> (z, w): [ap] = x + y; ap++ # z. [ap] = x * y; ap++ # w. ret end
Arguments are written to the “stack” before the
For example, to call
foo(4, 5) you should write:
[ap] = 4; ap++ # x. [ap] = 5; ap++ # y. call foo
call pushes two more values to the stack (next pc and current fp).
Thus, when a function starts, the arguments are available at
[fp - 3],
[fp - 4], …
(in reverse order).
For each argument, the Cairo compiler creates a reference
argname to its value
and a constant
Args.argname with its offset (0, 1, 2, …).
Any usage of the reference
argname is replaced by
[fp - (2 + n_args) + Args.argname].
This way you can access the value of an argument named
x simply by writing
Cairo supports the following syntactic sugar to call a function, which also supports compound expressions:
The function writes to the stack its return values just before the
Thus, after the function call the return values will be available to the caller at
[ap - 1],
[ap - 2] and so on.
For example, to use the values returned by
foo you may write:
foo(x=4, y=5) [ap] = [ap - 1] + [ap - 2]; ap++ # Compute z + w.
The Cairo compiler automatically creates constants named
with the values -1 and -2 respectively, so that
[ap - 1] can be written as
[ap + foo.Return.z].
In fact, one may define a typed reference
let foo_ret : foo.Return = ap.
Now, you can access
Cairo supports a syntactic sugar for these cases (which we call “return value references”):
let foo_ret = foo(x=4, y=5) # foo_ret is implicitly a reference to ap with type foo.Return. [ap] = foo_ret.z + foo_ret.w; ap++
Return values unpacking¶
Cairo supports syntactic sugar to assign multiple return values to references via tuples. The
let (z, w) = foo(x=4, x=5) assigns
foo’s return values to
let (z, w) = foo(x=4, y=5) [ap] = z + w; ap++
In many cases, you may want to copy the result to a local variable, in order to prevent it from
being revoked later. While you can add an instruction
local z = z, which rebinds the reference
to a new local variable with the same name, the same effect can be achieved using:
let (local z, local w) = foo(x=4, y=5) [ap] = z + w; ap++
In many cases it is helpful to let the compiler warn about inconsistencies between the lists of arguments in the function definition and in the function call. For example, if a function argument is added, you may want to get an error if that argument was not passed when the function was called. To allow the compiler to produce that alert, use the following pattern when calling a function:
let args = cast(ap, foo.Args*) args.x = 4; ap++ args.y = 5; ap++ # Check that ap was advanced the correct number of times # (this will ensure arguments were not forgotten). static_assert args + foo.Args.SIZE == ap let foo_ret = call foo
Note that this way you may pass the arguments in any order (for example, pass
Modify the function
fooby renaming the argument
new_x(don’t fix the calling code). Make sure you understand the error.
Do the same for adding/removing an argument from
Using the approach above allows one to do tail recursion efficiently.
Tail recursion refers to the case when a function ends by calling a second
function and immediately returning the output of this inner function without
For example, a function that ends with
return sin(2 * x) uses tail recursion
but a function that ends with
return 2*sin(x) does not.
Use the following pattern in this case:
call inner_func ret
The high-level syntax equivalent of a tail call is
return inner_func(...) (see
return inner_func(x=4, y=5)
in both cases the return values of
inner_func are propagated by the calling function.
Read the following Fibonacci program:
func main(): # Call fib(1, 1, 10). [ap] = 1; ap++ [ap] = 1; ap++ [ap] = 10; ap++ call fib # Make sure the 10th Fibonacci number is 144. [ap - 1] = 144 ret end func fib(first_element, second_element, n) -> (res): jmp fib_body if n != 0 [ap] = second_element; ap++ ret fib_body: [ap] = second_element; ap++ [ap] = first_element + second_element; ap++ [ap] = n - 1; ap++ call fib ret end
Make sure you understand the memory layout, the use of the
fp registers and the idea
of tail recursion return values.
Implement the function \(f(x, n) = x^n\) using the recursion rule \(f(x,n+1)=f(x,n) \cdot x\).
Add code that calls the function with
n=7, run it (if you get the
End of program was not reachederror, increase the number of steps) and verify the result (e.g., by using
--print_memoryor by adding a fake assert instruction
[ap - 1] = 1111and making sure the error says something like
An ASSERT_EQ instruction failed: 128 != 1111).
What is the running time of your program (i.e. exact number of steps as a function of
n)? Guess or calculate first, and then measure it by adding a fake wrong assert and running with
Cairo supports the following syntactic sugar which allows returning values from a function easily:
func foo() -> (a, b): return (<expr0>, b=<expr1>) end
This is equivalent to:
func foo() -> (a, b): [ap] = <expr0>; ap++ [ap] = <expr1>; ap++ ret end
Named arguments are checked against declared return type. Note that compound expressions are supported in the returned values.