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 ()
end

The lines 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:

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 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 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:

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 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, 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
17       17
18       7
19       1000
20       17
21       9
22       1000
23       17
24       11
25       1000

When main starts, the value of fp is 17, and the program calls the first invocation of foo, writing the current value of fp (17) and value of the program counter to return to (7). foo writes 1000 to the memory. The instruction ret restores the value of fp back to 17 and then jumps to pc = 7. 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__ = 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, w):
    [ap] = x + y; ap++  # z.
    [ap] = x * y; ap++  # w.
    ret
end

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 constants named foo.Return.z and foo.Return.w 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 as follows let foo_ret : foo.Return = ap. 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 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

  1. Modify the function foo by renaming the argument x to new_x (don’t fix the calling code). Make sure you understand the error.

  2. 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
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 ap and fp registers and the idea of tail recursion return values.

Exercise

  1. Implement the function \(f(x, n) = x^n\) using the recursion rule \(f(x,n+1)=f(x,n) \cdot x\).

  2. 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).

  3. 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, 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.