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

Political Civility

Date: 20170507

Tags: political-theory

I drafted a letter to my representive Tim
Murphy
about his support of the
AHCA.
While it wasn’t profanity ridden, it was lacking in civility. It ended



May you rot in hell, having to live and relive the suffering that the passage of this bill, if it passes the Senate, would inflict upon nearly all of your constituents. Over and over, reliving every mental health crisis, every overdose, every preventable death I wish to pass before you. You represent us, not the Republican party.



and contained lines like



Your lack of understanding of the ACA and the AHCA, your rush to push
this through without CBO scoring, and your complete apathy for your
constituents leave me disgusted with your spineless, wretched, soulless
being not worthy of the title `human’.



It wasn’t the most polite letter to say the least. It was a (partial)
release of the frustration I’ve been feeling with our system and the
inaccessibility
of
our
elected
officals
and the obvious lack of care for what’s best for their
constituents

in order to bend to party politics. It’s beyond frustrating. Our
elected officals appear to have no oversight and no repurcusions.


We’re at a point where I didn’t care that the letter I drafted was
hateful and incindiary because I didn’t even believe it would be read
beyond the point they realized I was against Murphy’s actions. This
caused a rift in me and I sent it to my wife and some of my closest
friends. They all said the same thing, more-or-less, “While I agree
and understand, it’ll be discarded as hate mail with no thought given to
your message.” That’s true. And even if I believe it won’t be read, I
should still strive to uphold the virtues of civil discourse. (I did
draft and send a less incendiary letter which I’ll post soon.)


Letting our political discourse be driven by hate, anger, emotion, and
team-psychology is an enormous problem, especially right now. The
hatred that Republicans felt towards Obama resulted in his
Constitutional Right to nominate a SCOTUS Justice to not even be
entertained. (Hearings weren’t even held! The Republicans controlled the
Senate and could have simply voted No.) It led to the disastrous AHCA,
which isn’t even an attempt to fix the problem, only to strike back at
the Democrats and Obama. The hatred many liberals are espousing
currently isn’t the solution. It’s not the way forward.


If all we expect from our opposition is hate and rhetoric, we maintain
no reason to actually listen to what they’re saying. When we fail to
listen, empathize, and understand (note, I didn’t say agree with or
capitulate to) other points of view, society, as a whole, becomes the
loser.


I can pick many examples from the past few months. The day following
the election I couldn’t do anything. I was so wrapped up in the hate
that 46% of the country rallied behind a man who brags about sexual
assault, espouses racist views, and has no real understanding of policy
that my chest hurt and I was red and hot for days. I was mortified,
angry, and hateful.


Over the next few months, I’ve slowly learned a different understanding
of that 46% of America. While I still vehemently disagree that any reason
justifies supporting Donald Trump, maybe I have the privileged of the
moral high ground. I’m not destitute. I haven’t just lost my job of
decades. I haven’t had a huge amount of uncertainty injected into the
core of my life. Clinton told these people that she supports better
educational programs and other means of bringing them into different
industries and those industries to them. I can only image that all these
people heard was “we’ll try something, but you’re going to have to deal
with the uncertainty”. Trump offered a very clear “You’ve been wronged;
I will right it and get your old job back.” The emotional trauma of
having what have become the core of your life ripped out from you isn’t
something I’ve ever lived through. However, by trying to better
understand these people’s position, I can better understand the reality
of the problem faced. They aren’t a thought experiment or statistical
value — they’re people who are fighting for their lives and livelihood.


That said, for the most part these people are not who I get to interact
with often. (Not that I avoid them. I’m a techie, as are many of my
friends and most of civic groups I attend have like minded people. We
all have a natural, self-imposed filter bubble. It’s not ideal, but it’s
practically what happens, and we’re all best to break out of it. We,
including me, should break out much more often.) I do run the risk of
simply making things up and creating sob stories. I run the risk of just
being silly. I don’t think I am, at least entirely though, based upon
my interactions with and interviews I’ve read with this group of people.


Do I think they made the choice that was best for their self interest?
No, absolutely not. I think they made the worst choice they could have
possibly made. However, I’m now able to have a conversation that doesn’t
begin “How could you possibly have supported someone who brags about
sexual assault and is so stupid he doesn’t even see the racism and
violence he spouts?” Perhaps now we could discuss their job, their
prospects, their thoughts about moving forward. There will be
idealogical misses — I’ve met many coal miners that believe Obama’s EPA
put them out of a job, not cheap oil and natural gas — but a
conversation could still happen. And that is the important part: A
conversation happened.


Moreover, name calling isn’t useful. Not only does it create barriers
to having the other person talk with you, but it’s more-often-than-not
coming from a place of hate. When someone complains about “immigrants”
or “Mexicans” taking their job, they may not be racist, and it’s
counterproductive to call them one. They may have actually lost their
job to cheaper labour here in the States, or even in their hometown.
While they’re description of the problem may grate ears or sound like a
dog whistle for something it’s not, it might not be factually wrong.
However, maybe the conversation could be turned from immigration to if
the problem is really immigrants or if the miniscule labour protects and
weak unions had a role in their job loss. Cheap labour is the
immediate, visible cause — but not necessarily the way to a solution.
We need to move beyond our politically inspired hatred to understand
that your fellow citizen is actually facing a problem; writing them off
as racist or over-exaggeration is no way to come to understand the
problem, let along work towards a solution.


Our hate and anger build walls just as terrible as Trump’s proposed
border wall, and, honestly, at a much higher cost to our society.

AMP and Instant Articles are Good Ideas, but hurt the web

Date: 20170407

Tags: web

Like most Americans, websites has by-and-large gotten heftier as the
web’s grown older. With the web in it’s mid-twenties we are facing an
obesity crisis on the web.


I opened a local news site’s webpage and watched the requests made in
the background, as the browser sat in the background.


And continued to watch the Chrome’s network inspector. (Yes, JPGs for a
screenshot of text. It’s smaller and they’re still readable.)






I could have let it go on longer, but I think having loaded 62MB over
8 minutes and no interactions hammers home my point: publishers, and
many web developers in general, are designing heavy websites. While this
is a notoriously bad site, even the a large national paper loads 17MB
after only a minute.



The largest file from the national paper is a video followed by ads and
A/B test javascript. The local site follows a similar pattern. It’s
frustrating, that without rejecting scripts, I could visit local site
once a day on my phone and burn through my anaemic mobile data plane
without doing anything else. Moreover, loading all of this content
adds considerable latency to loading and interacting with the page.
(Ever almost tap on something, but the page update and you tap on
something else?)


Another local publisher didn’t even have content in their initial
viewport! The majority of their bandwidth needs were, almost needless to
say, ads.


For the publishers, the obvious advantage to having lightweight pages is
user retention. There are a lot of reasons to have a fast load
time
— users will
only wait so long website to load; as high as 50% of users
will bail for load times over 2 seconds, and 80% after 3 seconds.
However, publishers also have competing goals of gathering analytics,
advertising, and looking like a “modern” site. These concerns can, and
need to be balanced. Like exercising and having a balanced,
correctly-portioned diet, sliming down a website requires thought and
effort. It takes time and often hard choices (“Do I really need to
have the cupcake someone brought in?” “Is serving three-quarters of the
initial viewport good?” “Getting up an house earlier will allow me a quick
exercise in the morning at the expense of a little sleep.” “Serving
image- or text- only ads will speed page load, decrease bandwidth, and
increase our reputation among readers, at the cost of diminished returns
of Flash and video ads.”)


Google’s AMP Project and FaceBook’s
Instant Articles are both attempts at
leading publishers to provide light-weight content. Page-load times,
caused by downloading less data which also affects how quickly one
approaches restrictive data caps, are the most visible benefits to the
end user. Additional benefits include decreased battery usage because
of having less to render and download. Both AMP and IA take similar
approaches to how they entice and enforce publishers to provide AMP- and
IA- compatible content: using a subset of HTML and prescribing that only
certain javascripts can be loaded.


While the AMP Projoect is suppose to be “open”, it’s largely to fully
controlled and used by Google. IA is completely controlled by FaceBook.
By using AMP or IA, the publisher is turning complete control over to
Google and FaceBook for the types of components and interface that your
page will have. Publishers looking to innovate or create interactive
features relevant are out of luck — they’re constrained to simple types
of common widgets. While prescribing only certain content from specific
domains does help with caching and “quality control”, it unreasonably
constrains developers and creates Single Points of Failure.


Moreover, both AMP and IA are ways that Google and IA prevent users
from entering the publisher’s ecosystem. By featuring the publisher’s
content within the Google or Facebook ecosystem. While the
publisher’s navigation may be present, it’s fighting with the display
ecosystems more native navigation.


While a convincing publishers to value load times (and by proxy
page weight) is a noble goal, AMP and Instant Articles (IA)
accomplish this goal by purposely limiting the types of content a
publisher can load. While this has some advantages, including resource
caching and forcing developers to consider these issues, the
straight-jacket approach is antithetical to how we should advance web
technology. It solves Google’s and FaceBooks problems, but only
tangentially works in favour of the publisher, at the expense of
diluting the publisher’s brand and making the publisher “work” for
Google or FaceBook, not the other way around.


Publishers would be better off realizing that they can
offer lightweight pages on their own, without needing to be led-on by
someone who is re-hosting their content, diluting their brand,
straight-jacketing them, and making it more difficult for readers to
stay within the publisher’s ecosystem.

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.


```language-cpp pre_class=“line-numbers”


