As discussed in Part 1, OR-causality is a useful and important part of specifying circuits, and with our recently released tool (https://github.com/tuura/concepts), we needed to include OR-causality in the translation from concepts to STGs.

To include this in the tool, we needed to design an algorithm which can take OR-causality, and seamlessly use it in conjunction with standard AND-causality.

This part will detail our algorithm. Our tool is written in Haskell, and while some of the algorithm is based on Haskell constructs, we will aim to use pseudo code to describe this algorithm.

OR-causality, an algorithm

For an example to explain this, we will use Example 2 from Part 1 of this post, an OR-Gate with a single AND-causality. This will display well OR- and AND-causality interaction.

Let’s just remind ourselves of the concepts for this:

circuit  = orGate a b c ⋄ buffer d c

This can also be described using signal-level concepts:

circuit = [a+, b+] ~|~> c+ ⋄ a- ⇝ c- ⋄ b- ⇝ c- ⋄ d+ ⇝ c+ ⋄ d- ⇝ c-

The first thing we need to think about is how we store this information. As we said in Part 1, OR-causality is described by listing the possible causes for a single effect, for example from:

[a+, b+] ~|~> c+

We can see that a+ and b+ are the possible causes for the c+ effect transition.

Therefore, we can list OR-causality as a list of causes for each effect. However, this will cause issues when there is more than one list of OR-causality causes for a single effect, but we will discuss this later.

This also causes an issue with AND-causality causes, as we cannot simply add these to the list of OR-causality causes, as this would change the type of causality from AND to OR.

To solve this problem, we treat each type of causality as a separate list, where OR-causality is a list of at least two causes, and AND-causality is a list with a single cause. These are stored with the corresponding effect to the causality. So, for c+ in this example, we would store:

Causes: [a+, b+] & Effect: c+
Causes: [d+] & Effect: c+

Now, looking back at the example, the resulting STG features two c+ transitions, but how do we arrive at the number of transitions we need?

The next step in this algorithm is to rearrange these stored lists of effects so we then have the cause transitions required for each of the resulting effect transitions, c+ in this case, to be able to occur. This is done using the Cartesian Product, commonly used in mathematics to “expand the brackets”, which, due to how lists are stored, also applies here. The Cartesian product will produce a number of results, based on the size of the inputs. In this case, we have two lists, one of size 2 and one of size 1. Multiplying these numbers gives us 2 results, and thus, 2 effect transitions.

With that in mind, we need to perform the Cartesian product on these two lists, which will provide us with two new lists which are the effects required per cause transition. This will be performed as follows:

1 – [a+, b+] * [d+] — The original lists
2 – [a+ * d+], [b+ * d+] — A list of lists after performing the Cartesian product on 1

2 holds a list of lists, each list being the required effects for a single transition to occur, one requiring both a+ and d+, the other requiring both b+ and d+. Due d+ being in an AND-causality relationship with c+, it is required to have occurred, regardless of whether a+ or b+ has occurred.

Now we need to include the two c+ transitions in the output of the tool, to be included when importing into Workcraft. The tool outputs the STG in dotG format, which is commonly used by existing tools which work with STGs. This format allows for the inclusion of more than of the same signal transition. The first of each transition will be output as expected, c+, but a second one will be output as c+/1. A third will be known as c+/2, and so on. For this example we will have c+ and c+/1.

With this information, we can now apply the specific transitions to the lists we have for each transition:

Causes: [a+, d+] & Effect: [c+]
Causes: [b+, d+] & Effect: [c+/1]

And this can now be converted to the transitions and read-arcs as expected, to produce the STG shown in Example 2 in Part 1 of this blog post.

A full example – 2 OR gates

Now we have discussed OR-causality, and the algorithm for this, let’s do an example from start to end, 2 OR gates. In this example, signals a, b, d and e are inputs, c will be the only output.

The concept for this is:

circuit = orGate a b c <> orGate d e c

Expanded into signal-level concepts, this is:

circuit = [a+, b+] ~|~> c+ ⋄ a- ⇝ c- ⋄ b- ⇝ c- ⋄
                    [d+, e+] ~|~> c+ ⋄ d- ⇝ c- ⋄ e- ⇝ c-

So, the tool will take these as these lists:

Causes: [a+, b+] & Effect: c+
Causes: [d+, e+] & Effect: c+

We now perform the Cartesian product on the two causes lists, which, knowing that there are two causes in each list, this will give us 4 c+ transitions. The result, with the transition names included will be:

Causes: [a+, d+] & Effect: [c+]
Causes: [a+, e+] & Effect: [c+/1]
Causes: [b+, d+] & Effect: [c+/2]
Causes: [b+, e+] & Effect: [c+/3]

And this will translate to an STG like this:

This clearly has 4 c+ transitions, and testing it proves that for any of them to allow any c+ to occur needs at least one of a+ and b+, as well as, at least one of d+ and e+. 

Finally

In both of these parts of the blog post, I have introduced OR-causality, and the algorithm to translate this to STGs. Through several examples, it can be seen that the algorithm works to produce STGs which display OR-causality.

The now released concepts translation tool can be effectively used to specify circuits with many functions, and the inclusion of OR-causality makes this better still.

The future of this blog series will include some concepts used in the translation process to specify signal types and initial states, which in turn serve as somewhat of a tutorial for the tool.

The tool is now available from https://github.com/tuura/concepts, which includes a manual to help with installation. It is also integrated with the STG plugin of Workcraft, and is included with a download of the latest version of Workcraft.

OR-causality is an interesting part of specification of circuits, specifically when using Signal Transition Graphs (STGs). We have recently released a translation tool for Concepts (available from https://github.com/tuura/concepts), which will take a set of concepts, and produce an STG specification for this. This includes both standard AND-causality, and OR-causality. OR-causality poses a challenge, as with STGs, and in this post we aim to discuss this.

This will be a 2 part series, with several examples to help explain OR-causality in this post, part 1, and an algorithm in part 2 to translate OR-causality concepts to STGs.

OR-causality, an introduction

For this, let’s use four simple examples. Here, we will assume initial states for all signals as 0.

1. OR-Gate

A standard gate used in many applications, an OR-gate, and the associated causality,  is important and a good example to use to display OR-causality.

In concepts, an OR-gate is defined as follows:

orGate a b c = [a+, b+] ~|~> c+ ⋄ a- ⇝ c- ⋄ b- ⇝ c-

There are some operators to discuss here:

[a+ , b+] – This is how signal transitions are listed.
~|~> – This shows an OR-Causalilty relationship

In words, this is a composition of three concepts. First, either a+ or b+ cause c+. Then, a- causes c-, and b- causes c-.

This will mean that, when a+,  b+ or both of these occur, c+ can occur. But, for c- to occur, a- and b- must have occurred.

This is the STG produced from translating the OR-gate concept. This looks like any other STG we have shown on this blog, however notice that there are two c+ transitions. This is how OR-causality is displayed in STGs. When a+ occurs, one of the c+ transitions can occur. When b+ occurs, the other c+ transition can occur. If both a+ and b+ have occurred, then either of the c+ transitions can occur. However, both a- and b- can occur, then and only then can c- occur.

Notice, that for the c+ transition, there is OR-causality with a+ or b+, but for the c- transition, there is AND-causality with a- and b-.

2. OR-Gate with a single AND-causality

This is an OR-gate with inputs a and b, and output c, with another input signal d. d will form a buffer with c, including some AND-causality as well. This way we can show how AND- and OR-Causality interact. In concepts this is:

circuit  = orGate a b c ⋄ buffer d c

And, expanded into signal-level concepts, this is:

circuit = [a+, b+] ~|~> c+ ⋄ a- ⇝ c- ⋄ b- ⇝ c- ⋄ d+ ⇝ c+ ⋄ d- ⇝ c-

In words, for c+ to occur, d+ must occur, and either b+ or c+. For c- to occur, all of a-, b- and d- must occur.

So, as a thought experiment, if a+ and b+ have occurred, no c+ transition can occur without d+ having occurred.

The STG after translating the above concept is:

Notice that this looks similar to the previous image, but with an extra consistency loop for the signal d. However, notice that d1, the place showing when d+ has occured, is connected to both c+ transitions. And d0 is connected to c-. This will therefore mean that, regardless of which of a+ or b+ have occured, c+ cannot occur without d+ occuring.

3. AND-Gate

Another standard gate. In this case, when thinking of it in terms of causality, it is the opposite of the OR-gate. i.e. For the c+ transition, there is AND-causality with both the a+ and b+ transition. Yet, with the c- transition, there is OR-causality between the a- and b- transitions.

The concepts for this is:

andGate a b c  = a+ ⇝ c+ ⋄ b+ ⇝ c+ ⋄ [a-, b-] ~|~> c-

This can be described in words as in the previous paragraph.

Let’s translate this to an STG.

Notice that this time, there are two c- transitions, as this transition is the OR-causality in an AND-gate. Notice the similarities between this and the OR-gate STG, just a sort-of mirror image.

4. AND-Gate and OR-Gate

For this, signals a and b are the inputs to an OR-gate, and signals d and e are the inputs to an AND-gate. The outputs for both of these gates are c. Synthesizing this would not simply produce an AND and OR gate, but for this example, it shows how the AND and OR causality can interact in and interesting way.

This in concepts is:

circuit = orGate a b c <> andGate d e c

If we expand this:

circut = [a+, b+] ~|~> c+ ⋄ a- ⇝ c- ⋄ b- ⇝ c- ⋄
                  d+ ⇝ c+ ⋄ e+ ⇝ c+ ⋄ [d-, e-] ⇝ c-

In words, this means that for c+ to occur, either a+ or b+, and both d+ and c+ must have occured. For c- to occur, both a- and b-, and either d- or e- must have occured.

This is slightly more confusing than the previous examples, and the resulting STG produced by translating this concept is interesting:

It does look a little confusing, but notice there are two of both c+ and c- transitions. Their interactions with the other signals determine which of these are able to transition. Testing this would prove that the concept description above works.

Finally

There is little reuse here. The concepts above feature some reuse of previously discussed concepts, but due to the inclusion of OR-causality, we cannot use any previously included gate- or protocol-concept as they do not feature any OR-causality.

So in this post, we have discussed OR-causality, and some uses of it. Specifically, I have aimed to show how it works on it’s own, and in conjunction with AND-causality.

Part 2 of this post will include an algorithm, as we have previously discussed how concepts are translated to STGs, but this algorithm will explain how OR-causality is translated, as this is quite specific.