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

Content-Signature

Date: 20161027

Tags: programming crypto http

Type-madness, Part 2: Advanced constraints with types

Date: 20161023

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; /** * Loads a value into the current accumulator (position in the stack). */ LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET…> LOAD; /** * Logical AND with the paramter and the accumulator (position * in the stack). */ LadderRung<STACK_DEPTH, MAX_STACK_DEPTH, ALREADY_SET…> AND; /** * 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
{ 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
{ 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
{ 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: " << stack0 << "," << stack1 << "," << stack2 << "," << stack3 << 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 .AND; print_stack(stack); bool stack2[] = {false, false, false, false}; LadderRung<0,4>(stack2) .LOAD .AND; print_stack(stack2); bool stack3[] = {false, false, false, false}; LadderRung<0,4>(stack3) .LOAD .AND .PUSH .LOAD .AND .ORP .LOAD; print_stack(stack3); auto pin1 = OutputPin<1>(); bool stack4[] = {false, false, false, false}; LadderRung<0,4>(stack4) .LOAD .AND .PUSH .LOAD .AND .ORP .LOAD .OUT; print_stack(stack3); auto pin2 = OutputPin<2>(); bool stack5[] = {false, false, false, false}; LadderRung<0,4>(stack5) .LOAD .AND .PUSH .LOAD .AND .OUT .ORP .LOAD .OUT; print_stack(stack3); /** * Cannot set the same output twice bool stack5[] = {false, false, false, false}; LadderRung<0,4>(stack5) .LOAD .AND .PUSH .LOAD .AND .OUT .ORP .LOAD .OUT; 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                                   
{                                                                                                                
  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.

Unsupported Voting Machines

Date: 20161022

Tags: foss voting

I recently read an article about how Pennsylvania’s voting machines run Windows XP. While these devices aren’t (normally? ever?) connected to a public network, which limits the surface area of an attack, it is none-the-less appalling that critical parts of our infrastructure are; first, being run on proprietary, unvettable software; and second, being run on software without a maintenance and support contract. To me, this clearly represents why public infrastructure should be based on Free, Open Source Software. We, as a people, should not be hamstrung and left in an insecure place for no reason than a company decided to abandon a release. (Which, baring a support contract, they have every right to do.) If these machines were based on Free Software it’s both possible for support to exist indefinitely and it’s quite possible that support and upgrades will exist and continue to exist — look at some of the devices still supported by the linux kernel.

Additionally, these voting machines, with perfectly fine hardware, may not be able to be upgraded; we will need to spend money on new hardware to support the new software the vendor peddles.

We, as the public, need to push our elective officials, and appointed bureaucrats, to use software that we know can be kept up-to-date regarding security.

When putting out public files, “open data”, the dumps should be in formats that don’t require expensive software to use — even the poor should have access to data!

Type-madness, Part 1: Enforcing simple constraints with types

Date: 20161018

Tags: programming types c++

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 two other main goals as well: stack-only
allocation and code size. 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 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.


The last 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.


To tease the read, as this will be discussed in the next post, the
single-setting of an output was a tour through some of the more
interesting type mangling and compile-time expressions. The basic idea
here is that each operation returns the set of outputs (actually their
types) that have already been set, e.g. OR will return the same set,
SET will return the old set unioned with the type being set. Now that
magic that makes this happen: using enable_if and some helper types and
compile-type expressions to disallow that list to have repeated types.
(I must admit, while I thought of doing this, my actual implementation
was based on some help and examples from
##C++
(webchat).) All
of these checks also happen at compile-time and also generate no code.
Needing to have each output be its own type isn’t a terrible solution,
and should be a near zero-cost abstraction since the type need only
extend another type, not implement any code.


One potential issue that I’m still exploring is each templated class
will generate code for each unique set of template parameters. This
isn’t ideal. What I decided to do was create another class that does
the actual implementation of all of the methods, but isn’t templated; it
takes the type parameters as argument as needed. This allows for the
templated class to be inlined and for no code to be generated for it,
only the functions calls to the class implementing the logic. I’m
testing if -Os is good enough to know that, or if I need to forcibly
tell the compiler to inline it. We’ll discuss in a later post.


Stack Protection


A stack is a type of data-structure where objects are placed on the top
each time they’re added, and removed from the top when they’re removed
(think a stack of paper on a desk); this is known as Last-In First-Out
(LIFO) or First-In Last-Out (FILO). (Compare to a queue, like a British
queue, an American “line”, waiting for an event where the first person
in the line is the first person in: First-In First Out (FIFO).)


Stacks, among other things, are used by computers to keep track of
nested computations. Nested computations? Imagine we have:

<code class="python">(2+2) * (3 + 3)
</code>

We need to compute 2+2 and 3+3 before we can compute their product.
In order to do so, we need to temporarily store the value of one of the
additions, while we compute the other. One means of doing this is to use
a stack. (Another way would be one of the additions in another memory
address or register while the next addition is performed.) Some
machines, called Stack
Machines
, have no registers
or memory in the extreme case, there are various levels of “hybrid”
machines with registers and direct memory access. Many Virtual Machines,
like the JVM,
Cython,
YARV,
Forth, as
well as some classic
architectures

are implemented like this as it makes the implementation simpler and
easier to validate. Let’s compute 3+3 and push it on the stack:

Stack
-----
 6    

Let’s “push” it onto the stack


Now, let’s compute 2+2 and push it onto the stack:

Stack
-----
6
4

We can then “pop” both 4 and 6, add them, and push the result onto
the stack.

Stack
-----
 10

(This is very similar to how Reverse Polish
Notation
is
written and implemented.)


Why is this important for us? IL has stack and most instructions affect
the current location in the stack, the rest control which location in
the stack is being examined.


Since there is a finite amount of memory, the depth of the stack is
intrinsicly limited. If we would like to enforce that limit — or a more
restrictive one, say only 4 deep instead of all of memory — at compile
time, we need to be able to know both the current stack location, and
the maximum number of slots in the stack. One way of using this
information is to have each instruction return the slot in the stack
that the next instruction will affect.


Stack protection was relatively straight-forward to implement using the
C++ templating system. The basic idea is based around embedding the
maximum and current stack depths into the type of the current IL
mnemonic. We can do this because any constant expression and type can be
used as a template parameter in C++, not just types; in this case, we’re
using an integer as our template parameter.


By initializing the first instruction as depth 0 and with a
pre-allocated stack (i.e. of a known size, which gets transmuted into
the max stack depth), each following instruction returns the appropriate
stack depth, e.g.



  • AND returns the same

  • PUSH returns a location one larger than the current

  • ORP returns one fewer (and ORs the current and one fewer’s values, storing the result in the one fewer than current location.


We will always know the current and maximum depths at compile time. The
maximum depth is a value that is passed from mnemonic to mnemonic
unchanged, and is set when the initial space for the stack is allocated,
which we must do at compile time (no dynamic allocation!). We also know
the current stack depth because each mnemonic returns the location the
next one is to use. For most mnemonic this is the same value as the one
it operated on. For PUSH and ORP it is one higher or lower,
relatively, than the current one. Inductively we can show that this
value is always known. For example:

LOAD true (@0 max 4) -&gt; true - - - @0 max 4)
AND false (@0 max 4) -&gt; false - - -  (@0 max 4)
PUSH (@0 max 4) -&gt; false - - - (@1 max 4)
LOAD true (@1 max 4) -&gt; false true  - - (@1 max 4)
ORP (@1 max 4) -&gt; true - - -  (@0 max 4)

Because these are all constant expressions, at compile time we can check
to ensure that the operation will return a stack depth less than the max
depth and greater than or equal to zero. Since these checks happen at
compile time
, no code is generated to perform these comparisons. The
fast code is that which doesn’t exist. The following is a sample
implementation.


#include <iostream>

/** * 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>
using pos = typename std::enable_if<positive<VAL>::value>::type;

/** * Used by `lt` to verify that the first param is less than the second. */
template<int8_t VAL, int8_t MAXVAL>
struct less_than
{ const static bool value = VAL < MAXVAL;
};
/** * Used by enable_if to verify that the first param is less than the second. */
template<int8_t VAL, int8_t MAXVAL>
using lt = typename std::enable_if<less_than<VAL, MAXVAL>::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`. * */
template< int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH>
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]);

/** * Loads a value into the current accumulator (position in the stack). */ LadderRung<STACK_DEPTH, MAX_STACK_DEPTH> LOAD; /** * Logical AND with the paramter and the accumulator (position * in the stack). */ LadderRung<STACK_DEPTH, MAX_STACK_DEPTH> AND; /** * 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> 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> ORP; };

template< int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH> :: LadderRung(bool (&base_stack)[MAX_STACK_DEPTH]) : stack(base_stack)
{}

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

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

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

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

void print_stack(bool (&stack)4)
{ std::cout << "Stack: " << stack0 << "," << stack1 << "," << stack2 << "," << stack3 << std::endl;
}
int main()
{ std::cout << "Test running" << std::endl;

bool stack[] = {false, false, false, false}; LadderRung<0,4>(stack) .LOAD .AND; print_stack(stack); bool stack2[] = {false, false, false, false}; LadderRung<0,4>(stack2) .LOAD .AND; print_stack(stack2); bool stack3[] = {false, false, false, false}; LadderRung<0,4>(stack3) .LOAD .AND .PUSH .LOAD .AND .ORP; 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 a side note, the above was done to encapsulate the checks in the type
system, not just at compile-time. However, using a static_assert in
PUSH and ORP can produce better error messages and occur where
someone jumping into the code would expect it to occur, i.e. in the
function, not in creating the return value.


    /**
     * 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.
     */
    LadderRung<STACK_DEPTH+1, MAX_STACK_DEPTH> 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. */ LadderRung<STACK_DEPTH-1, MAX_STACK_DEPTH> ORP;

template<int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH>
template<lt<STACK_DEPTH, MAX_STACK_DEPTH>*>
LadderRung<STACK_DEPTH + 1, MAX_STACK_DEPTH>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH> :: PUSH
{ static_assert(STACK_DEPTH + 1 < MAX_STACK_DEPTH, "Max Stack Depth exceeded"); return LadderRung<STACK_DEPTH + 1, MAX_STACK_DEPTH>(stack);
}

template<int8_t STACK_DEPTH, int8_t MAX_STACK_DEPTH>
LadderRung<STACK_DEPTH – 1, MAX_STACK_DEPTH>
LadderRung<STACK_DEPTH, MAX_STACK_DEPTH> :: ORP
{ static_assert(STACK_DEPTH > 0, "Min Stack Depth exceeded"); stack[STACK_DEPTH – 1] = stack[STACK_DEPTH – 1] | stack[STACK_DEPTH]; return LadderRung<STACK_DEPTH – 1, MAX_STACK_DEPTH>(stack);
}

The static_assert are checked at compile-time, as would the type-based
check above, but, as mentioned, are a bit more friendly to the
programmer. However, the mechanism of passing the current and maximum
depth around still needs to be in place.


Tune in next time


In the next installment, we’ll investigate
using a similar technique to help ensure we don’t set an output multiple
times in the same program

Fun and Interesting Waypoints

Date: 20160721

Tags: trivia air-travel

None of the maps or data presented here should be used for actual navigation

At lunch yesterday some coworkers and I got onto the topic flight waypoints and I was reminded of funny air waypoints. While waiting for some code to run, I decided to look up some for Pittsburgh. I found the STARs and IAPs and saw obvious gems like TERBL TOWEL, MYRON COPPE, PENGN GUINZ, RIVERZ, and HEINZ. I knew I had to look deeper! I had some trouble finding a list of waypoints, but stumbled upon fplan and its 2015 database. With a little `sed` magic, I was able to extract a file qgis could read. I quickly found a handful more!

I attempted to catalouge those as well as some interesting names. The theory on why each of the blue beacons is named as it is are my own. If you have better data or a good theory for some others, let me know!

ID Type Thoughts
COPPE RNAV-WP Myron Cope (see MYRON)
CRSBY RNAV-WP Sidney Crosby (see CYDNY)
CYDNY RNAV-WP Sidney Crosby (See CRSBY)
DIXIN REP-PT Mason-Dixon Line
FLURY RNAV-WP Marc Andre Fleury
GOLDH RNAV-WP Golden Triangle? (Not sure at all)
GUINZ RNAV-WP Penguins Hockey (see PENGN)
HEINZ RNAV-WP H J Heinz Corp
JOEPA RNAV-WP Joe Paterno :-\
JOHNB REP-PT Former Mayor of Pittsburgh / Constitutional Convention Deligate
KEDKE RNAV-WP KDKA (1st Commerical radio station)?
LEMEW RNAV-WP Mario Lemieux
LMBRT RNAV-WP Jack Lambert
MLKIN RNAV-WP Yevgenie Mulkin
MYRON RNAV-WP Myron Cope (see COPPE)
PEETE REP-PT Pengiuns’ first mascot??????? (not sure at all)
PENGN RNAV-WP Penguins Hockey (see GUINZ)
PITTZ REP-PT Pittsburgh
PROGY RNAV-WP Pierogi?
RACOO REP-PT Racoon Creek State Park
RIVRZ RNAV-WP Three Rivers
STARG REP-PT Willie Stargell (see WIILE)
STILR RNAV-WP Pittsburgh Steelers
TERBL RNAV-WP Terrible Towel (see TOWEL)
TOWEL RNAV-WP Terrible Towel (see TERBL)
WIILE REP-PT Willie Stargell (see STARG)
WOLES RNAV-WP Wholey’s ?
WYLER REP-PT Heinz Brand??
YINZZ RNAV-WP Pittsburgheese Plural You