include


include


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


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


/* * Used by lt to verify that the first param is less than the second. /
template
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
using pos = typename std::enable_if::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::value;
};


/* * Uses all_false and std::is_same to determine if the set of types * in ALREADY_SET containts T. /
template
using NoDuplicates = typename std::enable_if< all_false< std::is_same… >::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 :: LadderRung(bool (&base_stack)[MAX_STACK_DEPTH]) : stack(base_stack)
{}


template
template, ALREADY_SET…>*>
LadderRung>
LadderRung :: OUT
{ std::cout << typeid(out).name() << “ ### “ << (static_cast(STACK_DEPTH)) << “ ### “ << stack[STACK_DEPTH] << std::endl; return LadderRung>(stack);
}


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


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


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


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


void print_stack(bool (&stack)4)
{ std::cout << “Stack: “ << stack0 << “,” << stack1 << “,” << stack2 << “,” << stack3 << std::endl;
}


template
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&lt;1&gt;();

bool stack4[] = {false, false, false, false}; LadderRung<0,4>(stack4) .LOAD .AND .PUSH .LOAD .AND .ORP .LOAD .OUT; print_stack(stack3);


auto pin2 = OutputPin&lt;2&gt;();

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


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:


python (2+2) * (3 + 3)


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.


~~~~{.language-cpp pre_class=“line-numbers”}


include


/ * Used by pos to verify a value is greater than or equal to zero. */
template
struct positive
{ const static bool value = -1 < VAL;
};
/
* Used by enable_if to verify a value is greater than or equal to zero. */
template
using pos = typename std::enable_if::value>::type;


