Explaining the Qubic Computation Model: part 3

Research & Development Mar 29, 2019

In the first part of this series we have looked at a conceptual overview of the Abra specification, which describes the how data flow is achieved within the Qubic Computation Model. In the second part we used the Abra specification to start implementing Qupla, a higher level programming language for Qubic. We introduced Qupla’s most basic entities (trit vectors, look-up tables, and constants) and how they map to Abra. This third part will introduce how we can use functions and expressions to create Qupla programs.  

The basic entities that make up a Qupla program are (user-defined) trit vectors, constants, and look-up tables (LUTs). These entities will be used as components in expressions that describe how to transform input values into output values by having the input values processed by Qupla’s programming constructs. Expressions in turn can be grouped into functions to achieve more complex tasks.  

A Qupla function is a named group of expressions that describe how to transform input data into output data. A function will take one or more trit vectors as parameters, and always returns a trit vector holding the result value of the transformation. Qupla functions, as is the case with most functional languages, are pure functions.  

A pure function is a function that defines a unique relation between the input values and the return value. This means that calling a function multiple times with the same input values will always produce the same return value. There are no side effects that could cause the function to produce different return values for the same input values. Eliminating such side effects makes it much easier to understand and predict the behavior of a function and reason about the correctness of the function.  

An additional advantage of pure functions is that any of their expressions that have no data dependency between them within the function can be executed in any order, or even in parallel. This gives the compiler freedom to reorder or combine the evaluation of these independent expressions. When compiling for FPGA the ability to run all these independent expressions in parallel will result in highly efficient program execution.

The opposite of a pure function, of course, would be a function that does not necessarily return the same value when invoking it multiple times with the same input values. Such a function can have one or more internal state variables that may influence the function return value differently for each invocation. Due to the potential side effects that state variables can cause it is much harder to reason about the correctness of such an impure function.  

Impure functions have their own role in programming, because it is often important to express the state of a program. Take a key/value store for example. It stores a value under a certain key. The retrieve function uses the key to retrieve the stored value. Note that because it is possible to overwrite the value stored under a key with any new value, and the return value of the retrieve function will always return the last stored value, the returned value of the retrieve function can differ for the same input key value.

Qupla, through Abra, deals with function state variables in a very specific way to alleviate this problem. When a function is called, the value of the state variable at the moment of calling is ‘fixed’ for the duration of the function call. This means that any expression that uses the state variable anywhere in the function will use the same value, even when some expression inside the function expresses changes to the state variable. That change will only take effect on the state variable after the function return value has been calculated.

By doing things this way, state variables look like hidden input values to the function, and given the same set of input parameter values and state variable values the function return value will always be the same. Even the new values for the state variables will always be the same given the same combination of input and state values. From the viewpoint of the function it can be seen as pure again, which means it can be reasoned about and reorganized just like any stateless pure function.

Qupla expressions are made up of a very limited number of basic operations. These operations can be combined in different ways to express the intent for the expression. There are only five basic operations in Qupla from the programmer’s viewpoint:

  • Call, which calls a predefined function with a given number of input parameters and evaluates to the return value associated with those input values.
  • Look-up, which looks up a given combination of input trits in a specific LUT and evaluates to the corresponding LUT output value.
  • Slice, which evaluates to a sub-vector slice taken from a given input trit vector at a given offset and size within that trit vector.
  • Concatenate, which evaluates to a single trit vector made up of the concatenation of multiple given input trit vectors.
  • Merge, which evaluates to the single non-null trit vector from several given equal-sized input trit vectors.

Notice how there are none of the usual arithmetic, logical, or conditional operations in Qupla. Such functionality can be created of course, but they are all expressed in terms of the above five operations by using functions and/or LUTs that combine to implement the desired functionality. We will discuss each of these operations in more detail later in a separate article, but first we will discuss how a function in Qupla is defined, so that we can show how the operations can be used as part of expressions within functions.

Functions in Qupla -just like in most programming languages- consist of two parts: the function signature and the function body. The function signature describes the function name, the exact parameters the function expects to be called with, and it also describes the exact return typeof the function. In addition it is possible for a function to have type specifiers.  

The function signature is like a contract specification for the function. It provides anyone that wants to call the function with enough information to do so without having to know its internal workings. Lets look at an example:

func Int square (Int value) {return multiply(value, value)}

