Explaining the Qubic Computation Model: part 2

Research & Development Mar 28, 2019

In the first part of this series we have looked at a conceptual overview of the Abra specification, which describes the how dataflow is achieved within the Qubic Computation Model. In this second part, we will use the Abra specification to start implementing Qupla, a higher level programming language for Qubic.  

Qupla is an acronym that stands for Qubic programming language. The goals we are trying to achieve with Qupla are twofold:  

  1. Provide a trinary data flow programming language according to the Abra specification that can function as a higher level programming language for Qubic.
  2. Lower the barrier for programmers to get started with Qubic programming by leveraging existing knowledge as much as possible. This means that we try to keep the language and its behavior as familiar as possible while still providing access to the new and unfamiliar functionality of the Qubic Computation Model.

At first glance, Qupla has a number of things in common with existing programming languages. Some concepts, entities and constructs will look very familiar to programmers, but there are also a few twists that will be completely new. The most obvious new twist, of course, is that Qupla is a trinary programming language.  

Binary systems use bits to represent code and data, where each bit can assume only one of 2 possible values. Larger values can be represented as binary numbers by using a series of bits. The values that a single bit can assume are generally 0 and 1. Larger value of N bits are usually encoded either as unsigned numbers in the range from 0 to (2^N)-1, or as two’s complement signed numbers in the range from -(2^(N-1)) to (2^(N-1))-1.  

Similarly, trinary systems use so-called trits to represent code and data, where each trit can assume only one of 3 possible values. Larger values can be represented as trinary numbers by using a series of trits. Just like with binary numbers, there are 2 ways of representing larger trinary values:  

  • Unbalanced trinary representation, which allows for a single trit to assume the values 0, 1, and 2. Using unbalanced trinary representation a series of N trits can represent unsigned values from 0 to (3^N)-1.
  • Balanced trinary representation, which allows for a single trit to assume the values 0, 1, and -1. Using balanced trinary representation a series of N trits can represent signed values from -((3^N)-1)/2 to ((3^N)-1)/2.
Examples of upper values for representation rangesNote that binary signed values run from -N-1 to NBalanced trinary signed values run from -N to NBits/Upper value (N)tritsBinaryTrinary21433134740515121631364763 10938 127 32809 255 984110 51129524

The Abra specification allows us complete freedom to choose how a trit vector will be interpreted. But a programming language needs to provide a number of standard concepts to be useful. Therefore we have chosen that the Qupla language will interpret a trit vector that represents an integer number as balanced trinary because of certain desirable properties of this representation when using it for math.  

Trit vectors that encode integer numbers are most naturally encoded in Qupla with the least significant trit first. This allows us to extend a value to the same value for a larger trit vector by simply padding the value with enough zero trits at the end. This works for both positive and negative values.

The opposite action, shrinking a larger value to fit in a smaller trit vector, is similarly easy. Just truncate the trit vector to the required size. Of course in this case if any non-zero trits get truncated away the resulting value will become different. But this is unavoidable and similar to what happens when you try to fit a 64-bit integer into a 32-bit integer in binary systems.

Limiting data type sizes to the minimum necessary size for the value range achieves a reduction of energy needs by limiting the amount of circuitry actually needed on FPGAs. Imagine a variable that only needs to be able to represent the values 0–10. With most traditional programming languages you would need to use an 8-bit (0 to 255) byte variable at a minimum, where 4 bits (0 to 15) would have sufficed, and the hardware is designed to manipulate bytes at a time anyway. With Qupla, by following Abra, you can suffice with a trit vector of 3 trits (-13 to 13) instead, and on FPGA you end up with only the circuitry necessary to manipulate 3 trits.

Even though Qupla only has the trit vector as its single built-in data type, it is still possible to define convenient reusable named data types by defining the type name and its size. This way you have an easy way to use a symbolic name for certain fixed-size trit vector sizes and you can use these throughout the Qupla code. The main advantages of this way of indicating trit vector size are that you are programming using concepts instead of hard numbers, and that you only have to change a single location in your code in case it turns out that the trit vector size would need changing.

// define some standard trit lengths we will use in our examples// note that you can define the optimal trit size for any type's// range to reduce energy requirements accordingly, but for// simplicity we'll only define power-of-3 sized types for nowtype Trit[1]// -/+ 1type Tryte [3]// -/+ 13type Tiny[9]// -/+ 9,841type Int[27]// -/+ 3,812,798,742,493type Huge[81]// -/+ 221,713,244,121,518,884,974,// 124,815,309,574,946,401type Hash[243]// standard 81 trytes hash valuetype Hash3 [Hash * 3]type Hash9 [Hash * 9]type Signature [Hash * 27]// define a convenience type to make code more readable// should always be a binary boolean value false or true// (note: this convention is not (yet) enforced by Qupla)type Bool [Trit]

