sitr.us - posts by Jesse Hallett

Nix, NPM, and Dependabot

Fri, 08 Mar 2024 00:00:00 GMT

I have a project, git-format-staged, that I build with Nix. It includes NPM dependencies, and it is convenient to have Dependabot keep those up-to-date for me. Dependabot creates pull requests that update package-lock.json when it sees updates with security fixes and such. But my Nix configuration includes a hash of the project NPM dependencies - that hash must be updated when package-lock.json changes. Unfortunately Dependabot does not know how to do that. So I came up with a workflow to help that bot out.

The hash is in test/test.nix:

The product of that repo is actually a zero-dependency Python program. I'm just using Node and NPM to run a test framework (for perfectly-valid reasons). I have implemented test runs as derivations which means they run in Nix' sandboxed build environment. To get reproducibility that means network requests are not allowed unless I specify the hash of what's going to be downloaded up front. The hash here is a recursive hash of a directory of downloaded NPM packages that can be installed later by running npm install --cache.

(When I'm working on Rust projects I use Crane which is able to infer dependency hashes from Cargo.lock so I don't need to update a hash in a Nix expression when dependencies change. I haven't found a tool that does that for NPM, so for now at least I have this hash to keep up to date.)

Updating the Hash

So what I want is an automated process that updates that hash when package-lock.json changes. That means I need to be able to:

compute the new dependencies hash
update test/test.nix with the new hash

There are existing solutions out there for doing this kind of thing. For example the nixpkgs repo has maintainers/scripts/update.nix. I did some looking to see if there is something out there that would work for me. But then I decided it would be easier to write my own solution.

fetchNpmDeps is a fetcher in nixpkgs that is specialized for fetching NPM dependencies - given a source directory with a package-lock.json file it fetches exactly what you need. Most Nix fetchers come with a corresponding "prefetch" tool that tells you the hash of the fetched content. fetchNpmDeps is paired with prefetch-npm-deps (defined in the same file) for that purpose. I can use prefetch-npm-deps for step 1, and a little sed for step 2. I ended up with this package definition in my flake.nix:

Now I can run this command to update the hash automatically:

The script ends up being quite simple, partly because I only have one hash in test/test.nix so it is easy to target the sed script. I could keep things cleaner by separating the hashes out into a separate file:

In that case the update script would look like this:

Automation to Help Dependabot

Every one of the Dependabot PRs in my repo was failing required checks because the PRs updated package-lock.json, but did not update that hash. So the next step was to set up a Github workflow to run the hash-updating script after every change from Dependabot.

It would be great if I could configure Dependabot to run a custom shell command along with its updates. But as far as I can tell that is not an option. Instead I added a workflow that runs on pushes to Dependabot's PR branches. Those all have names of the form dependabot/npm_and_yarn/*. After some research I used this workflow, .github/workflows/dependabot-post.yml:

This workflow enables a special permission to allow it to push commits back to the repo. That can be dangerous if you have third-party code running because that code would have access to modify your repository. Notably NPM packages can run arbitrary code when they are installed. But that is not an issue here: prefetch-npm-deps does not "install" dependencies so it does not run package install scripts. Instead it pre-populates a local cache that can be "installed" later.

Normally Dependabot will refuse to automatically update one of its PRs after someone else has pushed commits to it. The workflow includes [dependabot skip] in its commit messages to signal to Dependabot that it is OK to throw those commits out when it recreates or rebases its PRs. When that happens the workflow runs again, and re-applies the correct hash.

Note that I don't have to worry about getting into an infinite loop because once the correct hash is set any subsequent runs will be noops, and so will not trigger more branch push events.

So now I'm happily automated, and I've been merging a bunch of Dependabot PRs that I let pile up.

`void` is not a unit type in TypeScript

Sat, 04 Dec 2021 00:00:00 GMT

In type theory a unit type is any type that represents exactly one possible value. The unit types in TypeScript include null, undefined, and literal types.

TypeScript also has the type void which is used as the return type for functions that don't have an explicit return value. In JavaScript a function that does not explicitly return implicitly returns undefined; so at first glance it would seem that void is an alias for the undefined type. But it is not!

We can test this by checking assignability:

If they were the same type, undefined and void would be mutually assignable.

According to the Handbook, "[void is] the absence of having any type at all." TypeScript is nicely consistent with the behavior of types as sets. (any is an exception because it does not behave like a well-defined set.) "The absence of any type at all" is not a sensical statement about sets; so that description seems odd to me. But that may be a way of explaining that in some ways void, like any, does not behave as a well-defined set.

undefined is assignable to void which tells us that the type void does include the value undefined. From a type theory perspective the fact that the reverse is not allowed implies that void represents a set of possible values that includes values other than undefined. And we can see that is true in practice. If you have a variable with a function type where the return type is void, any function is assignable to that variable regardless of the actual return type as long as the argument types are compatible.

This behavior is convenient - instead of requiring certain return values the use of void in this case is more like a statement by the caller that it will ignore the return value of the callback. But we can see in this example that although the type of x is void, values assigned to x could strings, numbers, or booleans. In fact x could be assigned any type of value!

This makes it look like it would be most accurate to think of void as an alias for unknown. That would be consistent with the assignability tests from before: undefined is assignable to unknown, but unknown is not assignable to undefined. But now let's look at the ways in which void does not behave like a set.

If void were a set that contains every possible value (and in the foo example we have seen that in practice it is) then we should be able to assign any value to a variable of type void. But it turns out that the only value that TypeScript will permit assigning to a variable of type void is undefined:

It looks like either TypeScript has a special rule that prohibits assignment to void variables, or TypeScript thinks of void as a small set but the void return callback feature lets non-void values "leak" into void variables.

My suggestion for making TypeScript more consistent is to make void a proper alias of undefined. It's possible the reason that it was not set up that way in the first place is that void predates unknown. In any case, that is how I am going to think of void going forward.

Choosing a headless CMS

Wed, 29 Apr 2020 00:00:00 GMT

This is an excerpt of a post that I wrote for my employer, Originate.

One of our recent projects called for a feature to allow editors to manage and publish content. In other words, we needed a CMS. We already had a React-based web app, and a React Native mobile app in the works where we wanted to present that content. So we needed a Headless CMS. Unlike Wordpress or other traditional CMS solutions, a headless CMS does not come with a web interface where readers will see published content. Instead, a headless system acts more like a database: it hosts content, and your app uses an API to fetch content to display. As a result, your choice of app architecture is not tied to your choice of CMS. This can be especially helpful if you want to incorporate managed content into an app that is not primarily a publishing platform, or if you want to present the same content differently in different contexts as was the case with our web vs mobile apps.

One of the biggest challenges with headless CMS systems is choosing one. The field is wide open, and headless systems have not been around long enough for a clear leader to stand out.

» Read the rest on the Originate blog.

When to use `never` and `unknown` in TypeScript

Tue, 29 Jan 2019 00:00:00 GMT

This is an excerpt of a post that I wrote for LogRocket.

The never and unknown primitive types were introduced in TypeScript v2.0 and v3.0 respectively. These two types represent fundamental and complementary aspects of type theory. TypeScript is carefully designed according to principles of type theory, but it is also a practical language, and its features all have practical uses – including never and unknown. To understand those uses we will have to begin with the question, what exactly are types?

Types explained using set theory

When you get down to a fundamental definition a type is a set of possible values, and nothing more. For example, the type string in TypeScript is the set of all possible strings. The type Date is the set of all instances of the Date class (plus all structurally-compatible objects), and the type Iterable<T> is the set of all objects that implement the iterable interface for the given type of iterated values.

TypeScript is especially faithful to the set-theoretic basis for types; among other features, TypeScript has union and intersection types. A type like string | number is called a "union' type because it literally is the union of the set of all strings, and the set of all numbers.

» Read the rest on the LogRocket blog.

Automatic Code Formatting for Partially-Staged Files

Thu, 16 Aug 2018 00:00:00 GMT

This is an excerpt of a post that I wrote for Olio Apps.

I wrote git-format-staged to apply an automatic code formatter or linter to staged files. It ignores unstaged changes, and leaves those changes unstaged. When run in a Git pre-commit hook git-format-staged guarantees that committed files are formatted properly, and does not clobber unstaged changes if formatting cannot be applied to working tree files cleanly.

How I learned to love automatic formatting

I used to pay a lot of attention to code formatting. I would split or join lines, indent to just the right column, and so on. Then I learned about Prettier, and tried it out in my Javascript projects. After setting up an editor plugin I could tap a key combination, and Prettier would do the same things that I was doing by hand in an instant without any thought on my part. The code did not wind up in exactly the style that I was used to - but it was formatted according to a set of consistent, sensible rules that I can live with. I realized that if I can trust a program to format my code nicely I can free up a not-insubstantial chunk of my attention. That leaves me with more mental capacity to devote to matters that actually require human input. I have not looked back!

» Read the rest on the Olio Apps blog.

I finally set up XMonad to build with Stack!

Sun, 13 May 2018 00:00:00 GMT

The XMonad window manager is configured in Haskell. That means that when you want to apply a new configuration you actually build xmonad itself incorporating code from your configuration file. It sounds more painful than it is - when you install xmonad you get an executable called xmonad that handles the details of bootstrapping your custom build. The command xmonad --recompile builds ~/.xmonad/xmonad.hs, and subsequent invocations of xmonad run the executable that is produced.

When you configure xmonad you are actually writing your own version of the program. Because you can write arbitrary code the possibilities for customization are endless! As with any software project, you get maximum expressive power when you bring in third-party libraries. xmonad-contrib is a popular choice - but you can import any Haskell library that you want. With libraries come the problem of managing library packages. In the past I used the cabal command to globally install library packages. From time to time I would clear out my installed packages, or change something while working on another Haskell project, and then my window manager would stop working. I wanted a better option.

Stack is my preferred dependency management and build tool for Haskell projects. Stack automatically fetches project dependencies, and maintains isolated sets of installed packages for each project. With stack I declare dependencies in a .cabal file, and stack ensures that I have up-to-date copies of all libraries whenever xmonad builds itself.

To use stack I needed to hook into xmonad's build process. I used this blog post as a starting point. That post provides instructions for using the stack ghc command to invoke ghc in an environment prepared by stack. But I have some custom code modules in ~/.xmonad/lib/, and I had problems getting ghc to find those when running stack ghc. So I opted to set up a fully-fledged stack project which is built with the usual stack build command. You can take a look at my ~/.xmonad/ directory to get the high-level view.

The key is the build script. Starting in xmonad v0.13 if there is an executable called build in your ~/.xmonad/ directory then xmonad will defer to that script. build gets a path as an argument which is where the compiled xmonad executable should be placed. My script looks like this:

My my-xmonad.cabal file declares an executable named my-xmonad (which is actually my customized version of xmonad). This script builds that executable, installs the it to ~/.xmonad/bin/my-xmonad (thanks to the --local-bin-path argument to stack install), and finally moves the executable to the location given by the first argument to the build script.

You can detailed on working with stack from stack's user guide. If you want to get going quickly I created a stack project template to set up xmonad with stack. Here is what you do:

Install xmonad and stack using your preferred package manager - you need xmonad v0.13 or later.
Run stack new my-xmonad https://raw.githubusercontent.com/hallettj/dot-xmonad/master/home/.xmonad/xmonad.hsfiles
If you are setting up a new xmonad configuration then mv my-xmonad ~/.xmonad. Otherwise copy files from my-xmonad/ to ~/.xmonad/ and then delete my-xmonad/. The relevant files are:
- my-xmonad.cabal, your project manifest
- build
- lib/ - this directory must exist or the project will not build!
- xmonad.hs, in case you do not have your own
- .gitignore, in case you want to version-control your xmonad config
chmod a+x ~/.xmonad/build - if the build script is not marked as executable xmonad will not execute it.
In ~/.xmonad/ run stack setup to install the version of ghc that stack wants to use. (Stack installs ghc in a sandbox so that it does not conflict with any other ghc installation on your machine.)

Names of any custom modules that you have in ~/.xmonad/lib need to be listed in the other-modules section in ~/.xmonad/my-xmonad.cabal. If you want to add library dependencies beyond xmonad and xmonad-contrib then add them to the build-depends section in the same file. Stack pulls dependencies from Stackage, which hosts curated sets of packages. The resolver setting in stack.yaml determines the version of each dependency that you get, and the version of ghc that stack will use to compile xmonad. If you want to use libraries that are not hosted on Stackage you will need to list package names with exact version numbers in the extra-deps section in stack.yaml according to these instructions.

Test everything by running xmonad --recompile from any directory. If that works then you are all set!

Checking Types Against the Real World in TypeScript

Thu, 12 Apr 2018 00:00:00 GMT

This is an excerpt of a post that I wrote for Olio Apps.

The shape of data defines a program. There are important benefits to writing out types for your data.

Let’s consider a Hacker News client, which consumes stories and other items from the Hacker News API. This is a TypeScript type that describes the format for stories:

In Javascript and other dynamically-typed languages, it is common to write a program without any explicit description of a data structure like Story. The shape of the data is implied in the code that manipulates the data. But that means anyone reading the code has to mentally reconstruct that shape from context, or refer to documentation outside of the program itself.

» Read the rest on the Olio Apps blog.

Type-Driven Development with TypeScript

Mon, 12 Feb 2018 00:00:00 GMT

This is an excerpt of a post that I wrote for Olio Apps.

I am always interested in making my coding process faster and more robust. I want to be confident that my code will work as expected. And I want to spend as little time as possible debugging, testing, and hunting down pieces of code that I forgot to update when I make changes to a project. That is why I am a fan of correct-by-construction methods. Those are methods of constructing programs where the program will not build / compile unless it behaves the way that it is supposed to.

Correct by construction

Test-driven development is one form of correct-by-construction method. The philosophy of test-driven development is that your tests are the specification for how your program should behave. If you look at your test suite as a mandatory part of your build process, if your tests do not pass the program does not build because it is not correct. Of course the limitation is that the correctness of your program is only as certain as the completeness of your tests. Nevertheless studies have found that test-driven development can result in 40%-80% fewer bugs in production.

Writing your program around types

Type-driven development is the practice of writing your program around types, and of choosing types that make it easy for the type checker to catch logic errors. In type-driven development your data types and type signatures are the program specification. Types also serve as a form of documentation that is guaranteed to be up-to-date. Type-driven development is another correct-by-construction method. As with test-driven development, type-driven development can improve your confidence in your code, and can save you time when making changes to a large codebase.

» Read the rest on the Olio Apps blog.

What is Poodle

Tue, 20 Jun 2017 00:00:00 GMT

This is a description of my passion project. I plan to publish more detail and motivation when I get to a minimum viable product.

I want to make social collaboration software without walls. A company can have its private discussions and documents - but people in a company should be able to include clients or contractors in discussions seamlessly. It should not be necessary to require people to join a private account on service X just to have a conversation.

The idea is to make a decentralized protocol - there is no central server, and no one company that controls everything. This has been attempted before by Identi.ca, Diaspora, Google Wave, and others. I thought that a decentralized protocol could have more success if it takes a different approach: reinvent as little as possible, and build on top of an existing protocol with a large user base. I'm working on a reference client (called Poodle) that implements a new protocol that builds on email.

Email is one of the few decentralized social protocols that has broad adoption (2.6 billion users); and it has stood the test of time. Email is not perfect - but over the years email systems have evolved to address many subtle problems; and we have deployed a great deal of email infrastructure and supporting software. A protocol that builds on email instead of attempting to replace it will have a massive head start thanks to all of that work.

There is a deeply-set mindset that email messages are text or HTML, and that one message corresponds to one reply. This is the same way people thought about web pages in the '90s. Then AJAX came along and changed everything by decoupling HTTP requests from page views. That was the big idea that led to Web 2.0. I want to apply a similar idea: decouple email messages from conversation replies, and use email to transport structured JSON data representing activities. A basic activity type would be "post a message" or "post a reply". But there are less obvious activity types, such as "make an edit to a message that I sent earlier", or "upvote that other message". Those latter types affect the way that participants see a discussion, but are not presented the same way that replies are. I think that this idea can lead to many new applications that operate over email in ways that we never imagined.

An important feature is that I do not have to get people to switch to a new system en masse. These new-style exchanges degrade gracefully when viewed in a traditional email client. If someone edits one of their messages after sending it, Poodle users see the edited version with a small note that says "edited a few minutes ago". Users on traditional email clients see the edit as a follow-up message with the new content. Where Poodle users see +1 counts, traditional email users see messages that just say "+1" (or whatever text the sender has selected for their fallback "like" message). This works because email supports multiple data parts, including fallback presentation for clients that do not understand a new format. Poodle messages contain a JSON part intended to be consumed by Poodle (or other interoperable clients), and an HTML view of the same content for traditional clients.

Poodle supports interaction modes beyond the traditional "email exchanges are discussions" point of view. Poodle splits out several activity types that can serve as the starting point of an interaction - for example there is a "share a document" option. The document might be HTML edited directly in the client, or an uploaded file such as a spreadsheet, presentation, image, or video. Anyone who the document is shared with can edit the document. What really happens is that their client sends out an "edit" activity to collaborators; but what everyone sees is that the document in their client updates with the new changes. (And anyone can browse previous revisions of a document at any time, because those revisions are really just email messages on their IMAP server.) Once again, people using traditional clients see document edits as follow-up messages with the new content in its entirety.

I have a small slide deck of screen shots from an early iteration of Poodle.

Keep in mind that all of the features that you see work without any new servers. This is all just email. The only thing that is new is a special email client (which runs locally via a downloaded app). And everything gracefully degrades when interacting with people with regular email clients.

Going slide-by-slide:

Participants can edit their own post after-the-fact; each activity has +1 counts.

An interaction might be presented as a collaborative document instead of as a thread. In this case there are calls-to-action to edit, or link to the document. (In this example the document content is markdown; but this concept could work for any type of file: images, videos, slide decks, whatever.)

Linking to email messages is a much under-used feature in my opinion. There is actually already an RFC that specifies how to construct a globally-unique URI for any email message.

This is an early iteration of the process of linking to a document from another activity. Combining collaborative documents with linking allows for a decentralized wiki that actually lives in copies in the participant's email accounts.

I was experimenting with features to make email more usable generally. I tried to design Poodle to make it really obvious who sees what in any exchange. Poodle uses a reply-to-all form as the default reply option, and the user must go through extra steps to reply to just one person, or to a subset of the people already participating in a discussion.

If someone does reply without including everyone, you get this "private aside" feature. (This works just by examining To:, From:, and Cc: fields in email messages in the discussion.) The private aside acts like a self-contained sub-discussion, interleaved with the original discussion. My hope is that this kind of feature can help to avoid embarrassing information leaks.

Private aside messages are interleaved time-wise with the top-level discussion. And each private aside has its own private reply form after the last message in the aside.

Somehow I missed including a slide showing another feature that I think is useful: when someone includes a new person in the recipient list in a reply, there is a card that appears in the discussion view that says "so-and-so joined the discussion".

I think those features work well for small discussions with a fixed set of participants. On the roadmap is scaling up via hosted groups. Each group has its own email address - to start an interaction with the group you send to the group's address (e.g. backyard-goats@raddiscussions.net). People who join the group later have access to existing discussions and documents via archives on the group server. This is basically just the concept of a mailing list, but with some added usability features. The combination of social collaboration features and groups produces something like subreddits, or Facebook groups, or Jive communities. Groups support the philosophy of decentralization: anyone can start up their own group servers and have complete control over them; anyone can bring people from outside the group into a group interaction by including them in the recipient list; an interaction can be shared with multiple groups simultaneously; and so on.

Changes I would make to Go

Tue, 21 Feb 2017 00:00:00 GMT

I have been programming primarily in Go for about six months. I find it frustrating. There are two reasons for this:

First, functional programming is particularly difficult in Go. In fact the language discourages functional programming. This frustrates me because the imperative code that I write requires a lot of boilerplate, and I think it is more error-prone than it could be if I could use functional abstractions.

Second, I see Go as a missed opportunity. There is exciting innovation in programming languages - especially in areas of type checking and type inference to make code safer, faster, and more ergonomic. I wish Google had chosen to put their weight behind some of those ideas.

I am not the first person to look at Go this way. Here are other posts that echo my feelings:

I will add to those with some of my own opinions. To highlight exactly how I think Go could be better, I want to make comparisons to Rust.

Work on Go and Rust began at close to the same time: Go was first announced to the world in 2009, Rust in 2010. There is a lot of overlap in their philosophies; both languages:

compile to fast, native binaries
eschew inheritance in favor of composition
support imperative programming
omit exception-catching in favor of explicitly passing error results
emphasize concurrency
come with static type-checking
come with a modern packaging system that promotes modularity

Both languages may have been intended to replace C++: Go's designers have said that a primary motivation for Go was their dislike of the complexity of C++. One of Mozilla's prominent applications for Rust is Servo, a potential replacement for the Gecko HTML rendering engine, which is written in C++.

As I see it the key differences are that Rust aims for soundness,¹ powerful abstractions, and high performance; Go aims to be accessible, consistently simple, and fast to compile.

That said, Rust is not necessarily a replacement for Go, and I do not mean to say that everyone using Go should switch to Rust. Rust supports real-time operation, can operate with stack-only allocation if necessary, and has a sophisticated type system that can, for example, detect problems due to concurrent access to shared data at compile time. Those requirements add to the complexity of Rust programs. The borrow-checker in particular has a reputation for its learning curve. My purpose for making comparisons to Rust is to provide context for specific ways in which I think Go could be better. Rust borrows a lot of good ideas from other languages, and puts them together in one nice package. Most of those ideas are not even tied to borrow-checking. I think that Go could be a better language if it adopted some of the same ideas that Rust has adopted.

You can grab the code examples from this post. The examples come with executable tests to encourage experimentation.

So, here is my view of how Go compares:

The Good

I think that Go's use of interfaces to promote composition is great.

I like the separation of behavior and data: structs store data, methods manipulate data in structs - it is clean separation of state (structs), and behavior (methods). I think that distinction can become unfortunately blurry in languages that use inheritance.

Go is easy to learn. Go repurposes object-oriented concepts to make something new in a way that makes it approachable to programmers who are familiar with other object-oriented languages.

There is often a pretty clear "Go way" to solve a problem. This is also an oft-touted virtue of, for example, Python. Encouraging consistent idioms via the languages makes it likely that any Go programmer will be able to understand code written by any other Go programmer. This is part of a philosophy of simplicity that is described in the keynote Simplicity and collaboration.

There are lots of features in the Go standard libraries that have clearly had a lot of thought put into them. This is one of my favorites:

Goroutines are cheap, so programs can be structured in the way that makes most sense algorithmically, even if that involves spawning large numbers of goroutines. (But this is not unique to Go. Erlang and Scala also implement lightweight actors. Rust and other languages have their own solutions for lightweight concurrent and parallel programming.)

Since I am using Rust as a point-of-reference I will point out that Rust has a separation of behavior and data that is a lot like Go's, and Rust also goes for composition-over inheritance. Instead of structs and interfaces, Rust uses structs, enums, and traits. Rust traits serve the same purpose as interfaces; but they are different enough that they might seem a little weird to programmers with an object-oriented background. Rust and Go differ in that Rust prioritizes expressiveness over simplicity, and type safety over fast compile times. (Fast compile times are a high priority for the Rust team - just not the top priority.)

I could go on - there are plenty of nice features in Go. But there are also:

The Bad

These are features of Go that I find especially frustrating.

`nil`

I am disappointed by the decision to include null pointers in a new language when safer solutions have been in use for decades. Or to be more precise: I think it is a bad idea for a language to use nil as a bottom-ish type, where nil is type-compatible with every pass-by-reference type.

I understand that nil is not technically a null pointer - but its behavior is close enough that criticisms that apply to null pointers also apply to nil. I have read Understanding Nil, and I understand that it is possible to implement methods where the receiver is nil, and that nil can be useful. Go does some nice things to make nil less bad than it could be. But the fact remains: nil is type-compatible with every pass-by-reference type, whether or not methods on that type have sensible behavior for nil receivers, and that leads to lots of opportunities for runtime errors. To me that seems like an opportunity to make language changes so that it is easier for the type checker to catch problems at compile time.

Some newer languages have a null, but treat it as a distinct type that is generally not compatible with other types. (For example, Fantom and Flow do this.) In those languages values are non-nullable by default. Here is how one might declare and use a nullable variable in Flow when writing React code:

Without a concept of nullability, uses of nil are contradictions of what is stated in your type signatures. This Go signature claims that the argument is a pointer to a User struct - but if you take that claim at face value you are likely to get a nil pointer dereference error:

In Go every variable with a pass-by-reference type comes with the implied ambiguity, "...or it might be nil". Support for non-nullable types makes a language expressive enough to avoid that ambiguity.

The problem with nil in Go is exacerbated by the fact that nil checks sometimes fail. If an interface value has a concrete type but its value is nil, a nil check will not return true. The purist explanation for this is that the value is not really nil: it is an interface value that happens to have nil in its value slot. I don't find that explanation to be satisfactory. When a method is dispatched on that not-really-nil value, the receiver value will really be nil in the method body.

But what about zero values? What would the zero value be for a function type or an interface type without nil? Well, I think that zero values are also a bad idea.

One of the design decisions in Go is that every type must have a well-defined default value, which is called the zero value. This can be convenient because it means you do not have to write constructors by hand when all you need is a default value. But I suspect that the real reason why zero values are a part of Go is that they provide well-defined behavior for what happens when you use uninitialized variables. C and C++ are notorious for undefined behaviors, which lead to traps for programmers, and to problems making code portable between compiler implementations. Use of uninitialized variables is one notable example of undefined behavior in both languages.² I imagine that the designers of Go learned from C and C++, and set out to clearly define as much of Go's behavior as possible. I think that is a great attitude for language designers to adopt! But there is another option that I think leads to better code safety: Rust, Flow, and other languages use data-flow analysis to detect uses of uninitialized variables, and fail type-checking if any such uses are found.

The zero-value requirement introduces a constraint that nil must exist and must be assignable to a variety of types. A lot of types have no sensible default value, so nil is the only choice. So that is one problem. Another problem is that the language does not have enough information to produce sensible default values for domain-specific types. The fact that it tries anyway undermines soundness in code. The zero values for functions and interface values (i.e., interface values with no runtime type tag) are not going to be useful under any circumstances. Pointer types can implement methods with nil receivers - but that is not useful for types that do not have sensible behavior for uninitialized values. Default struct values can be useful in some cases - but in other cases the default value violates invariants that would have been enforced by a hand-written constructor.

The author of Three Months of Go called out problems with zero values in work at Pusher:

Zero values caused so many problems over the summer, because everything would appear to be fine, then it suddenly breaks because the zero value wasn't sensible for its context of use. Perhaps it's an unrelated change that causes things to break (like a struct getting an extra field).

How Rust does it differently

Rust goes a step beyond nullable types: it does not have a null or nil value. Rust uses enums, which are types whose values come in multiple variants, where each variant is effectively a distinct struct. If you want to represent an absence of a value you use an enum variant that holds no data. The generalized form of this pattern is known as the "Option Pattern". The definition of the Option type from Rust's standard library looks approximately like this:

None and Some are constructors: essentially they are each a function that returns a value of type Option<T>. Some takes one argument, None takes zero arguments. Given an Option<T> value, you can use pattern matching to determine which constructor was used to create the value; and pattern matching is also how you read back any constructor arguments. (In the case of a value created by calling Some(x), pattern matching lets you get access to that x value.)

Here is the Option pattern in action (source):

An advantage of the option pattern over nullable types is that you can distinguish between values like None versus Some(None). If you are looking up values in a cache (for example), a None result might indicate that there is no entry in the cache for a given key; and a Some(None) result might indicate that there is an entry, and the value of the entry is None.

I once advocated for use of the Option pattern at a Java company - but at least one of my coworkers was put off by the idea of allocating an extra object on the heap just to distinguish between a value and an absence of a value. Rust is built with the Option pattern in mind, and prioritizes zero-cost abstractions: If the type parameter for Option<T> is a reference type, then the None case can be safely represented at runtime as a null pointer. So the Some or None wrapper often disappears at compile time. In those cases the code is just as efficient as it would have been if the language allowed uses of unsafe null values in source code.

In the example above since neither Option<i32> nor the i32 parameter are reference types, the compiler allocates contiguous space on the stack for the numeric result, and for a tag to distinguish between Some and None. There is no extra heap allocation, and no added pointer indirection.

The Rust Book has a lot more detail on error handling.

It is possible to implement the Option pattern in Go with similar efficiency; and one could even get a compile-time check that errors are handled by implementing a match method that uses the visitor pattern (example). But without generics there would be no type safety for values wrapped in an Option type.

Error-handling boilerplate & lack of compile-time checks unhandled errors

Error handling in Go has two related problems: there is a lot of boilerplate required; and if the programmer neglects to check for an error, or makes a small mistake such as checking the wrong error variable, the compiler will not detect the problem.

Rust has a type, Result<T,E>, that is quite similar to Option<T>. The difference is that the failure variant of the Result<T,E> enum is not empty - it contains an error value (of type E). A returned value of type Result<T,E> may be either Ok(value) (on success) or Err(err) (on error).

A common complaint about the Option and Result patterns is that unwrapping success values is a pain. But a language with support for pattern matching makes unwrapping painless, and first-class result values permit combinators that can handle a series of potential failures more cleanly and safely than explicit error checks.

Consider this Go function:

There are a few ways the fetchAllBySameAuthor function this could be implemented in Rust. The pattern matching approach is probably the most accessible to people who do not have prior experience with the Option or Result Pattern:

The match keyword introduces a pattern-match block. The block includes a pattern for each possible variant of the type of the expression in the head of the match paired with an expression to evaluate if that pattern matches. This is somewhat like the type switch feature in Go, where the code that runs depends on the type of the variable in the head of the switch block. But the Rust version comes with a compile-time check that a pattern is given for every possible variant of the given type, which avoids potential runtime errors. This is especially helpful when a custom type is updated to add new variants: the compiler will immediately point out any uses of the type that need to be updated.

Anyway, that Rust code is no less verbose than the Go version - but it demonstrates that unwrapping Result<T,E> or Option<T> values does not have to be any more onerous than nil checks; and if we had left out a failure check in the Rust version Rust would have emitted an error at compile time.

Rust has a macro, try!, that abstracts the pattern matches and early returns that we see above. So this is an equivalent function:

try! rewrites an expression at compile time. For example, try!(fetch_post(post_id)) is expanded to put the fetch_post call inside a match, and inserts the boilerplate pattern matches for the Ok and Err match cases.

The try! macro was used so often that Rust's designers decided to extend the language a bit to better support the pattern: putting the ? postfix operator at the end of an expression has the same effect. For example, the line let post = try!(fetch_post(post_id)); can be equivalently written as let post = fetch_post(post_id)?; And type-checking will fail appropriately if you forget the ?.

But Go does not support macros. Thankfully, the Result pattern does not require macros to be concise. For the more functionally-inclined, here is another equivalent implementation that uses combinator methods:

and_then is a method on Result<T,E> values. If the value is a successful result, it runs the given callback, which should return a new Result<U,E> value. Or if the value is an error result, and_then short-circuits, and passes the error result through. and_then is a lot like the then method on Javascript promises.

But wait - what if you want to wrap error results to add context? There is a combinator for that to: map_err permits arbitrary transformations to error results.

The idea is that failure checks are almost always the same: check for an error, return the error if it exists, otherwise continue. The DRY thing to do is to abstract the common pattern into a helper method or a macro. And again, a common theme in all of these Rust implementations is that there is a compile-time guarantee that every error is handled. That could be with some recovery code, or by passing the error up the call stack.

Result<T,E> does not get the same disappear-at-compile-time optimization that Option<T> does because both enum variants hold data. But its efficiency compares favorably with Go's multiple return values. Go allocates enough space for every value in a multiple return. Rust allocates enough space to hold either T or E (i.e., enough space to hold the largest possible value), plus a tag to distinguish between an Ok(value) value and an Err(err) value.

A nice thing about the generality of Rust enums is that if Result<T,E> did not exist, it would be easy to implement it as a library. So what about using the Result pattern in Go? Well, we can't put methods on Go tuples (a.k.a, multiple return values), because they are not first-class values. It is not possible to define a function that that accepts a tuple and a callback: a Go function that takes a tuple cannot accept additional arguments (because Go tuples are not first-class values). Those constraints make the combinator pattern difficult. We could implement a custom struct type - but without generics it would not be very useful.

List manipulation is not practical

There is a special slap-in-the-face for functional programmers built into Go: there is no good way to write a polymorphic function that can manipulate slices with arbitrary types. In Rust you can write a function with a signature that looks like this:

That is a function that takes a callback and an input slice, and returns a new array that is computed by accumulating the results of applying the callback to each element in the input array. Even better, there are built-in methods in Rust's iterator types that do exactly this. The input slice might hold any type of values; type variables allow the type checker to track how the type of the output array relates to the type of the input slice, and also allow the type checker to check that the callback has the appropriate input and output types.

That pattern does not work well in Go. Without type variables the only way to express a type that is polymorphic over all slice types is to use the top-type: []interface{}. For example:

But that function is not really polymorphic: a slice type with a more specific type parameter (e.g., []int) is not type-compatible with []interface{}. So you cannot pass a variable with type []int to that Map function. You have to create a new slice of type []interface{} first, and copy int values to the new slice one-by-one in a for loop. Then after getting a result from Map you have to copy result values into yet another slice to get the proper final slice type. That means two custom loops are required around every invocation of Map - plus a runtime type assertion or type switch in the callback implementation.

A slice with an arbitrary type parameter is type-compatible with the top-type, interface{}. If you just use interface{} type for every polymorphic argument you get a signature like this:

With that signature you can pass in any slice type and callback type that you want, and assign the result to a variable with the proper type. But to make that work it is necessary to use the reflection API to fix up runtime type tags for the input slice, the input callback, and the output slice. The process is described in Writing type parametric functions in Go. The reflection code is ugly, but can be hidden in implementations of general-purpose functions. The unavoidable downsides are that you lose all compile-time type-safety, and there is an order-of-magnitude performance cost.

The same problem applies to other list manipulation functions: Filter, Take, Reduce, etc. This is bad because list manipulation is the bread-and-butter of functional programming. The fact that Go discourages such a basic building block as Map means that functional programming is not likely to thrive in Go, and the Go community will not be able to benefit from the advantages of functional programming.

You might have noticed a pattern here: Go does not support generics, and that leads to problems. Except the issue is not just lack of generics. Dynamic languages like Javascript, Python, and Ruby do not support generics either - at least not in the sense of compile-time checking. But functional idioms work just fine in those languages. For example, in Javascript you can pass any list to a generic list manipulation function, and it just works. Go occupies an awkward middle ground where it checks types at compile time, but does not provide tools to explain to the compiler how input and output types relate to each other.

Generics - and type variables in particular - are a means to "talk" about types. They let you use function signatures to make statements like, "This function takes a slice of values of some type, and returns a slice of values of the same type." Working in a programming language with no type variables is as frustrating to me as talking in a spoken language without the word "the".

So Go code must re-implement list abstractions everywhere. Consider this Go function:

That function iterates over an input collection, skips over some values, does something with the values that are not skipped, and returns a collection with the results. In other words, this is a filter, map, take operation. Here is an equivalent Rust implementation:

The Rust version lets you say what you mean. In other words, the Rust function is "declarative". And the difference becomes more pronounced if you want to process values concurrently - for example to make network requests in parallel. More on that in a bit.

I once complained to a coworker about a lack of abstractions in Go. My coworker replied, "Well, maybe you shouldn't be doing that." So I want to emphasize that functional abstractions do not necessarily make code less efficient. Rust typically does "list" manipulation using lazily-evaluated iterators. (This is also how the standard data structures in Clojure work.) So you can chain filter, map, take, without intermediate collection allocations, and without wasting cycles on computing values beyond those that the caller requests. The function above does not run those filter and map callbacks on every element in the input collection - it stops processing elements as soon as it has enough results to satisfy the take(count) step. On top of that, iter, filter, map, take, and collect are polymorphic methods, but they are dispatched statically thanks to a compile-time monomorphization step. And the compiler will probably inline the filter and map callbacks. There are some notes in the Rust Book on performance of functional abstractions on iterators.

It is possible that my coworker was more concerned with cognitive burden than with performance. I think that complaints of cognitive burden may be partly a result of looking at unfamiliar idioms. To an experienced functional programmer, a call to, e.g., map states a clear intention: "The input collection will be transformed according to this mapping function." With some practice declarative code is fast to read and understand. And type checkers are more effective at checking declarative code than at checking custom for loops.

Let's get into the parallel-fetch problem that I mentioned. Here is a Go function that I wrote recently to fetch a set of documents in parallel:

The use of a WaitGroup, the allocation of a new slice, copying result values, and explicit error checks are all low-level details that I should not have to reimplement every time I want to do things concurrently.

Now that I am looking at this again, I realize there might be a problem here with concurrent access to the docs slice. Maybe it would be a good idea to use a mutex around updates to docs, or to send results from goroutines back to the main thread via a channel. But if I use a channel I will need to implement a custom struct or use two channels, because I want to capture errors, and I cannot send the type (models.Document, error) over a channel, because Go tuples are not first-class values...

Rust gives a compile-time error if a mutable reference to a thread-unsafe data structure is passed to a function that could run in another thread. So I don't have to worry as much about what is or is not thread-safe when writing Rust code. But that is almost made moot by the fact that Rust can hide hairy concurrency details in library functions.

Compare the Go code to an equivalent Rust function that uses the futures library:

The Rust function works the same way that the Go function does: if all fetches are successful, you get a collection of data from responses. But if any fetches fail, you get the first failure as an error value. The difference is that in the Rust version the concurrency, mapping, and error-checking details are handled by a general-purpose library. (Another difference is that the Rust version returns as soon as any fetch fails, but the Go version always waits for all fetches to finish.)

This example shows that the map abstraction is so powerful that concurrent versus sequential execution is an implementation detail. (I will talk more about more about functional parallel processing in a later section.)

The Rust implementation assumes that fetch_document returns a Future. The function future::join_all also returns a Future. (Futures work very similarly to promises in Javascript: they represent an eventual result or error.) It would be more idiomatic to return that last future directly instead of using wait to block on the result. But blocking gives us a function that is logically equivalent to the Go version, and shows that using futures in Rust does not lock you into using callback-driven code everywhere.

Using futures, and the related Stream type, makes some kinds of network server implementations much simpler than with blocking IO. In particular, streaming requests and responses are easy if code is implemented in terms of Stream values.

Third-party libraries are second-class citizens

Go has a magical function called make that seems to do whatever the standard library authors need for a given type. It takes a type as an argument, which is unlike most other Go functions. Called with one argument it initializes a small slice, map, or channel. make can take one or two integer arguments, depending on the choice of the first argument. For example, when creating a slice you can provide a length and a capacity:

When creating a channel, you can specify the channel's buffer size with a second argument to make. As far as I know, this is the only way to set a channel's buffer size.

It seems that standard libraries have a special privilege to overload make to delegate to custom constructor code when initializing their types. Third-party libraries do not get to do this.

We see something like this with the range operator also. range is one of the few constructs that changes its behavior depending on the number of arguments that are assigned from its output:

But more importantly: only standard library types get to be range-able. There is no way to make a third-party data type iterable. Library authors can implement adapters to output a view of their data structure as a slice, or to spit out values over a channel. But that puts extra complexity on code that uses third-party data structures, and requires programmers to use non-standard idioms.

Yet another privilege is that only standard types can be compared using ==, >, etc.

And of course only standard libraries are allowed to define generic types. This is severely limiting to the library ecosystem around Go. It means that, for example, a third-party functional data structures library, or a third-party futures library will never be as usable as the standard library collection types.

Rust supports generics for third-party code; and Rust implements iteration, equality, and comparison via traits that any third-party type can implement. Third-party Rust types are nearly indistinguishable from standard library types, which promotes innovation in Rust's library ecosystem.

Incidentally, make and range are ad-hoc examples of a pattern that has generalized support in Rust: functions that are polymorphic in their return type. Rust traits are more flexible than typical object-oriented interfaces: when an interface method is dispatched the choice of the method implementation to execute is determined solely by the type of the receiver of the method. But a trait method implementation can be selected based on the type of the receiver, the type of any argument position, the combination of types of multiple argument positions (e.g., an equality trait can require that the two polymorphic arguments to an equals method have the same type), or by the expected return type. An implementation of make in Rust might look like this:

Any type can implement any trait. The only rule is that the code for an implementation must be in the same crate as either the type or the trait. (A "crate" is a distributable Rust package.) So if Rust itself or a Rust library implemented make, then any third-party library could define their own custom implementations.

I had to implement make and make_with_capacity as separate methods because Rust does not support method overloading. But in theory neither does Go.

The Ugly

These are some features of Go that I dislike on what I think are more subjective grounds than the "bad parts", or that could be worked around if some of the bad parts were fixed.

No tagged unions, limited pattern matching

Scala is another language that encourages passing messages over channels. Scala supports tagged-union types in combination with pattern matching. These features make great companions for channels: a tagged union describes a fixed set of message types that a channel can accept or produce.

Rust supports tagged-union types in the form of enums:

Rust does not require channels to be closed explicitly. Channel senders and receivers implement a Drop trait; any type can implement Drop to schedule some cleanup code to run when a value goes out of scope. In this example when the background thread terminates resp_tx goes out of scope, and closes automatically.

This block is the pattern matching code from the example above:

The block matches against instr, which has the type CounterInstruction. There are three variants for CounterInstruction; each variant is represented by a pattern in the match block with code to run in case the pattern matches.

Go has type switches, which are similar to pattern matching. Comparable Go matching code could look like this:

The difference is in compile-time type-safety: A tagged union describes a fixed set of possible messages. When sending a value to a channel in Rust, the compiler is able to check that the value has a type that the channel consumer knows how to handle. And what is especially valuable is checking that all pieces of code that send or receive on a channel are consistent in the types of values that the they produce or consume. If you make a change to the set of possible messages in a Rust program, but forget to update some critical code to accommodate the change, the type checker will report an error at compile time.

Because Go does not support tagged unions, messages over polymorphic channels are dynamically typed. You can use an interface as the type parameter for a channel, which does limit the types of messages that are sent over the channel. But a Go interface is not sealed: when a new type is created that implements the interface there is no compile-time check to ensure that all consumers of the channel are updated to handle the new type. Unpacking channel messages with a type switch (as opposed to using exclusively interface methods) can lead to bugs that a different type system would have caught.

Dynamic typing

Go makes heavy use of dynamic type-checking. Any use of interface{}, any type assertion or type switch, is dynamic typing. This is good and bad: without generics, it is often necessary to coerce a value to a different type; dynamic type assertions are a safer way to do this than unchecked type casts. Either way the program will (probably) crash at runtime if a value ends up having an unexpected type. But with an unchecked cast the program might corrupt memory or leak information to attackers before crashing.

The fact that errors are reported at runtime means that problems are likely to go unnoticed without good test coverage. That does not just mean 100% code coverage - there might be different combinations of conditions that lead to a code path and a type error might not manifest under every combination.

A type checker that can detect errors at compile time is like an extra test suite that always tests every combination of conditions. Dynamic type tests are nearly unheard of in Rust because the compiler resolves types at compile time. Pattern matches on enum variants looks a bit like a dynamic type test - but pattern matching is qualitatively different because enums are sealed. There is a compile-time guarantee that pattern matching will not fail.

There are two caveats:

unsafe blocks, functions, and traits in Rust do make unchecked type casts - especially when interacting with the foreign function interface. But unsafe implementations are delimited regions where the normal rules do not apply. The best practice is to keep unsafe code to a minimum; and most libraries do not use any unsafe code.
Rust supports trait objects, which is are cases where the compiler does not resolve a concrete type for a value at compile time. But the compiler does verify at compile-time that the value implements a given trait. A trait object is a lot like a Go interface value - except that a trait object cannot have a nil value. Despite the lack of a compile-time concrete type, it is safe to dispatch trait methods on a trait object because there is compile-time verification that whatever value is in the object implements the given trait and therefore implements the appropriate methods.

Dynamic dispatch, reinventing the wheel

In general Rust resolves every value to a concrete type at compile time. That means that Rust can use static dispatch when invoking trait methods.

(As I mentioned, the exception is trait objects, which do use dynamic dispatch much like Go interface values. My understanding is that idiomatic Rust code uses trait objects sparingly. Most uses of traits in Rust use the trait as a bound on a type variable, which leads to compile-time resolution to a concrete type. For details see the Rust book sections on traits and trait objects.)

In Go every invocation of an interface method uses dynamic dispatch. Dynamic dispatch, type assertions, and type switches require runtime reflection, which adds some runtime overhead.

The technique of resolving concrete types at compile-time is not new to Rust, and it has nothing to do with borrow-checking. Haskell was doing the same thing at least ten years before work began on Go. And Haskell has just as much polymorphic flexibility as Rust or Go. (Rust traits are an adaptation of Haskell type classes.)

The designers of Go wanted a model for polymorphism that is simpler and more flexible than what other object-oriented languages provide. In particular they wanted composition over inheritance, and an ability to implement interfaces after-the-fact so that new interfaces can be applied to pre-existing types. This is exactly what traits and type classes do. The solution that Go introduced feels to me like a less-capable reinvented wheel.

No first-class tuple

Go supports multiple return values. Other languages (including Rust) support multiple return values via first-class data types called "tuples". First-class values can have methods, can be stored in data structures, and can be passed over channels. Multiple-values in Go cannot do any of those things.

We already saw tuple return values in the implementation of the Make trait, and in the new_counter example. Here is a smaller example:

A consequence of the lack of first-classness in Go is that there is no obvious way to communicate potential failures over a channel. It seems like this should work, but it does not:

As far as I know the best options for doing this are to define a custom struct type; to coerce both success and error values to interface{}, and use a type switch to distinguish success and error on the other end of the channel; or to send success and error values over two parallel channels.

Another consequence is that there is no good way to define methods on multiple return values, or to define a function that accepts multiple return values with a callback. This makes it impractical to define an analog of Rust's and_then combinator for Go return values.

Shortage of high-level parallelism and concurrency features

The post Channels Are Not Enough makes a detailed argument about problems with Go's lack of concurrency abstractions. In the section "List manipulation cannot be abstracted" I pointed out that Go does not provide an easy way to run a set of computations in parallel. @kachayev points out that the problem is more general than that. Really this is another symptom of lack of generics.

In the parallel fetch example I showed a Rust solution that uses futures, which are great for concurrent IO. The futures library relates to a larger async IO library called Tokio, which seems to be popular. But async IO is not intended to provide parallelism. The excellent book Parallel and Concurrent Programming in Haskell has this to say about the distinction between parallel and concurrent code:

A parallel program is one that uses a multiplicity of computational hardware (e.g., several processor cores) to perform a computation more quickly. The aim is to arrive at the answer earlier, by delegating different parts of the computation to different processors that execute at the same time.
By contrast, concurrency is a program-structuring technique in which there are multiple threads of control. Conceptually, the threads of control execute “at the same time”; that is, the user sees their effects interleaved. Whether they actually execute at the same time or not is an implementation detail; a concurrent program can execute on a single processor through interleaved execution or on multiple physical processors.

Go uses goroutines for both parallel and concurrent programming. Rust libraries offer a selection of tools whose strengths make them especially useful for different kinds of problems.

When you want true multi-core parallel processing, the Map-Reduce pattern offers a powerful solution. This is another application of list abstractions. You can apply Map-Reduce in Rust using parallel iterators from the Rayon library:

Parallel iterators implement a variation of the map method that divides work among a set of job queues that feed into a worker pool, so that invocations of the map callback run in parallel. As with goroutines, this is lightweight parallelism that scales to a large number of parallel tasks. But parallel iterators are a high-level abstraction that take care of some complicated details for you. For example, Rayon transparently splits work into batches, which provides better performance than queueing up every invocation of the map callback separately. (The default batch size is 5000 items, but that value is tunable.) The sum method (which is the Reduce step in this example) is also part of Rayon - which means that it is optimized for consuming batches of results from worker threads.

It might seem strange to have to use two different libraries for concurrent vs parallel code. But those are separate concerns, with different underlying assumptions. Usually you do not actually want both at the same time.

Conclusion

How do I think Go 2.0 could be better? Generics. Nearly all of my complaints boil down to lack of support for generics. But I think that support for non-nil-able types, and getting rid of zero values would also be useful changes. Even Rust-style traits might be workable. Traits would require support for receiver-less methods; bit it might be possible to make traits work with Go's implicit implementation feature.

In its current form, I prefer not to use Go. It is not that Go is bad - it is just that there are lots of languages available that I find more enjoyable. When I work with Go I cannot help thinking about how I could be doing things differently in another language.

If you are willing to put in the time to understand lifetimes and borrow checking, Rust makes a fantastic language that does everything that Go does, but has none of the "bad parts" that I called out.

Javascript is (like Go) easy to learn, and has wonderful support for concurrency (if not parallelism). When paired with Flow or Typescript you get more robust type safety than Go provides. The combination of Javascript and Flow in particular has none of the "bad parts" from this post.

Erlang and Scala both support lightweight concurrency in the same style that Go does, and they are both great for functional programming.

Clojure is not type-safe - but it does fantastic things! My favorite functional data structure implementations are the ones in Clojure. And Clojure encourages functional programming.

Haskell has amazing type safety, some of the best concurrency and parallelism features that I have seen in any language, and is well-suited to network server code. Haskell is another language that avoids the "bad parts" from this post.

We have better tools than ever for getting work done. Even Go - whether I like it or not - is clearly useful for building cool things. But if you take anything away from this post, I hope it is an interest in taking a look beyond the imperative / object-oriented world. I encourage you to pick one of the languages above, and take some time to learn about it and to get a good feel for its strengths. I think you will be glad that you did.

Soundness is a property of a type system where any "claims" made by program types are guaranteed to hold at runtime. Runtime type errors will not occur if a language is sound.↩
This may have changed over time; the C and C++ language specifications are evolving, and I am not very familiar with the details.↩

Flow Cookbook: Flow & React

Tue, 03 Jan 2017 00:00:00 GMT

This recipe is part of the Flow Cookbook series.

Flow and React are both Facebook projects - so as you might imagine, they work quite well together. React components can take type parameters to specify types for props and state. Type-checking works well with both functional and class components.

Flow type annotations provide an alternative to propTypes runtime checks. Flow's static checking has some advantages:

Problems are reported immediately - it is not necessary to run tests that evaluate every component to identify props mismatches.
Flow types can be more precise and concise than propTypes.
Flow can also check state as well as props.
In addition to checking that a component gets the correct props, Flow checks that props and states are used correctly within the component's render method, and in other component methods.

Flow changed the way that it handles React types in version 0.53.0. This recipe assumes that you are using Flow v0.53.0 or later.

How it works

With Flow you specify the types of props and state using type parameters on the React.Component class. The form for type parameters is:

Where Props, and State can be whatever object types you want. If your component has the props title, createdAt, and authorId then a definition for Props could look like this:

If your component is stateless then you can omit the State parameter, in which case the state type defaults to void.

Props should list types for all props - even props that are optional or that have default values. If you add a defaultProps value to your component then Flow will automatically infer that fields from defaultProps are not required when your component is called. So you should not use a ? in the corresponding field in your Props type. Leaving out the ? lets you avoid unnecessary undefined checks in your component's methods.

To declare a type for props in a stateless functional component use a type annotation like this:

Once again, Props can be any object type that you want, and should include types for all props, even those that have default values. The return type for a functional component is React.Element<*> - but Flow can infer that so don't bother with a return type annotation.

Type definitions for React are built into Flow. The Flow documentation includes a type reference for React types. It is useful to look at those definitions to see exactly what Flow expects. You can also go straight to the source: a lot of what I know about using Flow came from examining Flow's type definition file for React and other files in the same directory.

The Flow documentation also includes its own guide on using Flow with React.

A Hacker News client

Let's build on the code from the Unpacking JSON API data recipe, and build a simple Hacker News client. The client will fetch lists of stories from the Hacker News API to display. When the user selects a story, the client will fetch and display comments.

Let's start with a component that displays a Hacker News story as a single line, and accepts a callback to do something if the user selects that story. First we define a type for the props that this component will accept.

We import the Story type from 'flow-cookbook-hacker-news', which is the example code from the Unpacking JSON API data recipe. That Story type is a ready-made type that describes everything we will want to display in the new client. Take a look at the source file to see what Story looks like. (The import { type T } bit is Flow syntax - it is not part of Javascript.)

The StoryListItemProps type lists the props that will be given to our component. The props are a story, and a callback called onSelect. The type indicates that onSelect must be a function that takes zero arguments, and that returns undefined (a.k.a. void). It is not necessary to require that the return type be undefined - you could use mixed instead if you do not want to put any constraint on the callback's return type.

My opinion is that using void is a clear indication to the caller that the component will not do anything with a return value. On the other hand you might get an irritating type error if you provide a single-expression arrow function that implicitly returns a value.

And here is the StoryListItem component itself:

The type annotation, props: StoryListItemProps, does two things for us: when StoryListItem is rendered, Flow will check that it is given the required props of the appropriate types; and Flow will also check uses of props in the body of the StoryListItem function for consistency with StoryListItemProps. Checking props from both directions ensures that a component is in alignment with its callers.

In general if a component does not have internal state, and does not use life cycle callbacks such as componentDidMount, then I prefer to use a functional component, like StoryListItem. A functional component cannot have methods that refer to this.props; so I made the selectStory event handler a top-level function that accepts a reference to the component's props as an argument. Reusing the StoryListItemProps type in the signatures for the component and for the event handler means that we can easily keep track of available props in both functions.

selectStory also takes an event argument. The Event type is built into Flow, and Flow knows about the preventDefault method. Flow's version of the Event type is defined in Flow's DOM type definitions file.

To populate instances of the StoryListItem component, we will need to make API requests and update some state. Here is a type for that state, and the parameters for the top-level component, which will manage that state:

The definition of AppState shows that the state will hold an array of stories, which will not be defined while stories are loading; a selectedStory, which will be defined when the user is viewing comments on a story; and an error, in case something goes wrong while loading stories.

Because every property in AppState is optional, state can be initialized as an empty object. (The question mark at the end of a property name indicates that property might not be set.) selectedStory is optional, and its type is nullable, so there are two question marks on that line. That is because selectedStory is initially not set, and after a user views a story and then backs out to the story list selectedStory will be set to null.

Since App has a constructor, we specify the props type both in the second class type parameter, and again in the type of the props argument to constructor. That is because a subclass can define a constructor with a signature that differs from the parent class' constructor. It would not make much sense to do that in a React Component; but Flow must be able to check all sorts of classes, so it does not make assumptions about types of constructor arguments.

App will fetch stories when it is mounted. So we extend its definition with a componentDidMount callback.

fetchTopStories takes an argument that specifies the number of stories to fetch, and it returns a promise.

Once stories are loaded we can display them via a render method. But the component will initially display while the API request is loading; so we will have to check whether stories have loaded, and display a loading indicator if they are not ready.

The import piece of the JSX that is finally returned from render is content, which is assigned a different value depending on whether an error occurred while fetching stories, a specific story has been selected, or there is an array of stories available, and none has been selected. If none of those cases applies, then it means that stories are still loading.

When displaying a list of stories, content is populated by a list of instances of StoryListItem, which we defined earlier. There is nothing special about rendering a type-checked component - you pass props the same way as with any component.

Flow can track changes to the type of a variable over a series of statements. Flow infers that when content is first defined its type is void; and it infers that no matter which code path gets executed, by the time we get to the return statement the type has changed to either React.Element<*> or React.Element<*>[] - either of which is compatible with Flow's expectations for JSX content.

The event handling methods selectStory and deselectStory make state changes to track whether the user is looking at a specific story:

Those state changes affect the output from render to switch between displaying a list of story titles, or a detail view for a single story.

At this point we have made references to App's state in componentDidMount, render, selectStory, and deselectStory. Flow checks all of those uses against the definition of AppState. For example, if we made a mistaken assumption that selectedStory holds an ID, as opposed to a value of type Story, and tried to write something like this.setState({ selectedStory: story.id }) Flow would report an error, and point out the mismatch.

I have not given the implementation of StoryView, which is responsible for displaying comments on a story. It happens that StoryView is quite similar to App - except that StoryView loads comments where App loads stories. The interested reader can see the full details of StoryView in the accompanying code.

Complete working code is available at https://github.com/hallettj/flow-cookbook-react. Your next assignment is to clone that code and to add some features. Some ideas to try are to add links to the original article for each story, or to display profile pages for posters and commenters.

The example code here uses React's own state features to manage app state. That helps to keep this recipe self-contained. But in my opinion the best practice is to keep state in a third-party state-management framework such as Redux. For details on using Flow with Redux and react-redux take a look at the next recipe, Flow & Redux.

Flow Cookbook

Tue, 20 Dec 2016 00:00:00 GMT

Type-checking can be a useful asset in a Javascript project. A type checker can catch problems that are introduced when adding features or refactoring, which can reduce the amount of time spent debugging and testing. Type annotations provide a form of always-up-to-date documentation that makes it easier for developers to understand an unfamiliar code base. But it is important to use type-checking effectively to get its full benefit.

The Javascript community is fortunate to have a choice of two great type checkers. These recipes focus on Flow, and introduce patterns for using Flow effectively.

To get updates when new recipes or extras are posted, subscribe to the Atom feed, or follow @FlowCookbook. I appreciate your requests, questions, and suggestions! Please send feedback by leaving comments here, or on recipes or extras; or send messages to @FlowCookbook.

Recipes

These are primers on practical patterns for Flow. I recommend using these patterns in any project that uses Flow.

(Coming soon) Flow types are duck types - Flow is not a new, strait-jacketed OOP language. Flow is not Java or C#. Flow is a codification of previously-unwritten Javascript idioms.

(Coming soon) Uses for union types introduces a pattern for managing data that comes in different shapes. Union types are helpful for describing Redux actions, for unpacking incoming JSON data, and for passing messages over a channel. If you have been tempted to use subclasses, take a look at union types to see if they might be a better fit.

Unpacking JSON API data - Javascript's flexibility is useful for handling incoming data in whatever form it may take. Flow is designed to be just as flexible when type-checking functions that process data. This is a case study that uses the Hacker News API as an example for type-safe data processing.

Flow & React - This recipe demonstrates how to use Flow effectively when creating React components. Including type parameters in functional and class components provides an alternative to propTypes that can provide better safety and modularity.

(Coming soon) Flow & Redux - Flow and Redux could have been made for each other. This recipe demonstrates several patterns that are useful for building Redux action creators and reducers. This is a companion to the post on React.

Extras

Extras are not about practical patterns. In these articles we explore ideas just because they are interesting. Read these if you want to dig deeper into type theory, or to learn about Flow's lesser-known capabilities.

(Coming soon) What are types? The short answer is, types are sets of possible values. This post gets into what that means, and shows that Flow takes more of a purist approach to types compared to most object-oriented languages.

(Coming soon) The "algebra" in "algebraic data types" - In the recipe Uses for union types I mentioned that union types are also called "sum types" or "algebraic data types". This post gives a brief background on type algebra so that you can understand where those terms come from.

(Coming soon) Advanced algebraic data types - Union types are great, but not perfect. This post introduces an alternative formulation for sum types that allows Flow to check for missing pattern matches. It also shows that GADTs are almost possible in Flow.

More resources

Flow has inspired many programmers to put bits to screen. Here are some articles that I found to particularly helpful:

Getting started with Flow is a tutorial from the official documentation. If you don't know where to start, start there.

Why use type-checking? And if you do, Why Use Flow? Follow that link for the answers, and learn some things that you might not know about Flow. Aria Fallah covers a lot of background, and also introduces some interesting work from Giulio Canti.

Authoring and publishing JavaScript modules with Flow is a detailed guide on publishing an NPM module with Flow type annotations included, so that anyone who uses the library can benefit from those annotations if they choose to use Flow as well.

Flow Cookbook: Unpacking JSON API data

Tue, 20 Dec 2016 00:00:00 GMT

This recipe is part of the Flow Cookbook series.

Hacker News provides a public API. One of the endpoints of that API accepts an ID and responds with an item:

Here is an example of a response:

An "item" might be a story, a comment, a question, a job posting, a poll, or a voting option in a poll. Each item type has different properties - for example stories have a title, but comments do not. If you don't have context for the ID, the only way to know what you have fetched is to check the type property of the response at runtime. To add type safety to a call to this API, it is necessary to describe a type that encompasses all of the possible shapes that the returned data might take. That is going to be a union type, which will look something like this:

There are not a huge number of properties in the API responses - but if we list out all of the properties in every branch the result will be too big and dense for light reading. So let's start by factoring out common properties into helper types.

All of the different item types have by, id, and time properties. So we can put those all into one type:

Those Username and ID types are just aliases that I defined for primitive types:

I think that using aliases like these helps to provide clarity on the purpose of each property. If we had a property with the type by: string it would not be obvious whether the value of that property is an ID that happens to be a string, or a human-readable value. Using the Username type alias makes it obvious that the property will contain a value that might be suitable for display to users. Otherwise the types string and Username are interchangeable.

There is more common structure in Hacker News item types: the story, ask, job, and poll response types all represent top-level submissions, which have several properties in common:

With those helper types in place, we can produce a type that describes all possible items:

An intersection type like { type: 'story', kids: ID[], url: URL } & ItemCommon & TopLevel is essentially a shorthand for an object type with a type property that is always equal to 'story', combined with all of the properties listed in the ItemCommon and TopLevel types. Each branch of the union type contains a type intersection that combines common properties with the properties that are particular to each item type.[^top-level union]

[^top-level union]: It would have been more concise to write type Item = ItemCommon & (/* union type */). That would put the union type inside of the intersection type. But due to a quirk in Flow as of version 0.36 the union type must be the outermost layer of of composition for type narrowing to work.

We don't have to do anything special to parse incoming data into that type. Flow types are duck types - Item is just an alias for plain Javascript objects with a certain structure. We just need to declare that API responses have the Item type. That is done with with the return type in this function signature:

You might have noticed something a little strange about the types of the type properties in Item. We used string literals where there should have been type expressions! For example, we gave 'story' as a type in the first branch of the union type. In fact string literals are types. In a type expression, the literal 'story' is a type with exactly one possible value: the string 'story'. ('story' is a subtype of the more general type, string.) This is useful because it signals to Flow which branch of the union type is applicable inside the body of a case or if statement.

Consider this function, which does not type-check:

Flow can narrow the type of a variable in certain contexts. A runtime comparison with a static string literal does the trick:

Hacker News does provide endpoints for fetching recent submissions of a specific item type (e.g., the latest stories). But to demonstrate the flexibility of the Item type, let's write some code that fetches and displays the latest items of any type. We will need to switch on the type property of each item to display it properly:

Flow is able to infer which item type is given in each case body. This is just like how type-narrowing worked in the if body in the getTitle function.

Flow's checking has an added bonus: if you have a case body with no return or break statement, execution falls through into the next case body. When switching on item.type, a fall-through would result in a situation where a case body might be executed with any of several different item types. For example:

Flow allows this, because all of the types listed in that example have a title property. But if a case body did something not compatible with all of the different item types that could fall-through into it, then Flow would report an error.

Next up are functions to determine which items to fetch, and to make the necessary requests:

And finally, some code to set everything running:

Refining the model

Later on we may realize that it would be useful to be able to refer to each item type individually. To do that, we can create a named alias for each item type:

Then we can replace the earlier definition of Item with a simpler one:

This well let us write specialized functions, such as a function that specifically formats a poll with its options.

So how do we get to a point where we can call a function that accepts only polls? The answer is, once again, type-narrowing:

Notice the use of flatMap in fetchPollOpts. This filters results to check that the results are actually poll options. At the same time, Flow is able to infer that the filtered results all have the PollOpt type. This uses a custom definition for flatMap:

If you trust that all of the items that are fetched will be of the right type, and you do not want to bother with a runtime check, then you could use a type-cast instead:

Finally, here is a function that feeds fetched items to the new-and-improved item formatting function:

The code from this article is available at https://github.com/hallettj/hacker-news-example. I encourage you to check out the code to tinker with it. Try building more functionality, and see how type-checking affects the way you write code.

Advanced features in Flow

Sun, 31 May 2015 00:00:00 GMT

Flow has some very interesting features that are currently not documented. It is likely that the reason for missing documentation is that these features are still experimental. Caveat emptor.

I took a stroll through the source code for Flow v0.11. Here is what I found while reading type_inference_js.ml and react.js.

Edit: It has been pointed out to me that Flow features prefixed with $ are not technically public, and that the semantics of those features may change. But they are useful enough that I plan to use some of them anyway :)

