# Chapter 11

In the previous chapter, we introduced different instructions that manipulate and transform different stores of data like sets, maps and big maps. We learned how to create these stores, how to save new values inside and how to get them out. However, we left aside one of the most powerful features of this type of data. Instead of manipulating the values one by one, what if we'd loop through the whole structure and gain access to all the data at once? 🤯

This chapter is about instructions that will help us manipulate all the values in sets, maps or big maps, whether we want to read those values, use them or modify them. As you will notice throughout the chapter, the instructions we use are sometimes the same and apply to different types, although they may be used differently. This is why you have to remember precisely how the instruction affects the structure on the stack and how the elements must be ordered on the stack before calling the instruction you want.

# The LOOP instruction

Most of widely used programming languages have loops so you may be familiar with the concept. In a nutshell, loops consist of a piece of code that repeats itself until a certain condition is met. This can also be done in Michelson. Here is a very simple example of a loop:

DEBUG False ;
storage unit ;
parameter unit ;
BEGIN Unit Unit ;
DROP ;
PUSH int 0 ;
PUSH bool True ;
LOOP {  
    PUSH int 1 ; 
    ADD ; 
    DUP ;
    PUSH int 5 ;
    CMPNEQ ;
    } ;
DUMP ;
value type
5
int

This is a naive example to demonstrate how loops work. One of the main characteristics of loops is that they "sit" on a boolean value. As long as the boolean value is True, the loop will keep executing the code inside. At the end of the loop, you must have at least a boolean value to tell the loop if it must continue iterating or not.

In this example, we push int 0 to the stack and True before starting the loop. Then, we push int 1, add it to the value present on the stack, duplicate it to keep the value on the stack, push int 5 and compare the 2 values. CMPNEQ checks if the value we got from the addition is not equal to 5. Before we reach 5, the instruction returns True, which keeps the loop iterating. As soon as the value is 5, CMPNEQ returns False and the loop stops.

Loops can become more interesting if you use them with values like lists where you will be able to fetch every element of the list and use them however you want. Let's crank the difficulty up a notch and imagine we want to concatenate all the strings in a list:

DEBUG False;
storage unit ;
parameter unit ;
BEGIN Unit Unit ;
DROP ;
PUSH string "" ;
PUSH (list string) {"hello " ; "world " ; "and " ; "Tezos"} ;
PUSH bool True ;
LOOP { 
    IF_CONS
        { SWAP ; DIP { SWAP ; CONCAT } ; PUSH bool True }
        { PUSH bool False } ;
    } ; 
DUMP ;
value type
"hello world and Tezos"
string

This one is a little more complex as it makes it more difficult to follow the different changes of state of the stack.

Before the loop, the stack is made of three blocks: a bool True block necessary to start the loop, a (list string) containing the strings we want to concatenate together and an empty string we will use for the first concatenation.

On the first iteration, the bool True block is removed from the stack, which exposes the list below. IF_CONS pops the head of the list, pushes the tail onto the stack and pushes the head above if the list is not empty. At this point, the stack is made of a string, a (list string) and the empty string. SWAP puts the two strings next to each other and DIP { SWAP ; CONCAT } concatenates them. We then push bool True to continue the execution of the loop which will end only when the list is empty.

# Iterating on sets

As you remember from the previous chapter, sets are a store of values similar to lists with the major difference of containing only unique values. From the various types we will study in this chapter, sets will probably be the easiest ones to iterate. There is only one instruction available to iterate sets, the ITER instruction. It allows you to loop through a set and run some code at each iteration. Let's check an example to see how it works:

DEBUG True;
storage (set int) ;
parameter unit ;
code {
    CDR ;
    EMPTY_SET int ;
    SWAP ;
    ITER { PUSH int 3 ; ADD ; PUSH bool True ; SWAP ; UPDATE } ;
    NIL operation ;
    PAIR ;
} ;

