As I was learning to program, Python lists seemed totally magical to me. I imagined them as being implemented by some sort of magical datastructure that was part linked-list, part array that was perfect for everything.

As I grew as an engineer, it occurred that this was unlikely. I guessed (correctly) that rather than some sort of magical implementation, it was just backed by a resizable array. I decided to read the code and find out.

One of the nice things about CPython is the readable implementation. Although the relevant file is over 2000 lines of C, it’s mostly the sorting algorithm, and boilerplate to make the functions callable from Python code.¹ The core list operations are short and straightforward.

Here are a few interesting things I found reading the implementation. Code snippets below come from the CPython source with explanatory comments added by me.

List Resizing

If...

After 4 days climbing long moderates in Tuolumne Meadows, Eben and I were stoked to get out of the park for the weekend and escape the crowds on some eastside alpine rock.

After a few minutes of flipping through the guidebook, we settled on the North Arete on Bear Creek Spire. The granite prow of Bear Creek Spire rises to 13713’, roughly 1500’ above the scree at its base. The North Arete climbs the steep north ridge line through 10 pitches up to the summit. With just one crux 5.8 pitch and 7 pitches of easy fifth, it seemed like a good match for all the moderate simul-climbing we’d done in Tuolumne the week before.

While we could have tackled the route in a long day, with a 4-5 hour hike to the base coupled with 10 pitches up to 5.8, we decided to hike in the day before. The hike in on its own is worth doing, following a well maintained trail winding past innumerable alpine lakes...

Several months ago, we accidentally left our garage door open. A bunch of stuff got stolen and it sucked. I resolved to make sure this never happened again by making our garage door text us if we left it open. The components of this build are very similar to what I wrote about in my DIY nest article, so I’ll skip the nitty gritty and just tell you what to buy and lay out how it works. This article is intended for someone with the required knowledge to do this on their own, but wants to know what parts work well up front and skip painful Squirrel debugging.

The Spec

Our garage door has the following nice features:

• Semi-secure text endpoint for opening and closing the door
• Secure web endpoint for opening and closing the door
• Door state web endpoint
• Door-open-too-long-detector + texter

Parts List

• Electric Imp (the brains) ~$25
• Electric Imp breakout board ~$12
• Magnetic contact...

Evaluating the NFA

In part 1, we parsed the regular expression into an abstract syntax tree. In part 2, we converted that syntax tree into an NFA. Now it’s time evaluate that NFA against a potential string.

NFAs, DFAs and Regular Expressions

Recall from part 2 that there are two types of finite automata: deterministic and non-deterministic. They have one key difference: A non-deterministic finite automata can have multiple paths out of the same node for the same token as well as paths that can be pursued without consuming input. In expressiveness (often referred to as “power”), NFAs, DFAs and regular expressions are all equivalent. This means if you can express a rule or pattern, (eg. strings of even length), with an NFA, you can also express it with a DFA or a regular expression. Lets first consider a regular expression abc* expressed as a DFA:

Evaluating a DFA is...

The code for this post, as well as the post itself, are on github.

This post is part of a 3 part series.

• Part 1
• Part 2
• Part 3

Converting the Parse Tree to an NFA

In the last post, we transformed the flat string representation of a regular expression to the hierarchical parse tree form. In this post we’ll transform the parse tree to a state machine. The state machine linearizes the regex components into a graph, producing an “a follows b follows c” relationship. The graph representation will make it easier to evaluate against a potential string.

Why make yet another transformation just to match a regex?

It would certainly be possible to translate directly from a string to a state machine. You could even attempt to evaluate the regex directly from the parse tree or the string. Doing this, however, would likely involve significantly more complicated code. By slowly lowering the...

This post is part 1 part of a 3 part series.

• Part 1
• Part 2
• Part 3

The code from this post, as well as the post itself, are on github.

Until recently, regular expressions seemed magical to me. I never understood how you could determine if a string matched a given regular expression. Now I know! Here’s how I implemented a basic regular expression engine in under 200 lines of code.

The Spec

Implementing full regular expressions is rather cumbersome, and worse, doesn’t teach you much. The version we’ll implement is just enough to learn without being tedious. Our regular expression language will support:

• .: Match any character
• |: Match abc or cde
• +: Match one or more of the previous pattern
• *: Match 0 or more of the previous pattern
• ( and ) for grouping

While this is a small set of options, we’ll still be able to make some cute regexes, like m (t|n| ) | b to match Star Wars...

When I first watched the pilot of HBO’s Silicon Valley, I thought it was pretty funny. I found its over-the-top antics about startups, venture capitalists, and Google comically accurate. Some of my friends were less amused, primarily by the complete lack of women. While initially, this didn’t bother me, I’ve come around to a different point of view: I think the depiction of the valley with no women and asshole guys negatively impacts both the valley, and efforts to increase the number of women in engineering.

Take it from the perspective of a high school girl considering pursuing computer science. Would you want to go off to a career where you’d be the only woman, the men were not only dorky, but mean, and your opinion wasn’t respected?

The effort to get more women into computer science is an uphill one already – we don’t need to make it any more difficult.

During a brief stint of funemployment I decided to make an internet controllable thermostat for our apartment. While I had our normal thermostat on a schedule, it would be nice to turn it off before a trip and be able to turn it back on from my phone during the car ride home. You can buy a smart thermostat like a Nest, but they’re either very expensive or equally hard to use. Anyways, it’s more fun to build things yourself.

With no expertise in HVAC, I had no idea how thermostats worked. They obviously measure the temperature and communicate with the heater, but beyond that I had no idea. This (lack of) knowledge in hand, my first step was to pull the thermostat off the wall and start playing around. I found two wires leading to terminals that ran into the wall. On a hunch, after verifying that the terminals didn’t carry high voltage, I connected them with a jumper cable. Success! The...