`Class<T>`

Type of the class whose instances are of type T. This lets you pass around classes as first-class values - with proper type checking.

I use this in an event dispatch system where events are class instances, and event handlers are invoked based on whether they accept a given event type:

This gives me a compile-time guarantee that event handlers can handle events of the type they are invoked with.

`$Diff<A,B>`

If A and B are object types, $Diff<A,B> is the type of objects that have properties defined in A, but not in B. Properties that are defined in both A and B are allowed too.

React uses this to throw type errors if components are not given required props, but to leave props with default values as optional.

Where P is the type for component props, and D is the type for default props.

Here is a simplified example:

In my testing, this worked equally well if $Diff was used directly in the type of P instead of as a type bound. But in the React type declarations, it is used in a type bound.

`$Shape<T>`

Matches the shape of T. React uses $Shape in the signatures for setProps and setState.

Where P is the type of a component's props, and S is the type of a component's state.

An object of type $Shape<T> does not have to have all of the properties that type T defines. But the types of the properties that it does have must match the types of the same properties in T.

In React this means that you can use, e.g., setState to set some state properties, while leaving others unspecified. Note how the type of state in replaceState differs: when calling replaceState you must include a value for every property in S.

Some examples:

An object of type $Shape<T> is not allowed to have properties that are not part of T.