RUN %default Unit { 1 ; 2 ; 3 };
stdout
storage (set int); parameter unit; code { CDR ; EMPTY_SET int ; SWAP ; ITER { PUSH int 3 ; ADD ; PUSH bool True ; SWAP ; UPDATE } ; NIL operation ; PAIR }; RUN: use %default; drop all; push (Unit, {1, 2, 3}); CDR: pop (Unit, {1, 2, 3}); push {1, 2, 3}; EMPTY_SET: push []; SWAP: pop [], {1, 2, 3}; push []; push {1, 2, 3}; ITER: pop {1, 2, 3}; push 1; PUSH: push 3; ADD: pop 3, 1; push 4; PUSH: push True; SWAP: pop True, 4; push True; push 4; UPDATE: pop 4, True, []; push {4}; push 2; PUSH: push 3; ADD: pop 3, 2; push 5; PUSH: push True; SWAP: pop True, 5; push True; push 5; UPDATE: pop 5, True, {4}; push {4, 5}; push 3; PUSH: push 3; ADD: pop 3, 3; push 6; PUSH: push True; SWAP: pop True, 6; push True; push 6; UPDATE: pop 6, True, {4, 5}; push {4, 5, 6}; NIL: push []; PAIR: pop [], {4, 5, 6}; push ([], {4, 5, 6});
value type
{ 6 ; 5 ; 4 }
set int

As you can see, ITER goes through each element of the set, pushes it to the stack and runs the code provided between brackets. You can either make some calculations with the values and save them in a new set, in which case you have to create an empty set before calling ITER like we did in this example or you can reduce the set, for example:

storage int ;
parameter (set int) ;
code {
    UNPAIR ;
    ITER { ADD } ;
    NIL operation ;
    PAIR ;
} ;

RUN %default { 1 ; 2 ; 3 ; 4 ; 5 ; 6 } 0 ;
stdout
storage int; parameter (set int); code { { DUP ; CAR ; DIP { CDR } } ; ITER { ADD } ; NIL operation ; PAIR }; RUN: use %default; drop all; push ({1, 2, 3, 4, 5, 6}, 0); DUP: push ({1, 2, 3, 4, 5, 6}, 0); CAR: pop ({1, 2, 3, 4, 5, 6}, 0); push {1, 2, 3, 4, 5, 6}; DIP: protect 1 item(s); CDR: pop ({1, 2, 3, 4, 5, 6}, 0); push 0; restore 1 item(s); ITER: pop {1, 2, 3, 4, 5, 6}; push 1; ADD: pop 1, 0; push 1; push 2; ADD: pop 2, 1; push 3; push 3; ADD: pop 3, 3; push 6; push 4; ADD: pop 4, 6; push 10; push 5; ADD: pop 5, 10; push 15; push 6; ADD: pop 6, 15; push 21; NIL: push []; PAIR: pop [], 21; push ([], 21);
value type
21
int

In this example, the initial storage set to 0 works as an accumulator and each value in the set is added to the accumulator.

# Iterating on maps

Like lists or sets, maps are a type a value that can be iterated, which means that it is possible to loop through all the key/value pairs, to have access to them or to modify them. Two different instructions exist in Michelson to loop through maps. The first one, ITER, loops through the map and return a pair containing the element on the left and the value on the right:

storage (set string) ;
parameter (map string string) ;
code {
    CAR ;
    EMPTY_SET string ;
    SWAP ;
    ITER { CAR ; PUSH bool True ; SWAP ; UPDATE } ;
    NIL operation ;
    PAIR ;
} ;

