One of the things I needed in my Boggle solver was a bitmap. The average Boggle! board is 4×4, or 16 squares, and one of the rules is that you may not use the same letter twice. I needed a data structure that would handle the "Have I seen this before?"

Now, for a 4×4 board, a 16-bit integer will work just fine. And, in fact, the Ledger structure in the solver is, by default, a 64-bit integer, capable of handling boards as big as 8×8. In those case, the "mark" and "check" operations are just indices. Since this is a two-dimensional structure, we need a way to convert two-dimensional constructs into a one-dimensional number.

We want to move forward through the bitmap, using the width of the bitmap to find which row we’re in, and then the position on that row as the final offset.

These functions use the Rust bitmap operators. << means "shift left", and for a lot of programming operations these are used to mean "multiply by two." An accompanying function >> means "shift right", and can mean "divide by two"; in assembly language, both of these functions have an associated register that will tell you if a zero or one "fell off", and there are are similar instructions that will actually "shift around"; if a ‘1’ falls off at the 0th position of a 64-bit register, a ‘1’ will be inserted into the 63rd position, and vice-versa.

For our purposes, though, we just care about "the bit at a given position," and we use the shift operator to shift that bit into that position. In this case, we just create a new u64 bitmap with that one bit set:

pub struct Ledger(isize, isize, u64);

impl Ledger {
    fn point(&self, x: isize, y: isize) -> u64 {
        1 << (self.1 * x + y)
    }
}

And then marking the bitmap consists of ‘or’ing it against the representative bitmap.

   fn mark(&self, x: isize, y: isize) {
       self.2 |= self.point(x, y);
   }

And checking the bitmap is to ‘and’ the pointed bitmap against the internal bitmap and checking that the result is not zero (a very fast operation in assembly language).

   fn check(&self, x: isize, y: isize) -> bool {
       self.2 &= self.point(x, y) != 0
   }

As trivial as that is, what if the board is bigger than 8×8? At that point, we’re beyond the largest integer provided by mainstream CPUs, so we have to move to something simple: a map of maps. We’ll use a Vec<u8>, and kinda do what point() does up above, only in reverse: turn a single coordinate into a coordinate pair indicating which index in the vector to target, and then which bit in that u8 we want to set or change.

The only challenge here is that we need to know how big the vector will be ahead of time, and we need to ensure that the vector is pre-populated and that the entire bitmap starts out set to zero. In the event that our size isn’t evenly divisible by eight, we need one more block of bits for the overflow:

pub struct Bitmap(Vec<u8>, usize);

impl Bitmap{
  pub fn new(b: usize) -> FSBitmap {
        let s = b / 8 + { if (b % 8) == 0 { 0 } else { 1 } };
        FSBitmap((0..s).map(|_| 0 as u8).collect::<Vec<u8>>(), b)
  }
}

The index of a point is then two numbers: which byte we want to examine, and then an offset into that byte. In many ways, it’s exactly what the Ledger does, only backward. The Ledger doesn’t care about machine sizes, just the board. The bitmap, though, cares about machine sizes.

  fn index(&self, p: usize) -> (usize, usize) {
    (p / 8, p % 8)
  }

This format isn’t usable as a number, but as a way of tracking "in a modestly large atomic space, which units are in a which binary state?" it’s perfect. Marking a bit uses this pair:

  pub fn mark(&mut self, p: usize) {
    let (cell, byte) = self.index(p);
    self.0[cell] |= 1 << byte;
  }

As does checking it. In this particular case, any bit referenced outside the size of the requested original size is assumed to be zero:

  pub fn check(&self, p: usize) -> bool {
    if p >= self.1 { return false; }
    let (cell, byte) = self.index(p);
    self.0[cell] & (1 << byte) != 0
 }

Other operations such as flip and unmark can be written with just these operators.

Bitmaps aren’t the most thrilling data structures in the world, although there are some significant uses for very large, sparse bitmaps that have to be stored in something more esoteric than just a Vec<u8>. But for the purposes of Boggle! this was straightforward and not too difficult.

There was a research project named Wyvern (not related to the current programming language Wyvern) that was intended to invent what would probably be called a "lexically scoped paradigmatic programming language."