$Shape is like a supertype for objects. Consider that a type { foo: number } (when used as a type bound) represents all objects that have a foo property of type number. That includes objects that have additional properties, such as { foo: 1, bar: 'string' }. So { foo: number } is a supertype of, e.g., { foo: number, bar: string }. The type $Shape<{ foo: number, bar: string }> allows values of type { foo: number }. That is to say, $Shape<T> refers to types that are more general than T - i.e., supertypes.

`$Record<T>`

Update: $Record<T> is gone in Flow v0.12. But instead of $Record<T>, you can use the nearly equivalent construct: {[key: $Enum<T>]: U}, where U is the type of values in the record.

The type of objects whose keys are those of T. This means that an object of type $Record<T> must have properties with all of the same names as the properties in T - but the types assigned to those properties may be different.

React uses $Record to check the type of propTypes. Here is a simplified example:

Note that Flow does not verify that React.PropTypes.number matches the type number. It just checks that propTypes1 has all of the same keys.

A $Record type might have additional keys that are not included in the original object type.

An important detail to note is that a $Record type can only use property names that are known statically. Dynamic lookups are not allowed.

In its real definition, React actually uses $Record in combination with $Supertype so that you do not get an error if you omit some properties from propTypes.

`$Supertype<T>`

A type that is a supertype of T. React uses $Supertype in the type of propTypes:

Where the type variable P is the type of the props for a component.

It looks like the intent is to check that if a component defines propTypes, all of the properties listed are also in the type of props. But it should not report an error if propTypes excludes some props. I could not get a type error when testing this. It could be that interaction between $Supertype and object types is still a work in progress.

If you are thinking of using $Supertype with an object type, consider $Shape - it might be a better choice.

`$Subtype<T>`

A type that is a subtype of T. This is what you get when you use a type bound. For example, these signatures are equivalent:

But the second version has the disadvantage that you cannot refer to the type that obj gets in the return type of the function, or in the types of other arguments.

While trying to come up with example cases for $Subtype, I came across other nice improvements to Flow that render $Subtype unnecessary in a lot of cases. In a previous version of Flow, I recall (possibly incorrectly) having to use a type bound in a function that takes on object with certain required properties, where you don't want to prevent the caller from including additional properties. But now this works without a type bound:

I also had a thought that $Subtype could be used to implement a composition pattern that previously did not work.

But in Flow v0.11 this does work. Hooray!

$Subtype could be useful if you want to define an object type that can be assigned properties that are not declared in the type:

However this weakens property checking on the extensible type. For example, Flow does not infer that the type of a.foo must be number. (It checks the type of foo correctly when the object is first created, but not on reads or reassignment).

`$Enum<T>`

The set of keys of T. One use for this is to write a lookup function, and have Flow check that the lookup key is valid.

The type $Enum<typeof props> is a lot like this type:

But with $Enum, Flow computes the type union for you.

Flow's tests include more examples.

Existential types

Flow supports an "existential type": *. When * is given as a type, it acts as a placeholder, leaving it to the type checker to infer the type for that position.

Let's generalize the getProp function from the section above. Let's write a function that takes any object and returns a getter. The getter can be used to get arbitrary properties out of the object, without having to refer to the object itself after creating the getter. We would like to write this:

The use of $Enum<T> ensures that a getter can only be called to get properties that actually exist on the given object.

But Flow objects to the lack of type declarations in the inner function. It reports an error:

An obvious idea is to copy types from the return type of makeGetter into the signature of the inner function. But that leads to another problem.

This time the error is:

The problem is that type variables in a function signature (in this case, in the signature of makeGetter) are not in scope in the function body. So we cannot refer to the type T in inner function types, or in variable types in the body of makeGetter.

On the other hand, Flow might be smart enough to figure out what the argument type in the inner function should be. So we can use * to kick the problem over to Flow.

Now we can see makeGetter in action.

Another option would have been to use any instead of *. But that is so much less elegant! The important difference is that where * appears, Flow will fill in a specific type, which could lead to accurate type checking in other areas of the code where the value of type * appears. If you annotate a value with any, Flow will not attempt to type-check expressions where that value appears - which could lead to type errors being missed.

In this case the choice of * versus any does not matter, since the outer function has the type signature that we want.

React uses an existential type to define the ReactClass type:

This allows React to pass around a polymorphic class as a first-class value without losing type information.

Scoped type variables in classes

I mentioned in the last section that type variables in a function's signature are not in scope in the body of that function. I find it interesting that classes do not have this restriction: type variables in a class declaration are in scope in the class definition. (They are not in scope within method bodies; but you can use these variables in method signatures and class variable types). Because of this, there are some problems that do not exactly work with functions but that do work with classes.

We can reimplement makeGetter from the last section as a class.

This probably seems unremarkable - every object-oriented language with static type-checking scopes class-level type variables this way. But ES6 classes are mostly syntactic sugar for ES5 constructor functions - yet a straight translation of Getter to ES5 syntax does not work:

We get the same error: identifier T, could not resolve name. This time to fix the problem we have to refer to T indirectly using typeof obj.

The ability of classes to scope type variables over inner methods, and the ability to use instanceof for type refinement, lead me to use classes more often than I would if I were not using Flow.

Type checking React with Flow v0.11

Sun, 31 May 2015 00:00:00 GMT

This is an old post - for an up-to-date guide see Flow Cookbook: Flow & React.

Flow v0.11 was released recently. The latest set of changes really improve type checking in React apps. But there are some guidelines to follow to get the full benefits.

Use ES6 classes

React added support in version 0.13 for implementing components as native Javascript classes (more information on that here). The latest version of the React type definitions take full advantage of class-based type checking features.

`React.Component` takes type parameters

When creating a component, be sure to provide type parameters in your class declaration to describe the types of your props, default props, and state. Here is a modified example from the React blog:

The parameter signature is React.Component<DefaultProps,Props,State>. This is not exactly documented; but you can see types of React features in Flow's type declarations for React. All of the type declarations in that folder are automatically loaded whenever Flow runs, unless you use the --no-flowlib option.

If you define a constructor for your component, it is a good idea to annotate the props argument too. Unfortunately Flow does not make the connection that the constructor argument has the same type as this.props.

Note that I included type annotations on render() and context. This is just because Flow generally requires type annotations for class method arguments and return values.

When those type parameters are given, here are some of the things that Flow can check:

when instantiating your component, the required props are given with correctly typed values.
props that are not required have default values (checked only if defaultProps is defined)
references to this.props or this.state are checked to make sure that the properties accessed exist, and have a compatible type
properties set with this.setState() are declared in your state type and have the correct types

Use JSX

I mentioned above that Flow will check that components are given required props. In my testing, there were some cases where this worked when I used JSX syntax, but did not work with the plain Javascript React.createElement option. (The case I had trouble with was with a conditionally-rendered child in a render method - my uses of of React.createElement worked fine with both syntaxes.) I suspect that engineers at Facebook tend to prefer JSX, and, and maybe test code written with JSX syntax more heavily.

General-purpose features

What is nice is that most of the features that Flow uses to support React are general-purpose. As far as I can tell, the only feature in Flow that is React-specific is support for JSX syntax. But some of the features that make Flow work so well are not yet documented. For details, see my post on Advanced features in Flow

Flow is the JavaScript type checker I have been waiting for

Fri, 21 Nov 2014 00:00:00 GMT