On the first line you see the function signature. The func keyword indicates that what follows is a function declaration. Next we see that the function returns an Intsized trit vector. Then the name of the function is declared assquare, followed by a single function parameter declaration within parentheses. In this case, the function parameter is an Intsized trit vector named value. Qupla expects parameter values to be an exact match to the size of the declared parameter. The only exception to that is when a constant value is passed in as a parameter. Constant values are allowed to be smaller than the parameter and will silently be padded with zeroes to the correct size.  

Between the curly braces you see the function body. This one contains a single expression that will be evaluated by the function when it is called, by substituting the parameter names with the values passed in for these parameters. The return directive indicates that the result of the subsequent expression after evaluation is returned to the function caller.  

In this case we see that the expression calculates the square of the value that was passed in by multiplying the value by itself. This is done by calling another function called multiply that handles the multiplication of two values. Note that because Qupla has no arithmetic operators like the ones found in other computer languages any arithmetic will be done by calling predefined arithmetic functions.  

Also note that for this to work correctly the function signature for the multiply function will have to look like this:  

func Int multiply (Int lhs, Int rhs)

This function signature declares two parameters between the round braces, separated by a comma. We will ignore the implementation of the multiply function for now. You can find out exactly how multiplication is done in Qupla by examining the multiplication code in the standard library that we provide with Qupla.

One thing we have not discussed yet is the aforementioned function type specifiers. Here’s why we need it and what it does. Imagine we have the following two functions:

func Int square (Int value) {return multiply(value, value)}func Huge square (Huge value) {return multiply(value, value)}

Notice how the only difference between the two is the size of the trit vector they operate on? The first one operates on the 27-tritInttrit vector, and the other on the 81-tritHugetrit vector. This is something we will be encountering a lot in Qupla: functions that are married to a certain trit vector size. Due to fact that trit vectors always have a fixed size, it is not easy to create a single function that can deal with various differently sized trit vectors. It usually means that we will need to create a function for each different trit vector size we want to support. But in that case, the above lines will cause a duplicate function name error because Qupla will not be able to determine what the intended usage is when someone callssquare(100)for example.

Of course it would be possible to change the names of the functions to something like this:

func Int squareInt (Int value) {return multiplyInt(value, value)}func Huge squareHuge (Huge value) {return multiplyHuge(value, value)}

See how we now distinguish between functions that are meant for different types by adding the type name to the function name? But there are a few problems with that approach. It means you will have to write every single function that depends on a certain type you ever want to use separately. In a lot of cases the code of such functions is pretty much identical, like above, but you will have to edit every instance of the type to the correct one. Which can be error prone and time consuming. And imagine you want to change the name of a type you use, you would have to change the name of every instance where that type is used to reflect the new name.

In addition, there can be different types that have the same size which could be served by the same function. Imagine we defineInt27to be the same size asInt. In that case I could reuse the functions defined for theInttype, but I would have to either create versions forInt27that call the Intversions, or come up with a different naming scheme. That all sounds a bit too contrived.  

That’s why we can declare type specifiers associated with a function. The type specifiers are only used to distinguish between similar functions that have incarnations for different types. Otherwise the type specifiers can be omitted. It looks like this:

func Int square<Int> (Int value) {return multiply<Int>(value, value)}func Huge square<Huge> (Huge value) {return multiply<Huge>(value, value)}

See how instead of concatenating the type name to the function name we now add a modifier between angular braces? The function names are still the same, but we can easily change the name of the type now without having to change the function names. We can also reuse a function for a same-size type.multiply<Int>(value, value)will call the same multiply function as multiply<Int27>(value, value).  

Qupla will, behind the scenes, create a modified function name by appending a special separator character and the type size to the name for each type specifier. Qupla does not allow the programmer to create function names that contain that special separator character, so it is impossible to accidentally create a name like that. Note that in our examples we only used a single type specifier, but there are cases where you need more than one and Qupla supports that.

Of course, type specifiers do not resolve the repetitive code for every trit vector type size yet. Qupla has another trick up its sleeve to deal with that situation: the template.  

In the previous example, we saw that we created two square functions that only differed in their trit vector size. Using templates we can declare such a function in a single location as follows:  

template square<T> {func T square (T value) {return multiply<T>(value, value)}}

The template keyword indicates that what follows is a template declaration. The template has a name, in this casesquare (just like the function), that can be used to instantiate functions for different types. The T between angular braces directly after the template name is called the type placeholder. As you can see we put the function declaration inside the template and replaced the original Inttype everywhere it was used with the T placeholder.  

We can now manually instantiate specific functions explicitly as follows:

use square<Int>use square<Huge>