Programming languages are built on paradigms. In programming language theory, a "paradigm" is a set of ideas that form a mutually exclusive way of expressing the meaning of a program. The imperative paradigm treats programming mechanistically: "do this, then do this, then do this"; the functional paradigm treats programming mathematically: "if you have these different transformations of the data, eventually you get the answer you want."

The notion of lexically scoped paradigmatic programming is back, and I still believe it’s a bad idea. Jinnzest writes in favor of the idea: "[I]f a language, on the contrary, provides means to split code into separate paradigm we will have to examine only one of them at once abstracting away all other."

The idea of lexically scoped paradigmatic programming is simple: using some kind of syntax, we tell the compiler "Okay, now we’re gonna go all-functional, but we’re gonna glue it together with imperative," or "Everything in here should be assumed to be async and event-driven," and so on.

… and we’re back to Lisp. Lisp in Small Pieces, specifically. (Seriously, anyone who is working with a programming language who has not worked their way through LiSP is missing out.) We’re back to a world where reading someone else code is basically a "guess what’s going on here" and "your idea of the environment, stack, and so on are laughable." Lisp is a great language, but only if your people are super-disciplined about using it one way and one way only; otherwise you end up with all the paradigms all mixed up in a bucket.

This is one of the reasons I recommend Go for a commercial venture that’s trying to move away from Python and Node. Go has only one paradigm: imperative. It’s not even a very good event-driven language; goroutines and message passing devolve into imperative code very easily.

On the other hand, it’s a vile, ugly language, and that’s why I like to write in Haskell for learning, Rust for performance and Lisp for elegance. So, you know, not in production.

05Aug

Data Structures: Tries in Rust

Posted by Elf Sternberg as Uncategorized

I recently went to a job interview (I’m looking for work, by the way; hire me!) and one of the questions put to me was “solve the Boggle™ board.” I don’t think I did very well on the question and it wasn’t until I got home that I remembered “Dammit, the fastest structure for checking if a word is in a dictionary is a trie!”

Whiteboard exercises are terrible. I don’t think I’ve ever actually programmed a trie, not even in Data Structures class I took way back in college in 19mumblemumble. I’m sure I’ve used them, but I’ve never had to write one.

So what is a trie?

A trie is a data structure that encodes every word in a dictionary as a string of nodes, one per letter. This trie encodes the dictionary containing the words “a”, “an,” “ant”, “art”, and “aunt”. If we’re looking up “ant,” we start at the root node and traverse to “a”, then “n”, and then “t”. The “t” is double-circled, that is, it’s marked as a terminal node, and thus “ant” is in this dictionary. If we were looking up the word “any”, we would get to “a,n,” and then fail, because “any” is not in this dictionary. Likewise, we might ask if “aun” is in the dictionary, and we would get to “a,u,n,” but that “n” is not double-circled, and thus “aun” is also not a complete word in this dictionary.

Like a regular expression, a trie search is successful when the string is exhausted, the trie is still active, and we find ourselves on a node marked as a word terminator. If the trie exhausts before the string, or if the string exhausts on a non-terminating node, the search fails to find a complete word.

The rules of Boggle™ are very simple: on a 4×4 grid, sixteen dice are shaken and dropped into place. Each die has six letters on it, probabilistically arranged. Players have three minutes to find every valid word on the board, where “valid” means “found in the dictionary the players have agreed to use,” modulo some rules like “no contractions or abbreviations.” The letters of the words must be adjacent in any of the eight cardinal directions (modulo the borders of the grid), and no letter may be used twice for the same word.

So, to solve for Boggle, we need a fast lookup dictionary, and thus we need a trie. Tries are extremely fast, Ο(n) where n is the length of the word. They’re memory-intensive, but these days memory is cheaper than time. Each node has two conditions: the list of letters that it leads to, and whether or not it is a terminal node. For the “list of letters,” we’re going to use a HashMap. The child nodes must be Boxed as we’re building this on the heap (it will be huge for a full-sized dictionary) and it must be RefCell‘d because we’ll be mutating child nodes repeatedly as we build the trie.

For a canonical dictionary lookup, this implementation is different the Wikipedia page’s description.  There’s no utility to storing the node’s value in itself; we know what the value is by the key we used to reach it!  We do need to know if the node is a terminator node.