I am very excited about Flow, a new JavaScript type checker from Facebook. I have put some thought into what a type checker for JavaScript should do - and in my opinion Facebook gets it right. The designers of Flow took great effort to make it work well with JavaScript idioms, and with off-the-shelf JavaScript code. The key features that make that possible are type inference and path-sensitive analysis. I think that Flow has the potential to enable sweeping improvements to the code quality of countless web apps and Node apps.

From the announcement post:

...underlying the design of Flow is the assumption that most JavaScript code is implicitly statically typed; even though types may not appear anywhere in the code, they are in the developer’s mind as a way to reason about the correctness of the code. Flow infers those types automatically wherever possible, which means that it can find type errors without needing any changes to the code at all.

This makes Flow fundamentally different than existing JavaScript type systems (such as TypeScript), which make the weaker assumption that most JavaScript code is dynamically typed, and that it is up to the developer to express which code may be amenable to static typing.

Path-sensitive analysis means that Flow reads control flow to narrow types where appropriate.

This example comes from the announcement post:

The presence of a use of length with a null argument informs Flow that there should be a null check in that function. This version does type-check:

Flow is able to infer that x cannot be null inside the if body.

An alternate fix would be to get rid of any invocations of length where the argument might be null. That would cause Flow to infer a non-nullable type for x.

This capability goes further - here is an example from the Flow documentation:

The type of o is initially null. But Flow is able to determine that the type of o changes when o is reassigned, and that its type is definitely string on the last line.

In addition to null checks, Flow also narrows types when it sees dynamic type checks. This example (which passes the type checker) comes from the documentation:

The inferred return type of foo is string | number. That is a type union, meaning that values returned by foo might be of type string or of type number. The typeof checks in bar narrow the possible types of x and y in the if body to just number. That means that it is safe to multiply values returned by bar - the type checker knows that bar will always return a number.

A coworker told me that what he would like is support for type-checked structs. That would let him add or remove properties from an object in one part of a program, and be assured that the rest of the program is using the new object format correctly. Struct types work using structural types and type aliases:

Notice the type keyword and type annotation on mkPoint - Facebook's literature is a little misleading, in that Flow is really a new language that compiles to JavaScript. But the only differences between Flow and regular JavaScript are the added syntax for type aliases and type annotations, and the type-checking step. Flow can be applied to regular JavaScript code without type annotations.

How well that works will depend on how that code is written. If the JavaScript is cleanly written, you might get a lot of help from Flow without ever needing type annotations. But there are some valid JavaScript idioms that will not type-check (at least not at this time.) For example, optional arguments are not allowed unless you use either Flow's syntax or ECMAScript 6's default parameter syntax.

These are early days for Flow. I am optimistic that over time it will only get better at operating on code that was not written with Flow in mind.

~~There is a side benefit to using the Flow language: it supports [ECMAScript 6][], but [compiling Flow programs][] produces ECMAScript 5 code that can run in most browsers.~~

Edit 2016-08-19: Early in Flow's development, Facebook recommended using their own jsx compiler to process code that used Flow. That is what produced ECMAScript 5 code, as mentioned in the previous paragraph. Currently the best practice is to use Babel with the React preset to process Flow code. You still get the benefit of transpiling ECMAScript 6 code to ECMAScript 5, if you have Babel configured to do that.

One of my favorite features of Flow is that null and undefined are not treated as bottom types. A value is only allowed to be null if it has a nullable type. This makes Flow better at catching null pointer exceptions than almost any other object-oriented language.

For example:

A type expression ?T behaves pretty much like T | null | undefined. (From what I can tell, null and undefined are distinct types in Flow - but it does not seem to be possible to use them in type annotations at this time. void is allowed, which seems to be an alias for undefined.)

In the past I have talked to one or two people who said that they would only be interested in type-checked JavaScript if it supported algebraic types. (These are the kind of people I work with :)) That is possible too - here is an example that I wrote:

Thanks to type narrowing, accessing tree.value passes type-checking in the if body where tree instanceof Node is true. Without that check, the type checker would not allow accessing properties that do not exist on both Node and EmptyTree.

There are some details in this example that I want to call out:

The class syntax is from ECMAScript 6 - but it is extended in Flow to support type annotations for properties.
Tree is a type alias. It has no runtime representation. None is needed, since Node and EmptyTree have no shared behavior. And unlike a superclass, Tree is sealed, meaning that it is not possible to add more subtypes to Tree elsewhere in the codebase.
Flow supports parameterized types (a.k.a. generics, a.k.a. parametric polymorphism).
You can specify the exact type of function values (in this case, the type of predicate).
find might return a value from a tree, or it might return undefined. So the return type is T | void (where void is the type of undefined). Writing ?T would also work.

I have not been sold on prior JavaScript type checkers. They did not seem to "get" JavaScript. Flow is a type checker that I actually plan to use.

Javascript generators and functional reactive programming

Sat, 02 Aug 2014 00:00:00 GMT

tl;dr: ECMAScript 6 introduces a language feature called generators, which are really great for working with asynchronous code that uses promises. But they do not work well for functional reactive programming.

ES6 generators allow asynchronous code to be written in a way that looks synchronous. This example uses a hypothetical library called Do (implementation below) that makes promises work with generators:

It is possible to use generators now in Node.js version 0.11 by using the --harmony flag. Or you can use Traceur to transpile ES6 code with generators into code that can be run in any ES5-compatible web browser.

I recently saw an informative talk from Jacob Rothstein on Co and Koa. Those are libraries that make full use of generators to make writing asynchronous code pleasant. The implementation of the above example in Co is almost identical.

Co operates on promises and thunks, allowing them to be expanded with the yield keyword. It has nice options for pulling nested asynchronous values out of arrays and objects, running asynchronous operations in parallel, and so forth. One can even use try / catch to catch errors thrown in asynchronous code!

Co is specialized for asynchronous code. But when I look at it I see something that is really close to being a monad comprehension - very much like the do notation feature in Haskell. With just a little tweaking, the use of generators that Co has pioneered can almost be generalized to work with any kind of monad.

For example, libraries like RxJs and Bacon.js implement event streams, which are a lot like promises, except that callbacks on event streams can run more than once. This example uses Bacon to manage a typeahead search feature in a web interface:

The idea is that when the user enters more than two characters of text into a search box, a background request is dispatched and search results appear on the page automatically. This example requires a library that is a little more general than Co, that is able to operate on Bacon event streams in addition to promises and thunks. Here is a basic implementation of that library:

This is the function that makes the example at the top of this post work. It is a simplified version of what Co does - the difference being that Do delegates to a flatMap function to handle yielding. We just need an implementation of flatMap that can operate on some different monad types. The one above works with promises or with Bacon event streams. An implementation that is easier to extend would be nice; but I will leave that problem for another time.

Unfortunately, the Bacon example does not work. Streams - unlike promises - get many values. That means that the code in each generator has to run many times (once for each stream value). But ES6 generators are not reentrant: after resuming a generator from the point of a given yield expression, it is not possible to jump back to that entry point again (assuming the generator does not contain a loop). With the Bacon example, after the first keyup or change event the search result list will just stop updating.

Getting synchronous-style functional reactive programming to work well would require immutable, reentrant generators. ES6 generators are stateful: every invocation of a generator changes the way that it will behave on the next invocation. In other words, a generated is mutated on every invocation:

An immutable implementation would return a new object with a function for the next generator entry point, instead of mutating the original generator:

An immutable generator could be implemented with some simple syntactic transforms. The basic case:

would transform to:

The next property is returned is a generator that is used to invoke the next step. In this view generators are just functions. Not only that - a generator is a closure that has access to the results of previous steps via closure scope.

There would just need to be a few cases to handle appearances of yield in a return statement, a try-catch block, or as its own statement. With that kind of stateless design, the Bacon example would work fine. But as far as I know, there is no plan for stateless, reentrant generators in ECMAScript.

It is possible to make functional reactive programming work with non-reentrant generators by using loops in the generators. This approach is not as general or as composable. Asynchronous pieces would have to be declared specially at the top of the function, for example.

Notice that yield is overloaded to accept asynchronous values and to return results - which requires some awkward logic to inspect generator values. I do not know how to implement resultView as a loop, since it requires combining two event streams: search queries and JSON responses. I do not see any advantage of loops in generators over asynchronous-style callbacks. But maybe someone more imaginative than me can come up with a more elegant solution.

Kinesis Advantage with DSA keycaps

Mon, 19 May 2014 00:00:00 GMT

I now have a Kinesis Advantage keyboard for use at work. I have been feeling some wrist strain recently; and some of my coworkers were encouraging me to try one. So I borrowed a Kinesis for a week, and found that I really liked it. The contoured shape makes reaching for keys comfortable; I find the column layout to be nicer than the usual staggered key arrangement; and between the thumb-key clusters and the arrow keys, there are a lot of options for mapping modifier keys that are in easy reach.

Kinesis Advantage, before modification

But I really like the PBT keycaps on my Leopold. I would not enjoy going back to plain, old ABS. I also don't want my keyboard to be just like every other Kinesis. So I decided to get replacement keycaps.

I did some research on buying PBT keycaps with the same profiles as the stock Kinesis keys. I assumed that I would end up getting blank keycaps - putting together a set with legends appropriate for a Kinesis seemed like it would be a painful undertaking, since there don't seem to be any sets made specifically for the Kinesis.

Most keyboards - including the Kinesis Advantage - use what is called a DCS profile, where the keys in each row have different heights and angles. (That does not include laptop keyboards, or island-style keyboards such as the ones that Apple sells. Those are in their own categories.)

DCS family: medium profile, cylindrical top, sculptured. (Image from Signature Plastics.)

Input Nirvana on Geekhack has a post with a list of all necessary keycap sizes and profiles to reproduce the arrangement on a stock Kinesis. It is possible to order these individually from Signature Plastics; but their inventory for à la carte orders varies depending on what they have left over from production of large batches. When I checked, SP did not have any row 5 PBT keycaps available. I got the impression that building a custom DCS set would be somewhat difficult.

Then I saw prdlm2009 on Deskthority suggest that DSA profile keycaps work well on a Kinesis. DSA is a uniform profile - every key has the same height and angle. It makes everything much simpler when dealing with unusual keyboard layouts, or unusual keyboards.

DSA family medium profile, spherical top, non-sculptured. (Image from Signature Plastics.)

DSA also features spherical tops. If you look at the keys on a typical keyboard, you can see that the top curves up on the left and right sides - as though someone had shaped them around a cylinder. The tops of DSA keys are spherical; as though shaped around a large marble. So the keys cup the fingertips from all sides.

Signature Plastics sells a variety of nice, blank DSA keycap sets. I did not order the optimal combination of keycap sets; but now I have a better idea of what that combination is. The key count on an Advantage is:

56 – 1x keys (optionally including two homing keys)
8 – 1.25x keys
4 – 2x keys

1x, 2x, etc. refers to the lengths of the keys.

One can get everything except the 1.25x keys with one ErgoDox Base set and two Numpad sets. The Numpad sets seem to be the cheapest way to get all 4 2x keycaps, along with additional 1x caps. The only set that includes 1.25x caps is the Standard Modifier set, which includes 7 of them. (So close!) I recommend ordering the 1.25x keycaps individually from the blank keycap inventory.

stock Kinesis keycaps (left), DSA keycaps (right)

The keycaps from SP are much thicker than the stock keycaps. And they are made from PBT plastic, which is denser than the more common keycap material, ABS. What I like most about PBT caps is their texture. The tops of the keys are usually slightly rough, somewhat pebbly. It gives a little bit of grippiness, and feels soothing on my fingers compared to featureless, flat plastic. I also think that the sound of PBT keys being pressed is nicer. It is slightly quieter, with a somewhat deeper tone.

All of the stock keycaps have been removed, revealing Cherry MX Brown switches.

The Kinesis Advantage comes with either Cherry MX Brown or Cherry MX Red switches.

For anyone wondering how to remove keycaps from a keyboard with Cherry MX switches, here is a video. What the video does not mention is that it is a good idea to wiggle the keycap puller while pulling up on the keycap. That helps to avoid pulling with too much force, which could break a switch.

I have another keyboard that also has Cherry MX Brown switches, and I really liked the change in key feel after installing o-rings. O-rings make typing a little quieter, and add some springiness to the bottom of the key travel. A tradeoff is that they reduce the length of key travel a bit.

installing o-rings in the new keycaps

I used 40A-R o-rings from WASD, which are relatively thick and soft. But when I tried these out with the DSA keycaps I could not discern any difference between a key with an o-ring and one without.

Comparing the underside of a DSA keycap to a typical DCS keycap reveals the issue:

blank DSA keycaps from SP (top), keycaps from a Leopold FC660M (bottom)

DCS keycaps have cross-shaped supports under the cap, which contact the top of the switch housing when the key is fully depressed. O-rings sit between those supports and the switch housing, absorbing some force from contact. But the DSA keycaps lack those supports. That means that the switch can reach the bottom of its travel before the underside of the keycap contacts the switch housing.

I found that doubling up o-rings pushed the rubber high enough to be effective. But I was concerned that two o-rings shorted key travel too much and introduced too much squishiness. In the end I left the o-rings out entirely. I may take another shot using either thinner, firmer o-rings, or with small washers in place of a second o-ring.

two o-rings installed in one keycap

When I ordered my keycaps I got one ErgoDox Base set and one ErgoDox Modifier set. I did not do enough checking - I assumed that the 1.5x keys in the Modifier set would fit in the Kinesis. But it turns out that the keys in the leftmost and rightmost columns of the Kinesis take 1.25x keycaps. The larger keycaps do not fit.

Whoops! That was supposed to be a 1.25x key, not a 1.5x.

I have ordered some appropriately sized keycaps. In the meantime, I am using 1x keycaps in the 1.25x positions.

stock 1.25x Tab key next to its intended, blank replacement

Even though the DSA keycaps are not the same shape as the stock caps, they fit quite well on the Kinesis. There are just two slightly problematic spots. The photo below shows the one key that comes into contact with the edge of the keyboard case when it is not depressed. Thankfully the operation of the key does not seem to be affected.

The fit is tight in this corner.

Due to small differences in switch positioning, the key in the same position in the other well has a little bit of clearance.

The other problem is that two of my 2x keys overlap very slightly. When I press the one on the right there is sometimes an extra click as it pushes past its neighbor.

There is not quite enough space between these two keys.

I am thinking of sanding down the corners of these keys a little bit to fix the problem.

This is another case where there is no problem with the keys in the same positions on the other side of the board. It seems that the switches in the left thumb cluster just happen to be a little too close together on my board.

All done!

Since I had to use 1u keycaps for the leftmost and rightmost columns, I ended up not having enough keycaps to replace the two keycaps in the top of each thumb cluster. But I think that having tall keycaps there makes them easier to press - those positions are a bit difficult to reach otherwise. So I may just keep the stock caps on those keys. Or I might try to get tall, DCS profile, PBT caps for those positions.

closeup of one of the wells to show key spacing

The other positions where I think that DSA does not work really well are the four keys in the bottom row of each well. I curl my fingers down to reach those; and I tend to either hit the edges of the keys, or to press them with my fingernail instead of with my finger. The stock keycaps for those positions are angled toward the center of the well, making it easier to reach the tops of the keys.

Those points aside, I am very pleased with how these new keycaps worked out! The DSA profile is quite comfortable. I love the texture of the PBT keycaps. And they make a more pleasant sound than the thinner ABS caps that came with the board.

shoe for science!

Category Theory proofs in Idris

Mon, 05 May 2014 00:00:00 GMT

Idris is a programming language with dependent types. It is similar to Agda, but hews more closely to Haskell. The goal of Idris is to bring dependent types to general-purpose programming. It supports multiple compilation targets, including C and Javascript.

Dependent types provide an unprecedented level of type safety. A quick example is a type-safe printf implementation (video). They are also useful for theorem proving. According to the Curry-Howard correspondence, mathematical propositions can be represented in a program as types. An implementation that satisfies a given type serves as a proof of the corresponding proposition. In other words, inhabited types represent true propositions.

The Curry-Howard correspondence applies to every language with type checking. But the type systems in most languages are not expressive enough to build very interesting propositions. On the other hand, dependent types can express quantification (i.e., the mathematical concepts of universal quantification (∀) and existential quantification (∃)). This makes it possible to translate a lot of interesting math into machine-verified code.

This post is written in literate Idris. The original markup can be compiled and type-checked. Code blocks that are prefixed with greater-than symbols (>) in the markup are evaluated. Blocks that are marked off with three backticks are given for illustrative purposes and are not evaluated.

In Idris, partial functions are allowed by default. A totality requirement can be specified per-function. This line enforces totality checking by default for functions in this module.

A function that is total is guaranteed to terminate and to return a well-typed output for every possible input.¹ A function that does not terminate, or that throws a runtime error for some inputs, is said to be partial.

A partial function can introduce a logical contradiction, which would make proofs unreliable. So totality checking is useful for theorem proving.

Theorem proving

Consider the definition of the natural number type in the Idris standard library:

This defines a type, Nat, with two constructors for producing values: a number may be zero (Z), or it may be one greater than another number (S Nat).

A type can be indexed by another type. That describes a type produced by a type constructor that takes one or more values as parameters. Here is a constructor for indexed types from the Idris standard library:

This declares that LTE is a constructor that takes two Nat values as parameters, and produces a concrete Type. The types that LTE constructs also happen to be propositions which state that one natural number is less than or equal to another. It should be read, "the natural number n is less than or equal to the natural number m".

Two value constructors are given. They are written so that a value that satisfies a given LTE type be written if and only if the n in that type is less than or equal to the m. In this way, a value that satisfies a type of the form LTE n m is a proof that n really is less than or equal to m.

lteZero is a singleton value - it is a constructor that takes no arguments. But its type contains a variable; so it is polymorphic. lteZero can satisfy any type of the form, LTE Z n. lteZero is effectively an axiom, stating a fundamental property of natural numbers.

Given the definition of LTE it is possible to write a proposition, such as, "zero is less than or equal to every natural number".

The proposition is written as a function that takes a number as input. The value that is given is assigned to the variable n, which is used to specify the return type. Thus the return type of nonNegative depends on the input value. Wherever you see (a : A) it can be read as, "Some value of type A will be given here, and that value will be assigned to the variable a."

To write an implementation for nonNegative, it is necessary to produce a value of the appropriate LTE type without any information about what input might be given - other than the fact that it will be a natural number. Totality checking is enabled, so any implementation must be applicable to every possible input. Thus a type of the form, (x : A) -> P x describes universal quantification over the type A.

nonNegative happens to be a restatement of the axiom, lteZero. So an implementation / proof is trivial:

On the other hand, lteSucc maps a given proof to a proof of a related proposition. It is used in proofs-by-induction. For example, a proof that every number is less than or equal to itself:

The proof that zero is equal to itself is given by the axiom. For every other number, the proof is given as an inductive step using a proof for the next-smallest number.

Because the type of lteSucc is that of a function, it can be read as a proposition involving logical implication: "n <= m implies that n + 1 <= m + 1." In general, types of the form P x -> Q y can be read as logical implication.

We have seen that the input value to a function can be labelled and referenced in the output type. That is a special property of functions. For example, it is not permissible to label the value in the first position of a tuple type to reference it in the second position. But there is a special construction, the dependent pair, which does allow this. Dependent pairs are used to represent existential quantification.

A dependent pair type of the form (x : A ** P x) is read as existential quantification over the type A.

A proof of a proposition with existential quantification can be given as a pair of an arbitrary value and a proof that the proposition holds for that value. For example, here is a proof of the Archimedean Property of natural numbers, "For every natural number, n, there exists a natural number, m, where m > n":

The quantified proposition uses (S n) instead of just n to indicate that m must be strictly greater than n - greater-than-or-equal-to is not sufficient. The proof supplies S n as a witness - a specific value that is used to prove that the quantified proposition holds. Remember that S n is just another way of writing n + 1. The second component of the dependent pair value must be a proof that the witness is greater than or equal to S n - as is required by the type. Since S n and S n are equal, lteReflexive suffices.

Definition of Category

I have been studying Category Theory; so I decided to use that as a topic for exercises when learning about Idris. If you are wondering what Category Theory is all about, take a look at Why Category Theory Matters.

There is a much more complete description of Category Theory concepts written in Agda. The definition below was an exercise for me in learning about Category Theory concepts myself.

A category is a set of objects combined with a set of arrows that encode relations between objects. When talking about all possible categories, the concepts of "object" and "arrow" are very abstract. They could be pretty much anything. Descriptions of specific categories make specific statements about what objects are and what arrows are.

Let's implement a type class to capture this definition.

Arrows are indexed by objects. That is, the type of an arrow carries its domain (the object that an arrow originates from) and its codomain (the object that an arrow points to). Note that obj is given as an unqualified variable. In some categories objects will be types - as in the Set category. In others they will be plain values.

The methods of this type class will define the category laws. For starters, there must be an id arrow for every object. This line specifies that an instance of this type class must provide a cId implementation with the given type:

As was shown above, a function type serves as a proposition with universal quantification. So the type of cId states that every object must be both the domain and codomain of at least one arrow. The implementation will also provide a means to identify that arrow.

Arrows must be composable. If one arrow points from objects a to b, and another arrow points from 'b' to 'c', then it must be possible to combine them to produce an arrow from 'a' to 'c'.

Arguments in curly braces are implicit parameters. In most cases the compiler will infer those values. So they are generally not given as explicit arguments when invoking the function. However, it is possible to provide implicit parameters explicitly when needed.

cId and cComp are the only required functions that actually produce arrows. But it is necessary to provide more specific rules about how they should behave.

These propositions state that id arrows must not only have the same object as domain and codomain - they must also be identities under composition. Implementations of cIdLeft and cIdRight will never be used at runtime - they are just proofs that cId and cComp obey the category laws.

Here (=) is a type constructor, very much like LTE. Its definition looks like this:

The parameters to (=) can be any expressions - including plain values or types. refl is another axiom, stating that equality is reflexive. Basically, to prove that two expressions are equivalent it is necessary to demonstrate to the type checker that they have the same normal form.

This implies that there might be multiple arrows pointing between the same two objects; and that those arrows are not necessarily equivalent. When talking about all possible categories, it is not possible to say what it is that makes arrows different or the same. Rather, any specific category must have its own definition of equality of arrows. Some categories will have many arrows between each pair of objects; some will have at most one.

One more proof is required to complete the Category type class. Arrow composition must be associative.

I have cheated slightly. In the types for cIdLeft, cIdRight, and cCompAssociative I left the implicit arguments to cComp implicit. But I was not able to get those definitions to type-check. I actually had to list out the implicit parameters when applying cComp in a type expression. The working definitions are a bit more difficult to read:

It has been pointed out to me that the compiler is not able to determine which implementation of cidLeft, cIdRight, or cCompAssociative should be invoked, unless the implicit parameters are listed. If Category were implemented as a record type instead of as a type class this would probably not be necessary.

A partial ordering category

With the definition of Category in place, it is possible to describe specific categories - and to prove that they obey the category laws.

The LTE type constructor can be used to describe a category where arrows are LTE relations, and objects are natural numbers. In this category, there are arrows that point from each number to every other number that is larger, and also back to the number itself.

An id arrow in this category is a proof that a number is less than or equal to itself. This is the same thing that was proved by lteReflexive; so the implementation is the same.

Arrow composition is a proof that the less-than-or-equal-to relation is transitive. For reference, here is the type for cComp specialized for LTE:

And the proof construction:

In the first equation, the second input is lteZero; which implies that a is zero. a is also the domain in the LTE result that we want to prove; so the proof is trivial. The second equation takes advantage of the fact that the lteSucc constructors of input arrows can be recursively unwrapped, until reaching the base case, where the second input is lteZero.

There is no pattern for a case where the first input is lteZero where the second is not. It is not required, because that case is not allowed by the type of cComp - and the type checker is able to confirm that. If it were necessary to make explicit that this case is not possible, that could be stated with a third equation:

The keyword impossible is one tool available for proofs of falsehood.

Now to prove the remaining category laws.

Demonstrating identity under composition of proofs is a little strange. What we need to show is that composing an identity arrow with any other arrow does not introduce new information.

In the base case of cIdLeft, if the given arrow, f, is lteZero then its domain must be zero. Therefore the identity arrow it is composed with must also be lteZero. Those are the same normal form, so the proof invokes refl - the axiom of reflexivity of equality.

The inductive step applies cong, which is a proof of congruence of equal expressions. It is defined in the standard library:

In this case the f that cong infers as its implicit parameter is lteSucc.

cong is an example of a proof constructor: it takes a proof as input and returns a proof of a related proposition. Functions like cong are the building blocks of multi-step proofs.

You may notice that cong takes refl as an argument and returns it. cong has equality proofs as its input and output. By definition, the only possible value of an equality type is refl.

