NEWTON

NEWTON


Popular tags

    Cairo Lang / StarkNet: What are Revoked references? What is alloc_locals?

    Asked

    4 months ago

    161

    views


    0

    Hello! This is day 5 of the 17 days of the Cairo Challenge. And I have no idea how to solve the playground exercise “Revoked references”. Can you run these 6 steps and write down what you see?

    // The scope of some types of references in Cairo (e.g., return values of
    // functions and temporary variables) is somewhat restricted.
    // For example, a call to another function may revoke those references.
    //
    // 1. Try to run the following code. You should get an error that `x` was revoked
    //    (this is because of the second call to `foo`).
    // 2. In simple cases, like this one, the compiler can solve this automatically
    //    if the "alloc_locals" keyword is used within the function's scope.
    //    Add "alloc_locals;" to the beginning of main(), and make sure the code works.
    // 3. To understand what happens behind the scenes, replace "alloc_locals;" with
    //    "ap += SIZEOF_LOCALS;" - this command allocates memory cells for local variables
    //    (you'll need them below) but doesn't enable the mechanism that
    //    automatically resolves revoked references.
    //    Trying to run the code now should result in the original error.
    // 4. Solve the problem manually by copying the value of `x` to a local variable
    //    (e.g., "local x2 = x;"). Local variables are not revoked when functions
    //    are called.
    //    You can read more about local variables [here](https://www.cairo-lang.org/docs/how_cairo_works/consts.html#local-vars).
    // 5. You can even use the same name: "local x = x;".
    //    This is called "reference rebinding", where the meaning of `x` changes:
    //      Before this line, `x` refers to the return value.
    //      After that, `x` refers to the local variable.
    // 6. A shorter syntax is "let (local x) = foo(10);" which achieves the same goal.
    //    Try it!
    
    %builtins output
    
    from starkware.cairo.common.serialize import serialize_word
    
    // Returns a^3 for a != 0 and 1 otherwise.
    func foo(a) -> (res: felt) {
        if (a == 0) {
            return (res=1);
        } else {
            return (res=a * a * a);
        }
    }
    
    // Outputs the value 10^3 + 5^3.
    func main{output_ptr: felt*}() {
        let (x) = foo(10);
        let (y) = foo(5);
        serialize_word(x + y);
        return ();
    }
    

    Answers to this question are a part of the ✨ 17 days of Cairo Lang with Playground & Newton. ✨

    Vote for your favorite answer - the best answer will win a $10 award. A new day – a new reward! During the next 17 days, our goal is to attract more developers to the Cairo language and to systematize the knowledge of Cairo lang. Read rules

      #17daysOfCairocairo-beginnerscairoplayground

    Newton

    asked

    4 months ago


    3 answers

    4

    Accepted answer

    Solution

    Steps:

    1. Output while running the whole code:
    Error: code:18:20: Reference 'x' was revoked.
        serialize_word(x + y);
                       ^
    Reference was defined here:
    code:16:10
        let (x) = foo(10);
             ^
    

    Explanation of error if there is a call to another function 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. Source: Cairo docs

    2 Adding "alloc_locals" to the beginning of main()

    In simple cases the issue can be resolved by adding the keyword, alloc_locals within function scopes, but in most complex cases you might need to create a local variable to resolve it.

    func main{output_ptr: felt*}() {
     alloc_locals;
     let (x) = foo(10);
        let (y) = foo(5);
        serialize_word(x + y);
        return ();
    }
    

    Code run successfully

    3 Replace "alloc_locals" with "ap += SIZEOF_LOCALS;"

    Same error returned

    Cairo provides the instruction alloc_locals which is transformed to ap += SIZEOF_LOCALS but doesn't enable the mechanism that automatically resolves revoked references.

    4 and 5 Solve the problem manually by copying the value of x to a local variable

    func main{output_ptr: felt*}() {
      ap += SIZEOF_LOCALS;
      let (x) = foo(10);
      local x2 = x; // or local x = x; 
      let (y) = foo(5);
      serialize_word(x2 + y); // or serialize_word(x + y) ,when local x = x
      return ();
    }
    

    "local x = x": Reference Rebinding which means hat different expressions may be assigned to the same reference.

    6 Using Shorter syntax

    func main{output_ptr: felt*}() {
      ap += SIZEOF_LOCALS;
    let (local x) = foo(10);  
      let (y) = foo(5);
    
      serialize_word(x + y);
      return ();
    }
    

    Code Run successfully

    Extra Points: Unlike temporary variables (variables created using the tempvar and let keywords) which are based on ap registers, Local variables are based on the fp** **register, and as such, not easily revoked.

    Registers to understand better what's going behind the scenes

    Program counter (pc) contains the address in memory of the current Cairo instruction to be executed.

    Allocation pointer (ap) , by convention, points to the first memory cell that has not been used by the program so far.

    Frame pointer (fp) points to the beginning of the stack frame of the current function. The value of fp allows a stack-like behavior: When a function starts, fp is set to be the same as the current ap, and when the function returns, fp resumes its previous value. Thus, the value of fp stays the same for all the instructions in the same invocation of a function.

    Source: Cairo whitepaper

    Final Working code using shorter syntax

    %builtins output
    
    from starkware.cairo.common.serialize import serialize_word
    
    // Returns a^3 for a != 0 and 1 otherwise.
    func foo(a) -> (res: felt) {
        if (a == 0) {
            return (res=1);
        } else {
            return (res=a * a * a);
        }
    }
    
    // Outputs the value 10^3 + 5^3.
    func main{output_ptr: felt*}() {
      ap += SIZEOF_LOCALS;
      let (local x) = foo(10);  
      let (y) = foo(5);
    
      serialize_word(x + y);
      return ();
    }
    
    

    Ishita Rastogi

    answered

    4 months ago

    0

    Revoke reference means compiler has lost the reference to the location we want to access. In this example, reference to the location where x has been stored is lost.

    When we use alloc_locals, then reference to local variables are fixed and are in relation to frame pointer fp. First variables location is [fp + 0], next local variable reference is [fp + 1] and so on, and compiler does not lose the reference to local variables.

    The solution Ishita Rastogi has mentioned all result in compiler not losing the reference to the variables in the program.

    I don’t recommend using low level programing constructs (ap, fp and such) to beginners. I am also a beginner. I hope Cairo compiler will mature over time and will to better optimization.

    The program below does not give revoked reference issue, since reference to x is not lost (function foo is not called again).

    In the original program, since function foo is called again, and “alloc_locals” was not used, compiler lost the location of x.

    ======================================================================

    %builtins output

    from starkware.cairo.common.serialize import serialize_word

    // Returns a^3 for a != 0 and 1 otherwise. func foo(a) -> (res: felt) { if (a == 0) { return (res=1); } else { return (res=a * a * a); } }

    // Outputs the value 10^3 + 5^3. func main{output_ptr: felt*}() { let (x) = foo(10); let y = 5; serialize_word(x + y); return (); }

    ============================================================

    Below are my notes when I was dealing with issue of “Reference 'syscall_ptr' was revoked” while solving one of the exercise from ZKP Boot Camp

    If..else statement in Cairo.

    • Seems like we need to put return statements (example below) inside if…else statements, else we get revoked references issue  Reference 'syscall_ptr' was revoked

    @external func bombard{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr, bitwise_ptr: BitwiseBuiltin*}(game_idx : felt, x : felt, y : felt, square_reveal : felt):

    alloc_locals
    
    #get address of the caller
    let (caller) = get_caller_address()
    ### some logic
    ### some logic
    ### some logic
    
    ### now some complex if...else logic
    if current_game.next_player == 0:
        ### logic
        ### logic
        ### logic
        return () ### --> pay attention
    else:
    ### logic
        ### some logic
        ### some logic
        ### some logic
        ### some logic
        if hit_by_prev_player == 1:
            if caller == current_game.player2.address:
                ### some logic
                ### some logic
                ### some logic
                ### some logic
                return ()   ### --> pay attention
            else:
                ### some logic
                ### some logic
                ### some logic
                return ()   ### --> pay attention
            end
        end
    end
    
    return()
    

    end

    1

    Here is the solution after following the instructions and testing with "ap +=" command.

    %builtins output

    from starkware.cairo.common.serialize import serialize_word

    // Returns a^3 for a != 0 and 1 otherwise. func foo(a) -> (res: felt) { if (a == 0) { return (res=1); } else { return (res=a * a * a); } }

    // Outputs the value 10^3 + 5^3. func main{output_ptr: felt*}() { ap += SIZEOF_LOCALS; let (local x) = foo(10); let (local y) = foo(5); serialize_word(x + y); return (); }

    answered

    4 months ago

    Your answer

    NEWTON

    NEWTON