I’m a computer science student at MIT, with a love for type theory and a newfound interest in declarative and functional programming. My programming experience ranges from assembly to Haskell, from microcontrollers to supercomputers. Blogging, however, is fairly new to me!
My main non-technical hobby is music. I enjoy using my piano, electric violin, guitar, viola, pennywhistle, ukulele, computer, and voice to make music when I’m not doing computer science. I am an active member of two collegiate a cappella groups, the Asymptones and the Centrifugues. In the past I have also been a baritenor for MIT’s Concert Choir.
Contact me by email. Find me on Facebook and Twitter. Subscribe to my RSS or Atom feeds (you can also subscribe to individual categories by adding /category to the feed URL).
I wrote a ballad for tenor voice and piano featuring lyrics from William Blake’s poem “Never Seek to Tell Thy Love.” From a music theoretic perspective, this is my most sophisticated composition to date. The piece is written in B major but borrows chords from G#, with a modulation to C major and finally to A minor. Unconventionally, the chord progression I -> III is featured prominently throughout, with III functioning primarily as a pre-dominant. The sheet music is free and you can get it here.
Bill Cutter, director of the MIT Concert Choir (of which I am an alumnus), offered to sing the piece to the accompaniment of Professor Charles Shadle, and together they gave an incredibly powerful performance:
I’m taking a music theory/composition class at MIT called Writing in Tonal Forms. One of our class projects was to write a minuet and trio for string quartet in the tradition of 18th- and 19th-century Haydn, Mozart, and Beethoven. We had a professional string quartet from the Worcester Chamber Music Society perform our pieces! Here is the quartet reading my piece for the first time:
Thanks to Professor Shadle for guiding me in writing this piece and for recruiting the WCMS to perform it. Also thanks to Luyi Zhang for recording and uploading the video.
Fluid and responsive layouts are becoming more commonplace in modern web designs. It’s important that web applications are usable on all kinds of devices, ranging from smartphones to high-resolution desktop displays. I often use the responsive grid system from Twitter Bootstrap to build these layouts, but there are a few problems with Bootstrap’s fluid grids:
The size of the gutters depends on how deeply nested the columns are. For example, suppose I have two main columns, and the gutter between them has width \( x \). If one of those columns has two nested columns, then the internal gutter will be proportionally smaller than \( x \). Visually, this looks incorrect.
Bootstrap’s responsive grid styles make it difficult to apply vertical margins to the rows. The problem is that in the markup, a row consists of several columns. But when the window width is below a threshold value (768px by default), the columns stack vertically—each column essentially becomes its own row. However, the markup doesn’t reflect this change, and neither do the styles. As a result, the vertical margins are not applied to every column. You can’t put vertical margins on the columns themselves either, because the margins will collapse on small screens (when columns have float: none), but not on larger screens (when columns have float: left).
On small displays, Bootstrap’s responsive margin on the body element forces you to add CSS fixes for any elements that should be full-width (such as a header bar or footer). This margin should be on container elements (see the next section), not body.
So I decided to write my own fluid and responsive grid system which doesn’t have these issues. The code is written in SASS, which compiles to CSS. If you just want the compiled CSS, you can get it here (or get the minified version here). Everything is open source and in the public domain.
A Fluid Container
First, let’s build a container that resizes to fit the window, up to some maximum width. Later we can put our fluid grid layout in one of these.
/* --------------- */
/* Fluid container */
/* --------------- */
/* A container (and its padding) will not grow larger than this width. */
$container-max-width: 1210px;
/* The horizontal padding around containers. */
$container-gutter: 20px;
/* Main container class. */
.container {
width: 100%;
max-width: $container-max-width;
padding-left: $container-gutter;
padding-right: $container-gutter;
-webkit-box-sizing: border-box;
-moz-box-sizing: border-box;
box-sizing: border-box;
margin-left: auto;
margin-right: auto;
}
Using it couldn’t be easier:
<div class="container">
Some content...
</div>
Super exciting demo:
Some content...
Note that this is completely independent of the grid system. We can use containers without the grid system, and we don’t have to put the grid system in a container.
A Responsive Grid
Here’s the code for the grid layout itself. It has a number of tricks to make sure it works in all modern browsers (all the way down to IE7)—you certainly don’t need to understand it to use it. Notice that we can easily change how many columns there are, the gutter size, etc.
Again, using it is very simple. The markup is compatible with Bootstrap’s grid system. Here is a simple two-column layout:
<div class="row">
<div class="span6">
Left column!
</div>
<div class="span6">
Right column!
</div>
</div>
And this is what it looks like:
Left column!
Right column!
Of course, you can nest columns:
<div class="row">
<div class="span6">
<div class="span3">
Left column A!
</div>
<div class="span3">
Left column B!
</div>
</div>
<div class="span6">
<div class="span3">
Right column A!
</div>
<div class="span3">
Right column B!
</div>
</div>
</div>
And this is what you get:
Left column A!
Left column B!
Right column A!
Right column B!
You can also skip columns with offset classes:
<div class="row">
<div class="span5">
Check out that space on my right!
</div>
<div class="span5 offset2">
Check out that space on my left!
</div>
</div>
Another super exciting demo:
Check out that space on my right!
Check out that space on my left!
These layouts will expand to fill whatever element you put them in (that’s the “fluid” part), such as the container class we defined above. When the screen width is small, the columns will stack (that’s the “responsive” part).
Responsive Styles
For devices with small screens, we often don’t want all of the columns to stack. We may want to hide some information on mobile devices to save screen space. Here are some useful classes, inspired by their Bootstrap analogues, that can be used to conditionally display elements based on the screen size:
By default, mobile browsers optimize the viewport for presenting websites designed for a desktop browser. If you build a responsive layout that scales well to mobile screens, then you’ll want to configure the viewport manually. Apple has excellent documentation on mobile viewports, but you will likely find that you only need to add this markup to the head tag:
This tells the mobile browser to size the viewport to match the device’s physical screen size (rather than a larger virtual desktop).
Conclusion
This is a non-invasive replacement for Bootstrap’s responsive and fluid grid layouts. It can, of course, still be used with Bootstrap’s other features. It works in all the browsers that Bootstrap supports, and it doesn’t suffer from the issues I mentioned above. In fact, this blog now uses it! So all of the fluid, responsive grid demos on this page are actually nested in a bigger responsive grid that forms the layout of this blog—and this is no problem at all.
Subtyping can be a complicated topic, and it’s a nightmare for the programming language designer. This is due in part to confusion about a pair of concepts called covariance and contravariance\( ^1 \). In this article, I’ll explain how these concepts inductively provide a subtyping order on types in a type system.
Subtyping
The concept of subtyping is familiar to most programmers. The idea is that, given a type A, we can define a narrower type B, such that all values of type B are also of type A (inclusive subtyping) or convertible to type A (coercive subtyping). We write B <: A to signify that B is a subtype of A. This binary relation is usually reflexive (A <: A) and transitive (A <: B \(\wedge\) B <: C \(\Rightarrow\) A <: C), so it is a preorder on types. Types with the subtype relation may also form other graphical or order-theoretic structures such as directed acyclic graphs, partial orders, directed trees, or lattices, depending on the type system.
For simple types, we can define them to be subtypes of existing types. For example, I can define a type Monkey that is a subtype of Animal (i.e., Monkey <: Animal). But sometimes it is useful to have subtyping relations between types that we don’t explicitly define. For example, Integer -> Boolean is the type of Boolean-valued functions of integers. We never explicitly defined that type—so what are its ancestors and descendants? Parametric polymorphism also gives us families of types that we might want to give subtyping relations to. For example, if List<Number> is the type of lists of numbers, does it have ancestors and descendants? In the rest of this article, I’ll discuss how a type system might relate these composite types to other types with the <: relation.
Covariance
Perhaps the most obvious feature of subtyping is the ability to replace a value of a wider type with a value of a narrower type in an expression. For example, suppose I have some types Real, Integer <: Real, and some unrelated type Boolean. I can define a function is_positive :: Real -> Boolean which operates on Real values, but I can also apply this function to values of type Integer (or any other subtype of Real). This conversion from wider (ancestor) types to narrower (descendant) types is called covariance. The concept of covariance allows us to write generic code and is invaluable when reasoning about inheritance in object-oriented programming languages and polymorphism in functional languages.
Contravariance
Sometimes it makes sense for type conversions to happen in the other direction. For example, consider the function is_positive :: Real -> Boolean that we defined above. Suppose I want to write a function whose type signature is a subtype of Real -> Boolean. Then I could use that function in place of is_positive without worrying about type errors. What restrictions are there on the argument of this function?
We know that everywhere is_positive is called, it is passed a value whose type is Real or a descendant of Real (such as Integer). This means, at the very least, the function must accept values of these types. We are only allowed to change the argument type, Real, to any ancestor of that type (e.g., Number, provided that Real <: Number). For example, we could change the function to have type signature Number -> Boolean, but we can’t change it to Integer -> Boolean. This conversion from narrower (descendant) types to wider (ancestor) types is called contravariance, and it’s clear that function types are contravariant in their arguments.
Records
There are two ways to subtype records (tuples, structs, product types, objects, compound data). Consider the following record type, which represents a point on the plane:
struct Point {
x :: Real
y :: Real
}
One way to make a subtype of Point is to add extra members. This is called width subtyping. For example:
struct ColoredPoint <: Point {
x :: Real
y :: Real
color :: Color
}
Clearly, any operation that is valid for Point values will also work on ColoredPoint values (these operations can simply ignore the color field).
Another way to subtype Point is to do a covariant substitution of its member types. This is called depth subtyping. For example:
struct GridPoint <: Point {
x :: Integer
y :: Integer
}
For immutable records, this is allowed because Integer <: Real. However, depth subtyping breaks for mutable records. For example, suppose I have a function set_x :: (Point, Real) -> () which sets the x-coordinate of a Point (and returns nothing). I should be able to use this function on a GridPoint, because GridPoint <: Point. What happens if I try to use set_x to change the x-coordinate of a GridPoint to 2.5? A GridPoint isn’t allowed to have non-integer coordinates, so the type system isn’t sound. It must be the case that mutable records are invariant (neither covariant nor contravariant) in their member types.
Functions
Consider the function type ColoredPoint -> Real. An example of a function with this type is the function which returns the distance from a ColoredPoint to the origin (e.g., norm(p) = sqrt(p.x * p.x + p.y * p.y)). There are two ways I can subtype this function type.
Consider a version of the norm function which takes a Point (rather than a ColoredPoint) and is otherwise the same. It is clear that I can use this function in place of norm anywhere without type errors, so Point -> Real <: ColoredPoint -> Real. In fact, I could have replaced ColoredPoint with any of its ancestor types. In other words, function types are contravariant in their argument types.
I can also change the return type. We’re expecting a Real value from this function, so we can only change the return type to a descendant of Real. For example, I could write a version of norm that rounds the answer to the nearest Integer. This substitution would not cause any type errors, because Integer <: Real. So we have Point -> Integer <: Point -> Real. Of course, any descendant of Real would have worked, because function types are covariant in their return types.
So function types are contravariant in their argument types and covariant in their return types. You may recognize this as a formal way of stating the robustness principle.
Parametric Polymorphism
Parametric polymorphism is when code is written to work with a family of types rather than a single specified type. For example, you’ve seen parametrically polymorphic code if you’ve used templates in C++ or generics in Java (or almost any modern functional programming language).
Lists in most programming languages are parametrized on the type of their elements. For example, List<Point> is the type of lists of Point records. Recall that ColoredPoint <: Point. Naturally, one might ask: is it the case that List<ColoredPoint> <: List<Point> (or vice versa)?
In a pure functional programming language, then List<T> is covariant in its parameter T. Any operation we can do on a List<Point>, we can do on a List<ColoredPoint> as well (just by ignoring the colors!).
Things are not as nice when lists are mutable. If we have a List<ColoredPoint> and we try to add a Point to it, we get a type error because that Point might not be a ColoredPoint. So List<ColoredPoint> is not a subtype of List<Point>. But similarly, if we have a List<Point>, and we try to get the first element as a ColoredPoint, we will also get a type error (because the first element might not be a ColoredPoint). So List<Point> is not a subtype of List<ColoredPoint> either.
In general, mutable parametric types are invariant in their parameters.
Conclusion
Covariance and contravariance are simple concepts, although the way they interact with other features of a type system may lead to unexpected complexity. (The picture we’ve painted here is basically a simplified look at the System F\(_{<:}^2\) type system, which formalizes these notions.) For records and polymorphic types, things are nicer when data is immutable. Perhaps this is just another reason we should use pure functional programming languages.
[1] The Wikipedia entry on covariance and contravariance is not a great resource to learn about these concepts. It has some misleading or incorrect explanations (I have fixed some of them, but the article remains a bit topsy-turvy at the time of this writing).
[2] Cardelli, Luca; Martini, Simone; Mitchell, John C.; Scedrov, Andre (1994). “An extension of system F with subtyping”. Information and Computation, vol. 9. North Holland, Amsterdam. pp. 4–56.
I sometimes use Python for quick-and-dirty computations. Its “batteries-included” standard library makes it convenient for all kinds of tasks. Python is an interpreted programming language, and it sometimes shows. I often complain about its performance, but today I thought I would do a benchmark to back up my frustrations.
Now, first and foremost, naked Python is not a number-crunching tool. For I/O-bound operations, Python is an excellent tool, and this benchmark does not challenge that fact. However, other dynamic programming languages such as JavaScript and Lua are often JIT-compiled these days, and their performance is almost comparable to native code generated from a statically-typed language.
So today, I want to do the simplest possible benchmark to see just how much slower Python is than other programming languages when it comes to CPU-bound operations. We’re going to count to a billion with a simple while loop.
C++ (Unoptimized)
I’ll start with C++ as a baseline. I’m compiling the following in g++ with no optimizations:
int i = 0;
while (i < 1000000000)
++i;
Normally you would use a for loop for something like this, but for loops work differently in C++, Python, and JavaScript, whereas while loops are essentially identical in these languages.
The code above consistently takes about 1.78 seconds on my 2.6 GHz Intel Core i7 (so each iteration takes 1.78 nanoseconds). Just for fun, let’s take a look at the assembly for this loop:
Let’s go through this line by line. The first line tells the processor to jump to the L2 label, which is the conditional part of the loop. The second line is a label representing the beginning of the loop body. The third line corresponds to ++i in the source. Line 4 is the label we jumped to from Line 1, marking the start of the conditional part of the loop. Computing whether i < 1000000000 is a multi-step process: First, Line 5 computes i - 999999999 and updates the EFLAGS register with the result. The setle instruction on line 6 then looks at this register to determine whether i <= 999999999, storing the result in the AL (accumulator) register. The testb instruction on line 7 does a bitwise AND of AL with itself, updates ZF (the zero flag), and discards the result (i.e. this instruction tests if AL is zero). Finally, line 8 tells the processor to jump back to the beginning of the loop if ZF is unset. This is not an efficient way to count to a billion!
Interestingly, the math reveals that we are doing 2.8 billion instructions per second on my 2.6 GHz CPU. On CISC processors like my Intel Core i7, it is common to execute on average more than one instruction per clock cycle. This is due to instruction-level parallelism.
C++ (Optimized)
Here is the assembly listing for the same code compiled with optimization level 1 (-O1):
movl $1000000000, %edx
L2:
subl $1, %edx
jne L2
If we tell g++ to optimize the code any further, the optimizer actually removes the loop entirely! Notice that this assembly counts down from a billion rather than up. Compilers do weird things with your code. This version ran in 0.284 seconds. That’s more than 6 times faster than the version above.
The assembly is pretty straightforward. Line 1 moves the value 1000000000 into the EDX register. Line 2 is a label that marks the start of the loop body. Line 3 decrements the EDX register. Line 4 tells the CPU to jump to the beginning of the loop if EDX is nonzero.
The core loop consists of two instructions (the decrement and the jump). 2 billion instructions in 0.284 seconds is 7 billion instructions per second! Again, instruction-level parallelism is responsible for this incredible performance on a single core.
Python
Now let’s write the same code in Python.
i = 0
while i < 1000000000:
i += 1
This is a direct line-by-line translation from the C++, and took 58.01 seconds in CPython, the most popular Python implementation. That’s about 33 times slower than unoptimized C++, and 204 times slower than optimized C++. Here are the opcodes, again, just for fun:
Lines 4-12 are the opcodes that are run each iteration of the loop. So 1 billion * 9 opcodes / 58.01 seconds = about 155 million opcodes per second. It’s like we’re in the 1990s!
So, Python is slow. What else is new? Let’s compare Python to another dynamic programming language.
JavaScript
JavaScript and Python runtimes have a similar job—to execute source code in their respective languages. Both languages are dynamically-typed, which is a crutch to static optimization. We would expect their performance to be comparable. Here’s the JavaScript version of the benchmark:
var i = 0;
while (i < 1000000000)
++i;
I’m testing this in V8, which is the fastest JavaScript runtime at the time of this writing. JavaScript takes 2.32 seconds. That’s comparable to the unoptimized C++ version! The neat thing about V8 is that if you write JavaScript like C++, it will perform like C++. Most web applications, however, use frameworks that take advantage of JavaScript’s dynamic nature (prototypical inheritance, reflection, dynamic types, etc.) and run much slower.
Conclusion
So, while Python is invaluable as a tool for prototyping or writing IO-bound applications, its CPU-bound performance is behind the times. Other dynamic programming languages are rapidly approaching the performance of native code, whereas Python is still slowly chugging along behind.