The use keyword indicates that what follows is a template instantiation declaration. It instantiates a template for a specific set of types. In this case we instantiate two square functions, complete with their implementation, from the square template. The end result is as if we typed the separate function declarations forsquare <Int> andsquare <Huge>just like we did a few paragraphs back.  

Using templates allowed us to define a standard library of functionality for the Qupla language that works on the predefined types we discussed in the previous part of this series. We have used it to implement an assortment of generic arithmetic functions that can work on almost any trit vector size and predefined them for the convenient Tryte, Tiny, Int, and Hugetrit vectors. Any additional necessary functions for not-yet defined trit vector sizes can often simply be instantiated as needed with a specific use statement.  

As it turns out, explicit template instantiation through the use statement can become very tedious when other templates are referenced. It can cause the need for a cascade of use statements. Therefore Qupla attempts to do it for you. Whenever you use a function that has a type specifier Qupla will check the list of templates to see if any of them defines that function and automatically instantiate the template if necessary. It will do this recursively, so that any templated functions that are used within the instantiated function will be automatically instantiated as well.  

This means, that in most cases, the explicit use statement is not necessary any more. You only use it when you want to be absolutely sure that a template has been explicitly instantiated, for example when you create a module of library functions.  

In the previous examples the function body was specified as a single return expression. In practice, only the simplest functions will be specified by a single return expression. Most functions will need more than one expression to be able to achieve the correct result. Especially when decision logic enters the mix.

For now we will keep things simple and only use expressions that use function calls. We will also assume that every function operates on the Int type, so that we don’t need to provide any type specifiers. That way we avoid the added complexity of different constructs. Look at the following function that implements the well-known Pythagoras algorithm. It calculates c from a given a and b using the formulaa * a + b * b = c * c. We can write this as follows:  

func Int pythagoras (Int a, Int b) {return squareRoot(add(multiply(a, a), multiply(b, b)))}

However, expressing it in a single line of code quickly becomes hard to read, especially because function calling order goes from innermost to outermost. It does not read naturally for a human. That is why we will improve readability by separating out the function calls and assigning their values to temporary variables, like this:

func Int pythagoras (Int a, Int b) {aSquared = multiply(a, a)bSquared = multiply(b, b)sum = add(aSquared, bSquared)return squareRoot(sum)}

Note that temporary function variables in Qupla have an important property. They follow the Static Single Assignment(SSA) form. SSA requires that each variable is assigned exactly once, and that every variable is defined before that single use. The primary usefulness of SSA comes from how it simultaneously simplifies and improves the results of a variety of compiler optimizations. SSA is also an important element in the implementation of dataflow in Qupla.  

Qupla enforces SSA by having each expression assigned to a new, implicitly declared variable. That variable’s trit vector size will always be equal to the size of the assigned expression result. In addition each variable or parameter name must be unique within the function.

There is one exception to the implicit variable declaration rule and that is when a function declares one or more state variables. State variables are always declared first within the function body, before any assignment expressions, and they are always implicitly initialized to zero. Take the following example:  

func Int runningTotal (Int value) {state Int sumnewSum = add(sum, value)sum = newSumreturn newSum}

This function declares a state variable named sum of sizeInt, and uses that to calculate a running total sum of the values passed in each successive call and returns that running total.  

You can see that the declaration of and the assignment to the state variable sumare separate. However, this still follows SSA in that the declaration precedes the assignment, and the state variable is only allowed to be assigned to once in the function body. The size of the assigned expression must match the size declared in the state variable declaration.  

Also remember from our earlier explanation that wherever in the function body the state variable is used, it will use the value that it had at the start of the function call. And even though the state variable necessarily is assigned an expression before the return statement, that value will only be actualized in the state variable after the return statement has been executed.  

One peculiarity of state variables is that their trits cannot hold null values. This has to do with their implementation on FPGA devices. Their value is held by the registers at the end of LUT circuitry. And since null means ‘no value’ it is impossible for those registers to hold this value. What happens when you try to write a trit vector that contains null trits into a state variable is that the trits that are non-null get stored in their state variable counterparts, but the trits that are null will cause no change to the value of their state variable counterparts. In the extreme case where the entire trit vector is null as you try to store it in a state variable, that state variable will remain unchanged entirely.

Qupla functions are made up of one or more expressions. Functions can be analyzed as pure function even when they have state associated with them. Similar functions that operate on different types can be distinguished by using a type specifier, and templates remove the need for cloning functions for each of those different types.

In the next part of this series we will explore the basic operations that can be used in Qupla expressions.


IOTA Foundation

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