Flip Internal Design

Opcode

This chapter describes the design of opcodes of Flip. It shows first the properties of opcodes and then go through a number of different examples.

Overview

An opcode is an instruction of a transaction. They represent a command that can be executed by the Flip virtual machine.

The Flip virtual machine has a very special property : it can execute programs in different directions, so that if a program is executed and then executed in reverse, the machine will be in the same state.

This property is available at the transaction level, but also at the opcode level.

Properties

Each opcode is designed in a way where it must be inversible.

This means that if that if an opcode Op is defined, then its inverse exist and composing the two functions is identity. However for this to work, opcode are going to restrict their definition domain to keep this property always true.

Restricting the input domain allows to ease the control flow of Flip and make opcode design easier. At the same time it is still quite easy for the operation design to match the end user needs.

When an opcode cannot be executed because the input value does not match the opcode domain definition, it is called a conflict.

Example Design 1

This section shows how a value type is designed. Internally it follows the idea of “compare and swap” : if a value is in a state we assume, then change it to another value.

With the property above, this means that the definition domain is restricted to one element : the value we assume.

For example, Int is modelized Op : A -> B and in the following way when executing :

if value is A
   change to value B
else
   conflict

and the inverse is then :

if value is B
   change to value A
else
   conflict

Example Design 2

Opcodes internally encode a difference. One could think about encoding this into the opcode, so that for a value type like Int, Op : _ -> _ + D where D express the difference of value.

increment value by D

From the Flip point of view, this would have been a perfectly valid design, as long as overflows are correctly managed. The inverse operation is :

increment value by -D

One can see that there are no conflict in this case, so that if two users change the same value at the same time, the value is going to change to the sum of the difference.

Flip does not design the operation this way for multiple reasons :

Example Design 3

With the example above, one could think about encoding the difference and using it as a model for Float. This example is here to show that this would defeat the inversible property of Flip.

increment value by D
increment value by -D

It is easy to see that in many cases (for example adding a very small and a very big number), adding to floating point values is going to lose precision, and therefore lose information. In this case the inversible property of Flip cannot be met.

Example Design 4

This section shows how flip containers are designed.

key/value if key already present, conflict (or inverse wouldn’t work