Saturday, February 17, 2018

Scala FP: how good an idea now?

Ed Kmett’s reddit comment full of biting commentary on the troubles of attempting functional programming in Scala remains the most concise listing of such problems, and remains mostly up-to-date over four years after it was written. It covers problems from the now famous to the less well known. It’s still a useful guide to what needs to change for Scala to be a great functional programming language, or conversely, why a functional programmer might want to avoid Scala.

But not everything is the same as when it was written. Some things have gotten better. Some can even be eliminated from the list safely. Some haven’t changed at all.

I’d like to go through each of Kmett’s bullet points, one by one, and elaborate on what has happened in the ensuing four years since he posted this comment.


[1:] If you take any two of the random extensions that have been thrown into scala and try to use them together, they typically don't play nice. e.g. Implicits and subtyping don't play nice together.

This hasn’t really changed. Paul Phillips’s age-old “contrarivariance” thread about the specific example Kmett uses here might as well have been written yesterday.

On a positive note, what is good hasn’t really changed, either. The type soundness of new features still cannot be justified merely because you can’t think of any ways programs would go wrong were your idea implemented; you still need positive evidence that your idea preserves soundness. This is more than can be said for, say, TypeScript.

On the other hand, we’ve seen a lot of attempts to “solve” these kinds of feature-compositionality problems by claims like “we don’t want you to write that kind of code in Scala”. New features like AnyVal subclasses are still made with the concerns of ill-typed, imperative programming placed above the concerns of well-typed, functional programming. Proposals like ADT syntax are likely to support only those GADT features deemed interesting for implementing the standard library, rather than what application programs might find useful.

[2:] Type inference works right up until you write anything that needs it. If you go to write any sort of tricky recursive function, you know, where inference would be useful, then it stops working.

Still 100% true.

[3:] Due to type erasure, its easy to refine a type in a case expression / pattern match to get something that is a lie.

I’m not sure why Ed wrote “due to type erasure” here, but the underlying problems are there. This comment came after the introduction of “virtpatmat”, which improved things in a lot of ways, not least with the improved support for GADTs. I’ve noticed some things get better for GADTs in 2.12, too.

But there are numerous unsound things you can do with pattern matching, some accompanied by compiler warnings, some not. Most of these are due to its reliance on Object#equals. Paul Phillips wrote several bug reports a long time ago about these, and one of the major ones is fixed: the type consequences of pattern matching used to think that Object#equals returning true implied that the two values were perfect substitutes for each other. For example, you could use an empty Buffer[A] and an empty Buffer[B] to derive A = B, even when they’re completely incompatible types.

This has been fixed, but the very similar problem with matching constants has not. I suspect that it will never be fixed unless pattern matching’s use of equals is removed entirely.

[4:] Free theorems aren't.

In the base Scala language, nothing has changed here. But we’ve tried to account for this shortcoming with practice. I wrote an article elaborating on the free theorems problem in Scala; surprise surprise, Object#equals makes another villainous appearance. Tony Morris popularized the “Scalazzi safe Scala subset” through his “Parametricity: Types are Documentation” talk, and since then “Scalazzi” has become the shorthand for this style of Scala programming. (If you’ve heard “Scalazzi” before, this is what it’s about: free theorems.) Tools like Wartremover have arisen to mechanically enforce parts of the Scalazzi rules (among other rules), and they’re well worth using.

So the situation in the Scala language hasn’t changed at all. The situation in Scala practice has gotten better, as long as you’re aware of it and compensating in your projects with tools like Wartremover.

Collections and covariant things

[5:] Since you can pass any dictionary anywhere to any implicit you can't rely on the canonicity of anything. If you make a Map or Set using an ordering, you can't be sure you'll get the same ordering back when you come to do a lookup later. This means you can't safely do hedge unions/merges in their containers. It also means that much of scalaz is lying to itself and hoping you'll pass back the same dictionary every time.

I don’t want to cover this in detail, because Ed’s already gone into it in his talk “Typeclasses vs the world”. I’ve also written about Scalaz’s “lying to itself” approach (a fair characterization), and why we think it’s the best possible choice for Scalaz users in Scala as it’s defined today.

You can think of this as the “coherence vs local instances” argument, too, and Ed is describing here how Scala fails as a substrate for the coherence approach. But he’s not saying that, as a result, coherence is the wrong choice. Since we think that, despite the potential for error, coherence is still the best choice for a Scala library, that should tell you what we think about the alternative: that with local instances, the potential for error is still greater.

So for us, the important question is, what has changed in Scala? There’s been a “coherence” proposal, but its purpose is not to force you to define only coherent instances, nor even to detect when you have not; instead, it’s to let you assert to the compiler that you’ve preserved coherence, whether you have or not; if you’re wrong, scalac simply makes wrong decisions, silently.

This would be very useful for performance, and I will embrace it for all typeclasses if implemented. It will make many implicit priority hacks unnecessary. But it wouldn’t address Ed’s concern at all.

[6:] The container types they do have have weird ad hoc overloadings. e.g. Map is treated as an iterable container of pairs, but this means you can't write code that is parametric in the Traversable container type that can do anything sensible. It is one of those solutions that seems like it might be a nice idea unless you've had experience programming with more principled classes like Foldable/Traversable.

The design of the current collections library is the one Kmett was talking about, so nothing has changed in released code. As for the future collections library, known as “collections-strawman”? The situation is the same.

[7:] You wind up with code that looks like all over the place due to CanBuildFrom inference woes.

I’m not sure what Kmett is referring to here, because I’ve been relying on the correct behavior for a long time, that is, without the trailing .toMap. The only thing I can think of would be the function being passed to map returning something implicitly convertible to two-tuple instead of a proper two-tuple, which would require an extra step to force that conversion to be applied.