There are strong feelings about tuples vs structs for values with multiple fields, with most people preferring structs.  For a value with two fields, I feel a tuple ought to be adequate.  A record with so many fields it has to name them, and therefore a struct, has a code smell and is worth examining closely for cognitive complexity.  I’ll address that in the next post.

pub struct Node(HashMap<char, Box<RefCell<Node>>, bool);

For this structure, we’re going to build it imperatively; that is, each word will be presented to the structure one at a time, and each word will be an iterator over its characters. The first thing we need to do is say, for a given node, if the word is exhausted, then we are a terminator node:

impl Node {
    pub fn insert(&mut self, word: &mut Iterator<Item = char>) {
        let c = match word.next() {
            None => {
                self.1 = true;
                return;
            }
            Some(c) => c,
        };

Note that we’re returning from this function if we’re a terminator. There is no character to insert into the next node.

If we’re not a terminator, we must then either access or create a child node, and then keep traversing the word until its exhausted. In the “create a new child” scenario, we create the full trie before inserting it.

        match self.0.get(&c) {
            None => {
                let mut newtrie = Node::new();
                newtrie.insert(word);
                self.0.insert(c, Box::new(RefCell::new(newtrie)));
            }
            Some(node) => {
                node.borrow_mut().insert(word);
            }
        };
    }

One tricky feature of Boggle™ is that we want to end a search for a word early if the “word” found isn’t really a word. That is, if on the board you find the sequence “tk”, no word starts with “tk” and you want the search to terminate early. But as in our example above, “aun” is also not a word, but we do not want to terminate the search, as there may be a handy ‘t’ nearby to finish the word.

So we want to be able to search the trie, but we have two different criteria: “is this a word” and “could this be the prefix of a word?” We want our search engine to be able to handle both.

How do we handle both? Let’s go back: what are the failure conditions? The trie gets exhausted or the string gets exhausted. If both are exhausted at the same time and we’re on a terminator, it’s a word. If the word is exhausted but the trie is not, this is a prefix, regardless of its terminator status.

So, our search feature will be a recursive function that, letter by letter, transits the trie node by node. If the word exhausts and we’re still in the trie, we check the end state (always true for a prefix, is a terminator for a word), otherwise we recurse down to the next letter and the next node.

First, let’s see what we do if we run out of word. For the endstate, we’re going to pass it a function that says what to do when we run out of word:

    fn search(&self, word: &mut Iterator<Item = char>, endstate: &Fn(&Node) -> bool) -> bool {
        let c = match word.next() {
            None => return endstate(self),
            Some(c) => c,
        };

Note that it’s not pub! This is the search function, but it’s going to be invoked by the functions that make the distinction between finding a word and affirming a prefix. Flags are a code smell, and to the extent that you use them, they should never be accessible to client code.  Search, by the way, is completely immutable with respect to the structure being searched; only the word is mutating as we iterate through it, and the per-search recursion is wholly stacked based.  Once built, the trie could be safely used by multiple threads without the need for locking mechanisms.

Finally, if the trie is not exhausted, we try to get the child node, passing the endstate handler forward:

        match self.0.get(&c) {
            None => false,
            Some(n) => n.borrow().search(word, endstate),
        }
    }

And the two functions, find and prefix:

    pub fn find(&self, word: &mut Iterator<Item = char>) -> bool {
        self.search(word, &|s| s.1)
    }

    pub fn is_prefix(&self, word: &mut Iterator<Item = char>) -> bool {
        self.search(word, &|_s| true)
    }

And finally, the constructor. We create a new, empty node, and then we insert words into the trie, using that node as the root of the dictionary. The root node is never a terminator.

    pub fn new() -> Node {
        Node(HashMap::new(), false)
    }
}

And that’s it. That’s the whole of a trie, just two functions: a builder and a searcher. I had one special need (whole word vs prefix), but that was handled by using a distinguishing function as a flag on the semantics of the search.

Tries are a fun data structure. This version is pretty memory-heavy; it might be possible, for those cases where a word prefix has only one child, to pack them into a denser structure. The cost of running the discriminator versus a win on space density might even be worth it.

But if you have a finite dictionary, even one as big as the Scrabble™ legal words list (178,960 words as of 2012), a trie is the fastest data structure for determining if a string of letters is a real word, or possibly the prefix of a real word.

