About Me!

This blog is about my musings and thoughts. I hope you find it useful, at most, and entertaining, at least.

Résumé [PDF]

Other Pages

Quotes

Links

Oak Island

Items for Sale

Presence Elsewhere

jim@jimkeener.com

del.icio.us

Twitter

Facebook

LinkedIn

GitHub

BitBucket

Keybase.io

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.

#include <iostream>
#include <typeinfo>

/**
 * Used by `pos` to verify a value is greater than or equal to zero.
 */
template<int8_t VAL>
struct positive
{
    const static bool value = -1 < VAL;
};

/**
 * Used by enable_if to verify a value is greater than or equal to zero.
 */
template<int8_t VAL, int8_t BASEVAL>
using lt = typename std::enable_if<less_than<VAL, BASEVAL>::value>::type;

/**
 * Used by `lt` to verify that the first param is less than the second.
 */
template<int8_t VAL, int8_t BASEVAL>
struct less_than
{
    const static bool value = VAL < BASEVAL;
};

/**
 * Used by enable_if to verify that the first param is less than the second.
 */
template<int8_t VAL>
using pos = typename std::enable_if<positive<VAL>::value>::type;

/**
 * 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<CONDITIONS...>::value;
};

/**
 * Uses `all_false` and `std::is_same` to determine if the set of types
 * in `ALREADY_SET` containts T.
 */
template<typename T, typename... ALREADY_SET>
using NoDuplicates =
      typename std::enable_if<
          all_false< std::is_same<ALREADY_SET, T>... >::value
          >::type;


/**
 * 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<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...> :: LadderRung(bool (&base_stack)[MAX_STACK_DEPTH]) :
  stack(base_stack)
{}

template<int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH, typename ...ALREADY_SET>
template<typename OUT_TYPE, NoDuplicates<std::decay<OUT_TYPE>, ALREADY_SET...>*>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET..., std::decay<OUT_TYPE>>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...> :: OUT(OUT_TYPE& out)
{
    std::cout << typeid(out).name() << " ### " << (static_cast<int>(STACK_DEPTH)) << " ### " << stack[STACK_DEPTH] << std::endl;
  return LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET..., std::decay<OUT_TYPE>>(stack);
}


template< int8_t STACK_DEPTH, int8_t  MAX_STACK_DEPTH, typename ...ALREADY_SET>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...> :: LOAD(bool value)
{
  stack[STACK_DEPTH] = value;
  return LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...>(stack);
}

template< int8_t STACK_DEPTH, int8_t  MAX_STACK_DEPTH, typename ...ALREADY_SET>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...> :: AND(bool value)
{
  stack[STACK_DEPTH] = stack[STACK_DEPTH] & value;
  return LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...>(stack);
}

template< int8_t STACK_DEPTH, int8_t  MAX_STACK_DEPTH, typename ...ALREADY_SET>
template<lt<STACK_DEPTH, MAX_STACK_DEPTH>*>
LadderRung<STACK_DEPTH + 1, MAX_STACK_DEPTH, ALREADY_SET...>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...> :: PUSH()
{
  return LadderRung<STACK_DEPTH + 1, MAX_STACK_DEPTH, ALREADY_SET...>(stack);
}

template< int8_t STACK_DEPTH, int8_t  MAX_STACK_DEPTH, typename ...ALREADY_SET>
template<pos<STACK_DEPTH>*>
LadderRung<STACK_DEPTH - 1, MAX_STACK_DEPTH, ALREADY_SET...>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET...> :: ORP()
{
    stack[STACK_DEPTH - 1] = stack[STACK_DEPTH - 1] | stack[STACK_DEPTH];
  return LadderRung<STACK_DEPTH - 1, MAX_STACK_DEPTH, ALREADY_SET...>(stack);
}

void print_stack(bool (&stack)[4])
{
  std::cout << "Stack: " << stack[0] << "," << stack[1] << "," << stack[2] << "," << stack[3] << std::endl;
}

template<int8_t PIN>
class OutputPin {};

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;
}

Better Errors

As we discussed last time, the point of this exercise was to constrain the checks to the type system. However, this produces the error in an awkward location -- generating the return value, as opposed to clearly in the function or function call. A more human-friendly means of having this constraint would be to perpetuate the list inside the type system as before, but to use a static_assert to generate the error.

template<int8_t MAX_STACK_DEPTH, int8_t STACK_DEPTH, typename ...ALREADY_SET>                                    
template<typename OUT_TYPE>                                                                                      
LadderRung<MAX_STACK_DEPTH, STACK_DEPTH, ALREADY_SET..., std::decay<OUT_TYPE>>                                   
LadderRung<MAX_STACK_DEPTH, STACK_DEPTH, ALREADY_SET...> :: OUT(OUT_TYPE& out)                                   
{                                                                                                                
  static_assert( all_false< std::is_same<ALREADY_SET, std::decay<OUT_TYPE>>... >::value, "Already outputed"); 
  std::cout << typeid(out).name() << " ### " << (static_cast<int>(STACK_DEPTH)) << " ### " << stack[STACK_DEPTH] << std::endl;
  return LadderRung<MAX_STACK_DEPTH, STACK_DEPTH, ALREADY_SET..., std::decay<OUT_TYPE>>(stack);                  
} 

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.