Skip to content

Blog

Marginal vs. Conditional Subtyping

In computer programming, a type is a just a set of objects—not a physical set of objects in memory, but a conceptual set of objects. The type Integer is the set {0, 1, -1, ...}. Types are used to reason about the correctness of programs. A function that accepts an argument of type Integer, will work for any value 0, 1, -1, etc., for some definition of "works". Subtyping is used to define relationships between types. Type B is a subset of a type A if the set of objects defined by B is a subset of the objects defined by A. Every function that works on an instance of A also works on an instance of B, for some definition of "works". If we were just doing math, subsets would be the end of subtyping. But types as pure sets exist only conceptually. Actual types must be concretely defined. It is not very efficient to define the Integer class by writing all possible Integers! In most programs, the possible values of a type are constrained by their fields. Subtypes and supertypes typically differ by having more or fewer fields than the other. Sometimes, the subtype has more fields, and sometimes, the supertype has more fields. Many of you may be thinking, "What? It's always one way, not the other!" The funny thing is that some of you think the subtype always has more fields and others think the supertype always has more fields. That's because there are two kinds of subtyping. The first is what I call "marginal subtyping", which is encountered in application programming and is well modeled by inheritance. The second is what I call "conditional subtyping", which is encountered in mathematical programming and is well modeled by implicit conversions. Depending on the genre of programming you work in, the other kind of subtyping may be unknown and the language features needed to implement it may be maligned. But both needs are real and both features are necessary.

  • in culture
  • 4 min read

The Missing 23rd of the Month

Previously, I explained why the 11th of most months is mentioned far less than the other days in the Google Ngrams database of English literature from 1800-2008. This was to solve a long-standing question posed in an xkcd comic. While researching this, I encountered another mystery: the 2nd, 3rd, 22nd, and 23rd are unusually low as well—but only until the 1930s, at which point they become perfectly normal days. Last time, I set this question aside to focus on the 11th. In this installment, I explain the strange behavior of these four days.

  • in culture
  • 9 min read

The Missing 11th of the Month

In months other than September, the 11th is mentioned substantially less often than any other date. It's been that way since long before 9/11 and I have no idea why. In months other than September, the 11th is mentioned substantially less often than any other date. It's been that way since long before 9/11 and I have no idea why. Source xkcd. Image licensed under CC-BY-NC.

On November 28th, 2012, Randall Munroe published an xkcd comic that was a calendar in which the size of each date was proportional to how often each date is referenced by its ordinal name (e.g. "October 14th") in the Google Ngrams database since 2000. Most of the large days are pretty much what you would expect: July 4th, December 25th, the 1st of every month, the last day of most months, and of course a September 11th that shoves its neighbors into the margins. There are not many days that seem to be smaller than the typical size. February 29th is a tiny speck, for instance. But if you stare at the comic long enough, you may get the impression that the 11th of most months is unusually small. The title text of the comic concurs, reading "In months other than September, the 11th is mentioned substantially less often than any other date. It's been that way since long before 9/11 and I have no idea why." After digging into the raw data, I believe I have figured out why.

Sane Equality

Equality: every programming language has it, the == syntax is as universal as 1+1, and it works almost the same in every language. When the left and right operands are the same type, equality is easy. No one questions that 1==1 evaluates to true or that "a"=="b" evaluates to false. This post is about what to do when the operands are different types. What should 1=="1" be? Or what should Circle(1,2,2)==Point(1,2) be? Or what should ColoredPoint(1,2,red)==Point(1,2) be?

When Sequences Go Bad

In my last post, I talked about the various kinds of syntax for getting and setting elements in sequences. This post will talk about semantics. What exactly should get and mutate do when invoked? What should happen when the index is valid is hopefully obvious. But because we have to handle the case of an invalid index—in particular, an index larger than the length of the sequence, the answer is not as clear-cut as it may seem. If "throw an exception" is the only thing that comes to mind, you have been stuck in procedural programming for too long.

One-Sided Debate over Sequence Syntax

Computers are famously stupid machines. You have to tell them in perfect detail not just what you want them to do but how to do it. A computer may be able to add 1 and 2 faster than I can, but it will take me longer to tell it to do that than for me to do it myself. The more complex the task, the more time it takes to code. Coding is still laborious and entirely not worth it unless such code will be used many times. I posit that a computer is only useful for doing work when the vast majority of the work to be done is repetitive tasks on simple objects. The most common abstraction for representing a bunch of objects is the sequence (also known as a list or array), in which each object in the collection is associated with an integer called its index. There is a wide diversity of syntax and semantics for accessing and changing sequences.

Difficulty of Pattern Matching Syntax

Pattern matching is compact syntax, originating in functional programming languages, that acts a super-charged switch statement, allowing one to concisely branch on the types and components of a value of interest. Like a traditional switch statement, a pattern match takes a single object and compares it to sequence of cases, running the code body associated with the matching case. There are many parts to a pattern matcher. and design concise and unambiguous syntax is a difficult endeavor, one failed by many popular programming languages.

  • in policy
  • 9 min read

Free Star Wars for Everyone

You got a robotic vacuum cleaner for Christmas. It is the cutest little thing—circling around the room, diligently picking up confetti from the New Years Eve party the night before. You just can't let all that cuteness go to waste. So you record the whole cycle on your phone—the whole two hours and twenty minutes—and post it to your Youtube channel. You have 5 subscribers, all spam bots. Your video goes on to get a million views because the pet name you gave to the vacuum matches the name of an politician recently embroiled in scandal, making "<politician's name> Cleans House" accidental clickbait.

Comparison of Iteration Styles in Programming

It is difficult to overstate the importance of iteration in programming—the process performing an operation on each element of a list. I would rank only variable assignment, functions calling, and branching as more important. Unlike the if statement, which is essentially the same in every language, the semantics of the for loop varies across languages. Mainly for my own future reference, this post compares the various styles of iteration that I have come across. The examples are in pseudo code which is the only way to write so many different iteration styles under similar syntax. Each of the examples is trying to do the same thing: print out each element of a list called list.

  • in policy
  • 7 min read

The Electoral Jury

How much time to do you spend figuring out how you should vote? A few hours? A few minutes? Any time at all? I could not find a study that measured the average time that voters spend researching their candidates, but I did find that three quarters of Americans do not know how long a senator's term is. Perhaps an average voter reads the blurbs in the local newspaper, listens to some soundbites on the news about each candidate, and watches a myriad of television ads. Does he read each candidate's website? If not, this is like owning a bagel shop and hiring a manager without reading his resume. Imagine a bagel shop where all employees are hired with the same consideration that the average voter gives to political candidates. Such a shop would operate with the legendary efficiency and effectiveness of a DMV.