All of this code is available on my Github, and licensed under the Mozilla Public License v. 2.0.  The code on Github is a little more generic, and will work with both char and byte strings.

02Aug

“But what are they for?”

Posted by Elf Sternberg as Uncategorized

“But what are they for?”

Do you remember the days in pre-college when you were taking geometry, or algebra, or calculus, and wondering when in your long and varied life you would ever have a need to use the quadratic equation? I remember having that thought lots of time. I had that thought once more, the other day, when I stumbled across Julie Moronoki’s A Brief Guide to a Few Algebraic Structures.

The last six months of my life have been deeply engrossed in regular expression theory, and so it blew my mind a little when I stumbled upon this table:

Algebra Logic Types Regular Expressions
a + b a ∨ b Either a b (a|b)
a ⨯ b a ∧ b (a, b) ab
ba a ⇒ b a -> b ba
a = b a ⇔ b isomorphism a ≅ b
1 Unit ε
0 Void

This table is taken from Thinking with Types. That fourth column, “regular expressions,” isn’t in the original table, but it fits fairly well right there. The first two columns are known as the Curry-Howard Isomorphism, and is essentially a proof, in the mathematical sense, that every computer program is a mathematical equation and vice versa. Since every regular expression is a computer program and a mathematical equation, of course it fits in the Curry-Howard Isomorphism, but it does so with surprisingly direct elegance, and since type systems and regular expressions are set membership assertions with the exact same shape, every regular expression solver is a type system solver, and vice-versa.

This “algebraic structure” is known as a “semiring with closure,” and I’ve been head deep into regular expressions as semirings for the past couple of months.

Here’s the thing, though: I still wonder “What the hell are these things for?” I mean, I started to get part of it: if it fits into a semiring, you can replace it for a regular expression.

In fact, that’s what regexs do: as the regex consumes a string, it replaces that point in the regex and the string with a true/false value (see the “Logic” column above): “keep going” or “fail”. If you reach the end with “keep going” active, the you found the string you were looking for.

If instead of “keep going,” what if you (a) collected the letter being analyzed, and (b) did something smart with it, like, had a set of empty matches and then, for the | symbol, collected all the matches that passed, and for one expression following another, created the cartesian product set of matches. When you reached the end of the string, you’d either have an empty set (“fail”), or you’d have a set with all the legitimate matches — and that’s how capture groups work in classic regular expressions.

Categorically, we say that a regular expression is a function that takes a string and a semiring and returns a new semiring. The set of the semiring may contain a boolean about recognizing the string, or it may contain the number of valid paths through the expression for that string, or it may contain the set of strings found by that expression within the string. That’s it. That’s the whole story.

Great. But what are semirings for?

This, I think, is where mathematics breaks down for most people. It’s not enough to know “semirings” (or semigroups, or functors, or monads); you have to know not just what they are, but how they interact with other mathematical structures to produce results. It also requires a certain degree of cleverness, to be able to take those disparate elements and have that sudden insight.

Hao Huang recently did that with his Sensitivity Proof, in which he used an insight from a completely different section of mathematics to prove how sensitive a function might be, that is, how much change you would have to do to the inputs of a function in order to change the output. The problem has been well-known for 30 years, and Huang’s proof is considered ridiculously elegant, the hypothesis of which fits into a friggin’ tweet, and the total paper is only two pages long.

This is part of my love/hate relationship with Haskell. Haskell forces you to be a better programmer. You don’t have a choice. But at the same time, there needs to be a better way of explaining: “This is what this is for.”

Tech Republic has an article entitled Top priorities for professional developers: Why devs are always looking to learn new programming languages. It’s not until the bottom of the article that we get to any mention of programming languages versus programming skills in general. General skills are about things other than languages: Kubernetes and AWS are configuration skills, not languages. React is a skill and not a programming language. Using an IDE effectively is a skill and not a language.

"Opportunities for professional growth" and "Developing my skills as an engineer" are what are listed as the "top priorities," which includes but doesn’t specify programming languages.

Nonetheless, I think that there’s an important kernel of truth to the idea that it’s languages that developers want to learn, because programming languages are the only things that teach you how to think better.