RUN %default { Elt "cherry" "red" ; Elt "banana" "yellow" ; Elt "apple" "green"} {} ;
stdout
storage (set string); parameter (map string string); code { CAR ; EMPTY_SET string ; SWAP ; ITER { CAR ; PUSH bool True ; SWAP ; UPDATE } ; NIL operation ; PAIR }; RUN: use %default; drop all; push ({'cherry': 'red', 'banana': 'yellow', 'apple': 'green'}, set()); CAR: pop ({'cherry': 'red', 'banana': 'yellow', 'apple': 'green'}, set()); push {'cherry': 'red', 'banana': 'yellow', 'apple': 'green'}; EMPTY_SET: push []; SWAP: pop [], {'cherry': 'red', 'banana': 'yellow', 'apple': 'green'}; push []; push {'cherry': 'red', 'banana': 'yellow', 'apple': 'green'}; ITER: pop {'cherry': 'red', 'banana': 'yellow', 'apple': 'green'}; push ('cherry', 'red'); CAR: pop ('cherry', 'red'); push cherry; PUSH: push True; SWAP: pop True, cherry; push True; push cherry; UPDATE: pop cherry, True, []; push {'cherry'}; push ('banana', 'yellow'); CAR: pop ('banana', 'yellow'); push banana; PUSH: push True; SWAP: pop True, banana; push True; push banana; UPDATE: pop banana, True, {'cherry'}; push {'cherry', 'banana'}; push ('apple', 'green'); CAR: pop ('apple', 'green'); push apple; PUSH: push True; SWAP: pop True, apple; push True; push apple; UPDATE: pop apple, True, {'cherry', 'banana'}; push {'cherry', 'banana', 'apple'}; NIL: push []; PAIR: pop [], {'cherry', 'banana', 'apple'}; push ([], {'cherry', 'banana', 'apple'});
value type
{ "apple" ; "banana" ; "cherry" }
set string

This contract accepts a map of type (map string string) and returns a set of type (set string) with the names of the fruits. As you can see, ITER takes as a parameter a piece of code that will act on the pair of key/value pushed to the stack. The name of the fruit is extracted (CAR), a value of type bool is pushed onto the stack (PUSH bool True) before being swapped (SWAP) to be set in the order to update the the set of strings (UPDATE).

ITER is an instruction that allows you to get the keys and values out of the map and manipulate them. However, it doesn't affect the original map. If you want to change the values of a map in a deterministic way, you can use MAP. Like ITER, MAP loops through a map but its values will be modified by the code you write between curly braces. Here is an example:

storage (map string nat) ;
parameter (map string nat) ;
code {
    CAR ;
    MAP { CDR ; PUSH nat 5 ; ADD } ;
    NIL operation ;
    PAIR ;
} ;

RUN %default { Elt "cherry" 16 ; Elt "banana" 24 ; Elt "apple" 32} {} ;
stdout
storage (map string nat); parameter (map string nat); code { CAR ; MAP { CDR ; PUSH nat 5 ; ADD } ; NIL operation ; PAIR }; RUN: use %default; drop all; push ({'cherry': 16, 'banana': 24, 'apple': 32}, {}); CAR: pop ({'cherry': 16, 'banana': 24, 'apple': 32}, {}); push {'cherry': 16, 'banana': 24, 'apple': 32}; MAP: pop {'cherry': 16, 'banana': 24, 'apple': 32}; push ('cherry', 16); CDR: pop ('cherry', 16); push 16; PUSH: push 5; ADD: pop 5, 16; push 21; pop 21; push ('banana', 24); CDR: pop ('banana', 24); push 24; PUSH: push 5; ADD: pop 5, 24; push 29; pop 29; push ('apple', 32); CDR: pop ('apple', 32); push 32; PUSH: push 5; ADD: pop 5, 32; push 37; pop 37; push {'cherry': 21, 'banana': 29, 'apple': 37}; NIL: push []; PAIR: pop [], {'cherry': 21, 'banana': 29, 'apple': 37}; push ([], {'cherry': 21, 'banana': 29, 'apple': 37});
value type
{ Elt "cherry" 21 ; Elt "banana" 29 ; Elt "apple" 37 }
map string nat

This piece of code loops through the map and at every iteration, a pair containing the key on the left and the value on the right is pushed onto the stack. The value is extracted from the pair and 5 is added to it. The difference with ITER is that the value remaining at the end is the one that will be saved back in the map as the new value for the current key. Obviously, this value must be of the same type as the type of the other values in the map.

NOTE

Iterating on big maps is not possible from Michelson. The reason is that big maps are lazily deserialized to save on gas cost and the contract is not aware of all the key/value pairs in a big map as they are deserialized on demand one by one.

add add