Monads and higher kinds

[8:] Monads have to pay for an extra map at the end of any comprehension, because of the way the for { } sugar works.

This hasn’t changed at all, but is worth some elaboration. This behavior makes it so you can’t write “tail-recursive” monadic functions in the obvious way. As Dan Doel demonstrated, this can turn a purely right-associated bind chain, i.e. one that can be interpreted tail-recursively, into a repeatedly broken chain with arbitrary left-binds injected into it, thus either crashing the stack or requiring useless extra frames to be repeatedly shoved onto the heap.

This is kind of silly, and could be ameliorated if for wasn’t trying to be non-monadic. But that’s not going to change.

[9:] You have type lambdas. Yay, right? But now you can't just talk about Functor (StateT s IO). Its Functor[({type F[X] = StateT[S,IO,X]})#F], and you have to hand plumb it to something like return, because it basically can't infer any of that, once you start dealing with transformers ever. The instance isn't directly in scope. 12.pure[({type F[X] = StateT[S,IO,X]})#F] isn't terribly concise. It can't figure out it should use the inference rule to define the implicit for StateT[S,M,_] from the one for M[_] because of the increased flexibility that nobody uses.

This is probably the best story of the bunch, and possibly the most well-known of the whole series. This is good for Scala marketing, but probably not best for the future of Scala FP…

We first got the kind-projector to help us write these type lambdas more succinctly. So Kmett’s first example above can now be written Functor[StateT[S, IO, ?]]. Not as nice as the curried Haskell form, but much better.

Eventually, though, Miles Sabin implemented the “higher-order unification” feature, often called the “SI-2712 fix” after the infamous bug. This feature performs the inference Kmett describes above, and gets away with it precisely because it ignores “increased flexibility that nobody uses”.

The situation is not perfect—you have to flip this nonstandard switch, the resulting language isn’t source-compatible with standard Scala, and warts like bug 5075 (despite first appearances, this is quite distinct from 2712) remain—but Scala is in great shape with respect to this problem compared to where we were at the time of Kmett’s original writing.

[10:] In this mindset and in the same vein as the CanBuildFrom issue, things like Either don't have the biased flatMap you'd expect, somehow encouraging you to use other tools, just in case you wanted to bind on the Left. So you don't write generic monadic code over the Either monad, but rather are constantly chaining foo.right.flatMap(... .right.flatMap(....)) ensuring you can't use the sugar without turning to something like scalaz to fill it in. Basically almost the entire original motivation for all the type lambda craziness came down to being able to write classes like Functor have have several instances for different arguments, but because they are so hard to use nobody does it, making the feature hardly pay its way, as it makes things like unification, and path dependent type checking harder and sometimes impossible, but the language specification requires them to do it!

I’m not sure the situation was ever as severe as Kmett states, but that might be down to my personal experience in Scala, with Scalaz as my permanent companion.

The interspersed .rights never prevented you from using the for syntax, though they did make it significantly more obscure. Supposing foo and bar are Eithers:

for {
  x <- foo.right
  y <- bar.right

That trailing .right looks like it’s missing a dance partner, but it’s in just the right place for that biased flatMap or map method to kick in.

But in Scalaz, we never had to worry about it. Because we only supplied the right-biased Monad for Either. When you also bring in Scalaz’s Monad syntax, suddenly Either acquires the standard right-biased map and flatMap.

import scalaz.syntax.bind._, scalaz.std.either._

for {
  x <- foo
  y <- bar

No more lonely dancers.

But now ​right-biasing has returned to the standard library, so even these extra imports are no longer necessary.

Kmett pairs this point with a tangentially related point about functors over other type parameters. But I think higher-order unification is going to solve this problem, albeit in a very ad hoc way, in the long run. Programmers who want to use higher-kinded types will increasingly want to turn on the feature, or even be forced to by library designs that depend on it. Types that conform to right-bias—placing the functor parameter last, not first—will find happy users with nice inference.

class FA[F[_], A]

def fa[F[_], A](fa: F[A]): FA[F, A] =
  new FA

scala> fa(Left(33): Either[Int, String])
res0: FA[[+B]Either[Int,B],String] = FA@542c2bc8

This works even in more elaborate situations, such as with monad transformers:

trait EitherT[E, M[_], A]
trait ReaderT[R, F[_], A]
trait IO[A]
class Discovery[T1[_[_], _], T2[_[_], _], M[_], A]

def discover[T1[_[_], _], T2[_[_], _], M[_], A](a: Option[T1[T2[M, ?], A]])
    : Discovery[T1, T2, M, A] = new Discovery

scala> discover(None: Option[EitherT[String, ReaderT[Int, IO, ?], ClassLoader]])
res0: Discovery[[M[_], A]EitherT[String,M,A],
                [F[_], A]ReaderT[Int,F,A],
                ClassLoader] = Discovery@4f20ea29

Contrarian types that don’t conform will find themselves rejected for constantly introducing mysterious type mismatches that must be corrected with more explicit type lambdas. So the libraries should develop.

[11:] You don't have any notion of a kind system and can only talk about fully saturated types, monad transformers are hell to write. It is easier for me to use the fact that every Comonad gives rise to a monad transformer to intuitively describe how to manually plumb a semimonoidal Comonad through my parser to carry extra state than to work with a monad transformer!

This isn’t so much about inference of higher-kinded type parameters, which I’ve dealt with above, but how convenient it is to write them down.

As mentioned above, the kind-projector compiler plugin has made writing these types significantly easier. Yet it remains ugly compared to the curried version, for sure.

[12:] I've been able to get the compiler to build classes that it thinks are fully instantiated, but which still have abstract methods in them.

I haven’t seen this kind of thing in quite a while, but it wouldn’t surprise me if a few such bugs were still outstanding. Let’s give the compiler the benefit of the doubt and suppose that things have gotten significantly better in this area.

[13:] Tail-call optimization is only performed for self-tail calls, where you do not do polymorphic recursion.

There are two issues packed here. The first still holds: only self-tail calls are supported. Plenty of ink has been expended elsewhere; I point to Dan Doel again for some of that.

The second issue has a fix in Scala 2.12.4!

@annotation.tailrec def lp[A](n: Int): Int =
  if (n <= 0) n else lp[Option[A]](n - 1)
// [in 2.12.3] error:⇑ could not optimize @tailrec annotated method lp:
// it is called recursively with different type arguments

scala> lp[Unit](1000000)
res0: Int = 0

To pour a little oil on, this isn’t a 50% fix; this is a nice improvement, dealing with a particular annoyance in interpreting GADT action graphs, but the much larger issue is the still-missing general TCO.

[14:] Monads are toys due to the aforementioned restriction. (>>=) is called flatMap. Any chain of monadic binds is going to be a series of non-self tailcalls. A function calls flatMap which calls a function, which calls flatMap... This means that non-trivial operations in even the identity monad, like using a Haskell style traverse for a monad over an arbitrary container blows the stack after a few thousand entries.

And this is the same, for the same reason. Kmett goes on to discuss the “solutions” to this.

[15:] We can fix this, and have in scalaz by adapting apfelmus' operational monad to get a trampoline that moves us off the stack to the heap, hiding the problem, but at a 50x slowdown, as the JIT no longer knows how to help.

Nothing has changed here. We’ve tweaked the trampoline representation repeatedly to get better averages, but the costs still hold.

[16:] We can also fix it by passing imperative state around, and maybe getting scala to pass the state for me using implicits and hoping I don't accidentally use a lazy val. Guess which one is the only viable solution I know at scale? The code winds up less than 1/2 the size and 3x faster than the identity monad version. If scala was the only language I had to think in, I'd think functional programming was a bad idea that didn't scale, too.

This is still something you have to do sometimes. Just as above, nothing has really changed here. You just have to hope you don’t run into it too often.

Random restrictions

[17:] for yield sugar is a very simple expansion, but that means it has all sorts of rules about what you can't define locally inside of it, e.g. you can't stop and def a function, lazy val, etc. without nesting another for yield block.

One thing has changed in this area! You no longer have to use the val keyword when defining a val locally in the for block.

Otherwise, situation constant.

[18:] You wind up with issues like SI-3295 where out of a desire to not "confuse the computation model", it was decided that it was better to you know, just crash when someone folded a reasonably large list than fix the issue.. until it finally affected scalac itself. I've been told this has been relatively recently fixed.

As Kmett mentions, this was fixed. It remains fixed.

[19:] No first-class universal quantification means that quantifier tricks like ST s, or automatic differentiation without infinitesimal confusion are basically impossible.

def test = diff(new FF[Id,Id,Double] { 
   def apply[S[_]](x: AD[S, Double])(implicit mode: Mode[S, Double]): AD[S, Double]
      = cos(x) 

is a poor substitute for

test = diff cos

kind-projector has provided less well-known support for some varieties of polymorphic lambdas, such as FF in this example, for a while. The implicit constraint and fact that we’re trying to be polymorphic over a higher-kinded type might make things tricky, but let’s see if we can get it working.

Lambda[FF[Id, Id, Double]](x => cos(x))
Lambda[FF[Id, Id, Double]](x => implicit mode => cos(x))

// both forms fail with the uninteresting error:
// not found: value Lambda

Scalaz 8 contains a very clever unboxed encoding of universal quantification based on the observation that if side effects and singleton type patterns are forbidden, as they are under Scalazzi rules, multiple type applications in Scala are indistinguishable at runtime. (To see why this is, consider the difference between List.empty[A] and mutable.Buffer.empty[A].) The one that comes with Scalaz 8 only quantifies over a *-kinded type parameter, but we should be able to use the same technique to quantify over S: * -> *.

trait ForallK1Module {
  type ForallK1[F[_[_]]]

  type [F[_[_]]] = ForallK1[F]

  def specialize[F[_[_]], A[_]](f: [F]): F[A]

  def of[F[_[_]]]: MkForallK1[F]

  sealed trait MkForallK1[F[_[_]]] extends Any {
    type T[_]
    def apply(ft: F[T]): [F]

object ForallK1Module {
  val ForallK1: ForallK1Module = new ForallK1Module {
    type ForallK1[F[_[_]]] = F[λ[α => Any]]
    def specialize[F[_[_]], A[_]](f: [F]): F[A] = f.asInstanceOf[F[A]]
    def of[F[_[_]]]: MkForallK1[F] = new MkForallK1[F] {
      type T[_] = Any
      def apply(ft: F[T]): [F] = ft

// we're using an unboxed representation
type FF[F[_], G[_], T, S[_]] = AD[S, T] => Mode[S, T] => AD[S, T]

scala> ForallK1.of[Lambda[S[_] => FF[Id, Id, Double, S]]](
           x => implicit m => cos(x))
res3: ForallK1Module.ForallK1.ForallK1[
         [S[_$1]]AD[S,Double] => (Mode[S,Double] => AD[S,Double])
      ] = $$Lambda$2018/266706504@91f8cde

Upshot? Nothing has changed in core Scala. People in the Scala community have discovered some clever tricks, which work even better than on the slightly complicated test case Kmett supplied when tried with more traditional *-kinded rank-2 idioms like ST.

scala> Lambda[List ~> Option](_.headOption)
res2: List ~> Option = $anon$1@73c4d4b5

trait ST[S, A] {
  def flatMap[B](f: A => ST[S, B]): ST[S, B]
trait STVar[S, A] {
  def read: ST[S, A]

def newVar[S, A](a: A): ST[S, STVar[S, A]] = ???

def mkAndRead[S]: ST[S, Int] = newVar[S, Int](33) flatMap (

def runST[A](st: Forall[ST[?, A]]): A = ???

scala> :t Forall.of[ST[?, Int]](mkAndRead)[[α$0$]ST[α$0$,Int]]

scala> :t Forall.of[Lambda[s => ST[s, STVar[s, Int]]]](newVar(33))[[s]ST[s,STVar[s,Int]]]

scala> :t runST(Forall.of[ST[?, Int]](mkAndRead))

scala> :t runST(Forall.of[Lambda[s => ST[s, STVar[s, Int]]]](newVar(33)))
<console>:19: error: type mismatch;
 found   : Forall[[s(in type Λ$)]
                  ST[s(in type Λ$),
                     STVar[s(in type Λ$),Int]]]
 required: Forall[[α$0$(in type Λ$)]
                  ST[α$0$(in type Λ$),
                     STVar[_ >: (some other)s(in type Λ$) with (some other)α$0$(in type Λ$), Int]]]

Knowledgable use of these tricks will give you much better code than we could produce when Kmett wrote this, but it’s still nowhere near as elegant or easy-to-use as rank-2 in Haskell.

... but it runs on the JVM.

Indeed, Scala still runs on the JVM.

How good an idea is it?

So, a few things have gotten better, and a few things have gotten a lot better. That bodes well, anyway.

Functional programming practice in Scala will continue to encounter these issues for the foreseeable future. If you are writing Scala, you should be practicing functional programming; the reliability benefits are worth the price of entry. While you’re doing so, however, it’s no thoughtcrime to occasionally feel like it’s a bad idea that doesn’t scale.

This article was tested with Scala 2.12.4 -Ypartial-unification, Scalaz 8 3011709ba, and kind-projector 0.9.4.

Portions Copyright © 2013 Edward Kmett, used with permission.

Copyright © 2017, 2018 Stephen Compall. This work is licensed under a Creative Commons Attribution 4.0 International License.

Saturday, February 10, 2018

Writing about subtyping

I want programmers to stop using subtyping, yet I keep bringing it up, in article after article. Partly that is because it is very hard to avoid subtyping-related issues in Scala, and I find myself concerned with Scala when I ought to be devoting mental cycles to simpler, more powerful languages. But that may simply feed into what I suppose is the greater reason:

Subtyping is an amusing puzzle for my mind. I enjoy the mental diversion of the needlessly complex puzzle of practical programming techniques making use of subtyping.

I can justify this self-gratification by saying to myself, “the more they read about what subtyping really means, the more their desire to avoid this mess will grow”. I think this is more rationalization than honest motivation for myself, though I do think those who learn more about subtyping are more likely to avoid it, just as those who learn more about typing are more likely to advocate it.

Yet, it does have a kind of beauty. So I take it out here and there, and appreciate its facets for a while. Then I carefully return it to its display case, lest I am afflicted with the subtyping bug again.

Saturday, December 9, 2017

Spare me the tedium of “simple” linting, please

In the development environments of singly-typed languages like JavaScript and Python, one popular build step for improving code quality is the “linting” or “style” tool. Tools like jshint and pyflakes point out misspellings and references to missing variables, idioms that frequently lead to bugs like == usage, calls with apparently the wrong number of arguments, and many other things.

Much of this is meant to mechanize the enforcement of a team’s style guidelines—at their best, sincere and effective tactics for avoiding common sources of bugs. Unfortunately, many of these guidelines can seem excessively pedantic, forcing the programmer to deal with cases that could not possibly happen.

Normally, it would make sense to tell the programmers to just suck it up and follow the rules. However, this tactic can lead to a couple bad outcomes.

  1. The lint check can lose support among developers, for being more trouble than it’s worth. If programmers feel that a lint is causing more code quality issues than it’s solving, they’ll sensibly support its removal.
  2. Lints without developer support tend to be disabled sooner or later, or simply mechanically suppressed at each point they would be triggered, via “ignore” markers and the like. At that point, the bug-catching benefits of the lint are completely eliminated; in the worst case, you have a universally ignored warning, and are even worse off than if the warning was simply disabled.
  3. If the errors spotted by the lint are serious enough, but the lint warns for too many exceptional cases, the developers might decide to move the style rule to manual code review, with an opportunity to argue for exceptional cases. This is labor-intensive, carries a much longer feedback cycle, and makes it easy to accept an argument for an exception to the style rule that is actually erroneous, as it is not machine-checked.

Many of these “too many false positives” warnings could be a lot better if they simply had more information to work with about what will happen at runtime. That way, they can avoid emitting the warning where, according to the extra information, a construct that appears dangerous will not be a problem in practice.

That is one thing that type systems are very good at. So lint users are on the right track; the solution to their woes of needless ritual is more static analysis, rather than less.

Let’s consider some common lints in JavaScript and see how the knowledge derived from types can improve them, reducing their false positive rate or simply making them more broadly useful.

Suspicious truthiness tests

(This example has the benefit of a recent implementation along the semantic lines I describe, in Flow 0.52. I take no credit for any of the specific lint suggestions I make in this article.)

In JavaScript, a common idiom for checking whether an “object” is not null or undefined is to use its own “truthiness”.

if (o)        // checking whether 'o' is defined
if (o.magic)  // checking whether 'o's 'magic' property is defined

This is concise and does the trick perfectly—if the value being tested isn’t possibly a number, string, or boolean. If it can be only an object, null, or undefined, then this is fine, because even the empty object {} is truthy, while null and undefined are both falsey. Unfortunately, in JavaScript, other classes of data have “falsey” values among them, such as 0 for number.

The “lint” solution to this problem is to always compare to null directly.

if (o != null)                     // not null or undefined
if (o !== null && o !== undefined) // required in more pedantic code styles

This might be encapsulated in a function, but still doesn’t approach the gentle idiom afforded by exploiting objects’ universal truthiness. But the object idiom is simply unsafe if the value could possibly be something like a number. So the question of whether you should allow this exception to the “always compare to null explicitly” lint boils down to “can I be sure that this can only be an object?” And if in review you decide “yes”, this is a decision that must constantly be revisited as code changes elsewhere change the potential types of the expression.

You want to mechanically rule out “possible bugs” that are not really possible in your use of the idiom, so that the linter will not warn about benign use of truthiness—it will save the warnings for code where it could actually be a problem. Ruling out impossible cases so that you only need cope with the possible is just the sort of programming job where the type system fits in perfectly.

A type system can say “this expression is definitely an object, null, or undefined”, and type-aware linting can use that information to allow use of the truthiness test. If that data comes from an argument, it can enforce that callers—wherever else in the program they might be—will not violate the premise of its allowance by passing in numbers or something else.

A type system can also say “this expression will definitely be an object, never null”, or vice versa, thus taking the lint even further—it can now tell the programmer that the if check is useless, because it will always be truthy or falsey, respectively. This is just the sort of premise that’s incredibly hard for humans to verify across the whole program, continuously, but is child’s play for a type-checker.

A type system such as Flow can even say “this expression could have been something dangerous for the truthy test, like number | object, but you ruled out the dangerous possibilities with earlier if tests, so it’s fine here”. Manual exemption can regress in cases like this with something as simple as reordering “if-else if-else” chains a little carelessly—keep in mind here the decades of failure that “be sufficiently careful” has had as a bug-avoidance tactic in programming—but type-aware linting will catch this right away, waking up to declare its previous exemption from the style rule null and void.

The more precise your types in your program, the more understanding of your use of this idiom—in only valid places—the type-aware linter will be. It will not make the reasoning mistakes that human review would make when allowing its use, so you can use it with more confidence, knowing that the lint will only call out cases where there’s a genuine concern of a non-null falsey value slipping in. And there is no need to argue in code review about which cases need != null and which don’t, nor to revisit those decisions as the program evolves; as circumstances change, the type checker will point out when the verbose check becomes unnecessary, or when the succinct check becomes unsafe.

References to undeclared variables

It’s very common to mistake a variable name that isn’t defined for one that is. The larger a program gets, the easier this mistake is to make.

This mistake comes in a few forms. It may be a simple misspelling. It may be a variable you thought was defined here, but is actually defined somewhere else. It may be a variable defined later, but not yet.

Whatever the meaning of the error, linters can catch the problem via a relatively simple method. As the file is scanned, the linter keeps track of what variables are currently in scope. When encountering a variable reference, it checks the variable name against its current working list of variables. If one is not in the list, the linter reports it.

This is better than nothing. Compared to what you can do with a type checker, though, it’s not very good at all.

Suppose that you have a few local functions defined at the top level of your module, foo, bar, and baz. A linter will point out an undeclared variable if you try to call fop, gar, or bax. So you don’t have to wait for the browser reload or test cycle; you can correct these errors right away.

Later on, your module is getting larger, so you decide to group some functions into objects to clean up the top-level namespace. You decide that foo, bar, and baz fit under the top-level object q.

const q = {
    foo(...) {...}

    bar(...) {...}

    baz(...) {...}

During your refactoring, references to these three functions are rewritten to,, and q.baz, respectively. This is a nice way to avoid ad hoc name prefixes as a grouping mechanism; you’re using a first-class language feature to do the grouping instead.

But let’s give a moment’s consideration to q.fop, q.gar, and q.bax. The linter will verify that the reference to q is sound; it’s declared at the module level as const q. However, the linter will not then verify that the “member” references are sound; that is a fact about the structure of q, not its mere existence.

When all you have is “simple” linting, this becomes a tax on modularity, so to speak. If a variable is defined locally—very locally—references to it are checked. If it is defined remotely, whether in another module or simply “grouped” in a submodule, references to it are not checked.

A type system cuts the modularity tax by tracking the names that are beyond the purview of the simple linter. In the case of q, type-checking tracks more than its existence; its statically-known structural features are reqorded as part of its type.

  • In this module, q is defined.
    • It is an object,
    • and is known to have properties:
      • foo,
        • a function which is…;
      • bar,
        • a function which is…, and
      • baz,
        • a function which is…

This continues to work at whatever depth of recursion you like. It works across modules, too: if I want to call baz from another module, I can import this module in that one, perhaps as mm, and then the reference mm.q.baz will be allowed, but mm.q.bax flagged as an error.

An undeclared-variable linter is all well and good, but if you want to take it to its logical conclusion, you need type checking.

hasOwnProperty guards

The best lints focus on elements of code hygiene we’re reluctant to faithfully practice while writing code, but come back to fill us with regret when we fail to do so. One example arises with using for to iterate over objects in JavaScript; the lint checks that you’re guarding the loop with hasOwnProperty.

The purpose of these guards is to handle non-plain objects; that is to say, objects “with class”. The guards are always suggested by the linter to avoid nasty surprises should you try iterating over the properties of an object “with class”.

The irony of this check is that the intent of such code is usually to work with plain objects only, that is, classy objects should not be present in the first place! The construct is still perfectly usable with classy objects; it’s just that more caution is called for when using it in that fashion.

As such, there are two basic scenarios of for iteration over objects.

  1. iteration over plain objects only, and
  2. iteration over potentially classy objects.

The focus of the hasOwnProperty guard ought to be #2, but this concern bleeds over into #1 cases, needlessly or not depending on how pessimistic you are about Object.prototype extension. But this question is moot for the linter, which can’t tell the difference between the two scenarios in the first place.

By contrast, a type checker can make this distinction. It can decide whether a variable is definitely a plain object, definitely not one, or might or might not be one. With that information, depending on your preferences, it could choose not to warn about a missing hasOwnProperty guard if it knows it’s looking at scenario #1. So if a hasOwnProperty is needless, it need not pollute your code for the sake of the scenarios where it will be needed.

Computer, please try to keep up

Humans are pretty good at coming up with complex contractual preconditions and postconditions for their programs, and making those programs’ correct operation depend on the satisfaction of those contracts. But humans are very bad at verifying those contracts, even as they make them more complex and depend more on them.

“Simple” linting tools are good at checking for the fulfillment of very simple rules to help ensure correctness, freeing the human mind to focus on the more complex cases. What makes them a chore to deal with—a reason to put solving linter warnings on the “technical debt backlog” instead of addressing them immediately—is “they don’t know what we know”; they can handle laborious low-level checks, but lack the sophisticated analysis humans use to decide the difference between a correct program and an incorrect one.

Happily, through static analysis, we can get much closer to human-level understanding’s inferences about a program, while preserving the tireless calculation of contractual fulfillment that makes linting such a helpful companion in the development cycle, doing the parts that humans are terrible at. When your linter is so “simple” that it becomes a hindrance, it’s time to put it down, and pick up a type system instead.

Tuesday, November 28, 2017

Or, we could not, and say we don’t have to

I previously wrote “Values never change types”, whose central thesis statement I hope is obvious. And this still holds, but there is something I left unsaid: values do not have identity, so the notion of “mutating” them is as nonsensical as “mutating 4”. And the formal system of Scala types treats objects with identity similarly, by not permitting them or their variable aliases to change type, even though they are not quite values. But this is a design decision, and other choices could have been made.

There are very good reasons not to make other choices, though. Other type systems come with features that come very close to making the opposite design choice; by imagining that they went just a little farther down this garden path, we can see what might have been.

Refinement, flow, or occurrence typing, by any name

In Flow and TypeScript, when you test properties of a value in a variable, you can “change the type” of that variable. For example, you could have a let s: any; if you write an if block that tests whether s is a string, the type of s—at compile-time, mind you—“changes” to string within the if body. Within the body of that if, you could perform further tests to refine s’s type further; you might also have various other if blocks alongside checking for other types, so that s might variously “change” into number, function, object with a whatsit property whose type is another object with a whosit property, and so on.

So, instead of having a single type attached to a lexical variable over its entire scope, a variable has several types, each tied to a block of code that uses the variable. It is an order more sophisticated, but still tied to the lexical structure of the program, as if the variable has multiplied to honor all the faces it might have. This is a great way to model how people are writing programs at the type level without overly complicating the formal system, which still must always obey a complete set of sound rules.

Contradictory refinement

In the systems I’ve described, no further refinement can contradict a prior one. So once you determine that a variable is a string, it’s not going to turn out to be a number later; at most, it can get more specific, like being proven to be a member of a known static set of strings. So this way you know that inner blocks cannot know less than outer blocks about the nature of a variable; that is what I mean by “tied to the lexical structure.”

What “real JavaScript code” could be written that would violate this assumption?

function foo(arg) {
    let s = arg
    if (typeof s === 'string') { // refines s to type string
        s = {teaTime: s}
        // "point of no return"
        if (s.teaTime === "anytime") {

The first if test establishes a block in which s’s type is string. Then we pull the rug out from under the type-checker by assigning to s; with that assignment, it is no longer true that s is a string. Why does this make type-checking more complex?

Let’s twist and tangle the program to support our beloved mutation

The type of the variable s no longer follows the block structure of the program, in the way we usually perceive blocks in a structured program. That’s because the fact established by the outer if test is suddenly invalidated partway through the block. So our first problem is one of raising the complexity burden on human interpretation of the program—the reader can no longer assume that the specificity of a variable’s type only increases as you move inward, reading the block structure of the program—but it is not fatal in itself, at least for this example. We can salvage the model via the Swiss Army knife of semantic analysis, the continuation-passing style (CPS) transform.

function foo(arg, k0) {
    return (s => if (typeof s === 'string') {
                     (_ => if (s.teaTime === "anytime") {
                               drinkTea(s, k0)
                     )(s = (teaTime: s))

Now it is still possible for inner blocks to contradict outer blocks, but at least this is only possible at the block level. So, by “merely” revisualizing our programs in terms of the flow of continuations rather than the visibly apparent block structure, we can sort of still think of the type of variables as a “block”-level concern, as it was before.

Unluckily, performing a CPS transform in your head with all the code you see is a kind of “reverse Turing Test”, something that an AI would have to not be able to do very well in order to fool us into thinking it was human. So no matter what, we are stuck with a significant new complication in our formal model.

But not a fatal one. Yet.

Loop unrolling according to the phase of the moon

What will prove fatal to the formal model of type-changing mutation is delay. Let us see how the seeds of our destruction have already been sown.

while (forSomeTimeNow()) {
    if (itsAFullMoon()) {
        s = {teaTime: s}

The first question, and the last, is “is it safe to drinkTea?”

One necessary prerequisite is that it has been a full moon. I’m using this boolean expression to inject the Halting Problem—we cannot determine in a Turing-complete language whether a boolean expression will evaluate to true or false, generally—but it is probably sufficient to say that it is nondeterministic, even if not Turing-complete. (Pragmatists love Turing completeness and nondeterminism, because “more power is always better”.) So it’s hard enough—by which I mean generally impossible—to say whether the s assignment has happened.

The next prerequisite, which should drive us wholly into despair now if hope yet remains, is that the moon has been full once. Eh? Here’s where the tie of variable types to any semblance of code structure breaks down completely, because s takes on a surprisingly large number of types in this code sample.

To assign a precise type to this program, we have to accurately model what is happening in it. So, suppose that prior to entering this loop, the type of s is string. Each assignment to s—made each time the while’s test is true and the moon is full—takes us one step down this list of types.

  1. string
  2. {teaTime: string}
  3. {teaTime: {teaTime: string}}
  4. {teaTime: {teaTime: {teaTime: string}}}
  5. {teaTime: {teaTime: {teaTime: {teaTime: string}}}}
  6. •••

Now if you want to assign (potentially) all of these infinite possibilities to the program, you have to go even further from the block structure model. Imagine a third dimension of the program text: at the surface, you see s having only the first two types above, but as you look deeper, you see the branching possibilities—oh so many iterations in, oh so many times the moon has been full—each assigning different types to what is on the surface the same code. Looking at this as two-dimensional text, you would only see the infinite superimposition of all possible types of s, weighted according to their probability.

Three dimensions might be too few for this code.

Of course, there’s a well-known, sensible way to type this code, sans the log call: abandon the folly of modeling mutation and assign this recursive union type to s for at least the whole scope of the while loop, if not an even wider scope:

type TeaTimeTower = string | {teaTime: TeaTimeTower}

And supposing the drinkTea function is so polymorphic, all is well, and as a neat side bonus, easy to understand. But we aren’t here to pursue sanity; we gave that up to try to model mutation.

The devil in the delay

If fully desugared, while is a two-argument (not counting still thinking in CPS) higher-order function, taking test functions as arguments. Just like you’re writing Smalltalk.

while(() => forSomeTimeNow(),
      () => {
             () => s = {teaTime: s})

The thing that makes so much trouble for flow analysis is this delay. Type-changing requires us to contradict earlier refinements of a variable’s type, not simply refine them further. But the ability to capture a reference to a variable in a lambda means that we need a deep understanding of how that lambda will be used. It might never be invoked. It might be invoked later in the function, just when we thought it was safe to contradict whatever refinement it was type-checked with. It might be saved off in another variable or data structure elsewhere in the program, making reasoning about when the variable might be referenced in the future a futile endeavor.

Doing flow analysis with sources of delayed execution whose behavior is 100% known, like if and for, is tricky enough. Doing it in the presence of unknown, novel, potentially nondeterministic sources of delay is intractable, if not impossible.

And that’s for the computer. How many dimensions does the model in your head have, now? Zero, no, negative points for abandoning this ivory-tower static analysis and declaring “common sense” the arbiter of your programs’ correctness.

Did anyone else see you come here?

An object with known properties can be thought of as a group of named variables. This is a longtime, straightforward way to represent modules of functions, or clean up a global namespace by putting a lot of related items laying on the floor into the same drawer.

Since we love mutation, and we love mutating variables, we should love mutating object properties (and their types) even more, right?

function schedule(s) {
    s.teaTime = "anytime"

The type of s in the caller after schedule finishes is straightforward: it’s whatever it was before, with the teaTime field (whatever it might have been before, if anything) type set to string, or perhaps the literal singleton type "anytime".

But what schedule is so eager to forget will not be so easily forgotten by the rest of the program.

Namely, the contradicted, earlier type of s is very hard to reliably eradicate. This is an aliasing problem, and it brings the excitement of data races in shared-mutable-state multithreaded programs to the seemingly prosaic JavaScript execution model.

To type s in the aftermath of schedule, you must perfectly answer the question, “who has a reference to s”? Suppose that teaTime was a now-contradicted function. Any code that calls that function via property lookup on its reference now takes on another dimension: before schedule executes, it is safe, but afterwards it no longer is, so it takes on the prerequisite “can only be called before calling schedule(s).” The dimensional multiplication directly results from the multiplication of possible types for s.

The problem broadens virally when you try to model other variables that are not s, but whose types will still change due to schedule being called! Here is an example of such a variable.

const drinks = {coffee: coffeeMod; tea: s}
  // where s is the value we’re talking about

So all the analysis of references to s induced by the type mutation means references to drinks must undergo the same ordeal. And references to something that refers to drinks, and references to something that refers to that, and so on, ad infinitum.

And that is assuming we can statically determine what object identities will be flying around the program. As with so much else in this article, this is generally impossible.

By the way, the problem with lambdas is just a special case of this one; it’s exactly that lambdas alias variables that causes so much grief for our wannabe-mutating ventures.

A different kind of power, at a much more reasonable price

Since we are only imagining this insanity, not attempting to truly partake of it, we have something good to feel about, after all: the grass is really quite brown on the other side, alas, but that on this side is a little greener than first glance might indicate.

Type systems like those of Haskell, Java, OCaml, Scala, and many other languages simply don’t permit the types of variables to change. When you consider the introduction of type equalities in Haskell or Scala GADTs, or more direct refinements made in Typed Racket, Flow, or TypeScript; you can include all of these languages in the broader category of type systems whose variable types can only complement, never contradict.

This is a powerful simplifying assumption, because under this restriction, none of the above problems matter. “Functional types” are not only powerful enough to model programs, and far easier to understand for the human programmer, they are the only way out of the quagmire of complexity wrought by trying to “model mutation”. Even problems that almost look amenable to mutation analysis, like the while example above, admit a simpler solution in an immutable type like the recursive TeaTimeTower.

More power is sometimes worse.

When you forbid unneeded capabilities, you get back capabilities in other areas. Sometimes this comes in the form of improved understanding, such as we get for large programs by introducing type restrictions. It makes sense to give up “power” that is not practical to get benefits that are.

Take the forbidding of mutation. We take type-level immutability for granted in the same way that many practitioners take value-level mutability for granted. Perhaps one reason for resistance to functional programming might be that we are so accustomed to the drawbacks of unconstrained mutability that it does not seem quite as insane at the value level as, seen above, it is at the type level.

But, familiarity cannot make the insane any less so.

This article was tested with Flow 0.57.2 and TypeScript 2.5.

Thursday, July 27, 2017

Advanced type system features are [usually] a good thing

The desire to allow more programs to be typed—by assigning more accurate types to their parts—is the main force driving research in the field. – Benjamin Pierce, Types and Programming Languages

Type system design is a major factor in whether you can write programs, and how easily you can do so. Simplicity is an important consideration, but that entails a trickier question to start: “what is simplicity?”

In this article, I want to consider two questions about type system simplicity by comparing two—relatively good as these things go—type systems, Haskell’s and TypeScript’s.

First: what dangers come from an excess of pragmatism in type system design? By pragmatism, I mean the elevation of design compromise as the highest virtue. The pragmatist seeks to compromise even those “pure” designs that are entirely suitable when considering the practical constraints in play.

I don’t use this word, ‘pragmatist’, because I think it’s nice and accurate. Nor do I think that it’s fair to those who don’t fit the definition I’ve just given, yet still think of themselves as “pragmatic” in the broader sense. I use this word because the people I describe have claimed the mantle of “pragmatism”, and reserved it for themselves, quite successfully in the world of programming. And first, we must name the enemy.

Second: what is so compelling about advanced type system features? New type systems are often beset with users requesting features like rank-N types, higher-kinded types, GADTs, existential quantification, &c. There are good, practical reasons these features are requested; they result in a kind of “simplicity” that cannot be had simply by having a small number of features.

An unsound feature in TypeScript

Function parameters are a contravariant position; contravariance and invariance are the only sound choices for them. So TypeScript’s “function parameter bivariance” is a deliberately unsound choice; if you’re unfamiliar with it, I strongly recommend stopping now and reading the linked documentation, along with the explanation of why they do it; it’s a good piece of documentation, describing an eminently practical circumstance in which it might be used.

However, this example is worth examining more closely. Think about it from the perspective of a type system designer: how would you support the call to addCallback below?

enum EventFlag {

interface Event;
interface MouseEvent extends Event {/*...*/}
interface KeyEvent extends Event {/*...*/}

function addCallback(
  flag: EventFlag,
  callback: (Event) => void): void {
  // ...

addCallback(EventFlag.MousePress, (e: MouseEvent) =>
  { } // handle e

The temptation of pragmatism

TypeScript’s design choice to support this sort of call is unsound. This is explained by the documentation; again, please refer to that if you haven’t yet.

There is always the temptation to poke a hole in the type system when dealing with the problem, “how do I express this?” That’s because you can then do something you want, without having gone through the bother of proving that it’s safe. “You can’t do whatever you feel like doing” is exactly what a sound type system must say. The benefits of soundness diffuse across your program, filling in the negative space of the tests that you no longer need to write; they can seem far away when confronted with a problem here to be solved now.

In this way, unsound features are the greatest ally of the pragmatist. They’re an asymmetric weapon, because sound features can never say “just do what you like, here; don’t worry about the distant consequences”.

We who have a strong distaste for pragmatism must make do instead with research.

A sound alternative, in Haskell

Haskell is a testbed for many advanced type system features, demarcated by extension flags. One of the joys of working with Haskell is learning about a new extension, what it means, and thinking of ways to use it.

Many of these features are guarded by an extension flag; we’re going to call on one such feature by placing at the top of the Haskell source file


One of the things this enables is that you can attach type parameters to enum members. EventFlag gets a type parameter indicating the associated type of event.

data EventFlag e where
  MousePress :: EventFlag MouseEvent
  KeyPress :: EventFlag KeyEvent

-- MouseEvent and KeyEvent can be
-- related types, but don't have to be
data MouseEvent = -- ...
data KeyEvent = -- ...

addCallback :: EventFlag e
            -> (e -> IO ())
            -> IO ()

e is a type parameter; when you pass an EventFlag to addCallback, the callback type (e -> IO () above) changes to reflect what event type is expected.

λ> :t addCallback MousePress
(MouseEvent -> IO ()) -> IO ()
λ> :t addCallback KeyPress
(KeyEvent -> IO ()) -> IO ()

This is a better design in two ways.

  1. It is sound; you cannot screw up the relationship between the EventFlag argument and the event type that will be passed to the callback.
  2. It is more convenient; if you pass a lambda as the callback argument, it will simply “know” that the argument type is KeyEvent or MouseEvent; your editor’s coding assistance can act accordingly, without you having to declare the lambda’s argument type at all.

I would go so far as to say that this makes this addCallback simpler; it’s easier and safer to use, and can even be implemented safely. By contrast, function parameter covariance requires you, the user of the function, to think through in your head whether it’s really OK, without type-checker assistance, and even then the library function can’t offer any help to callers if they declare the lambda argument type wrong.

What’s simpler?

A type system without powerful features for polymorphism makes it difficult or impossible to describe many programs and libraries in fully sound ways. A more powerful type system simplifies the task of the programmer—its features give you a richer language with which to describe generic APIs.

When the core of a type system doesn’t give you a way to type an interface, you might follow the pragmatist’s advice, and poke a hole in the type system. After that, you won’t be able to generally trust the conclusions of the type checker throughout the program, anymore.

Instead, you might look at the leading edge of type system research, for a sound way with which to express the API. This is not so expedient, but yields APIs that are safer and more convenient to use and implement.

With an unsound feature, the pragmatist can offer you the world, but cannot offer the confidence that your programs don’t “go wrong”. Powerful type system features might bend your mind, but promise to preserve that confidence which makes type systems, type systems.

This article was tested with TypeScript 2.4 and GHC 8.0.2.