About Me!
This blog is about my musings and thoughts. I hope you find it useful, at most, and entertaining, at least.
Other Pages
Presence Elsewhere
Type-madness, Part 2: Advanced constraints with types
Date: 2016-10-23
Tags: programming types c++
In the last installment I discussed how to
enforce a simple constraint using only the C++ type system. enable_if
was critical to this endeavour and will still be a central tool in our
belt. However, we will variadic templates/parameter
packs to help
us enforce a more complex constraint based upon building up a history of
what we've already done.
Last time, we were enforcing a constraint that enabled us to not access unallocated memory at compile time. In this installment, we'll be enforcing a stylistic rule at compile time: the same output should not be set more than once per cycle. This rule helps simplify our understanding of our uil program.
I've begun work on APBduino, a basic implementation of Automatic-Permissive Block Signalling system for an Arduino. (I'll have to write more on that.) After a bit of mulling, I realized that a lot of the core logic is (unsurprisingly) similar to Ladder Logic. As such, I am working on another project that will allow a basic form of Instruction List, a standard method of programming the PLCs Ladder Logic runs on. My implementation is called µIL (micro IL, styled uIL).
Since I don't have access to the spec, only some PLC manuals I've found online, and am not aiming for 100% spec compatibility, I decided to use this as a chance to learn more about the C++ type system by implementing two constraints via types: stack-depth protection and setting outputs only once. These two additions will help prevent errors when specifying the ladder logic. The first by preventing illegal operations, the later by disallowing, otherwise valid, but confusing programs.
While implementing these, I had to other main goal as well: stack-only allocation. Not having to dynamically allocate memory at run-time makes static analysis easier and also removes a few classes of errors.
Something else I kept in mind while writing all of this was that it'll be running a teensy-weensy microprocessor. I need the code to be space efficient. Luckily, much of the type magic doesn't map to executable code, allowing very complex things to be done in the compiler, on my relatively giant, humongous, speed-daemon of a laptop.
The first (done previously) allows us to define certain amounts of memory to be defined at compile-time, and any operation that would violate those memory constraints will cause a compile-time error. Since accessing invalid or an unbounded amount of memory would be pernicious to the system, not allowing these operations to compile eliminates a large class of errors.
What we'll be tackling in this installment is more interesting. Ladder logic was originally implemented as Relay logic, and the entire "program" (electrical circuit) executed simultaneously. Multiple outputs to the same relay could cause unexpected results. Now that Ladder logic is implemented in a microprocessor, the programs are executed in serial. However, they become easier to reason about if every output is set once. Similar to a computer program that changes a variables value all of the time, it can make jumping into a program to understand it difficult. Since hardware is being controlled, and often safety-critical systems are being implemented, easily reasoning about the software is extremely useful.
Single Outputs
To keep track of the stack depth, we passed the current stack depth around, or modified it as needed. To ensure that we never double-set an output, each output will need to be its own type; then we can keep track of all of the types that have been set, and have the type of out only be valid when the thing being outputted is not yet in our list of set outputs. Consider
OUT{}(Pin<1>()) -> OUT{Pin<1>}
OUT{Pin<1>}(Pin<2>()) -> OUT{Pin<1>, Pin<2>}
OUT{Pin<1>, Pin<2>}(Pin<1>()) -> type error
As mentioned earlier, we'll use a varidic template to accumulate the types
set. To check if a type we're looking to set is in our list, we'll use
enable_if to unwrap our pack and reduce it with all_false and
std::is_same to check if the new type is in our list.
```language-cpp pre_class="line-numbers"
include
include
/*
* Used by pos to verify a value is greater than or equal to zero.
/
template
/*
* Used by enable_if to verify a value is greater than or equal to zero.
/
template
/*
* Used by lt to verify that the first param is less than the second.
/
template
/*
* Used by enable_if to verify that the first param is less than the second.
/
template
/* * Defines a struct with a variadic template. / template< typename... CONDITIONS > struct all_false;
/* * Base case: if there is no list, then they are all false, trivially / template<> struct all_false<> { const static bool value = true; };
/*
* Inductive case: if the first parameter is false, check the rest
* recursivly.
/
template< typename CONDITION, typename... CONDITIONS >
struct all_false< CONDITION, CONDITIONS... >
{
const static bool value = !CONDITION::value && all_false
/*
* Uses all_false and std::is_same to determine if the set of types
* in ALREADY_SET containts T.
/
template
/*
* LadderRun represents a sequence of instructions to execute each cycle.
*
* OK, so this isn't the best name for this; it's more like a single
* instruction.
*
* The STACK_DEPTH paramter represents the current depth of the stack,
* i.e. the index into the stack array.
*
* The MAX_STACK_DEPTH parameter represents the size of the array
* representing the stack, stored in the reference stack.
*
* The ALREADY_SET parameter represents the list of outputs that have
* already been set in this program.
/
template< int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH, typename ...ALREADY_SET>
class LadderRung {
private:
bool (&stack)[MAX_STACK_DEPTH];
public:
/**
* Constructs a new object with a reference to a stack.
*
* Reference to ensure we don't copy the stack by value, and hence
* have multiple copies of it.
*/
LadderRung(bool (&base_stack)[MAX_STACK_DEPTH]);
/**
* Outputs to a type; adds the type of the output to `ALREADY_SET` and
* checks if the type is already in `ALREADY_SET`
*/
template<typename OUT_TYPE, NoDuplicates<std::decay<OUT_TYPE>, ALREADY_SET...>* = nullptr>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET..., std::decay<OUT_TYPE>> OUT(OUT_TYPE& out);
/**
* Loads a value into the current accumulator (position in the stack).
*/
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...> LOAD(bool val);
/**
* Logical AND with the paramter and the accumulator (position
* in the stack).
*/
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...> AND(bool val);
/**
* Increments the stack depth.
*
* The `lt` is required to be valid when the class is created, so the
* protection comes from the `return` statement generating a class
* with a new `LadderRung` that is an invalid stack depth.
*/
template<lt<STACK_DEPTH, MAX_STACK_DEPTH>* = nullptr>
LadderRung<STACK_DEPTH+1, MAX_STACK_DEPTH, ALREADY_SET...> PUSH();
/**
* `OR`s the current position and one lower storing in the lower;
* Decrements the stack depth.
*
* The `pos` is required to be valid when the class is created, so the
* protection comes from the `return` statement generating a class
* with a new `LadderRung` that is an invalid stack depth.
*/
template<pos<STACK_DEPTH>* = nullptr>
LadderRung<STACK_DEPTH-1, MAX_STACK_DEPTH, ALREADY_SET...> ORP();
};
template< int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH, typename ...ALREADY_SET>
LadderRung
template
template< int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH, typename ...ALREADY_SET>
LadderRung
template< int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH, typename ...ALREADY_SET>
LadderRung
template< int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH, typename ...ALREADY_SET>
template
template< int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH, typename ...ALREADY_SET>
template
void print_stack(bool (&stack)[4]) { std::cout << "Stack: " << stack[0] << "," << stack[1] << "," << stack[2] << "," << stack[3] << std::endl; }
template
int main() { std::cout << "Test running" << std::endl;
bool stack[] = {false, false, false, false}; LadderRung<0,4>(stack) .LOAD(false) .AND(true); print_stack(stack);
bool stack2[] = {false, false, false, false}; LadderRung<0,4>(stack2) .LOAD(true) .AND(true); print_stack(stack2);
bool stack3[] = {false, false, false, false}; LadderRung<0,4>(stack3) .LOAD(false) .AND(true) .PUSH() .LOAD(true) .AND(true) .ORP() .LOAD(true); print_stack(stack3);
auto pin1 = OutputPin<1>();
bool stack4[] = {false, false, false, false}; LadderRung<0,4>(stack4) .LOAD(false) .AND(true) .PUSH() .LOAD(true) .AND(true) .ORP() .LOAD(true) .OUT(pin1); print_stack(stack3);
auto pin2 = OutputPin<2>();
bool stack5[] = {false, false, false, false}; LadderRung<0,4>(stack5) .LOAD(false) .AND(true) .PUSH() .LOAD(true) .AND(true) .OUT(pin1) .ORP() .LOAD(true) .OUT(pin2); print_stack(stack3);
/* * Cannot set the same output twice bool stack5[] = {false, false, false, false}; LadderRung<0,4>(stack5) .LOAD(false) .AND(true) .PUSH() .LOAD(true) .AND(true) .OUT(pin1) .ORP() .LOAD(true) .OUT(pin1); print_stack(stack3); /
/ * Max Stack Depth exceeded bool stack4[] = {false, false, false, false}; LadderRung<0,4>(stack4) .PUSH() .PUSH() .PUSH() .PUSH() .PUSH(); print_stack(stack4); /
/ * Stack Underflow bool stack4[] = {false, false, false, false}; LadderRung<0,4>(stack4) .ORP(); print_stack(stack4); / return 0; } ```
Tune in next time
In the next installment, we'll investigate how this gets turned into code, and how we can avoid code bloat when using templates in this manner -- where we use the templated class transiently and generate many classes in normal usage.