Underlying React are two concepts. The first is the zipper. Zippers are fascinating and tie in, ultimately, to type systems, advanced data structures, and "regular languages," one of my areas of expertise. Zippers are a damn complex data structure best explored in one of two languages: Scheme, or Haskell. You can’t understand zippers until you’ve mastered one of those two languages, and understanding both allows you to understand both the mechanistic (Turing-machine) and theoretic (Curry-mathematic) interpretation and implementation of zippers. The other is the continuation, which is the fundamental data structure that allows programs to handle decision making. All decision making in a program, every if statement, every exception, every loop, is in some sense an implementation of a continuation. Scheme, again, is the fundamental programming language necessary to understand continuations. React uses both zippers and continuations, but as a developer you’d never need to know or learn about them.

But if you read enough Haskell and enough Scheme, you will. And that’s why, although programmers have to want to learn how to configure cloud deployments and networking and so forth, that’s just plumbing. Learning a new programming language gives your brain the tools necessary to do the exciting new stuff.

I don’t know a single Haskell developer who doesn’t believe the weak version of the Sapir-Whorf Hypothesis.

I once read a heartbraking story about a young woman who finished her MFA (Master of Fine Arts) degree in classical composition by listening to her masters thesis work, a full-length 40-minute symphony, played by a professional orchestra. It was the high point of her life at that point.

In her essay, she wrote about the profound sadness she felt that she’d never hear it played again onstage. She’d probably never write another one, and even if she did the only way she’d hear it is through a synthesizer, in the privacy of her own home. Perhaps shared on SoundCloud or YouTube or even Spotify.

But she’d never hear it again the way orchestral music is meant to be heard. She was a scholarship student; she didn’t have rich parents who could afford to put her onto the international composition circuit, sponsor her to expensive music festivals, and get her in front of critical symphony directors.

Software development is undergoing an equally problematic phase change. As a programming language dilettante enthusiant, I have the luxury of sitting around all day, trying out my ideas in Haskell or Racket, and then implementing them in some language that’s more tractable for others, like Rust or C. And that’s pretty much been true since P-system Pascal was released in the late 1970s. All you needed was a computer. Just one. The one on your desktop.

But today, if you want to do anything substantial in some of the fundamental up-and-coming fields, such as artificial intelligence, data science, or cloud computing, you need far more money. You need to be able to rent several farms worth of compute space, and if you’re doing anything at all interesting with AI, the cost of a single experiment could easily run into the hundreds, if not thousands of dollars. Nobody except the wealthy can afford to do that, or let their kids specialize in it.

Companies looking for that kind of experience just can’t get it off the street. The only way startups get people with cloud experience is by tempting someone away from an established company that put the time and effort into training someone. It’s not available in schools, and you’re certainly not going to be self-taught in systems reliability engineering or Kubernetes cloud deployments. Those skills come only through spending time with very large systems while someone else foots the bill.

What this means for the future of software development is anyone’s guess, but I’m starting to see already an awareness that there needs to be some kind of revamping of the educational pipeline to enable people to get these skills without having wealthy sponsors.

01Jul

The Sterling Bullet

Posted by Elf Sternberg as Uncategorized

One of the best books on software development ever written is the 1986 No Silver Bullet. Brooks’s central argument is that software development in a team requires the constant, daily transfer of active knowledge of progress, and the cost overhead of this transfer exceeds the value of additional developers fairly quickly; adding more people to a failing software project will actually slow the project down.

The classic joke around this book is that, if your manager proposes hiring more people to get the job done, you should buy him two copies of the book so he can read it twice as fast.

Alex Mills recently wrote an essay that got my attention (and that of a lot of other developers), in which he crystallized an emotion that a lot of programming language enthusiasts feel: The World Might Be Missing A Programming Language. Mills’s impression is one I used to share. To some degree I still share it, and I still love hacking on programming languages, but Mills’s laundry list of features he wants in his perfect programming language is the wrong list.

Let’s talk about four programming languages that are awesome, first.

Racket (i.e. Lisp)

Lisp is the great granddaddy of all great programming languages. Functional-first, mutation-capable, and possessing the ur-construct of all special cases (exceptions, parallel programming, concurrent programming), call-with-current-continuation, Lisp isn’t really so much a programming language as a language for writing other languages. It’s so malleable and powerful it can do almost anything.

