Functions¶

Introduction¶

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 ret. In addition, the Cairo compiler supports high-level syntax for those instructions: foo(...) and return (...) respectively.

A function is declared as follows:

func function_name() {
    // Your code here.
    return ();
}

The lines func function_name() { and } 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:

call function_name;

or the high-level syntax:

function_name();

The full syntax of call is similar to jmp: you can call a label (a function is also considered a label), and make a relative or absolute call (call rel/abs ...).

The fp register¶

When a function starts the frame pointer register (fp) is initialized to the current value of 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 fp changes when bar starts but is restored when bar ends.

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.

Exercise¶

Compile and run (with at least 10 steps) the following code. Use the --print_memory and --relocate_prints flags for cairo-run.

func main() {
    call foo;
    call foo;
    call foo;

    ret;
}

func foo() {
    [ap] = 1000, ap++;
    ret;
}

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 ret instruction (which of the registers ap, fp, 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, return_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
+--------------+
|      ...     |

Example¶

Look at the memory values after running the program above:

Address  Value
     13
     3
     1000
     13
     5
     1000
     13
     7
     1000

When main starts, the value of fp is 13, and the program calls the first invocation of foo, writing the current value of fp (13) and value of the program counter to return to (3). foo writes 1000 to the memory. The instruction ret restores the value of fp back to 13 and then jumps to pc = 3. Then foo is called a second time. Make sure you understand the rest of the memory values.

Bonus Exercise¶

Use the information given in the last section, in order to write a piece of code that when executed puts the current values of ap, fp and pc in memory (say, write ap into [ap], fp into [ap + 1] and pc into [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 of 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__: felt* = 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 x and y and returns their sum z and product w:

func foo(x, y) -> (z: felt, w: felt) {
    [ap] = x + y, ap++;  // z.
    [ap] = x * y, ap++;  // w.
    ret;
}

Arguments¶

Arguments are written to the “stack” before the call instruction. For example, to call foo(4, 5) you should write:

[ap] = 4, ap++;  // x.
[ap] = 5, ap++;  // y.
call foo;

The instruction 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 x.

Cairo supports the following syntactic sugar to call a function, which also supports compound expressions:

foo(x=4, y=5);

Return values¶

The function writes to the stack its return values just before the ret instruction. 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 a type definition named foo.Return with the return type: (z: felt, w: felt). In fact, one may define a typed reference as follows: let foo_ret = [cast(ap - 2, foo.Return*)];. Now, you can access z as foo_ret.z.

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 - 2) 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 syntax let (z, w) = foo(x=4, x=5); assigns foo’s return values to z and w, respectively:

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++;

Named arguments¶

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 y before x).

Exercise¶

Modify the function foo by renaming the argument x to new_x (don’t fix the calling code). Make sure you understand the error.
Do the same for adding/removing an argument from foo.

Tail recursion¶

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 any modification. 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 tuple):

return inner_func(x=4, y=5);

in both cases the return values of inner_func are propagated by the calling function.

Exercise¶

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;
}

func fib(first_element, second_element, n) -> (res: felt) {
    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;
}

Make sure you understand the memory layout, the use of the ap and fp registers and the idea of tail recursion return values.

Exercise¶

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 x=2, n=7, run it (if you get the End of program was not reached error, increase the number of steps) and verify the result (e.g., by using --print_memory or by adding a fake assert instruction [ap - 1] = 1111 and 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 --debug_error --print_info

Return tuple¶

Cairo supports the following syntactic sugar which allows returning values from a function easily:

func foo() -> (a: felt, b: felt) {
    return (a=<expr0>, b=<expr1>);
}

This is equivalent to:

func foo() -> (a: felt, b: felt) {
    [ap] = <expr0>, ap++;
    [ap] = <expr1>, ap++;
    ret;
}

Named arguments are checked against declared return type. Note that compound expressions are supported in the returned values.

Functions¶

Introduction¶

The fp register¶

Exercise¶

Under the hood¶

Example¶

Bonus Exercise¶

Accessing the values of the registers¶

Function arguments and return values¶

Arguments¶

Return values¶

Return values unpacking¶

Named arguments¶

Exercise¶

Tail recursion¶

Exercise¶

Exercise¶

Return tuple¶

Cairo

Navigation

Related Topics