Showing posts with label haskell. Show all posts
Showing posts with label haskell. Show all posts

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 {
  MousePress,
  KeyPress
}

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

{-# LANGUAGE GADTs #-}

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.

Tuesday, April 3, 2012

Some type systems are much better than others.

As a shortcut, I previously complained about C and Java's type systems leaving bad impressions. Let's broaden that to the realm of type system research, avoiding useless discussion of the relative merits of this or that programming language as a whole. Some type systems let you express more of the set of valid programs, or different subsets. More out of the theoretical realm, but because we are human, different inference engines are better at figuring out types in different situations.

There is a nice graphic in Gödel, Escher, Bach that illustrates this issue: it displays the universe split into the true and the false, and elaborate structures covered with appendages illustrating “proof”. Of all valid programs¹, many are “typeable”, meaning that we can prove that they are sound, type-wise, with a particular type system; conversely, most invalid programs are not typeable.

However, you might imagine that the fingers stretch into the invalid space on occasion, and they don't cover the valid space entirely either; for any given type system, there are valid programs that are rejected, and there are invalid programs that are accepted.

Not so simple math

The goal of type system research is to both accept more valid programs and reject more invalid programs. Let's consider these three programs in three different languages, which implement one step of a divide-and-conquer list reduction strategy.
     def pm(x, y, z):                # Python
         return x + y - z
     
     pm x y z = x + y - z            -- Haskell
     -- inferred as Num a ⇒ a → a → a → a
     
     int pm(int x, int y, int z) {   /* C */
       return x + y - z;
     }
First, the expressive problem in C is easy to spot: you can only add and subtract ints. You have to reimplement this for each number type, even if the code stays the same.

The Haskell expressive problem is a little more obscure, but more obvious given the inferred type: all the numbers must be of the same type. You can see this with some partial application:
     pm (1::Int)      -- Int → Int → Int
     pm (1::Integer)  -- Integer → Integer → Integer
     pm (1::Float)    -- Float → Float → Float
The Python version works on a numeric tower: once you introduce a float, it sticks. This may be good for you, or it may be bad. If you are reducing some data with pm and a float sneaks in there, you won't see it until you get the final output. So with dynamic promotion, pm works with everything, even some things you probably don't want.

There are adjustments you can make to get the Haskell version to be more general, but this all depends on the kind of generalization you mean. This is a matter of continued innovation, even in the standard library; many commonly used libraries provide alternative, more generic versions of built-in Prelude functions, such as fmap for functors, one of many, many generalizations that work with lists, in this case replacing map.


Footnotes

[1] Use whatever meaning you like for “valid”, but if you want something more formal, perhaps “it terminates” will suffice.

Sunday, April 1, 2012

“Inference” is “proof assistance”.

As a Lisper, I'm used to just writing out some code that more or less expresses what I mean, then trying it out. I don't want to mess around with proving that what I'm writing makes sense. Moreover, when I first started learning Haskell, I didn't know nearly enough to begin proving what I meant.

Fortunately, Haskell can figure out all the argument types and return types of very complex functions.¹ You know how to write a function that applies a function to each element of a list, and then combines all the resulting lists into one, so just write it:

    concatMap _ [] = []
concatMap f (x:xs) = f x ++ concatMap f xs
-- inferred type of concatMap is (t → [a]) → [t] → [a]

That's pretty nice; I didn't have to specify a single type, and Haskell figured out not only the types of the arguments and results, one of which was itself a function type, but figured out the precise level of polymorphism appropriate. A frequent mistake when trying to guess this type is writing (a → [a]) → [a] → [a], which is not as general as the inferred version above. It will compile, but unnecessarily (and often fatally) restrict users of the concatMap function.²

So inference helps you prove things, often avoiding or explaining generalizations you didn't think of. It is a “proof assistant”. It greatly aids in refactoring, if you continue to rely on it, as you have to fix your proof in fewer places when you change the rules. It's an absolutely vital tool for entry into the typeful world, when you frequently know how to write a function, but not how to express its true, maximally polymorphic type.

Unfortunately, the “proof assistant” can't figure out absolutely everything. Moreover, the semantics of the language and type system affect how much the assistant can prove.³



Footnotes

[1] Haskell is really figuring out “the types of very complex expressions”, but that doesn't sound quite so good, despite being quite a bit better.

[2] As it happens, we've restricted ourselves to lists, where concatMap actually makes sense for all monads, but that's a result of our using the list-only operations for our implementation, not a failure of the type inference. In Haskell terms, concatMapM f xs = join (liftM f xs), which is inferred as a Monad m ⇒ (t → m a) → m t → m a. Other generalizations are possible, and you can accidentally lock them down in exactly the same way as concatMap, including to our original inferred type.

[3] To be overly general, features like mutability and looking up functions by name on a receiver type make inference harder. These are the rule in Simula-inspired object-oriented environments, making inference harder in OOP, and conversely, easier in functional environments. For example, in the Java expression x.getBlah(y), you can't infer anything about getBlah until you know the type of x. But in Haskell, getBlah has one known type, albeit perhaps polymorphic or constrained by typeclasses, which can be used to infer things about x and y without necessarily knowing anything else about them.

Thursday, March 29, 2012

With a type system, whether you can write a program depends on whether you can prove its correctness.

The trouble with bad type systems is that you have to use “escape hatches” pretty frequently. In C and many of its derivatives, these take the form of casts, which, in type terms, are like saying “I can't prove this even a little bit, but trust me, it's true. Try it a few times and you'll see.” The traditional cast system is very broad, as it must be to account for the shortcomings of lesser type systems. No one wants to reimplement the collection classes for every element type they might like to use.

After being so impressed by the power of Haskell's inference, many people next discover that they can't put values of different types into lists.¹ Well, that's not quite true, you can always chain 2-tuples together, but that's not what you really mean. Well, what did you mean?

Oh, well, I meant that sometimes the elements of my list are integers, and sometimes they're strings.

Okay, no problem. Put the integer type and string type together as alternatives in a single type:
     data IntOrString = AnInt Int | AString String
     [AnInt 42, AString "hi"] -- has type [IntOrString] 
No, I meant that it's alternating integers and strings, one of each for the other.

Well why didn't you say so!
     data IntAndString = IntAndString Int String
     [IntAndString 42 "hi"] -- has type [IntAndString] 
You can't just stick integers and strings together in a list without proving something about what you mean. To write any program typefully, you have to prove that it sort of makes sense. In the former example, you really meant that each element could be either one, and you have to prove that it's one of those, and not, say, a map, before you can put it in the list. In the latter example, you have to prove that you have exactly one string for each integer that you put into the list.

This permits a more analytical approach to programming than can occur in latent-typed systems. Let's say you had the [IntOrString], and you realized it was wrong and changed it to [IntAndString] in one module. You have two other modules that are trying to use the lists, and now they don't work, because you didn't prove that you had one string for each integer in those modules. Now nothing loads, and you have to jump around for a bit fixing your proofs until you can test again. This separates the task into two phases: one where you're only thinking about and testing the proofs, and the other where you're thinking about and testing the behavior.

I don't think this is an unqualified improvement over the latent-typed situation. On one hand, breaking tasks down into little bits is the foundation of human software development. Moreover, this example clearly helped us to clarify what we meant about the structure we were building. On the other hand, sometimes I prefer to focus on getting one module right on both type and runtime levels before moving on to the next. This is harder to do with most typeful programming languages, as type errors naturally cascade, and types both described and inferred usually influence runtime behavior.


[1] Haskell also has escape hatches, but using them is viewed rather like gratuitous use of eval is by Lispers. Whereas most C and Java programs use casts, very few Haskell programs use Data.Dynamic, just as very few OCaml programs use Obj.magic.

Sunday, March 18, 2012

A Lisper's perspective on “new hotness” typeful programming languages

A few years ago, I didn't care about functional programming. A year ago, it would have been unthinkable for me to work with a bunch of type system fanatics. I've been a Lisper for a long time, very much disliking anything breaking the Lisp mold, and it was just a little over a year ago that I learned, and came to appreciate, Haskell and the advantages it provides.

This is how I perceive the modern world of typeful programming, as a programmer who most naturally thinks in Lisp, with some experience in that area and a relatively newfound appreciation for it.

I won't discuss the benefits of immutable, persistent data structures, except where it naturally comes up in discussion of types. Clojure demonstrates that you don't need fancy type systems to get many of the advantages of immutable data. Were I to take on a large project in Common Lisp now, I would certainly try to use Funds or some implementation of Okasaki's data structures wherever beneficial, but I don't care to discuss that.

I will be similarly mute on the benefits of Haskell-flavored normal-order evaluation, for similar reasons. They will come up more often in relation to type systems, though.

I've broken up the discussion into simple assertions and discussion of them. You won't find rigorous logical backing of my statements, merely the empirical and anecdotal, because the former has already been done quite well elsewhere, and won't be as fun for me.

Here I keep links to articles already posted. The unlinked articles have been written, but not posted yet, for the sake of cadence.

  1. Type systems prove things about your programs.
  2. Optimization is just a side benefit.
  3. Type systems help with “a class of errors”: factual, but not true.
  4. C and Java do not have good type systems.
  5. With a type system, whether you can write a program depends on whether you can prove its correctness.
  6. “Inference” is “proof assistance”.
  7. Some type systems are much better than others.
  8. More type system features can make proofs harder to write.