The base case of cIdRight is not as trivial as the base case of cIdLeft. the codomain of lteZero is not necessarily zero; so the identity arrow involved could be some lteSucc value. However the compiler is able to do some normalization automatically. That means that it is not necessary to spell out every step.

The proof of associativity follows a similar pattern.

A monoid as a category

The natural numbers form a monoid under addition. In particular:

Two numbers can be combined by addition to produce a third number.
There is an additive identity (0).
Addition is associative.

The monoid also forms a category with just one object, (which will be arbitrarily represented with ()) where the arrows are integers, and arrows are composed by addition. Since there are an unbounded number of natural numbers, in this category there are an unbounded number of arrows pointing from () back to ().

This category is made a bit complicated by the requirement that arrows are indexed by domain and codomain. Those indexes will not be meaningful in a category with just one object. But for the sake of generality, a trivial higher-kinded wrapper around Nat is needed.

In Idris, as in Haskell, () is a type with exactly one value, which is also called ().

To make it clear that a NatArrow is really just a Nat, we can prove that the two types are isomorphic.

An isomorphism is a bidirectional mapping that preserves information in both directions. to and from specify the mapping; toFrom and fromTo prove that information is preserved.

Now the definition of the Nat category:

This implementation uses (+) for arrow composition. It reuses proofs of identity and associativity for (+). It is only necessary to apply cong to the predefined proofs to show that applying the getNat constructor to both sides of an equality does not change anything.

For another look at monoids in Idris, see Verifying the monoid laws using Idris (video).

Category of sets

In the Set category, objects are sets and arrows are functions. The implementation here will use Type as the type of objects. In Idris, the type of every small type is Type. For example, the type of Nat is Type. The type of String is also Type. The type of Type is Type 1 - meaning that Type is not a small type itself.

The definition of Category requires proofs of equivalence for arrows. But there is no predefined comparison operator for functions in Idris. All that you can really do with a function is to give it some inputs, and check what its outputs are.

To produce a viable category, it is necessary to introduce the axiom of function extensionality:

If two functions produce the same output for all possible inputs, then they are equivalent.

funext takes as input two functions and a proof that those functions produce the same output for all inputs. Note the parentheses in that type: As function types serve as universal quantifiers, higher-order functions provide a means to nest quantification inside of larger propositions.

I am told that it is not possible to prove funext in Idris - and that that limitation is not unique to Idris. Therefore, function extensionality must be given as an axiom:

believe_me is a "proof" to use sparingly.

Implementations for an identity function and for composition of functions are provided in the standard library. In fact, Idris includes a Control.Category module with a predefined Category type class. But that definition does not include all of the category laws. What remains to be defined are proofs of identity and associativity.

Proving that id (f x) and f (id x) reduce to f x is sufficiently easy that the compiler can do most of the work on its own. To make the next step to f x = f x -> f = f is just a matter of applying funext.

In order to prove associativity, it is helpful to have a helper proof that could be described as, "pointful composition".

The proof of associativity is a bit complicated. So it is broken into steps here, with proven intermediate propositions given for each step.

There are two standard library functions used here that have not been introduced yet. They are:

When a free, lowercase variable appears in a type expression, Idris inserts an additional implicit parameter at the beginning of the expression. It is up to the compiler to infer the types of the free variables. After carrying out that expansion, the type of trans looks like this:

There may be more steps listed in compAssociative than are really required. Hopefully including them helps to clarify the proof.

In Haskell, (->) is an ordinary type constructor that could be used as the arrow type in a type class like Category. It seems that is not the case in Idris. To work around that, the standard library includes a type, Morphism, that is isomorphic to the function type.

The proofs above provide everything that is required to prove the validity of a category of Types and functions. But the definition here uses Morphism for arrows; so a little extra translating is necessary.

The operator (~>) is an infix alias for Morphism.

As with Nat and NatArrow, the correspondence between (->) and Morphism is made official with a proof of isomorphism.

It is my hope that I can use these definitions to work out exercises as I continue to explore Category theory.

The Halting Problem states that there are programs that cannot be proven to terminate. That does not mean that it is impossible to prove that any program terminates. Idris and other languages with totality checking put some restrictions on the forms that functions are allowed to take so that totality checking is possible.↩

Functional data structures in JavaScript with Mori

Mon, 04 Nov 2013 00:00:00 GMT

I have a long-standing desire for a JavaScript library that provides good implementations of functional data structures. Recently I found Mori, and I think that it may be just the library that I have been looking for. Mori packages data structures from the Clojure standard library for use in JavaScript code.

Functional data structures

A functional data structure (also called a persistent data structure) has two important qualities: it is immutable and it can be updated by creating a copy with modifications (copy-on-write). Creating copies should be nearly as cheap as modifying a comparable mutable data structure in place. This is achieved with structural sharing: pointers to unchanged portions of a structure are shared between copies so that memory need only be allocated for changed portions of the data structure.

A simple example is a linked list. A linked list is an object, specifically a list node, with a value and a pointer to the next list node, which points to the next list node. (Eventually you get to the end of the list where there is a node that points to the empty list.) Prepending an element to the front of such a list is a constant-time operation: you just create a new list element with a pointer to the start of the existing list. When lists are immutable there is no need to actually copy the original list. Removing an element from the front of a list is also a constant-time operation: you just return a pointer to the second element of the list. Here is a slightly more-detailed explanation.

Lists are just one example. There are functional implementations of maps, sets, and other types of structures.

Rich Hickey, the creator Clojure, describes functional data structures as decoupling state and time. (Also available in video form.) The idea is that code that uses functional data structures is easier to reason about and to verify than code that uses mutable data structures.

Clojure, ClojureScript, and Mori

Clojure is a functional language that compiles to JVM bytecode. It is a Lisp dialect. Among Clojure's innovations are implementations of a number of functional data structures, old and new. For example, other Lisps tend to place prime importance on linked lists; but a lot of Clojure code is based on PersistentVector, which supports efficient random-access operations.

ClojureScript is an alternative Clojure compiler that produces JavaScript code instead of JVM bytecode. The team behind ClojureScript has ported Clojure collections to ClojureScript implementations - which are therefore within reach of JavaScript code.

Mori incorporates the ClojureScript build tool and pulls out just the standard library data structures. It builds a JavaScript file that can be used as a standalone library. Mori adds some API customizations to make the Clojure data structures easier to use in JavaScript - such as helpers to convert between JavaScript arrays and Clojure structures. Mori also includes a few helpers to make functional programming easier, like identity, constant, and sum functions. These are the data structures provided in the latest version of Mori, v0.2.4:

constructor	Mori	Clojure
`list`	Mori docs	Clojure docs
`vector`	Mori docs	Clojure docs
`range`	Mori docs	Clojure docs
`hash_map`	Mori docs	Clojure docs
`array_map`		Clojure docs
`sorted_map`		Clojure docs
`sorted_map_by`		Clojure docs
`set`	Mori docs	Clojure docs
`sorted_set`	Mori docs	Clojure docs
`sorted_set_by`		Clojure docs

All of these data structures are immutable and can be efficiently updated via copying and structural sharing.

The documentation for Mori is pretty good. But it does skip over some of the available data structures and functions. Since most of the stuff provided by Mori comes from Clojure, if you cannot find information that you need in the Mori docs you can also look at the Clojure docs. I provided links to the Clojure documentation for each data structure where more detailed descriptions are available.

Installing and running

To get Mori, install the npm package mori. Then you can require the module 'mori' in a Node.js project; or copy the file mori.js from the installed package and drop it into a web browser.

Examples

Let's take a look at the particular advantages of some of these structures.

`vector`

A vector is an ordered, finite sequence that supports efficient random-access lookups and updates. Vectors are created using the vector function from the 'mori' module. Any arguments given to the function become elements of a new vector. In Node.js you can import Mori and create a vector like this:

Mori also works with AMD implementations (such as RequireJS) for use in browser code:

Idiomatic Clojure is not object-oriented. The convention in Clojure is that instead of putting methods on objects / values, one defines functions that take values as arguments. Those functions are organized into modules to group related functions together. This approach makes a lot of sense when values are mostly immutable; and it avoids name collisions that sometimes come up in object-oriented code, since names are scoped by module instead of by object.¹

Since Mori is an adaptation of Clojure code, it uses the same convention. Data structures created with Mori do not have methods. Instead all functionality is provided by functions exported by the 'mori' module. That is why the code here uses expressions like mori.count(v) instead of v.count().

Existing vectors can be modified:

conj is an idiom that is particular to Clojure. It inserts one or more values into a collection. It behaves differently with different collection types, using whatever insert strategy is most efficient for the given collection.²

higher-order functions

Mori provides a number of higher-order functions. Here is an example that computes the sum of the even values in a collection:

Or, borrowing from an example in the Mori documentation, one might compute a sum for even values and a separate sum for odd values:

The example above returns a map created with array_map, which is a map implementation that works well with a small number of keys.

`sorted_set_by`

JavaScript does not have its own set implementation. (Though it looks like one will be introduced in ECMAScript 6.) Sets are a feature that I often miss.

A sorted set is a heavenly blend of a sequence and a set. Any duplicate values that are added are ignored, and there is a specific ordering of elements. Unlike a list or a vector, ordering is not based on insertion, but is determined by comparisons between elements.

One possible use for a sorted set is to implement a priority queue. Consider an example of a calendar application. sorted_set_by takes a comparison function that is used to to maintain an ordering of added values. With the appropriate comparison appointments are added and are automatically sorted by date:

Like the underlying set, this calendar implementation is immutable. When an appointment is added you get a new calendar value.

The comparison function for comparing appointments sorts appointments by date, and uses title as a secondary sort in case there are appointments with the same date and time. The sorted set uses this function to determine equality as well as ordering; so if it made comparisons using only the date field then the calendar would not accept multiple appointments with the same date and time.

Appointments can be added to a calendar and queried in date order:

Looks good! Now let's add an undo feature. In case the user changes her mind about the last appointment that was added, the undo feature should recreate the previous state without that appointment. The implementation of Calendar is the same as before except that the constructor takes an additional optional argument, the add method passes a reference from one calendar value to the next, and there is a new undo method:

Assuming the same set of appointments, we can use the undo method to step back to a state before the fourth appointment was added:

Immutability comes in handy in this scenario. It is trivial to step back in time.

Actually because Calendar is immutable, you don't necessarily need a special method to get undo behavior:

I'm sure that the Synesthesia Bike Tour is a lot of fun. It's just that when demonstrating an undo feature, something has to take the fall. That's just the world that we live in, I suppose.

`hash_map`

All JavaScript objects are maps. But those can only use strings as keys.³ The hash_map provided by Mori can use any values as keys.

If you use plain JavaScript objects as keys they will be compared by reference identity. If you use Mori data structures as keys they will be compared by value using equality comparisons provided by ClojureScript.

Mori maps are immutable; so there is never a need to create defensive copies. An update operation produces a new map.

The function assoc adds any number key-value pairs to a map; and dissoc removes keys.

All of this also applies to array_map, sorted_map, and sorted_map_by. See Different map and set implementations below for information about those.

There is a common pattern in JavaScript of passing options objects to constructors to avoid having functions that take zillions of arguments. It is also common to have a set of default values for certain options. So code like this is pretty typical:

I usually put in an empty object as the first argument to the Underscore _.extend call so that I get a new object instead of modifying the given options object in place. Modifying the options object could cause problems if it is reused somewhere outside of my constructor. An alternative to the defensive copy could be to use immutable Mori maps:

The function mori.into(coll, from) adds all of the members of from into a copy of coll. Both from and coll can by any Mori collection.

That does still involve copying the input options object into a new Mori map. It is also possible to provide a Mori sequence as input to start with - js_to_clj will accept either a plain JavaScript object or a Mori collection:

There is probably no performance gain from using Mori in this situation. It is unlikely to matter anyway, since the structures involved are small. In situations with larger data structures, or where data is copied many times in a loop, Mori's ability to create copies faster using less memory could make a difference.

But in my opinion applying immutability consistently - even where there are no significant performance gains - can simplify things.

Apples to apples

The transformations that are available in Mori - map, filter, etc.

return lazy sequences no matter what the type of the input collection is. (See Laziness below for an explanation of what laziness is). This is advantageous because the other collection implementations are not lazy. But what if you want to do something like create a new set based on an existing set? The answer is that you feed a lazy sequence into a new empty collection using the appropriate constructor or the into function, which dumps all of the content from one collection into another:

Applying map to the first set is lazy - but building the second set with into is not. So a good practice is to avoid building non-lazy collection until the last possible moment.

An odd quirk in Mori is that the set constructor takes a collection argument, but most of the other constructors take individual values or key-value pairs. The into function behaves more consistently across data structure implementations.

You might want to write transformations that are polymorphic - that can operate on any type of collection and that return a collection of the same type. To do that use mori.empty(coll) to get an empty version of a given collection. This makes it possible to build a new collection without having to know which constructor was used to create the original.

Here is a function that removes null values from any Mori collection and that returns a collection of the same type:

If the collection given is a map then the value of elem in the filter callback will be a key-value pair. So compact includes an is_map check and extracts the value from that key-value pair if a map is given.

A nice advantage of empty is that if you use it on a sorted_set_by or on a sorted_map_by, the new collection will inherit the same comparison function that the original uses.

Mori pairs well with Bacon

In a previous post, Functional Reactive Programming in JavaScript, I wrote about functional reactive programming (FRP) using Bacon.js and RxJS. A typical assumption in FRP code is that values contained in events and properties will never be updated in place. The immutable data structures that Mori provides are a perfect fit.

List versus Vector

Linked lists are nice and simple - but become less appealing when it becomes desirable to access elements at arbitrary positions in a sequence, to append elements to the end of a sequence, or to update elements at arbitrary indexes. The running time for all of these operations on lists is linear, and the append and update operations require creating a full copy of the list up to the changed position.

Clojure's PersistentVector is a sequence, like a list. But under-the-hood it is implemented as a tree with 32-way branching. That means that any vector index can be looked up in O(log_32 n) time. Appending and updating arbitrary elements also takes place in logarithmic time. For more details read Understanding Clojure's PersistentVector implementation.

Sequences that are implemented as mutable arrays of contiguous memory support constant-time lookups and modification (not including array resizing when array length grows). If O(log_32 n) does not seem appealing in comparison, consider that if you are using 32-bit integers as keys:

Which means that your keyspace will run out before your vector's tree becomes more than 7 layers deep. Up to that point operations will be O(7) or faster.

If your keys are JavaScript numbers, which are 64-bit floating point values, the largest integer that you can count up to without skipping any numbers is Math.pow(2, 53). The logarithm of that number is also small:

The hash_map and set implementations in Mori are also implemented as trees with 32-way branching. The sorted map and set structures are implemented as binary trees.

Equality, ordering, and hashing

Map and set lookups are based on either hashing or ordering comparisons, depending on the implementation. JavaScript does not have built-in hash functions - at least not that are accessible to library code. It also does not have defined ordering or equality for most non-primitive values. So Mori uses its own functions, which it gets from ClojureScript.

hash

Every Mori value has a hash that identifies its content:

If a value is recreated with the same content, it has the same hash:

Mori's hash function delegates to a specific hash algorithm for each of its data structures, which are ultimately based on internal algorithms that Mori uses to compute hashes for primitive JavaScript values:

Since Mori also accommodates arbitrary JavaScript values as map keys and set values, it also has a scheme for assigning hash values to other JavaScript objects.

It seems that Mori has a monotonically increasing counter for object hash values. The first object that it computes a hash for gets the value 1; the second object gets 2, and so on. To keep track of which object got which hash value, it stores the value on the object itself:

There are obvious hash-collision issues between non-Mori objects, numbers, and true. But Mori data structures can handle hash collisions. If a collection uses all of those types as keys it could end up with one hash bucket with three entries.

equals

Mori has its own equals function, which also comes from ClojureScript. As with hash, any two mori values that have the same content are considered to be equal:

It works on primitive JavaScript values:

When applied to non-Mori JavaScript objects, equals works the same way that the built-in === function does:

compare

ClojureScript has a compare function, which Mori uses in its sorted data structure implementations. Mori does not export the compare function. The function defines an ordering for Mori values and for primitive JavaScript values - but not for other JavaScript objects. So if you want to put non-Mori objects into a sorted structure you will have to use an implementation that accepts a custom comparison function.

Different map and set implementations

hash_map and set use a hash function for lookups and have O(log_32 n) lookup times; the sorted variants use comparison functions for lookups and have O(log_2 n) lookup times; and array_map is just an array of key-value pairs, so it uses only an equality function for lookups and has O(n) lookup times.

constructor	insert time	lookup time	how keys/values are checked
`hash_map`	log_32 n	log_32 n	`hash(key) === hash(target_key) && equals(key, target_key)`
`array_map`	1	n	`equals(key, target_key)`
`sorted_map`	log_2 n	log_2 n	`compare(key, target_key)`
`sorted_map_by`	log_2 n	log_2 n	like `sorted_map` with a user-supplied comparison function
`set`	log_32 n	log_32 n	`hash(val) === hash(target_val) && equals(val, target_val)`
`sorted_set`	log_2 n	log_2 n	`compare(val, target_val)`
`sorted_set_by`	log_2 n	log_2 n	like `sorted_set` with a user-supplied comparison function

hash and equals are provided by Mori. compare is part of ClojureScript, but is not exported by Mori.

Note that the sorted structures do not perform equals checks - instead they rely on a comparison function to determine whether values or keys are the same. On the other hand, the hash structures do perform equals checks to handle hash collisions.

array_map is unique among the map and set implementations in that it preserves the order of keys and values based on the order in which they were inserted. If a value is inserted into an array_map and then the map is converted to a sequence (for example, using mori.seq(m)) then the last key-value pair inserted appears last in the resulting sequence. The ordering in a new array_map is determined by the order of key-value pairs given to the constructor.

array_map is a good choice for small maps that are accessed frequently. The linear lookup time looks slower than other map implementations on paper. But there is no hashing involved and only simple vector traversal - so each of those n steps is faster than each of the log_32 n steps in a hash_map lookup.

The array_map implementation has an internal notion of the upper limit on an efficient size. Once the map reaches that threshold, inserting another key-value pair produces a hash_map instead of a larger array_map.⁴

The information here on implementations and running times mainly comes from An In-Depth Look at Clojure Collections.

Laziness

Many of the functions provided by Mori return what is called a lazy sequence. Being a sequence this is like a list and can be transformed using functions like map, filter, and reduce. What makes a sequence lazy is that it is not actually computed right away. Evaluation is deferred until some non-lazy function accesses one or more elements of the transformed sequence. At that point Mori computes and memoizes transformations.

The results of a lazy evaluation are cached. If the same sequence is forced again the map function will not be called a second time:

Mori runs just enough deferred computation to get whatever result is needed. It is often not necessary to compute an entire lazy sequence:

In the above case there is an intermediate lazy sequence that theoretically contains five values: the results of doubling values in the original set. But only the first two values in that sequence are needed. The other three are never computed.

Laziness means that it is possible to create infinite sequences without needing unlimited memory or time:

If you try this out in a REPL, such as node, be aware that when an expression is entered a JavaScript REPL will usually try to print the value of that expression, which has the effect of forcing evaluation of lazy sequences. If you enter a lazy sequence you will end up in an infinite loop:

The solution to this is to be careful to assign infinite sequences in var statements. That prevents the REPL from trying to print the sequence:

Powers of two are actually a terrible example of a lazy sequence: any element in that sequence could be calculated more quickly using Math.pow(). It just happens that powers of two are simple to demonstrate.

Algorithms that really do benefit from infinite sequences are those where computation of any element requires references to earlier values in the sequence. A good example is computing Fibonacci numbers.

This implementation uses the iterate function, which takes a function and an initial value. It creates an infinite sequence by repeatedly applying the given function. The given starting value is [0, 1], and each invocation of the given function combines the second value in the previous pair with the sum of the values in the previous pair; so the resulting sequence is: ([0, 1] [1, 1] [1, 2] [2, 3] [3, 5] ...). The map function is applied to that, taking the first value from each pair.

Using this sequence allows us to ask the questions:

A lazy sequence might also contain lines from a large file or chunks of data flowing into a network server. At the time of this writing I was not able to write a program that traversed a long sequence in constant space. But I have verified that this is possible in JavaScript. I may find a solution and post an update later.

Efficiency

In procedural code running a sequence through multiple operations that apply to every element would result in multiple iterations of the entire sequence. Because Mori operates lazily it can potentially collect transformations for each element and apply them in a single pass:

If applying map to a collection twice resulted in two iterations we would expect to see:

The fact that the first pass and second pass are interleaved suggests that Mori collects transformations and applies all transformations to a value at once. This is the advantage of lazy evaluation: it encourages writing code in a way that makes most logical sense rather than thinking about performance. You can write what are logically many iterations over a collection and the library will rearrange computations to minimize the actual work that is done.

You might be wondering how Clojure handles polymorphism, since the convention is to use functions instead of methods. Clojure has a feature called protocols that permit multiple implementations for functions depending on the type of a given argument. Elsewhere in the functional world, Haskell and Scala provide a similar, yet more powerful feature, called type classes.↩
When conj is used on a list it prepends elements (like cons) because prepending is much cheaper than inserting at other possible positions. Given a vector conj appends values. Appending is often desired, and appending to a vector is just as efficient as inserting at any other position. conj works on sets and maps too - but in those cases the idea of insertion position is not usually meaningful.↩
It does look like ECMAScript 6 will add a Map implementation and a WeakMap to the language spec, both of which will take arbitrary objects as keys (only non-primitives in the WeakMap case). But those implementations will not be immutable!↩
http://clojure.org/data_structures#Data Structures-ArrayMaps ↩

Functional Reactive Programming in JavaScript

Wed, 22 May 2013 00:00:00 GMT

I had a great time at NodePDX last week. There were many talks packed into a short span of time and I saw many exciting ideas presented. One topic that seemed particularly useful to me was Chris Meiklejohn's talk on Functional Reactive Programming (FRP).

I have talked and written about how useful promises are. See Promise Pipelines in JavaScript. Promises are useful when you want to represent the outcome of an action or a value that will be available at some future time. FRP is similar except that it deals with streams of reoccurring events and dynamic values.

Here is an example of using FRP to subscribe to changes to a text input. This creates an event stream that could be used for a typeahead search feature:

This creates an event stream from all keyup and change events on the given input. The stream is transformed into a stream of strings matching the value of the input when each event occurs. Then that stream is filtered so that subscribers to inputs will only receive events if the value of the input has a length greater than two.

Streams can be assigned to variables, shared, and used as inputs to create more specific streams. In the example above inputs is used to create two more streams: one that limits the stream so that events are emitted at most every 500 ms and another that takes the throttled stream and drops duplicate values that appear consecutively. So when the final stream, distinct, is consumed later it is guaranteed that events 1) will be non-empty strings with length greater than two, 2) will not occur too frequently, and 3) will not include duplicates.

That stream can be fed through a service via ajax calls to show a live list of results:

Here suggestions is a new stream that has been transformed from strings to search results using the searchWikipedia function. All of jQuery's ajax methods return promises and Bacon.fromPromise() turns a promise into an event stream.

The flatMapLatest transformer builds a new stream from an existing stream and a stream factory - and it only emits events from the last stream created. This means that if the user types slowly and a lot of ajax requests are made responses to all but the last request will be disregarded.

The suggestions stream is ultimately used by calling its onValue method. That adds a subscriber that runs code for every event that makes it all the way through the stream. The result is a list of search results that is updated live as the user types.

There are some other tricks available. It is possible to bind data from an event stream to a DOM element:

This creates a new stream that is pared down to just the query used to produce each set of results. Whenever a result set is rendered the corresponding query will also be output as the text content of the '#query' element. The new stream is converted to a property to make this work. A property is a value that varies over time. The main practical distinction between a property and an event stream is that a property always has a value. In other words a property is continuous while an event stream is discrete. This example provides '--' as the initial value for the new property.

Notice that property binding as shown here is more general than some data binding frameworks in that the destination is not limited to DOM elements and the source is not limited to model instances. This example passes values to the text method of the given jQuery object. It is possible to push data to any method on any object.

Streams can be combined, split, piped, and generally manipulated in all kinds of ways. Properties can be bound, sampled, combined, transformed, or whatever.

I put this code up on JSFiddle so you can try it out and play with it: http://jsfiddle.net/hallettj/SqrNT/

There are several FRP implementations out there. Two that seem to be prominent are Bacon.js and RxJS. The examples above are code from the RxJS documentation that I rewrote with Bacon. That gave me an opportunity to learn a bit about both libraries and to see how they approach the same problem. The original RxJS code is here.