Lisp’s malleability comes at a price: every developer writes it differently. Every lisp quickly becomes a hard-to-read pile of abstractions because every developer’s brain works differently, and Lisp has absolutely no guard rails.

Lisp also has exactly one semantic construct: the parenthetical. Every Lisp function looks exactly like every other function. Only the names changed. It can be hard, in a deeply nested Lisp function, to discover what is doing what to what.

Haskell

Haskell is the functional programming opposite of Lisp: it has Magical Guardrails. Haskell programs are strongly typed, but they use types not just as validation or as a description of memory, but as actual guidance to the compiler as to how the program should be assembled and run. Haskell is famous for the maxim "If it built, it will run," because types guarantee that the program will do something. It may not always be correct (it’s possible you wrote a plus where you meant minus somewhere, after all), but a huge set of possible errors simply don’t exist in Haskell.

Haskell’s syntax is clear and concise. Almost too concise; it can sometimes not be obvious where functionality is coming from, because the developer’s type-based request can lead to the compiler just going out into the library and, if there’s only one type match, automatically adding it. This is great if you know the library, not so great for beginners.

Haskell also uses some concepts from advanced topics in mathematics. Phrases like "structure-preserving transforms" and "monoids in the category of endofunctors" get thrown around, giving beginners a sense of terror at all the learning that’s about to happen.

Python

Python isn’t either of those language; Python is a dynamically typed language with a strict syntax and a huge standard library. Python is a hit because of that library: it was the first interpreted language to bring massive, available functionality for many of the things programmers did on a daily basis with its initial install. Python’s whitespace-oriented syntax annoyed people when it came out; now it’s considered something of a stroke of genius, as you ought to be indenting your scopes anyway.

Python is easy to learn, easy to teach, and at first glance "does what you mean." Its lack of types can lead to lots of debugging pain and unit testing, but for small programs it’s a wonder of fast productivity.

C

C gets a deservedly bad rap. It’s a language which pretends to have guardrails, but they’re mostly made of spaghetti. On the other hand, C creates predictable assembly language, and it’s possible to extract every last erg of power out of your CPU using it. But it’s "types" are mostly there to describe the layout of memory rather than securely associate functions with objects, and the semantics of C let you change types on the fly. This can be useful for systems programming, where a blob of memory can be a database structure, and the exact same blob just a stream of bytes to be passed over a network, without having to copy or transform the data, but the human overhead of debugging and the notorious security headaches has the world searching for an alternative.

Mills’ language already exists, sort-of

Every time I read a bullet point in Mills list, I had the reaction, Oh, you want Python, or Oh, you mean Haskell.

When he says "I want a language that makes writing asynchronous code easy," my reaction is: Haskell. Haskell goes the full math and says "If you squint just right, everything looks like everything else." A list is a container for a number of things; an exception is just a container for a thing that might fail; an asynchronous operation is just a container for a thing that will happen eventually. By leveraging this insight, Haskell can glue everything together into "an operation that might deliver a list eventually." But Haskell requires exceptional levels of cleverness to know how to put together its n-dimensional Lego pieces. It’s a great language to learn, and it is general purpose, but it’s hard to master.

He wants a Haskell that doesn’t require all that thinking.

A lot of his requests made me think: Lisp. The closest thing we have is Clojure, a Lisp that runs on the Java VM. It resists the classic Lisp explosion by leveraging the Java Standard Library, thus requiring that every deviation from the stock language converges on "tools that still run on the JVM." It’s a nifty restriction and Rich Hickey’s secret weapon. But it’s still a Lisp.

He wants a Lisp that can’t blow up, but isn’t restricted to a VM-only platform.

Like a lot of developers, I gripe a lot about the languages I know best. I complain about Python, Javascript, and Go because I know those languages, and am good at them. I love Haskell and Lisp and Rust, but I also know where those warts are and, unlike the first three, I’ve never been asked to work in them professionally; I suppose if I were using them for something other than recreational purposes I’d get tired of their faults just as quickly.

What Mills (and I, and a lot of other developers) really want is smarter programmers. Self-aware developers who care more abou the code than the usual hired guns we run across in this industry, the fly-by-night, $15/hour code-camp kids who just know how to search Stack Overflow.