In the above example we have defined several data types that we will use in the examples that follow. The type keyword indicates that what follows is a user-defined trit vector type declaration. Next we specify the name of the user-defined trit vector type, followed by the size of the trit vector type between square brackets. We decided to write it like this in Qupla because of the similarity to how other computer languages specify array/vector sizes.  

Note how a trit vector size can be defined in terms of an earlier defined data type as we do with the Signature data type for example. When using a data type name in an expression that defines the size of a trit vector, the data type name serves as a constant value which represents the size of that data type.  

Also note how we can use constant arithmetic to calculate trit vector sizes like we do with the definition of theHash3,Hash9, and Signature data types in the example above. Qupla supports the C-like operators+,-,*,/, and%in constant expressions.  

Qupla also allows you to construct a named data type for a structured trit vector. A structured trit vector is a trit vector that consists of named sub-vectors. This essentially turns a trit vector into a structure with named fields. This way it is easy to access the sub-vectors without constantly having to keep track of their respective offsets within the main trit vector.

A structured trit vector is represented by a single trit vector that concatenates all sub-vectors. Its total size therefore is the sum of the sizes of all sub-vectors.

type TinyFloat {Tiny mantissa// -/+ 9,841Tryte exponent// -/+ 3^13}

Note how we have defined the sub-vectorsmantissa and exponentin terms of the previously defined data types. The TinyFloats tructured trit vector will therefore have a size ofTiny + Tryteor 12 trits. You can even nest structured trit vectors by defining a structured trit vector as a separate type and then using that type for a field in another structured trit vector. There are no limits on the depth of nesting structured trit vectors.  

At the heart of Abra is the look-up table(LUT). Qupla of course implements LUTs as well, but it adds a little twist. In Abra, a LUT always has a single trit as output. Qupla allows a LUT to have multiple trits as output. Behind the scenes Qupla will map a multi-trit output Qupla LUT to multiple single-trit output Abra LUTs for us.  

A LUT in Qupla is a named table of sequences of 1, 2, or 3 input trit values and one or more corresponding output trit values. When using a LUT in a look-up operation the output trit values are returned as a single trit vector.

All input trit sequences in a LUT must be of exact same length and cannot exceed 3 trits. Each input trit sequence in a LUT must have a unique combination of values. Additionally, all output trit sequences must be of exact same length. Qupla will generate a syntax error if any of these rules are broken.

Any missing combination of input values in the LUT will cause the LUT to return anullvalue for that combination. Note that it is only possible to specify non-null trit vectors for input and output. This means that if any trit in the input vector is null, the resulting output trit vector will automatically be null as well.

This property where a LUT returns null in certain cases can be used to our advantage to implement conditional execution. We will explain this aspect in more detail in a separate section.

LUTs can be used to obviate the need for most common arithmetic and logical operations. These operations are instead implemented as functions that wrap one or more LUT operations.

// LUT logic: return -trit1lut neg {- = 10 = 01 = -}// Abra pseudo-code equivalent:lut 10-10-10-10-10-10-10-10-10- neg_0

In the example above the lut keyword indicates that what follows is a LUT declaration. It is followed by the name of the LUT and one or more LUT entries between curly braces.  

The above negLUT is one of the simplest. It will return a trit that is the negative value of the single input trit. Note how the table consists of a simple enumeration of what trit value to return for every possible input trit value. A balanced trinary number can be made negative very easily by negating each separate trit. So to negate an entire trit vector you would run each separate trit through thenegLUT. On FPGAs this can easily be done in parallel for all trits in the trit vector.  

Note how the Abra equivalent LUT block definition repeats the output values to fill up all the 27 entries in the LUT definition.

// LUT logic: return (Bool) (trit1 == trit2)lut equal {-,- = true-,0 = false-,1 = false0,- = false0,0 = true0,1 = false1,- = false1,0 = false1,1 = true}// Abra pseudo-code equivalent:lut 100010001100010001100010001 equal_0

This slightly more complex equalLUT determines if the two input trits are equal. It returns true when both input trits are equal and false otherwise. Since it always returns true or false the result is essentially a Bool data type. Again, note that this is a simple enumeration of all possible input trit combinations and what trit value to return for each respective input combination.  

// LUT logic: return (Bool) (trit1 != trit2)lut unequal {-,- = false-,0 = true-,1 = true0,- = true0,0 = false0,1 = true1,- = true1,0 = true1,1 = false}// Abra pseudo-code equivalent:lut 011101110011101110011101110 unequal_0

The unequalLUT determines if the two input trits are unequal. It returns false when both input trits are equal and true otherwise. Since it always returns false or true the result is essentially a Booldata type. Although we could achieve the same result by combining the previous equalLUT with a logical notLUT (see further below), the unequalLUT is more efficient because it only needs to do a single look-up.  

// LUT logic: return the sum of two trits as trit plus a carry//return (trit1 + trit2), carry(trit1 + trit2)lut halfAdd {-,- = 1,- // -1 + -1 =1, carry -1-,0 = -,0 // -1 +0 = -1, carry0-,1 = 0,0 // -1 +1 =0, carry00,- = -,0 //0 + -1 = -1, carry00,0 = 0,0 //0 +0 =0, carry00,1 = 1,0 //0 +1 =1, carry01,- = 0,0 //1 + -1 =0, carry01,0 = 1,0 //1 +0 =1, carry01,1 = -,1 //1 +1 = -1, carry1}// Abra pseudo-code equivalent:lut 1-0-0101-1-0-0101-1-0-0101- halfAdd_0lut -00000001-00000001-00000001 halfAdd_1

This half AddLUT demonstrates how multi-trit output values can be achieved. It will simply add the two input trits and return the resulting trit plus a carry. Again, it’s an enumeration of all possible input combinations with their respective outputs. Especially note how all input sizes are the same and how all output sizes are the same.  

The Abra pseudo-code shows how a 2-trit output LUT is converted into two 1-trit output LUTs. We will see in the section about LUT invocation that the code that accesses this LUT automatically invokes both LUTs and concatenates the 2 resulting trits into a single trit vector.

// LUT logic: return (trit1 == true) ? trit2 : null;lut nullifyTrue {true,- = -true,0 = 0true,1 = 1}// LUT logic: return (trit1 == false) ? trit2 : null;lut nullifyFalse {false,- = -false,0 = 0false,1 = 1}// Abra pseudo-code equivalent:lut @@[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@1 nullifyTrue_lut @[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@[email protected] nullifyFalse_

The nullifyTrue and nullifyFalseLUTs demonstrate how we can use missing input trit combinations to our advantage. They will return the second input trit only when the first input trit is true or false, respectively, and they will return null in all other cases. These LUTs will turn out to be pivotal in the way we create Qupla decision logic, because they can be used to create functions that turn an entire trit vector into null if the input condition is not met. You would read a null if yTruelook-up as “nullify the value when the input condition is not true”.  

Qupla will automatically create these two LUTs to support its conditional operator as we will see in the next part of this series.

// ************* BINARY OPERATORS *************// LUT logic: binary NOT//return !trit1lut not {false = true true= false}// LUT logic: binary AND//return (trit1 & trit2)lut and {false, false = falsefalse, true= falsetrue,false = falsetrue,true= true }// LUT logic: binary AND//return (trit1 & trit2 & trit3)lut and3 {false, false, false = falsefalse, false, true= falsefalse, true,false = falsefalse, true,true= falsetrue,false, false = falsetrue,false, true= falsetrue,true,false = falsetrue,true,true= true }// LUT logic: binary OR//return (trit1 | trit2)lut or {false, false = falsefalse, true= true true,false = true true,true= true }// LUT logic: binary OR//return (trit1 | trit2 | trit3)lut or3 {false, false, false = falsefalse, false, true= true false, true,false = true false, true,true= true true,false, false = true true,false, true= true true,true,false = true true,true,true= true }// LUT logic: binary XOR//return (trit1 ^ trit2)lut xor {false, false = falsefalse, true= true true,false = true true,true= false}// LUT logic: binary XOR//return (trit1 ^ trit2 ^ trit3)lut xor3 {false, false, false = falsefalse, false, true= true false, true,false = true false, true,true= falsetrue,false, false = true true,false, true= falsetrue,true,false = falsetrue,true,true= true }// LUT logic: binary NAND//return !(trit1 & trit2)lut nand {false, false = true false, true= true true,false = true true,true= false}// LUT logic: binary NAND//return !(trit1 & trit2 & trit3)lut nand3 {false, false, false = true false, false, true= true false, true,false = true false, true,true= true true,false, false = true true,false, true= true true,true,false = true true,true,true= false}// LUT logic: binary NOR//return !(trit1 | trit2)lut nor {false, false = true false, true= falsetrue,false = falsetrue,true= false}// LUT logic: binary NOR//return !(trit1 | trit2 | trit3)lut nor3 {false, false, false = true false, false, true= falsefalse, true,false = falsefalse, true,true= falsetrue,false, false = falsetrue,false, true= falsetrue,true,false = falsetrue,true,true= false}// LUT logic: binary XNOR//return !(trit1 ^ trit2)lut xnor {false, false = true false, true= falsetrue,false = falsetrue,true= true }// LUT logic: binary XNOR//return !(trit1 ^ trit2 ^ trit3)lut xnor3 {false, false, false = true false, false, true= falsefalse, true,false = falsefalse, true,true= true true,false, false = falsetrue,false, true= true true,true,false = true true,true,true= false}// Abra pseudo-code equivalent:lut @[email protected]@[email protected]@[email protected]@[email protected]@10 not_0lut @@@@[email protected]@@@@[email protected]@@@@[email protected] and_0lut @@@@@@@@@@@@@[email protected]@@@@[email protected] and3_0lut @@@@[email protected]@@@@[email protected]@@@@[email protected] or_0lut @@@@@@@@@@@@@[email protected]@@@@[email protected] or3_0lut @@@@[email protected]@@@@[email protected]@@@@[email protected] xor_0lut @@@@@@@@@@@@@[email protected]@@@@[email protected] xor3_0lut @@@@[email protected]@@@@[email protected]@@@@[email protected] nand_0lut @@@@@@@@@@@@@[email protected]@@@@[email protected] nand3_0lut @@@@[email protected]@@@@[email protected]@@@@[email protected] nor_0lut @@@@@@@@@@@@@[email protected]@@@@[email protected] nor3_0lut @@@@[email protected]@@@@[email protected]@@@@[email protected] xnor_0lut @@@@@@@@@@@@@[email protected]@@@@[email protected] xnor3_0

The above list of LUTs implement the standard binary logic gates and can be used in conjunction with theBooldata type to create logical expressions. They only take theBoolinput tritsfalseandtrueand will return such aBoolas output trit. Any other input is undefined and therefore returns null.

Note the special versionsand3,or3,xor3,nand3,nor3, andxnor3, that can take 3 inputs and perform the logical function on 3 operands at once.

These binary LUTs can be used to specify logical conditions in Qupla expressions. Because aBoolis a single trit these operations can be implemented directly as Abra LUT look-ups and are therefore really fast.

The only types ofnumericconstants that currently can be used in Qupla areintegerliterals andfloating pointliterals. For human convenience both these literals by default utilize standard decimal notation, but it is possible to use binary and hexadecimal integer values by prefixing such values with0band0x, respectively. For example,0b11001000(binary for the decimal value 200), or0x4e20(hexadecimal for the decimal value 20,000). These notations should be familiar to users of many other programming languages.

Qupla also defines the boolean literalsfalseandtrue, that can be used for clarity wherever aBooltype is used. Note that Qupla does not (yet) enforce these boolean types, so it is currently possible to bypass the use offalseandtrueand therefore it is possible to set it to a value that is notfalseortrue.

Finally, Qupla defines trinary literals, which are series of trits or trytes that can be used as constant for any trit vector, by prefixing such values with0t. For example,0t-111-1(trinary for the decimal value 200), or0tKPWCHICGJZXKE9GSUDXZYUQPLHU(a 27-tryte hash value).

Note an important difference between the trinary constants and the other constants. Trinary constants are always specified as big-endian, meaning that leading zeroes are significant and trailing zeroes are irrelevant when specifying a value. Binary, decimal, and hexadecimal constants are always specified as little-endian, meaning that leading zeroes are irrelevant and trailing zeroes are significant. This makes these latter constants human-readable and familiar.

An integer literal will automatically be converted to a trit vector of the minimum length necessary to be able to hold the integer value that represents the balanced trinary value equivalent of the integer value. These literals can be used in any place a trit vector is expected. There is also a comprehensive set of arithmetic functions that is provided by the standard Qupla library that accompanies the language.

When the constant is assigned to a parameter or variable, it will automatically be extended to the size of the assignment target. In this case, a value that is larger than the target size will cause a compilation error. Note that the only limits to an integer literal value are those imposed by the boundaries of the range that the receiving trit vector can represent.

When using constant values for a single trit, we are allowed to shorten the -1 to just the minus character. This means that a single trit can assume the values0,1, and-. You will notice that this will allow us to represent tabular data in much more compact and readable form. The most visible structure in Qupla that uses such tabular data is thelook-up table.

A floating point literal can only be used in places where a floating point type is expected. Floating point arithmetic functions are provided by the standard Qupla library that accompanies the language. Whenever a structured trit vector is encountered that consists of amantissaandexponentfield (which both can have any size), Qupla will allow a floating point literal to be assigned.

Floating point literals will always assume the size of the assignment target. As with integer literals, a value that exceeds either of the structure fields will cause a compilation error, but those are the only limits imposed upon the floating point value.

So now we know that Qupla defines constants. That’s all very nice, but there is nothing in the Abra specification that mentions constants. Remember, Abra is totally agnostic about the meaning of the contents of trit vectors, and it seems that it does not provide a way to specify them, either. So what kind of solution can we come up with to still be able to use this arguably very useful concept in Qupla?

To answer that, we have to think about what Abra describes: data flow. We know that Abra needs to receive input data to be able to transform it into output data. That means that even constants should hold true to that rule and only create the constant value when input data is received. This is our first clue. Abra uses branches with an input vector triggering the output data for the branch. So we need a mechanism that creates a constant value given an input vector, where the input vector could be anything. This is our second clue. Because we have a mechanism that can do just that: the LUT.

Let’s start building the smallest constants first: single trit values. How do we get a constant for a zero trit for example? We’ll need a LUT that returns 0 for any input. All we need to trigger data flow is a single input trit, and for any single input trit to return a 0 output trit, we can use the following Abra LUT definition block:lut 000000000000000000000000000 constZero_. Good! Things are moving forward.

Next challenge: where do we get the triggering input trit from? Well that should be easy. Any branch is triggered by an input trit vector. So why not take the first trit from that input vector as input for the LUT? Now the problem becomes how to take only a single trit from what could be a trit vector of any length. This is where one of the peculiarities of Abra comes in handy. We can define a branch that has only a single trit as input. Remember that in Abra you can pass any size trit vector to a branch, but the branch itself decides what parts to use and what parts to ignore. The branch can use the single trit to invoke the LUT through a LUT knot site, and use that as an output site to immediately return the resulting trit as output trit from the branch. In Abra pseudo-code it looks like this:

lut 000000000000000000000000000 constZero_lut 111111111111111111111111111 constOne_lut --------------------------- constMin_branch const_1_0[1] in trit[1] out ret = constZero_[trit]branch const_1_1[1] in trit[1] out ret = constOne_[trit]branch const_1_T[1] in trit[1] out ret = constMin_[trit]

So here we have 3 branches that can generate the 3 different constant values for a single trit. Now that we have the basic idea we can build it out in several ways. Let’s keep it simple for now. Just have each branch for each constant first set up the constants for zero, one, and min trits as body sites, and then use those as outputs. Remember that multiple outputs will be concatenated, so we can use that to our advantage. All we need is one additional trick. To use a body site as output you can use a merge with only one input. Again, there are other ways of doing this but this one is the straightforward way with our current knowledge. Let’s take the constant value0t-111-1(200) as our example:

branch const_6_T111T1[1] in trit[1] zero = constZero_[trit][1] one= constOne_[trit][1] min= constMin_[trit][1] out ret0 = merge{min}[1] out ret1 = merge{one}[1] out ret2 = merge{one}[1] out ret3 = merge{one}[1] out ret4 = merge{min}[1] out ret5 = merge{one}

Notice how we encode the constant branch name to hold the size and the value. That makes each different constant branch name unique and you immediately know what size and constant it returns.

Notice that in this case we could have left thezerosite out because the constant does not contain a zero and therefore it is not referenced at all. But you don’t have to worry about that in practice. Qupla knows exactly how to create the optimal code for a constant branch for you and do the translation to Abra for you. And even though this may seem like a lot of code for a simple constant, in practice on CPU implementations of Qupla the actual constant trit vector will be cached and referenced directly. On FPGA this will reduce to parallel invocations of the LUT knot sites and all the rest, inputs and outputs, will reduce to simple wiring.

The basic data type in Qupla is the trit vector. We can create user-defined types for specific fixed-sized trit vectors and use constant values that will automatically convert to trit vectors. Another basic entity in Qupla is the look-up table, which is key to the inner working of many of Qupla’s concepts.

In the next part of this series we will delve deeper into how these basic entities are used with Qupla programming language constructs.


IOTA Foundation

Official posts from the IOTA Foundation, and migrated posts from old platforms.