With FRP it is possible to describe complicated processes in a clean, declarative way. FRP is also a natural way to avoid certain classes of race conditions. When I wrote the initial version of the sample code above it worked perfectly on the first try. In my view that is a sign of a very well-designed library.

If you are interested in further reading I suggest the series of tutorials from the author of Bacon. And there is a great deal of information on the RxJS and Bacon Github pages, including documentation and more examples.

Monkey patching document.write()

Tue, 04 Sep 2012 00:00:00 GMT

This is one of the crazier workarounds that I have implemented. I was working on a web page that embeds third-party widgets. The widgets are drawn in the page document - they do not get their own frames. And sometimes the widgets are redrawn after page load.

We had a problem with one widget invoking document.write(). In case you are not familiar with it, if that method is called while the page is rendering it inserts content into the DOM immediately after the script tag in which the call is made. But if document.write() is called after page rendering is complete it erases the entire DOM. When this widget was redrawn after page load it would kill the whole page.

The workaround we went with was to disable document.write() after page load by replacing it with a wrapper that checks whether the jQuery ready event has fired.

The new implementation checks the value of jQuery.isReady and delegates to the original document.write() implementation if the page is not finished rendering yet. Otherwise it does nothing other than to output a warning message.

Disabling document.write() means that the problematic widget will not be fully functional if it is redrawn after page load. It happens that in the case of this app that is ok. The redrawn widget is only used as a preview when editing widget layouts.

A particular problem came up with IE compatibility. I wanted to use the apply method that is implemented by all functions in JavaScript to invoke the original document.write() implementation, like this:

But in older versions of Internet Explorer, document.write() is not really a function. There are a lot of examples in IE of native API methods and properties that do not behave like regular JavaScript values. For example if you pass too many arguments to a DOM API method in old IE you will get an exception. Normal JavaScript functions just silently ignore extra arguments. If you look at the value of typeof document.write the result is not "function". What is particularly problematic in this case is that document.write does not implement call or apply.

Fortunately I found that the Function prototype does implement both call and apply and furthermore you can borrow those methods to use on function-like values like document.write. call and apply are themselves real function values - so call and apply both implement call and apply.

In the workaround above I applied apply to document.write by taking the Function.prototype.apply value and using its call method. So this expression,

is equivalent to this one,

Except that the first version works in IE7.

If you find this difficult to follow, you are not alone.

We have had this workaround in our code for a couple of years now. So far it is working nicely.

Promise Pipelines in JavaScript

Tue, 31 Jul 2012 00:00:00 GMT

Promises, also know as deferreds or futures, are a wonderful abstraction for manipulating asynchronous actions. Dojo has had Deferreds for some time. jQuery introduced its own Deferreds in version 1.5 based on the CommonJS Promises/A specification. I'm going to show you some recipes for working with jQuery Deferreds. Use these techniques to turn callback-based spaghetti code into elegant declarative code.

The basics of jQuery Deferreds

A Deferred is an object that represents some future outcome. Eventually it will either resolve with one or more values if that outcome was successful; or it will fail with one or more values if the outcome was not successful. You can get at those resolved or failed values by adding callbacks to the Deferred.

In jQuery's terms a promise is a read-only view of a deferred.

Here is a simple example of creating and then resolving a promise:

Callbacks can be added to a deferred or a promise using the .then() method. The first callback is called on success, the second on failure:

For more information see the jQuery Deferred documentation.

Note that if you are using a version of jQuery prior to 1.8 you will have to use .pipe() instead of .then(). That goes for all references to .then() in this article.

Sequential operations

Actions, such as HTTP requests, need to be sequential if input to one action depends on the output of another; or if you just want to make sure that actions are performed in a particular order.

Consider a scenario where you have a post id and you want to display information about the author of that post. Your web services don't support embedding author information in a post resource. So you will have to download data on the post, get the author id, and then make another request to get data for the author. To start with you will want functions for downloading a post and a user:

In jQuery 1.5 and later all ajax methods return a promise that, on a successful request, resolves with the data in the response, the response status, and the XHR object representing the request.

The .then() method produces a new promise that transforms the resolved value of its input. I used .then() here just because using $.when() is simpler if each promise resolves to a single value. We will get back to that in parallel operations. Since only one argument is provided to .then() in these cases the new promises will have the same error values as the originals if an error occurs.

The result is that getUser() returns a promise that should resolve to data representing the user profile for a given id. And getPost() works the same way for posts and post ids.

Now, to fetch that author information:

When authorForPost() is called it returns a new promise that resolves with author information after both the post and author requests complete successfully. This is a straightforward way to get the job done. Though it does not implement error handling; and it could be more DRY. More on that in a bit.

Parallel operations

Let's say that you want to fetch two user profiles to display side-by-side. Using the getUser() function from the previous section:

The requests for userA and userB's profiles will be made in parallel so that you can get the results back as quickly as possible. This function uses $.when() to synchronize the promises for each profile so that getTwoUsers() returns one promise that resolves with the data for both profiles when both responses come back. If either request fails, the promise that getTwoUsers() returns will fail with information about the first failed request.

You might use getTwoUsers() like this:

The getTwoUsers() promise resolves with two values, one for each profile.

We now have several well-defined functions that operate on asynchronous actions. Isn't this nicer than the big mess of nested callbacks one might otherwise see?

I mentioned above that using $.when() is simpler when each of its input promises resolves to a single value. That is because if an input promise resolves to multiple values then the corresponding value in the new promise that $.when() creates will be an array instead of a single value.

Performing an arbitrary number of actions in parallel is similar:

This code fetches any number of posts in parallel. I used apply to pass the post promises to $.when() as though they are each a separate argument. The resulting promise resolves with a separate value for each post. It would be nicer if it resolved with an array of posts as one value. The use of .then() here takes those post values and transforms them into an array.

Combining sequential and parallel operations

Let's take the previous examples to their logical conclusion by creating a function that, given two post ids, will download information about the authors of each post to display them side-by-side. No problem!

From the perspective of a function that calls authorForPost(), it does not matter that two sequential requests are made. Because authorForPost() returns a promise that represents the eventual result of both requests, that detail is encapsulated.

Generalizing sequential operations

There are a couple of problems with the implementation of authorForPost() as presented above. We had to create a deferred by hand, which should not be necessary. And the promise that is returned does not fail if any of the requests involved fail.

These issues are not present in the parallel examples because $.when() does a nice job of generalizing synchronizing multiple promises. What we need is a function that does a similar job of generalizing flattening nested promises. Meet flatMap:

This function takes a promise and a callback that returns another promise. When the first promise resolves, $.flatMap() invokes the callback with the resolved values as arguments, which produces a new promise. When that new promise resolves, the promise that $.flatMap() returns also resolves with the same values. On top of that, $.flatMap() forwards errors to the promise that it returns. If either the input promise or the promise returned by the callback fails then the promise that $.flatMap() returns will fail with the same values.

Using $.flatMap() it is possible to write a function like authorForPost() a bit more succinctly:

By using $.flatMap() you also get error handling for free. If the request to fetch a post fails or the request to fetch the post's author fails the promise that this version of authorForPost() returns will also fail with the appropriate failure values.

Another potential problem is that authorForPost() does not give you access to any of the information on the posts that it downloads. You can combine $.flatMap() and .then() to create a slightly different function that exposes both the post and the author:

The promise that postWithAuthor() returns resolves to a post object with an added author property containing author information.

It turns out that .then() leads a double life. If the return value of its callback is a promise, .then() behaves exactly like $.flatMap()! This is the sort of thing that only a dynamic language like JavaScript can do. So if you want to skip the custom function, you could write postWithAuthor() like this:

Other uses for promises

The examples above focus on HTTP requests. But promises can be used in any kind of asynchronous code. They even come in handy in synchronous code from time to time.

Here is an example of a promise used to represent the outcome of a series of user interactions:

I suggest considering using promises anywhere you would otherwise pass a callback as an argument.

Conclusion

The promise transformations .then(), $.when(), and $.flatMap() work together to build promise pipelines. Using these functions you can define arbitrary parallel and sequential operations with nice declarative code. Furthermore, small promise pipelines can be encapsulated in helper functions which can be composed to form longer pipelines. This promotes reusability and maintainability in your code.

Use .then() to transform individual promises.

Use $.when() to synchronize parallel operations.

Use $.flatMap() or .then() to create chains of sequential operations.

Mix and match as desired.

I would like to thank Ryan Munro for coming up with the "pipeline" analogy.

Update 2012-08-01: .pipe() was added in jQuery 1.6. And it turns out that it behaves like $.flatMap() when its callback returns a promise. In jQuery 1.8 .then() will be updated to behave exactly like .pipe(), and .pipe() will be deprecated. So there is actually no need to add a custom method - you can just use .pipe() or .then() instead of $.flatMap().

Update 2013-01-30: jQuery 1.8 has been released, so I replaced references to .pipe() with .then(). I also included a more prominent explanation that .then() can do the same thing that $.flatMap() does.

Promises and Category theory

Good news! If you are able to follow the examples in this post then you have a working understanding of Monads. Specifically, $.flatMap() is a monad transformation, .then() with one argument is a functor transformation, and $.when() is almost a monoid transformation.

Monads, monoids, and functors are concepts from category theory that can be applied to functional programming. Really they are just generalizations of this idea of creating pipelines to transform values.

I bring this up because category theory can be useful, but is difficult to explain. My hope is that seeing examples of category theory in action will help programmers to get a feel for the patterns involved.

For more information on category theory in programming I recommend a series of blog posts titled Monads are Elephants. If you have read that and want to go further, I found the the book Learn You a Haskell for Great Good! to be very informative. And as a bonus it teaches you Haskell.

Those who are already into category theory will note that $.flatMap() could also be defined in terms of .then() and a $.join() function:

Except that this won't actually work because .then() will join the inner and outer promises before the result is passed to $.join().

Installing a custom ROM on the Transformer Prime: A start-to-finish guide

Sat, 12 May 2012 00:00:00 GMT

This guide provides step-by-step instructions for installing the Virtuous Prime community ROM on your Asus Transformer Prime TF201 tablet. This guide will be useful to you if you do not have root access to your tablet.

Be aware that following the instructions here will void your warranty and will wipe all of the data on your tablet. There is also a danger that you might brick your tablet. Proceed at your own risk.

So, why would you want to install a custom ROM on your tablet? In my case I wanted to gain root access, which allows one to do all sorts of nifty things. Community-made ROMS are also often customized to make the Android experience more pleasant for power users. And choosing your own ROM means that you are no longer dependent on the company that sold you your device to distribute firmware updates in a timely fashion. But if you are reading this then you probably already know why you want to install a custom ROM

so let's get on to the next step.

This guide specifically covers installing Virtuous Prime, which is based on the official Asus firmware. If you like the features that Asus provides, like the ability to switch between performance profiles and to toggle IPS+ mode then this is probably the ROM for you. Virtuous also adds some features like root access, the ability to overclock the processors to 1.6 GHz, and so on. Note to the Virtuous ROM devs: it is really awesome to have you all putting in the effort to make the Android experience better for everybody. It is especially amazing that you give your ROM away for free. You are virtuous people indeed! That said, these folks do accept donations.

If you would rather get a vanilla Ice Cream Sandwich experience then you might check out AOKP.

If you just want root access and you do not want to install a custom ROM then there is a simpler procedure that you can follow using SparkyRoot. The catch is that SparkyRoot does not work in firmware versions v9.4.2.21 or later. Part of the reason that I went for a custom ROM is that I upgraded the firmware on my Prime as soon as I got it - so I missed my shot at using SparkyRoot. Don't be like me: plan ahead!

If you have the newest firmware version it is possible to downgrade in order to use SparkyRoot. I chose to install a custom ROM instead because it seemed to me to be a safer option. Be aware that if you follow the directions here to install a custom ROM you will not be able to use the downgrade procedure in that link.

In brief, here are the steps that we are going to follow:

Unlock the bootloader using the official Asus tool.
Install ClockworkMod Recovery.
Install the Virtuous Prime ROM, using ClockworkMod.

Step 1: Unlock the bootloader

I am not completely sure that this step is necessary. I did not try installing ClockworkMod Recovery before unlocking. But even if it is not necessary, I imagine that there may come a time when I am glad to have an unlocked bootloader. You can try skipping this step; at worst nothing will happen.

The unlocking tool is provided by Asus. As you will see, Asus makes it very clear that using the unlock tool will void your warranty. But on the upside it will not wipe your data or anything like that. The only noticeable change will be that every time you boot up the tablet there will be a message in the upper-left corner of the screen that says, "The device is UnLocked". I assume that is there so that customer service representatives can see that they are not supposed to help you.

Download the unlock tool directly onto your tablet from the TF201 support section of the Asus website. Select "Android" as the OS and grab the "Unlock Device App" from the "Utilities" section. The file that you get is an apk that you will install as an app.

If you have not done so already, you will have to enable unknown software sources in your tablet settings. Go to Settings > Security > Device Administration and check the box that says "Unknown Sources".

Use your file manager to find the downloaded unlock tool. It is probably in /sdcard/Download/UnLock_Device_App_V6.apk. Tap it to install the app.

You will be prompted to confirm your Google account by entering your Google password. If you are using two-factor authentication on your Google account you will have to set up an application-specific password for this. You can revoke that password after your tablet is unlocked.

Next you will have to agree to a license and acknowledge a warning. Again, Asus wants to make it really clear that you are about to void your warranty.

After you agree to everything your tablet will reboot and your bootloader is now unlocked.

Step 2: Install ClockworkMod Recovery

ClockworkMod Recovery is a custom recovery image. The Transformer Prime comes with a recovery image provided by Asus that lets you do stuff like manually install OS updates. But the Asus recovery image will only let you install updates that are digitally signed by Asus. To install a community-made ROM you need a recovery mode that will let you install unsigned ROMs. That is what ClockworkMod does. It also provides extra features, like the ability to back up and restore your whole OS.

Installing ClockworkMod will probably void your warranty - in case you somehow got to this point with an intact warranty. There is also some danger that you could brick your tablet. Proceed at your own risk.

These instructions are adapted from a guide on TransformerPrimeRoot.com. I'm going to give you the slightly more complicated version that involves downloading files directly from ClockworkMod and from Google; and I will provide tips on what to do if the fastboot tool is not able to find your tablet. I personally appreciate it when I can get files from sources that I know I can trust. But if you are not convinced that is necessary then feel free to check out the TransformerPrimeRoot.com guide.

For this step you will need a computer.

Download the latest ClockworkMod Recovery image from ClockworkMod's downloads page. As of this writing the latest version for the Transformer Prime is 5.8.2.0. According to TransformerPrimeRoot.com earlier versions can put your device into a reboot loop (which you can recover from but it is scary when it happens, I imagine).

The Touch Recovery image should also work. It comes with a nicer touch-based UI. But the guides that I have read call for the non-touch version, so that is what I went with.

You will also need the fastboot tool from the Android SDK to install the recovery image. Download the SDK from Google and extract it. Run the android executable in the tools/ directory to launch the SDK package manager and use that tool to install the Android SDK Platform-tools: check the box next to "Android SDK Platform-tools" and click "Install packages...". After a few minutes that will add a new executable, fastboot, in the platform-tools directory in the Android SDK package. You will use the fastboot program to send commands to your tablet while the tablet is in fastboot mode.

Android devices have two boot modes apart from the normal boot-into-the-OS option: recovery mode and fastboot. Fastboot is a low-level mode that is used for flashing firmware. You can use fastboot to replace the recovery mode image - which is what we will be doing to install ClockworkMod. And you can use recovery mode to install a new OS. Likewise, if your OS breaks you can fix it from recovery mode and if recovery mode breaks you may be able to fix it from fastboot. What happens if fastboot breaks? Try not to let that happen! The Android devs have not yet provided us with an extra-fast-boot.

If you are on Windows then you will have to install a USB driver before proceeding. Linux and Mac users do not need any special drivers.

Make sure that your battery is charged to at least 50%. Bad things will happen if your battery dies while you are flashing a recovery image.

Boot your tablet into fastboot by holding down the power and volume-down buttons. The tablet will power off and reboot. Wait until you see several lines of white text in the upper-left corner of the screen, then let go of the power and volume buttons. Then wait for five seconds and you will see the fastboot options.

Press volume-down to highlight the USB icon and then press volume-up to select it. You have ten seconds to do this - after that the tablet will cold-boot Android instead. If that happens, don't worry. Just start over by holding down the power and volume-down buttons.

Plug the tablet into your computer using the USB cable that came with your tablet.

On your computer open a terminal. Assuming that you have the ClockworkMod Recovery image and the extracted Android SDK in the same downloads folder, cd to that folder. Run this fastboot command to make sure that your computer is talking to your tablet:

The -i 0x0b05 part tells fastboot which USB device to communicate with. The number 0b05 is the Asus vendor id for USB interfaces. If you want to double-check that vendor id you can use the lsusb command on Linux. On my machine the output includes a line that looks like this:

The vendor id is the portion of the ID before the colon.

Anyway, if the fastboot command that you ran worked you should see output that looks like this:

On the other hand, if you see a message that says < waiting for device >, and you wait a minute or two and nothing happens, then hit Ctrl-c to cancel. If you are in Linux you can fix this problem by creating a udev rule. Create a new file, /etc/udev/rules.d/99-android.rules and add this line to it:

But make sure to replace "yourusername" with your user name. Then restart udev with this command:

Now try the fastboot command again.

Ok, is fastboot talking to your tablet? Now for the next step: flashing ClockworkMod.

I recommend checking the md5 checksum on the ClockworkMod Recovery image to make sure that it has not been corrupted. On Linux you can use this command to do that:

It appears that ClockworkMod does not list md5 checksums on its downloads page. But here is the checksum that I got for version 5.8.2.0:

You should proceed only if the checksums match.

Run this command - and again make sure that the paths match the locations of the fastboot and ClockworkMod Recovery image files:

If all goes well you should see some output like this:

Now you have ClockworkMod Recovery installed.

Step 3: Install the Virtuous Prime ROM

Following the instructions here will wipe everything on your tablet. And you will void your warranty - again. Proceed at your own risk.

There are instructions on RootzWiki for installing Virtuous Prime. I'm going to give you the same instructions but with a bit more detail. But I recommend reading the information on RootzWiki too as there is a lot of useful background there.

Download the latest version of Virtuous Prime directly onto your tablet. As of this writing that is Virtuous Prime 9.4.2.21 v1, which is based on the Transformer Prime v9.4.2.21 firmware from Asus. You will get a zip file - don't unzip it!

Next to the download link there will be an MD5 checksum. We will refer back to that in a moment.

Use your file manager to move the zip file, virtuous_prime_s_9.4.2.21_v1.zip from /sdcard/Download/ to /sdcard/. I think that this step is superfluous; but it makes me feel better.

This is optional, but highly recommended: install the free MD5 Checker app. You can use this app to check the MD5 checksum of the file that you downloaded to make sure that it was not corrupted. Open MD5 Checker, click on the button labelled "Load File 1", browse to the Virtuous Prime zip file, and wait for MD5 Checker to compute the file's checksum. Make sure that the checksum that you see in MD5 Checker is the same as the one from the Virtuous Prime downloads page. If the checksums do not match then do not proceed! Download the file again and check the checksum again.

Shut down your tablet. But make sure that your battery is charged to at least 50% first. And make sure that the USB cable is unplugged.

Boot into recovery mode by holding both the power and volume-down buttons. As with fastboot, when you see several lines of white text in the upper-left corner of the screen let go of both buttons. But this time press volume-up right away. If you do not press volume-up within five seconds then the tablet will go into fastboot. If that happens then just start over by holding the power and volume-down buttons again.

After a moment you should see the ClockworkMod menu. You can use the volume-up and volume-down buttons to highlight the different menu options and the power button to select the option that you want.

Make a backup of your current ROM. Select "backup and restore", then "backup". This will create a timestamped backup directory on your tablet under /sdcard/clockwork/backup/.

There is a lot of information on backing up and restoring your tablet here.

The backup process will take a few minutes. When it is done you will see the ClockworkMod menu again.

Select "wipe data/factory reset". According to RootzWiki this step is optional, but is highly recommended. You will have to complete an elaborate confirmation step to start the wipe.

Once all of your data has been wiped, select "install zip from sdcard", then "choose zip from sdcard". Browse to the Virtuous Prime ROM and select it. And confirm that you are really sure about this.

You will be taken through a guided install process in which you will be prompted to choose between Typical, Complete, or Minimal install modes. There is a list of the differences between the three modes on RootzWiki.

When the installer is finished your tablet will reboot and you are done! Congratulations! Enjoy your new ROM!

More Resources

There is some useful information collected on TransformerPrimeRoot.com. Much of the information in my guide comes from that site.

If the worst should happen and your tablet becomes a brick, you may still be able to recover. Check out the recovery guide on XDA-Developers.

Update 2012-05-19

After about a week of use, the Virtuous Prime ROM is working very well. It does everything that the Asus firmware did and more. But I did run into some problems that I wanted to report along with some workarounds.

The Hulu Plus app does not work for me anymore. When I try to play a video I get this message:

Streaming Unavailable [91]
Sorry, we are unable to stream this video. Please check your Internet connection, ensure you have the latest official update for your device, and try again.

The Hulu app did work for me before I unlocked my tablet. There are reports that unlocking the bootloader is what causes this problem. This may not have anything to do with Virtuous Prime directly.

A helpful community member created a modified version of the Hulu Plus app that does work. From the first post in that thread you can download and install the Landscape Mod HuluPlus.apk package. You will need to enable "Unknown Sources" to install the package. Before you install this version I suggest wiping the data of the original Hulu app and uninstalling it.

The home view in the app is distorted; but the queue view works fine. This mod is based on a phone version of the original Hulu app rather than a tablet version. Video quality seems a bit low - I don't know whether that is due to my connection or to the app. With those caveats, the modified app works great for me.

Netflix works perfectly. Hooray for Netflix!

The Amazon Kindle app crashes when I try to open a book. I have tried wiping the app's data and reinstalling multiple times. I have also tried different books. And I have confirmed that I am running version 3.5.1.1, which is the latest version available in the Play Store right now.

I managed to fix the Kindle app by following instructions to fix Machinarium, which simply involves installing a missing font.

An alternative workaround is to use the Cloud Reader. Note that the Cloud Reader will work in Chrome for Android Beta, but will refuse to run in the default Android browser. You will not be able to install the extension that allows Cloud Reader to work offline since the mobile version of Chrome does not support extensions yet. So you will have to be connected to the internet to use the Cloud Reader.

Someone on the XDA Developers forum asked whether the game Machinarium would install under Virtuous Prime. I tested this and found that the game will install - but it crashes on startup. I did not test this game before installing Virtuous Prime. All other games that I have tested have worked fine.

It turns out that the problem with Machinarium is that there is a missing font in Virtuous Prime. Specifically the Droid Sans and Droid Sans Bold fonts are missing. There is a fix reported in the XDA Developers forum.

So with some digging it seems that I did not encounter any problems that I could not fix. Also, having root access to my tablet is excellent.

Cookies are bad for you: Improving web application security

Fri, 26 Aug 2011 00:00:00 GMT

Most web applications today use browser cookies to keep a user logged in while she is using the application. Cookies are a decades-old device and they do not stand up well to security threats that have emerged on the modern web. In particular, cookies are vulnerable to cross-site request forgery. Web applications can by made more secure by using OAuth for session authentication.

This post is based on a talk that I gave at Open Source Bridge this year. The slides for that talk are available here.

When a user logs into a web application the application server sets a cookie value that is picked up by the user's browser. The browser includes the same cookie value in every request sent to the same host until the cookie expires. When the application server receives a request it can check whether the cookies attached to it contain a value that identifies a specific user. If such a cookie value exists then the server can consider the request to be authenticated.

There are many types of attacks that can be performed against a web application. Three that specifically target authentication between the browser and the server are man-in-the-middle (MITM), cross-site request forgery (CSRF), and cross-site scripting (XSS). Plain cookie authentication is vulnerable to all three.

In a MITM attack the attacker is in a position to watch traffic that passes between some user's browser and an application server. If that traffic is not encrypted the attacker could steal private information. One of the most dangerous things that an attacker can do in this position is to hijack the user's session by reading cookie data from an HTTP request and including that cookie data in the attacker's own requests to the same server. This is a form of privilege escalation attack. Using this technique an attacker can convince an application server that the attacker is actually the user who originally submitted a given cookie. Thus the attacker gains access to all of the user's protected resources.