When I first moved to Seattle in 1991, I had a year’s experience working as a Cobol & DB2 developer, an accounting degree, and a couple of men in dark suits and sunglasses following me around asking if I wanted to take an Ada job that entailed six months on-site and then a six-month vacation. [True story. I finally told one that “I don’t want to work at Pine Gap.” At the time, no one outside the government was supposed to know about Pine Gap, but the previous year’s revolt, in which every Ada developer at the place just up and quit was all over Usenet. Why they’d quit was obviously a top secret; it was just that there were a lot of Ada developers suddenly looking for work, and where they’d come from sorta leaked out. Just saying “Pine Gap” was enough to get me off their hiring list and probably into a file somewhere.] Desperate for work, I took a data entry position at little cellular phone company that long ago merged with one of the bigger ones.

It wasn’t actually much of a data entry position; mostly I was playing sneakernet for a sales team that spent its time cold-calling subscribers and asking them if they wanted to upgrade. It was an eight-person team, five men and three women, and they were all surprisingly diligent and good at their jobs, given how much we all hate cold-call sales these days. I guess it was new back then. They were all very different people: Dave was a big man, loud and brash; Lauren was a confident woman who spoke softly but persistently; Alex was a little blond man who drank too much coffee. You could write novels around characters like them.

Work came in as a list of phone numbers encoded on some kind of primitive industrial digital tape cassette. First thing in the morning, the tape would go into a machine and the first number would roll out to the first salesperson, and then the second. When a call ended, the machine would click forward and send another number. Efficient and relentless, and yet the team could keep it up for two hours at a time, take a break, and start all over again. My job was to sneakernet their hits and misses, which they recorded on their own DATs, into my machine and collate the final report for the day.

These tapes were assembled regionally: one day would be “all Wisconsin,” another “all Colorado,” and the next, “Greater Los Angeles.” In-house marketing teams, driven by surveys and their own instincts, assembled the tapes by hand. Remember: this is 1992, before the Internet was a commercial venture. There was no “big data.” There were, at best, a couple of expensive database products out there, and Excel.

Having studied accounting, I was pretty damned good at Excel 3.0, which had been released the year prior. I started to track our team’s success at the individual contributor level.

After about three weeks, when the team manager and I were alone in my office, I said, “I have something interesting to show you.” I pulled up my spreadsheets and showed him my effort. Dave was fantastic in Los Angeles, but sold absolutely nothing in Wisconsin. Lauren had a steady and reliable hit rate in Colorado, but didn’t do well at all in LA. And so on. I showed how each salesperson’s style meshed or didn’t mesh with a given region, and how we could predict with some accuracy how well they’d do on a given day given a regional tape marking. I told him, “It would be a lot better if we could assign them to the markets they know and are good at. They’d be upselling much more every day.”

He first said, “Huh. Let me think about this.”

The next day he came back and said in an angry tone, “Delete it. Delete all of it. Throw those spreadsheets away and never mention them again. Especially don’t mention this to the team. That’s not what we hired you to do.”

I was surprised. He softened a bit and said, “Sorry. When I told my manager I got my ass chewed. There’s no mechanism for assigning someone to a specific region and marketing would cut off my balls if I asked them to build tapes that way. If you told anyone on the team that they were bad in a given region, they’d probably not try very hard that day.”

I pointed out that Dave probably already knew he’d have a good day, maybe eighteen hits, with an LA tape, but he’d be lucky to get two upsells if he had a Wisconsin or Colorado tape. The manager nodded and said, “Probably. But we can’t make it official.”

Despite having worked at a brokerage firm for a year, this was my first real taste of corporate bullshit.

After working on a take-home quiz I have four numbers with regard to the "twitter clone" project given to me by ${MEGACORP}.

2,572

2,572 different Javascript libraries ended up inside the build tree for the demonstration application. That number does not include the global instance of the Prisma toolkit that I ended up installing on the recommendation of the tutorial. That number does not include the Prisma back-end, running on AWS, over which I had no ownership or control.

That’s 2,572 potential cases of corruption, infiltration, or code unreliability. No one involved with this project could possibly have vetted all of them, and there’s very little chance anyone could have a web-of-trust that encompasses all of them.

2,371,451

The final build size for this project was 2,371,451 bytes. That’s the size of the payload that gets downloaded to your client— desktop, phone, tablet— to run on your browser. 2.4 Megabytes. That’s a lot of code to run when all you want is a simple scrolling twitter feed.

