Wednesday, March 12, 2014

Directory tiles, incentivisation, and indirection

Note: I have absolutely nothing to do with directory tiles, but they have been on my mind (and of plenty of other peoples), so here are my thoughts. My opinions are not those of my employer, but I am very grateful to be able to voice these opinions.

I agree with the need to diversify our revenue streams over the long run, and I think I agree with the sentiment that we should not 'leave money on the table'. However, some of the discussion around directory tiles makes me uneasy. (I think the worst thing about the whole thing has been how badly the idea was communicated, but that has been pretty well established, so I won't beat that horse any further. Personally, I don't think any revenue from the idea would be significant because, aiui, only new users will see the ads and then at most nine times, which if I were a company, I wouldn't pay for. But I don't know anything about such things and there are plenty of people at Mozilla who DO know about this stuff, so I'll believe it could make money somehow).

My position only makes sense if you assume that advertising is bad per se. I do. I know many people do not, especially in the technology sector. But I think advertising is a bane of modern civilisation - not just on the internet, but in magazines, on billboards, on public transport, in sport; it is poison. It is particularly insidious in that we don't realise we are seeing and being influenced by advertising, in part by design and in part because of its ubiquity. In the rare times I have spent time away from it (the subway in Prague a decade ago, hiking in the mountains) returning to a world full of advertising feels as jarring and unpleasant as it ought to. I would love to live in a world where we paid for websites and software. If I could pay 1/10th of a cent for every page I viewed and if Mozilla could be funded by administering that and taking 1/10th of a percent of it, then I would be very happy indeed. Unfortunately, people on the whole seem to prefer free, and so it is a dream.

The argument I dislike is 'we already send search traffic to Google in exchange for cold, hard cash, and Google in turn makes money by showing these people ads; therefore, showing our users ads directly in the browser is no different or no worse or something'. As a software engineer, I know that indirection is very, very important. It is totally incorrect to treat a value the same way as a pointer to a value, and I believe the analogy holds with monetisation too. It comes down to incentives - money is a very powerful incentive (not the only one, and I trust Mozilla more than pretty much any other organisation to balance other incentives, but it is still an incentive - we each want to keep getting paid to keep doing these awesome jobs we have).

So, with the current system, in order to maximise search traffic and thus income, we might tweak our design to make the search box more prominent or otherwise encourage more users to search via the search box (I believe that this is not quite the case because we do not get paid _per search_, i.e., there is some slack in the system, and I don't think we have ever done something like this or intend to). That is not so bad, I would not feel bad about encouraging people to search the internet - it is kind of an essential task. Now Google (or whoever we might sell search traffic to in the future) is incentivised to show their users more ads, but there is no incentive for us to modify the browser to show the user more ads.

With directory tiles (or any system where we are directly showing ads to users) the above does not hold. The monetary incentive is to show users more ads and more often. And that (in my opinion) makes for a worse user experience.

In summary, when the incentive is indirect, optimising for it does not negatively affect our users. When the incentive is direct, optimising for it does negatively impact our users. And that makes me very uneasy about going down that road.

However, I fear we might have to. We need money to fund our mission for a better web and the current situation may not last forever (maybe it will, and we can all live happily ever after, but I fear everything changes). Fortunately, I trust Mozilla better than anyone to ignore the incentive described above, I just wish we didn't have to ignore it.

Monday, March 10, 2014

Subtyping and coercion in Rust

Subtyping and coercion are two related concepts for enabling polymorphic re-use in programming languages. I want to lay out exactly what they are and how they exist in Rust, and in particular how they relate to variance which exists today, is being implemented, or will be implemented as part of the work on dynamically sized types (DST). My terminology will not exactly fit that used by PL people or Rust people, sorry.

In the general case (i.e., not just Rust) subtyping is a relation on types which says that T is a subtype of U if T is in some sense a more specific type than U. More precisely we might like to say that T and U denote sets of values and the set of values denoted by T is a subset of the set of values denoted by U. That gets complicated when thinking about existential types and so forth if we don't have explicit values for the introduction of such types, and if we do, then I think things get a little circular and not very helpful for thinking about real programming languages.

Thinking of expressions in a language, if an expression has type T, it can be used anywhere we would expect an expression of type U. This is inclusion polymorphism (aka the Liskov substitution principle or strong behavioral subtyping. There are subtle differences between these three terms, but I could only describe them in the most hand-wavy terms, so I won't).

Coercion is an operation on values (or expressions) where a value of type T can be changed in some way to a value of type U. An example is using an integer as a float - this is allowed transparently in many languages, but the compiler must insert code which does the low-level conversion from integer to float. We usually assume (hope?) that conversions due to coercion are cheap.

When actually writing code, subtyping and coercion often look the same. Many programmers do not realise there is even a difference. For example, 'subtyping' between pointer types in C++ with multiple inheritance is technically a coercion because of the pointer adjustment required by the implementation using multiple vtables.

Rust has basically no subtyping. The only subtyping it has is due to contravariance with respect to lifetime variables. I (Niko has done the hard work already) am currently extending this to variance (where safe, along the usual lines) with respect to subtyping. Rust has coercions between structs and traits given by `impl`s (well, between references to such things). It should, soon hopefully, have coercions between sub-traits and eventually, maybe sub-structs. Plus coercions between numeric types, etc., which are less interesting for now.

I would like to further classify subtyping and coercions along some axes. The key difference is that subtyping does not change the underlying value and coercion does (as discussed above). Both subtyping and coercion may be explicit or implicit. I sometimes refer to implicit subtyping as subsumption, but I'm not sure if that is common or correct. In Rust, subtyping is always implicit and coercion is sometimes implicit (trait objects) and sometimes explicit (numeric conversions, i.e., they require `as`. Coercion used to always be explicit until recently).

In Rust, only subtyping is used in the type inference algorithm.

The last axis I have thought of is a bit more hazy and a bit more of an implementation detail than a fundamental. It is that coercion restricts access to the value coerced. If coercion changes a value, it would be unsafe to continue to access the value via the old type. Either coercion must copy a value (i.e., only the new, copied value has the new type), or we must ensure that the old value cannot be accessed whilst the coerced value exists. Rusts linearity rules ensure this.

With DST, coercion becomes much more complicated. In particular we will add covariant coercions which must coerce fields of a struct. That is, they change things deep inside the struct, not just at the surface of a value. In contrast to subtyping, covariant coercion is always safe because we can no longer access the coerced value via its old type. (Thinking about proving safety gave me the insight that coercion actually _changes_ the type of a value, whereas subtyping gives multiple types to a single value (which is not to say that coercion always implies monomorphic types)).

We have talked a little (I think Niko has thought more) about perhaps changing the relationship between subtyping and type inference. Perhaps not all subtyping should be taken into account by the type inference algorithm. And/or perhaps some coercions should be taken account of. I don't really know - I have a hard time visualising how type checking would be affected by these changes.

I feel like I should have a point to make now, but I don't. I just did a lot of thinking to clarify all this in my head, so I thought I should write it down. And who knows? It might be helpful or interesting to someone else too.