Last year a Firefox extension called Firesheep made some waves when it was released. The purpose of Firesheep was to raise awareness of the danger of MITM attacks. Most web applications, at that time and today, use cookie authentication without an encrypted connection between browser and server. Firesheep makes it easy to spy on anybody who is using well known applications like Facebook and Twitter on a public network. With the click of a button you can perform a MITM attack yourself, steal someone's cookies, and gain access to that person's Facebook account.

MITM attacks can be effectively blocked by using HTTPS to encrypt any traffic that contains sensitive information or authentication credentials. When using HTTPS you will almost certainly want to set the "secure" flag on any cookies used for authentication. That flag prevents the browser from transmitting cookies over an unencrypted connection.

More and more web applications are offering HTTPS - often as on opt-in setting. Any web site that requires a login should offer HTTPS - and ideally it should be enabled by default.

XSS attacks involve an attacker pushing malicious JavaScript code into a web application. When another user visits a page with that malicious code in it the user's browser will execute the code. The browser has no way of telling the difference between legitimate and malicious code. Injected code is another mechanism that an attacker can use for session hijacking: by default cookies stored by the browser can be read by JavaScript code. The injected code can read a user's cookies and transmit those cookies to the attacker. Just like in the MITM scenario, the attacker can use those cookies to disguise herself as the hapless user.

There are other ways that XSS be used can be used to mess with a user - but session hijacking is probably the most dangerous. Session hijacking via XSS can be prevented by setting an "httpOnly" flag on cookies that are used for authentication. The browser will not allow JavaScript code to read or write any cookie that is flagged with "httpOnly"; but those cookies will still be transmitted in request headers.

CSRF attacks authentication indirectly. A malicious web page can trick a browser into making cross-domain requests to another web site. If a user visiting the malicious page is already logged in to that web site then the malicious page can access the site resources as though it were logged in as the unsuspecting user. For example, if a malicious page can trick the browser into making POST requests to a microblogging site it can post updates with spam links that appear to have been written by the victim.

If you use Facebook you might have encountered attacks like this yourself. You see a post on a friend's wall with a button that says "Don't click the button!" When you click on it you are taken to another site and the same message ends up posted on your wall.

This works because the browser automatically sends cookies set on a given domain with every request made to that domain, regardless of where those requests originated. The browser has no way of knowing that the requests initiated by the malicious page are made without the user's knowledge.

The malicious page could create a cross-domain request by including an image with a src attribute pointing to a URL on the site that it is trying to hack into. The URL does not have to be an image - the browser will make a GET request to that URL and will discard the response when it determines that the response is not image data. If that GET request produced any side-effects, like posting a microblogging update, then the malicious page has successfully performed an attack.

To make a cross-domain POST request the malicious site might include a hidden HTML form with an action attribute pointing at the site to be hacked. The malicious page can use JavaScript to submit the form without any interaction from the user. This is another case where the attacker cannot read the response that comes back but can trigger some action in the user's account.

In some cases CSRF attacks can also be used to read data. Because JSON is a strict subset of JavaScript, HTTP responses that contain JSON data can be loaded into script tags and executed. In some browsers a malicious page can override the Object and Array constructors to capture data from the JSON response as it is executed so that it can be sent to an attacker.

The biggest problem with CSRF is that cookies provide absolutely no defense against this type of attack. If you are using cookie authentication you must also employ additional measures to protect against CSRF. The most basic precaution that you can take is to make sure that your application never performs any side-effects in response to GET requests.

To protect against cross-domain POST requests a commonly used option is to use an anti-forgery token that must be submitted with every POST, PUT, or DELETE request. The token is generally injected into the HTML code for forms in such a way that malicious code on another site does not have any way to access it.

JSON responses can be protected by pre-pending the JSON response with some code that makes the response non-executable. For example, you could place a JavaScript loop at the beginning of the response that never terminates. Or you could put in a statement that throws an exception. Putting the whole JSON response inside of a comment block also works. The only way for a browser to read JSON data that has been obfuscated like this is to fetch the resource using XHR and to remove the extra code before parsing the actual JSON data. XHR is limited by the same-origin policy; so a malicious page cannot make a cross-site XHR request.

Such multi-layered approaches to CSRF defense work but are a pain to implement. I know from experience that the stateful nature of anti-forgery tokens make them a constant source of bugs in Ajax-driven applications where users might submit several requests to the server without ever loading a new page. It is too easy for the client and server to get out of sync and to disagree about which anti-forgery tokens are fresh. And great care must be taken to include the anti-forgery feature in every form and Ajax call in an application or a security hole appears.

JSON obfuscation is easier to apply to every JSON response as a blanket policy thanks to server-side filters and client-side hooks, such as those in jQuery's Ajax stack. But then you are not really serving JSON - you are serving a JSON-like type with a proprietary wrapper. I find that I spend a lot of time instructing people on the existence of obfuscation, explaining why it is there, and explaining how to set up hooks to remove it on the client side.

By combining the "secure" and "httpOnly" flags and using HTTPS you can make your application authentication proof against MITM attacks and against some XSS attacks. But there is nothing that will make cookie authentication resistant to CSRF attacks. The only way to protect against CSRF is to apply additional security measures. Often multiple measures are required to combat different possible CSRF vectors. And those measures are not always simple or transparent.

In my opinion CSRF stifles innovation on the web. Because cross-domain requests cannot be trusted, even if they appear to be authenticated, web applications have to be thoroughly locked down to reject any cross-origin traffic. There is a relatively new specification for making cross-origin XHR requests called Cross-Origin Resource Sharing (CORS). This specification could allow for exciting new mashups involving rich JavaScript applications and public APIs. Most modern browsers support CORS too - including Internet Explorer 8. But CORS is rarely used because it opens up a big hole that could be exploited by CSRF. Existing CSRF countermeasures rely on limiting XHR requests to the same-origin policy. For most web developers the risk is too great to justify experimenting with new technology.

The way to make the web a safer place is to switch to authentication mechanisms that provide strong protection against CSRF at the most basic level. The key is to choose a mechanism that is controlled by the web application, not the browser. The web browser has no way of distinguishing legitimate requests from forged ones - it will attach cookies to both. On the other hand, application code can be written to be smarter.

There are many authentication schemes that would work well. I lean toward OAuth 2.0. OAuth has some nice advantages: it is standardized; there are numerous server implementations; and the simplest form of the OAuth 2.0 draft specification is pretty easy to implement.

In a traditional OAuth setup there are three parties: the authorization server / resource server, the client and the resource owner. Through a series of steps the resource owner, typically a user working through a web browser, submits a password to the authorization server and the authorization server issues an access token to the client. You can read more about the OAuth protocol flow on the OAuth 2.0 web site.

When applying OAuth to session authentication the picture becomes simpler: the browser acts as both the resource owner and the client; so some of the indirection of three-legged OAuth can be skipped. Instead, a web application can use a protocol flow that the OAuth 2.0 specification calls Resource Owner Password Credentials in which the user enters her password into a login form, the password is submitted to the application server directly, and the server responds to that request with an access token. You can think of this as "two-legged" OAuth.

In both the two- and three-legged flows requests are signed by adding an "Authorization" header with one of two possible formats. In the bearer scheme the authorization header value is just the access token that was given to the client. For example:

The HMAC scheme is a bit more complicated: in that case the client is given an access token id in addition to the token itself and the authorization header includes the token id and an HMAC-signed hash of the request URL, the request method, a nonce, and possibly a nested hash of the request body. The OAuth access token is used as the key in the HMAC algorithm.

The advantage of the HMAC scheme is that it can provide some protection against MITM attacks even if signed requests are not encrypted with HTTPS.

I propose a design in which the browser submits credentials from a login form to the server via XHR, gets an access token back, and uses that access token to sign subsequent requests. Full page requests and form posts are difficult to sign with OAuth - hyperlinks and form tags do not provide a way to specify an "Authorization" header. So OAuth-signed requests would probably be limited to XHR. The browser could store the OAuth access token in a persistent client-side store to give the user an experience that is indistinguishable from a cookie-based application - but that is more secure.

It is entirely possible for JavaScript code running in a web browser to sign requests with HMAC. There are pure JavaScript implementations available of many cryptographic functions, including SHA-1 and SHA-256, which are the hash functions that are used for OAuth HMAC signing. However, if your application uses HTTPS to protect every request then the simpler bearer scheme is entirely sufficient.

In this design form posts would be eliminated. Instead form data would be serialized in JavaScript and submitted using Ajax. That way all requests that produce side-effects would be channeled through OAuth-signed XHR. I am not suggesting eliminating form tags though - form tags are an essential tool for semantic markup and for accessibility. I recommend that JavaScript be used to intercept form "submit" events.

There are a couple of options for dealing with full page loads. One possibility is to not require any authentication for requests for HTML pages and to design your application so that HTML responses do not include any protected information. Such an application would serve pages as skeletons, with empty areas that to be filled in with dynamic and protected content after page load using Ajax. The dynamic responses could be HTML fragments that are protected by OAuth, or they could be JSON responses that are rendered as HTML using client-side templates.

Facebook uses a process like this which they call BigPipe. Facebook's rationale for BigPipe is actually performance, not security. In my opinion the BigPipe approach gives a best-of-both-worlds blend of performance and security. Plus, it lets you put caching headers on full page responses, even in apps with lots of dynamic content.

A downside of BigPipe is that content that is loaded via Ajax generally cannot be indexed by search engines. Google's recently published specification for making Ajax applications crawlable may provide a solution to that problem. Or you might choose to use the BigPipe approach everywhere in your application except for publicly accessible pieces of content.

Another way to handle full page loads would be to continue using cookie authentication for HTML resources. HTML responses are less vulnerable to CSRF snooping than JSON because HTML is not executable in script tags. In this case you should still require OAuth signing on requests for JSON resources and on any requests that could produce side-effects. But allowing cookie authentication on non-side-effect-producing GET requests for HTML resources should be safe.

Using JavaScript to manage access tokens rather than relying on a built-in browser function makes CSRF attacks impractical. A malicious third-party site can no longer rely on browsers to automatically attach authentication credentials to requests that it triggers. Client-side storage implementations are generally protected by the same origin policy - so only code running in your application can retrieve an access token and produce an authenticated request. And if you combine OAuth with HTTPS then you are also protected against MITM attacks.

A drawback is that you lose the XSS protection that the "httpOnly" cookie flag provides with cookie authentication. An application that uses OAuth will have to use other methods to block XSS. But in my opinion there are better options for dealing with XSS than there are for dealing with CSRF. By consistently sanitizing user-generated content you can effectively block XSS at the presentation layer of your application. That would be necessary anyway, since "httpOnly" only prevents XSS-based privilege escalation attacks and by itself does not prevent other XSS shenanigans.

To track a session using OAuth applications will need some way to store access tokens for the duration of a user's session. There are various ways to do that:

In the simplest case you can store the token in memory by assigning it to a JavaScript variable. This might be useful in a single page application. The user will have to log in again if she goes to another page or opens your app in a new window.
localStorage can be used to store a token so that is persistent even if the user closes and re-opens the browser. Data stored in localStorage is available to all windows on the same domain. You will probably want to include a hook to clear local storage when the user logs out of your application.
sessionStorage works like localStorage, except that data is only accessible from the same window that stored it and the whole store for a given window is wiped when the user closes that window. So the user does not have to log in again if she goes to another page; but she does have to log in again if she opens your app in a new window.
sessionStorage can be a more secure option than localStorage - especially on a shared or a public computer. If you decide to use a storage option that does not expire automatically when the browser is closed I suggest including a "remember me" checkbox in your login form and using sessionStorage instead when the user does not check that box.
Although I have been arguing that cookies are not the best option for authentication, storing an access token in a cookie works just fine. The key is that the server should not consider the cookie to be sufficient for authentication. Instead it should require that the access token be copied from the cookie value into an OAuth header.
For the cookie option to be secure you should set the "secure" flag so that it is not transmitted over a connection that could be read via a MITM attack. You should not set the "httpOnly" flag because the cookie needs to be accessible from JavaScript.
A nice advantage of the cookie option is that users have been trained that they can delete cookies to reset a session. On the other hand, most users do not know about localStorage and most browsers do not provide an obvious way to clear localStorage. So the cookie option is likely to conform best to user expectations. Cookies can also be configured to expire when the browser is closed or to persist for a long period of time.
Other options include IndexedDB, which is a more sophisticated store that is similar to localStorage, Flash cookies, and userData in IE.

There is a good summary of client-side storage implementations and how to use them on Dive Into HTML5. Or if you want a pre-built solution that avoids most cross-browser headaches you can use PersistJS or a similar tool.

Web applications that rely on cookie authentication can often be designed to degrade gracefully, so that if JavaScript is disabled or is not available the application will still work. With OAuth that is not possible. I can imagine this being a major objection to ditching cookie authentication. Some people prefer to disable JavaScript for security or for privacy reasons. Many of the more basic mobile and text-only web browsers do not support JavaScript. And in the past screen readers have not handled JavaScript-driven web apps well.

In my opinion the requirement that JavaScript be enabled to use an application is generally worthwhile. Mobile browsers that do support JavaScript are rapidly pushing out those that do not. Text-only browsers will have to start supporting JavaScript sooner or later to keep up. The people who designed your web browser took great care to ensure that your security and privacy are protected even when JavaScript is enabled. Screen readers are much better than they used to be at making JavaScript-driven web sites accessible.

You should consider your target audience, your application requirements, and your security needs and decide for yourself whether dropping the noscript option is the right choice for your application.

No security protocol is bulletproof. Do lots of research and use common sense whenever you are working on an application that needs to be secure.

Image credits:

The OAuth logo by Chris Messina is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.

Other images used in diagrams are from the Open Clip Art Library and are in the public domain.

How Mobile Safari emulates mouse events

Thu, 28 Jul 2011 00:00:00 GMT

When you are adapting web apps to touchscreen devices particular challenges come up around events like mouseover and mouseout. Touchscreen devices like the iPad do not have a cursor, so the user cannot exactly move the mouse over an HTML element. However, Mobile Safari, the web browser that comes with the iPhone and iPad, has a fallback for websites that require hovering or cursor movement.

Usually when you tap on an element on a link or other clickable element Mobile Safari translates that into a regular click event. The browser also produces some touch events that do not exist in a lot of browsers. But from the perspective of a web page that was not designed with a touchscreen in mind, what you get is a plain click. More specifically, the browser fires mousedown, mouseup, and click in that order. But if a clickable element also does something on mouseover then tapping on that element will trigger a mouseover event instead of a click. Tapping on the same element again will produce a click event. A random example of a page that exhibits this behavior is the schedule page from the Open Source Bridge website. Try tapping on session titles and see what happens.

Mobile Safari will only produce mouse events when the user taps on a clickable element, like a link. You can make an element clickable by adding an onClick event handler to it, even if that handler does nothing. On tap Mobile Safari fires the events mouseover, mousemove, mousedown, mouseup, and click in that order - with some caveats which are explained below. Those events all fire together after the user lifts her finger. You might expect the mousedown event to fire as soon as the user presses her finger to the screen - but it does not. When the user taps on another clickable element the browser fires a mouseout event on the first element in addition to firing the aforementioned events on the new element.

So how do we get to the behavior where one tap emulates mouseover and a second tap emulates click? It turns out that after any mouseover event handlers run Safari checks the DOM for changes and if the content has changed it skips the mousedown, mouseup, and click events. So these events do not fire. When the user taps on the same element again the mouseover event does not fire again, so the browser goes ahead with the other events.

The mousemove event behaves in a similar way: if the DOM has changed after any mousemove handlers are finished running then Mobile Safari skips the remaining events.

Diagram from Apple's documentation demonstrating how the browser determines which mouse events to fire.

Safari does not accept just any change to a DOM element as a "content change" though. Through testing I discovered that adding a regular element to the DOM or showing a previously hidden element in a mouseover handler would prevent the click event from firing. But removing an element, hiding an element, or changing the content of a text node do not prevent the click event. I also tried adding class names to elements - which Safari also did not treat as a "content change". As far as I can tell only adding or showing an element will cause the mousedown, mouseup, and click events to be skipped.

I created some fiddles on jsfiddle.net to test Mobile Safari behavior. For your investigative pleasure I have an example of a mouseover handler that adds elements to the DOM, another that shows a hidden element, and a third that makes no changes to the DOM at all.

CouchDB Notes

Sun, 13 Sep 2009 00:00:00 GMT

Recently I gave a talk at Portland Ruby Brigade meeting on CouchDB, a document-oriented database. I thought I would share my notes from that talk. In some respects this was a followup to an earlier talk that Igal Koshevoy gave comparing various post-relational databases. Igal also wrote some additional notes on my talk.

In summary, some of the distinguishing features of CouchDB are:

Schema-less data store stores documents containing arbitrary JSON data.
Incrementally updated map-reduce views provide fast access to data, support powerful data processing, and eliminate lookup penalties for data in large or deeply nested documents.
Map-reduce views - which are again, incrementally updated - provide fast access to aggregate data, such as sums or averages of document attributes.
Schema-less design means no schema migrations are ever required. And new map-reduce views can be installed with no downtime.
"Crash-only" design protects data integrity in almost every crash scenario. No recovery process is required when rebooting a crashed database server.
Lock-free design means that read requests never have to wait for other read or write requests to finish. Writes are only serialized at the point where data is actually written to the disk.
Integrated, robust master-master replication with automatic conflict handling
MVCC, or "optimistic locking", prevents data loss from multiple writes to the same document from different sources.
RESTful interface makes it easy to integrate CouchDB with any environment that speaks HTTP.
Documents can contain binary attachments. Attachment support combined with the HTTP interface means that CouchDB can serve HTML, JavaScript, images, and anything else required to host a web application directly from the database.

More detailed information on all of the above points can be found in CouchDB's technical overview.

Some of the downsides:

Writes and single-document lookups are slower than other databases due to HTTP overhead and frequent disk access.
CouchDB optimizes CPU and RAM use by using lots of disk space. The same data set will take up a lot more space in CouchDB than in other database systems.
You must create map-reduce views in advance for any queries you want to run. SQL users are used to processing data at query time; but this is not allowed by the CouchDB design (assuming you are not using temporary views in production, which you should not do.)
There is a serious learning curve when learning to think in terms of map-reduce views.
Map-reduce views, though very powerful, are not as flexible as SQL queries. There may be cases where it is necessary to push data processing to an asynchronous job or to the client.
CouchDB is a young project and its API is undergoing rapid changes.
Documentation can be sparse - especially when very new features are involved.

Ruby Interfaces to CouchDB

I also talked about some of the high-level interfaces to CouchDB that are available for Ruby. As ActiveRecord did for SQL, the idea behind these libraries is to abstract away as much of the database behavior as possible without sacrificing the powerful features that CouchDB provides. The term "ORM" does not quite apply to CouchDB because it is not relational. The term I am using for the time being is "object-document mapping". The code examples I showed are all available in a gist.

Sadly I don't think I can say that any of these libraries are production ready as is. If you use one expect to write some patches as you go. That said I think that all three show some exciting potential. And they all provide a better starting point for your CouchDB project than writing your own ODM or using a low-level interface. I plan to submit a few patches to CouchPotato as I get to know it better. With some more help I imagine we can turn one or more of these interfaces into a nicely polished library.

The winner in my mind is CouchPotato. The philosophy behind CouchPotato is to do things differently than ActiveRecord does. Though it does borrow features from ActiveRecord, for example dirty attribute tracking, life cycle callbacks, and validations. The biggest innovation in CouchPotato in my opinion is the extensible system for defining views. As with the other libraries, support for declaring simple views is built in:

But similar shortcuts for more sophisticated types of views can be added by creating new view classes and passing a :type option to the view declaration method. For example, it might be possible to declare views like this:

My runner-up is CouchRest. CouchRest is a widely used low-level interface to CouchDB. But it also includes a high-level interface called CouchRest::ExtendedDocument. A neat feature of this library is that you can declare a different database to use for each model. It also supports declaring simple views with dynamic methods for querying those views:

CouchFoo is another strong contender. The goal of CouchFoo is to provide an API that is as close to ActiveRecord's as possible. The project may even be porting a large amount of ActiveRecord code for this purpose. The intention is to make migrating to CouchDB as painless as possible.

An interesting feature is that CouchFoo will create views automatically on demand. For example this query will automatically create a view that indexes Post documents by title:

On-demand view creation could be convenient. But my instinct is that it is a bad thing to do. Adding a new view to a large database comes with an expensive initial build step. It seems to me that that type of thing should only be done explicitly.

Testimonials

I mentioned a case where one team found that they got great performance improvements by pushing some data reporting tasks from a SQL database to CouchDB. That story was written up in a series of blog posts. An explanation of why this team went with CouchDB is presented in part 3 of that series.

There is a list on the CouchDB Wiki of sites that are currently using CouchDB in production. A couple of notable examples not on the list that have used CouchDB are the BBC and possibly Meebo.

Of note for Ubuntu fans: Canonical is working on a project called Desktop Couch which will be installed by default in Karmic Koala. The idea is to create a portable store for stuff like browser bookmarks, contacts, music playlists and ratings, and so on. There are already plugins to allow Firefox and Evolution to store bookmarks and contact data in CouchDB. Desktop Couch will provide CouchDB databases for every user to store this information, and will include tools for "pairing" computers on the same network. Desktop Couch will use CouchDB's built-in replication features to automatically replicate data between paired computers; so you will get the same bookmarks and contacts on all of your computers. This will all integrate with Ubuntu One too. Desktop Couch will be able to replicate your data to Ubuntu One's servers so that you can replicate that data back down to computers on a different network.

Exploring Further

The best resource for learning more about CouchDB is probably CouchDB: The Definitive Guide. This is a book that J. Chris Anderson, Jan Lehnardt, and Noah Slater are writing for O'Reilly. It is still a work in progress, but the latest draft is available online.

For API reference my source is the CouchDB Wiki.

Finally, as the CouchDB developers will tell you, the most up-to-date reference for the latest CouchDB features is the included test suite. This is a set of tests written in JavaScript that you can run from CouchDB's web interface to verify that your build of the latest SVN checkout is working correctly. These tests are run externally and access the database server via its HTTP API; so you don't have to know any nitty gritty Erlang stuff to understand what the tests are doing. When any changes to the API are introduced this test suite is updated accordingly.

How to install Haskell "Batteries Included" Platform on Ubuntu Jaunty

Thu, 02 Jul 2009 00:00:00 GMT

Just for kicks I thought I would take another shot at some Haskell programming. To get all of the common libraries and the automated package installer, cabal, I set up the Haskell Platform. Here is how I did it.

Ubuntu Jaunty includes a package for the Haskell compiler, ghc, at version 6.8. The Haskell Platform installer will roll its eyes at you if you try to proceed with this version of ghc. So the first step is to install ghc 6.10.

Paste these lines into /etc/apt/sources.list.d/haskell.list:

To get the key to verify packages from that PPA, run this optional command:

Then update your package list and install Haskell:

The Haskell Platform website does not list a package for Ubuntu yet. So download the source installer.

Before you run the installer you will want to install the necessary build dependencies:

Please leave a comment if you discover that I have left out any dependencies.

To perform the final installation step you will also need to have checkinstall installed:

Unpack the source installer wherever you like:

Finally cd into the installer directory and run the generic installation procedure:

This will build and install a deb package called haskell-platform. If you ever want to remove Haskell Platform just uninstall that package.

If all of the above worked, you should be good to go. You compile Haskell code with ghc. You can run an interactive read-eval-print-loop with ghci. And you can install Haskell libraries with cabal.

Database Queries the CouchDB Way

Tue, 30 Jun 2009 00:00:00 GMT

CouchDB is a document-oriented database. It has no rows or tables. Instead CouchDB is a collection of JSON documents. It uses a map-reduce pattern to index data. Queries in CouchDB pull data from what are essentially stored procedures called views. A view is made up of a map function and optionally a reduce function. Ninety percent of the time all you need is the map function, so I will focus on map-only views here.

A map function is a JavaScript function that takes a single document as an argument and emits any number of key/value pairs. Both the key and the value can be any JSON value you choose. The map function is run on every document in the database individually and the emitted key/value pairs are used to construct an index of your data.

A Simple Example

Imagine you have a database with user records and you want a view of those records using the last name of each user as keys.

The above map function will produce and index something like the one below. Because doc is used as a value for each entry the entire content of each JSON document will be accessible as the indexed values.

Notice that the map function checks each document for a last_name attribute before emitting a key/value pair. There may be documents in the database that are not user records. By performing that check the view excludes any non-user-record documents from the resulting index.