[NaN]

I don’t know how many random accounts I have out there. I’ve been on the Internet since 1991; I’ve had account on AOL, CompuServe, MySpace, and a zillion other places. Authorizing Prisma to have access to my GitHub account for the purposes of authentication was just one more, and it annoyed me that local-first isn’t even on some companies’ radars.

32

32 is the number of hours I spent on a coding challenge. That’s a ridiculous number; no one who’s actually got a job could possibly have gotten through this assignment in anything like a valid amount of time.

On the other hand, learning five new technologies sufficient to "make it go" in only 32 hours is an awesome, and it was really good to see that my coding chops at the browser level are still as solid as they are at the back-end.

Afterward

The thing of it all is, I look at This is a Motherfucking Website and wonder how the hell we got from that to, well, to React. My story sites use native Javascript and treats the HTML as the source-of-truth, which is one of the reasons it’s so damn fast. The Javascript on those pages is minescule… less than 1 kilobyte, but they do the job of helping people navigate the site fast and efficiently and are still ARIA-compliant.

React is like Golang: both are enterprise-ready solutions that let developers do things fast enough, but hem the developers into pre-packaged tooling and solutions that limit thought and creativity. They’re both great tool in their roles, but they’re not what I would choose to work with recreationally.

Which is too bad, but what else can you do? They really do let companies throw stuff out fast, and if the consumer can’t keep up, well, it’s the consumer’s responsibility to upgrade their phone or laptop, isn’t it? Upgrade or die.

The world still deserves better.

So how did I do on the coding challenge? I have no idea. But here’s what I went through:

The README promised that there was a working, minimal implementation in the ZIP file. There was not. So the first thing I did was go through the How To GraphQL tutorial, which kinda gets you to the point of having a working Twitter clone. While going through it, I realized that the coding challenge was this tutorial, more or less.

Prisma is ridiculously difficult to run locally. It’s a cloud-first solution, written in Scala. In fact, ${MEGACORP} provided me with a Prisma instance running somewhere on AWS rather than ask me to try and run it on my laptop. So the first discovery was that part of the reason the example code they gave me wasn’t working was that I didn’t have a Prisma account; I had to log into Prisma and give it authentication via Github.

The next thing I realized was that, looking at the schema they provided me, it didn’t look right. I ran the prisma generate account and all these warnings and errors came back to me. Despite being only three months old, the schema provided was already deprecated; the @unique attribute had been augmented by the @ID attribute for data keys, and the syntax for date/time fields had changed. With the schema fixed, the Prisma account activated, and the database seeded, I actually started to see something in my "Twitter" feed.

It was time to turn my attention to the client.

Figuring out how to do login / logout was the hardest part. It involved all the moving parts, including authentication, and it was tricky. I ended up wrapping the entire app in a hand-written React Authentication.Context object that provided hooks to the login and logout function, as well as a state that indicated if there was a user and who it was. I so missed Rust’s sum types here; I wish Javascript had them, and in that form. (One of the wildest things I saw recently was that Typescript has sum types and enums, and they’re not the same thing. I filed that under "What the whatting what?") But once it was working, it was working fine.

I did have one moment where I couldn’t figure out how to banish the log-in popup. It was a two-stage asynchronous operation, one to handle the ‘submit’ even and another to handle the ‘login’ event. On a hunch, I wrapped the login handler in a console.log() and it returned a Promise which contained the return value from the login, so I could use a successful Promise resolution as the event to call the .dismiss() method. It worked, and it was elegant as hell, but I get the feeling it’s rather un-React-y; it was a "do something" rather than "be something" implementation.

I wrote out a few decision tables and decided I could live with it.

After that, things accelerated: I quickly sketched out how I wanted it to look, how I wanted the toolbar and profile sidebar to update, and getting them to work was interesting. I learned a megaton of Material and Material-UI in the process, although I’m still not keen on Material’s thematic engine.

I had a good time doing this. It’s not the best use of my skills, but it’s certainly satisfying to see things working in real-time, and I’m impressed with the tooling, at any rate.

Subscribe to Feed

Categories

Calendar

September 2019
M T W T F S S
« Aug    
 1
2345678
9101112131415
16171819202122
23242526272829
30