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 marginal subtyping, which is encountered in application programming and is well modeled by inheritance. The second is 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.

Sane Equality

Equality: every programming language has it, the `==` syntax is 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.

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`.