If you include the couch.js library in a web page you can create client-side queries to pull data from CouchDB over HTTP. The function below will fetch all of the user records from your database by returning the value of each key/value pair emitted by the view above.

Map functions operate on one document at a time and cannot access data from other documents. The advantage of this is that the functions can process data in any order and can run on any piece of a data set independent of the rest of the set. CouchDB builds static indexes from the output of view map functions so that queries against those views will run quickly. When any documents change CouchDB can incrementally rebuild the indexes for just those documents without having to rebuild entire indexes from scratch.

The CouchDB design gets you great performance on large data sets. But it means that you cannot pass dynamic parameters to your map function when you run a query. You cannot ask for it to emit only user records with a given last name unless you want to maintain a special view for that particular last name. In most cases it is not practical to build separate views for every query that you might want to run someday. So what you can do is to run a query against the general purpose view above and request only key/value pairs that match a particular key.

This client code creates a query that requests data from the last_names view with a key parameter. CouchDB will only send back key/value pairs with keys that match the key parameter. In this case the query will return all user records with last names matching the last_name argument.

In a more advanced case you may want to take the first few letters of a last name and look up user records that match.

Data returned by a query is always sorted by key. In the case where the keys are strings the sorting will be lexicographic. The startkey and endkey parameters restrict the results of the query to key/value pairs that fall in the given range according to CouchDB's sort order.

When the above function is given the query string "Ha", it will fetch documents with keys sorted after "Ha" lexicographically, e.g. "Hallett", "Hathaway", and "Hazzold". The endkey is created by appending "\u9999" to the startkey. "\u9999" is a unicode character that comes after most other characters in lexicographic order and that is unlikely to appear in a data set. Effectively the string "Ha\u9999" sorts after every other string that begins with "Ha", but before any string that starts with "Hb".

Note that CouchDB uses the Unicode Collation Algorithm to sort strings. Sorting comes out differently than you may be used to if your are accustomed to the ASCII way. UCA collation is intended to mimic the order of strings you would see in a dictionary. For example, two strings that differ only in case will appear together in sorted order. The lower-case string will appear immediately before the upper-case string. So if you force your startkey to lower-case and your endkey to upper-case you will get case-insensitive matches. See the CouchDB wiki for more details.

Search by Keyword

Indexing text content can be a hard problem because you need a large index if you want to query data by arbitrary keywords or substrings. Fortunately CouchDB excels at managing large indexes.

Here is a map function that creates an index of all the words that appear in the text field of every document in a database.

The code splits text on word boundaries stripping out non-alphanumeric characters. It runs the resulting list of tokens through a unique filter so that only one index key is produced for each word in the text of a single document.

This is an example of a view that emits more than one key/value pair for each document. The values in each pair are the same for the same document. But a different key is recorded for each word in the document's text attribute. The index that would be created by this view for a document with the text "Live long and prosper" is below.

To look up documents that contain a given keyword you just need to create a query with that keyword as the key parameter. But what if you want to look for documents that contain a list of keywords? You could create index keys for every combination of words in each document. But that index would grow exponentially and might get to be unreasonably large. A better way might be to pick one keyword to perform your query and then to use client code to select the documents that match all of the keywords out of the results returned by CouchDB.

When you want more dynamic data processing than you can get with pure-CouchDB views, some client-side processing can make up the difference nicely. From a perspective of deploying applications leveraging your users' CPU cycles for data processing can really help getting your application to scale.

There is another approach to full text search documented on the CouchDB wiki.

Search by Substring

Maybe keyword search isn't good enough. Maybe you need to be able to search for occurrences of any substring in a data set.

For each document, this map function emits a key/value pair for every possible substring that runs to the end of the document's text. The idea is that the beginning of any substring in the data set can be lined up with the beginning of one of these keys. Here is an example of the index created for a document with the text "Hello, world!":

The substring that you want to search for can begin at any character within some document's text. It may or may not run until the end of that document's text field. We have an index with the beginning characters for every possible substring. So we can create a query that asks for a key range that encompasses both the given substring and a substring that runs all the way to the end of the document text.

CouchDB does not just sort data when responding to queries. In its internal representation indexes are always sorted by key. So a query with a key range targets a contiguous block of data from the database. Because of that CouchDB can serve up a key range very efficiently.

Just as with the keyword search, if you want to search for documents that match a list of substrings then get the matches for one of the substrings from CouchDB and use client code to select results that contain all of the rest of the given substrings.

If the text of your documents tends to be very long you can avoid a lot of really long keys by limiting the lengths of substring keys in your view. In that case make sure to truncate the key parameters in your queries so that they are not longer than the index keys.

Appendix: Helper Function Definitions

Some of the functions that I used in the examples above are not built into JavaScript or couch.js. Here are definitions of those functions for reference.

Given an attribute name, dot returns a function that when given an object returns the value of the specified attribute. This function is used in examples above to get the value attributes of rows fetched by CouchDB queries.

map is an Array method that given a function that takes a single argument returns a new array formed by applying the given function to every element of the original array in turn.

reduce is an Array method that given an initial value and a function that takes two arguments returns a single value produced by applying the given function to every element of the array in turn with the value from the previous function invocation and returning the last result.

select is an Array method that given a test function returns a new array made up of only elements in the original array that pass the test.

uniq is an Array method that returns a new array with any duplicate values from the original array removed.

How to use RSpec to describe a Sinatra application

Tue, 29 Jul 2008 00:00:00 GMT

This information was written a long time ago and has become pretty outdated.

Sinatra is a fun little web application microframework. Recently I started working on an application using Sinatra - and since I am working on good programming habits, before I dove into any coding I sat down to work out how to write specs for a Sinatra application.

Sinatra comes bundled with support for test/spec: a spec framework that builds on top of Rail's own Test::Unit to provide support for writing specs. Which is a really neat idea. But I have been using RSpec for my other work, and I wanted to continue doing so.

It turns out that RSpec takes a little bit of manual work to get going with Sinatra. I read a helpful article on gittr.com that pointed me in the right direction. The article advised me to add these lines to my spec files:

The first line loads your application; the second line loads RSpec; the third loads an RSpec-Test::Unit compatibility layer; and the fourth loads Sinatra's test helpers, which are written for Test::Unit.

Contrary to Sinatra's instructions for writing tests, you want to avoid loading 'sinatra/test/spec', which defines Sinatra's helper methods for test/spec, because that would load test/spec itself which conflicts with RSpec.

Those instructions mostly worked. I could write and run specs. But I had trouble with matchers. For example, this example:

Would give an error message like this:

Which I'm sure you can imagine is pretty annoying.

It was easy enough to identify 'sinatra/test/unit' as the root of the problem. When I removed that line RSpec's matchers worked fine; but then I didn't get Sinatra's test helpers, which make spec-writing much easier. So that wasn't a great solution either.

Examining Sinatra's code, I found that all 'sinatra/test/unit' does is to load 'sinatra/test/methods' - the actual helper methods - and mixes them into Test::Unit::TestCase. So I bypassed 'sinatra/test/unit' by copying and adapting some code from it to make the top of my spec file look like this:

Since that is a fair amount of setup, I moved all of it into a separate file called spec_helper.rb, which I loaded into my actual spec files. Because I am weird enough to write a Sinatra application that is split into multiple files and multiple spec files.

Anyway, now my specs run just as they should, with Sinatra's helpers and everything:

The next challenge was to write specs for Sinatra helpers. Although Sinatra actions and helpers generally appear in the outermost namespace, the DSL methods that define them actually bind the helpers to Sinatra::EventContext. You can't invoke helper methods directly from an example context; you have to create an instance of Sinatra::EventContext and send the method call to that - much the same way Rails instantiates a subclass of ActionController::Base to handle a controller action. Here is the code you will want in your example groups:

A body= method has to be defined on the response mock to prevent an error. But it doesn't have to actually do anything. With that setup code in place, you can do this:

and write something like this in your application:

And now you have a reasonably complete speccing setup. There are still a couple of issues though. For one thing, the spec helpers are missing a much needed assigns[] method. As it stands there is no good way to pry apart the behavior of an action if there is no convenient method call to stub. You can only define the parameters that are passed to it, and read response. On the upside, this does help to enforce good behavior-driven development.

The other issue is more of an annoyance than a serious problem. It seems that somewhere in all of this there are one or two method_missing definitions that bounce calls back and forth. If call a method that is not defined, you generally won't get an "undefined method" error, you will get a "stack level too deep" error instead. This is particularly unhelpful because it does not tell you what class received the undefined method, or which method is undefined. So a little extra manual stack tracing is required when this happens.

International Phonetic Alphabet

Tue, 02 Oct 2007 00:00:00 GMT

In last week's post I provided phonetic transcriptions of some example words using the International Phonetic Alphabet, or IPA for short. I thought it would be helpful to follow that up with some information about what the IPA is, and how to read it. And as a bonus, after learning about IPA transcription you will be able to better read pronunciation guides on Wikipedia.

You have probably seen many phonetic transcriptions before - especially as pronunciation guides in dictionaries. In dictionaries it is common to see a transcription convention that uses English spelling conventions to represent sounds. For example, the word "elucidate" might be transcribed as (ee-LOO-suh-date). That system is handy because it is immediately familiar to anyone who has experience reading stuff in English. But it has drawbacks too. There are a few main problems that are especially important for linguists; there are lots of linguists all over the world who are used to languages with entirely different spelling conventions. For example, the sound in English that is represented as "y" - the consonant, not the vowel - is written in Icelandic as "j". There are also a lot of languages with sounds that just don't exist in English. Linguists need to be able to transcribe those sounds; but since they don't exist in English there is no spelling convention to represent them. In fact there is no one language with enough spelling conventions to represent every sound in every language in the world. And finally, English spelling is ambiguous, as is the spelling of almost any language. That is already demonstrated by the need to add a note to distinguish "y" the consonant from "y" the vowel or any of the other vowel sounds represented by "y".

To solve all these problems, a group of linguistics developed the International Phonetic Alphabet in the late nineteenth century. The first standardized version was created in 1888. But it has been revised somewhat since then. The purpose of IPA is to provide a standard set of symbols that are used to represent sounds so that the same symbols always represent the sounds, even to people from different language backgrounds. Using the IPA it is theoretically possible to represent every sound in every language in the world. Though occasionally a new language is discovered with a new sound that we didn't know anything about before, which has to be quickly added to the IPA.

IPA was originally developed by French and British linguists, so it uses characters derived from the Latin alphabet and symbols are matched to sounds in a ways that are generally familiar to Europeans. But even in the Western world people have different ideas about how to spell things, so the IPA adopts some different phonetic conventions from different languages. For example, I mentioned earlier that the sound represented by "y" in English is spelled "j" in, among others languages, Icelandic; and in fact the symbol for that sound in IPA is [j]. Here is the complete IPA chart in its most recent revision. And by the way: in IPA, the word "elucidate" is transcribed [i'lu.sə.deɪt].

The sound an IPA symbol represents is described by the place of articulation of the sound, an the manner of articulation. When you voice a consonant you, you press your tongue against the roof of your mouth, or in some cases you press your lips together or put the tip of your tongue between your teeth. The exact spot on where you press your tongue is the place of articulation. For example, when you say [t] you press the tip of your tongue against a spot towards the front of your mouth called the alveolar ridge; whereas when you say [k] you press the back of your tongue against your soft palate, which linguists call the velum. [t] and [k] have the same manner of articulation - they are both plosives, which means that they are articulated by completely stopping air from flowing out of the mouth for a moment. But they have different places of articulation. Early on in a linguist's career he learns all about the structures of the mouth, throat, and nose to learn how each can be used to produce various sounds. I will explain some of the details in future articles; in the meantime it would probably be easiest to look up IPA symbols using this IPA chart on Wikipedia, which is specially designed for English speakers and provides example words to illustrate each sound.

Wikipedia provides the transcription for the English "r" as [ɹ]. This is the most technically correct transcription, since in IPA [r] represents a rolled "r", which is heard in Spanish. In linguistics speak, [r] is a trill and [ɹ] is a liquid. However, English doesn't have a trill, so people transcribing English often use [r] instead of [ɹ] because the former is more familiar - and easier to type. It is considered acceptable to make substitutions like that in cases where readers are unlikely to be confused by the switch. So when I transcribe an English word using [r] instead of [ɹ] I'm not actually trying to make you practice pronouncing trills.

As an aside, the rolled "r" in French is not the same sound as the rolled "r" in Spanish. The French "r" is transcribed [ʀ]. Both sounds are trills, so they share the same manner of articulation; but they have different places of articulation. [ɹ] is alveolar, meaning that to pronounce it the tip of the tongue is positioned on the alveolar ridge, in the same spot it is placed when pronouncing [t]. The sound is produced by vibrating the tongue against the roof of the mouth, which is what makes it a trill. To pronounce [ʀ], the back of the tongue is placed against the uvula and vibrates against that.

To make the alphabet more flexible, IPA employs a number of diacritics. Diacritics are small marks placed above or below a character. In IPA they are used to describe characteristics of a sound that differ slightly from the sound usually represented by a bare character. Last week I talked about consonants that are used as syllable nuclei, which are called syllabic consonants. Syllabicity is considered a phonological feature, so it is indicated with a diacritic. For example, the syllabic version of [n] is [n̩].

Another example of a diacritic is ʰ, which is used to indicate aspiration. Did you know that the letter "p" in English is used to represent two different sounds? The "p" sounds in "pull" and "stop" are slightly different. You can tell if you put your hand in front of your mouth, less than an inch away, and say each word. You will feel a puff of air on your hand when you say the "p" in "pull"; there is a puff when you say "stop" too, but it is not nearly as strong. A sound that makes that strong puff of air is said to be aspirated, and is marked with a diacritic that looks like a superscripted "h". So the IPA representation for an aspirated "p" is /pʰ/ and an unaspirated "p" is simply /p/.

Even though they are technically different sounds, English speakers treat /p/ and /pʰ/ as being the same. So they are written with the same letter. And in IPA they are usually both transcribed as [p] for simplicity. But on occasion it is important to have the ability to distinguish the two. The difference between sounds that are exactly the same and sounds that are treated as the same by language speakers is a very important consideration in linguistics - and it has to do with the sudden switch from square brackets to slashes surrounding the transcriptions above. I will talk about that in a future article too.

Anatomy of a Syllable

Mon, 24 Sep 2007 00:00:00 GMT

The syllable is a constant feature in every spoken language in the world. Each language has its own rules about what kinds of syllables are allowed, and what kinds aren't - but the general structure is the same everywhere.

A syllable has as many as three parts: onset, nucleus, and coda. The onset and the coda are consonants, or consonant clusters, that appear at the beginning and the end of the syllable respectively. The nucleus forms the the core of the syllable; it is most often a vowel, or a combination of vowels - but there are many exceptions to that. If you examine enough languages you can find almost every kind phone used as a syllable nucleus. In the word "far", [f] is the syllable onset, [a] is the nucleus, and [r] the coda. If a coda is present in a syllable, the nucleus and the coda form a single unit called a rhyme; otherwise the nucleus makes up the rhyme by itself. Looking at "far" again, [ar] forms the rhyme. A syllable does not necessarily have to have an onset or a coda - depending on the language - but a nucleus is always present.

Even in English, syllable nuclei are not restricted to vowels. For example, in the monosyllabic word, "hmm", the syllable nucleus is [ṃ], which is a consonant but is more specifically a nasal. Another nasal, [n], can be seen as a syllable nucleus in the word "isn't", which is transcribed into the International Phonetic Alphabet (IPA) as [ɪzzṇt]. In this case there are two syllables, and [ṇ] forms the nucleus of the second syllable.

The small dot underneath the characters ṇ and ṃ indicates that the sound represented is a syllabic consonant, which is any consonant that forms a syllable nucleus. Vowels are not marked with the same diacritic because they are always considered to be syllabic. Usually syllabicity is marked in IPA with a vertical stroke under the character instead of a dot; but in this case a dot was as close as I could get.

Anyone following closely may notice that it is difficult to decide exactly how to divide "isn't" into syllables. It seems like it should be either ['ɪz.ṇt], or ['ɪ.zṇt], where the dot (.) represents a syllable boundary and the apostrophe (') represents the beginning of a stressed syllable; but it is tricky to figure out whether the [z] is the coda of the first syllable or the onset of the second syllable. That is because in the [z] in "isn't" demonstrates ambisyllabicity, a common feature in English that I will write about in a future article. The short explanation is that [z] is both an onset and a coda, which is why I transcribed the word with two [z]'s. Anyway, in both analyses [ṇ] forms the nucleus of the second syllable, so we don't need to worry about the placement of [z] for now.

There are also arguably cases where a liquid forms the nucleus of a syllable in English. The liquids in English are [l] and [r]. Consider the word "sir" and the second syllable of "apple". If it is the case that the liquids in these syllables are the nuclei, then the words would be transcribed as [sṛ] and [æppḷ] respectively. However, not everybody agrees with that interpretation, and so these words are often analyzed as [sər] and [æppəl]. That would make the syllable nuclei [ə], which is a vowel. And by the way, the [p] in "apple" is also ambisyllabic.

The reason vowels are so likely to form syllable nuclei is that they are the most sonorous sounds available in spoken language. It is a general rule that syllable nuclei are formed by sonorous phones. Liquids and nasals are right behind vowels in that they are more sonorous than any other type of consonant. But it is possible to find syllable nuclei in other languages that are considerably less sonorant than any of the above. For example, there is at least one Berber language that contains syllables like [tḳt], where the nucleus of the syllable is [ḳ].

The onset and coda are always made up of consonants. Many languages have strict rules about how many consonants can appear, and what sort of order they appear in. English is relatively lax in this respect, so we can see syllables with several consonants clustered together in both positions. For example, "scrumptious", transcribed as ['skrʌmp.ʃəs], has three distinct consonant phones in the onset and two in the coda of the first syllable. But notice that you would never see a word in English like ['rksʌpm.ʃəs], which would probably be spelled "rksupmtious". Try pronouncing that and see what happens - and remember that it's cheating to make the [r] or the [m] into separate syllables!

Consonants in syllable onsets and codas are also governed by sonority. There is a rule, called the sonority sequencing generalization, that says that the sonority of a syllable peaks at the nucleus and decreases toward either boundary. So the sonority of consonants in the onset is supposed to increase going forward, and the sonority in the coda is supposed to fall of. This is a generalization, so there are exceptions - but if you deviate too much from the rule the result becomes difficult to pronounce. In the made-up word above I reversed the order of the consonants in the onset and coda of the first syllable, thus making the sonority sequence "wrong".

Every sound in a language has a place somewhere in the sonority hierarchy. And every language has its own sonority hierarchy ordering. So for example [star] is easy for English speakers to pronounce, but you don't see a word like [tsar]: [t] is more sonorous than [s] in English. But in Russian it is not uncommon to see a word like [tsar].

Restrictions on what is allowed in a syllable vary from language to language. Not all languages allow as many consonants to be clustered in a syllable onset as English does, while some allow more. Some languages require every syllable to have an onset, while others allow naked nuclei. Syllable codas are especially restricted. For example, in Mandarin Chinese the only syllable codas that are allowed are nasals. There are no languages that forbid onsets, but many languages don't allow syllable codas to appear at all.

For more information, and some neat diagrams, visit What is a syllable? and the Wikipedia entry for "Syllable".

Deixis

Mon, 17 Sep 2007 00:00:00 GMT

When someone says to you, "here" or "now", you probably know what he means. "Here" might the room that you are both sitting in. "Now" would be the span of time you spent sitting together. But if either word were uttered under different circumstances, it could mean something very different. For example, if I called you from the Andes and I used the word, "here", it would mean a mountainside somewhere - possibly thousands of miles away from the aforementioned room. The same word can mean both the room and the mountainside because of deixis.

Deixis is a form of exophora, which is an utterance that is given meaning by the context it is uttered in. Specifically, deixis represents the speech event itself: deictic expressions reference the speaker, the speaker's utterances, the speaker's location, and the time at which the speech event occurs. There are different types of deictic expressions that refer to each particular aspect.

Personal pronouns, such as "I", "you", "he", and "she", are deictic expressions. "I" refers simply to the speaker. The other pronouns are defined by the relation the referenced person has to the speaker in the discourse. As the role of speaker switches from person to person, the context represented by deixis in understood by participants of the discourse to change too.

Location and time are a little more complicated. Whenever someone speaks - or writes, or is quoted, etc. - there is an implicit deictic center that is formed in the minds of the speaker and any listeners. A deictic center is the point in space and time that spatial and temporal deictic expressions refer to. "Here" and "now" are the simplest examples. The verbs "to come" and to "to go" are also spatial deictic expressions: "to come" means motion towards the deictic center, and "to go" means motion away.

Based on this analysis, the phrase "come here" seems redundant at first. But actually the addition of "here" can be important, due to a phenomenon called sympathetic deixis. It is not uncommon, especially in phone conversations, to hear an utterance like, "I will come by later". For the speaker to move toward the deictic center is almost nonsensical when the speaker is the deictic center. But in this case sympathetic deixis causes the deictic center to shift from the speaker's location to the listener's location. So motion towards the deictic center actually translates to motion toward the listener.

Note that the shift caused by sympathetic deixis does not necessarily affect all the aspects of deixis. In the example above the meanings of personal pronouns do not change after the deictic center has shifted; in a similar sentence, "I will come to see you", "I" refers to the speaker, and "you" refers to the listener - as would be expected with or without a shifted deictic center.

An especially fun deictic puzzle is often heard in answering machine messages like, "I'm not here right now". It isn't possible that the deictic center is fixed upon the speaker during this message, because it is not possible for the speaker to not occupy his own location. So there must be sympathetic deixis in effect to shift the deictic center either spatially or temporally. As someone who has been on the receiving end of this message, I expect "here" to mean the location where the message was recorded, and "now" to be the time when I am calling. By that analysis the spatial location of the deictic center remains fixed on the location of the speech event, while the temporal aspect shifts to the listening event via sympathetic deixis. There is another possible analysis where both spatial and temporal sympathetic deictic shifts occur. In that case the spatial shift does not move the location of the deictic center to the listener, but instead moves it to the place where the listener expects it to be: in this case wherever the speaker's phone is. Under either analysis, the answering machine example demonstrates that deictic shifts can be temporal as well as spatial.

There are other forms of deictic expressions. There is a more complete list in the Wikipedia article on deixis.

sitr.us - posts by Jesse Hallett

Nix, NPM, and Dependabot

Updating the Hash

Automation to Help Dependabot

`void` is not a unit type in TypeScript

Choosing a headless CMS

When to use `never` and `unknown` in TypeScript

Types explained using set theory

Automatic Code Formatting for Partially-Staged Files

How I learned to love automatic formatting

I finally set up XMonad to build with Stack!

Checking Types Against the Real World in TypeScript

Type-Driven Development with TypeScript

Correct by construction

Writing your program around types

What is Poodle

Changes I would make to Go

The Good

The Bad

nil

How Rust does it differently

Error-handling boilerplate & lack of compile-time checks unhandled errors

List manipulation is not practical

Third-party libraries are second-class citizens

The Ugly

No tagged unions, limited pattern matching

Dynamic typing

Dynamic dispatch, reinventing the wheel

No first-class tuple

Shortage of high-level parallelism and concurrency features

Conclusion

Flow Cookbook: Flow & React

How it works

A Hacker News client

Flow Cookbook

Recipes

Extras

More resources

Flow Cookbook: Unpacking JSON API data

Refining the model

Advanced features in Flow

Table of Contents

Class<T>

$Diff<A,B>

$Shape<T>

$Record<T>

$Supertype<T>

$Subtype<T>

$Enum<T>

Existential types

Scoped type variables in classes

Type checking React with Flow v0.11

Use ES6 classes

React.Component takes type parameters

Use JSX

General-purpose features

Flow is the JavaScript type checker I have been waiting for

Javascript generators and functional reactive programming

Kinesis Advantage with DSA keycaps

Category Theory proofs in Idris

Theorem proving

Definition of Category

A partial ordering category

A monoid as a category

Category of sets

Functional data structures in JavaScript with Mori

Table of Contents

Functional data structures

Clojure, ClojureScript, and Mori

Installing and running

Examples

vector

higher-order functions

sorted_set_by

hash_map

Apples to apples

Mori pairs well with Bacon

List versus Vector

Equality, ordering, and hashing

hash

`nil`

`Class<T>`

`$Diff<A,B>`

`$Shape<T>`

`$Record<T>`

`$Supertype<T>`

`$Subtype<T>`

`$Enum<T>`

`React.Component` takes type parameters

`vector`

`sorted_set_by`

`hash_map`