/ * Used by lt to verify that the first param is less than the second. */
template
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
using lt = typename std::enable_if::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 :: LadderRung(bool (&base_stack)[MAX_STACK_DEPTH]) : stack(base_stack)
{}


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


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


template
template*>
LadderRung
LadderRung :: PUSH
{ return LadderRung(stack);
}


template
template*>
LadderRung
LadderRung :: ORP
{ stack[STACK_DEPTH – 1] = stack[STACK_DEPTH – 1] | stack[STACK_DEPTH]; return LadderRung(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.


~~~language-cpp pre_class=‘line-numbers” data-start=“75’ / * 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 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&lt;STACK_DEPTH-1, MAX_STACK_DEPTH&gt; ORP();

~~~


~~~language-cpp pre_class=‘line-numbers” data-start=“124’
template
template*>
LadderRung
LadderRung :: PUSH
{ static_assert(STACK_DEPTH + 1 < MAX_STACK_DEPTH, “Max Stack Depth exceeded”); return LadderRung(stack);
}


template
LadderRung
LadderRung :: ORP
{ static_assert(STACK_DEPTH > 0, “Min Stack Depth exceeded”); stack[STACK_DEPTH – 1] = stack[STACK_DEPTH – 1] | stack[STACK_DEPTH]; return LadderRung(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