Saturday, June 14, 2014

The trouble with weak static types

I got to this conclusion in a roundabout way, then I discovered there's a much simpler way to get there, so let me start there first.

JSON

In a dynamic language like Python, JavaScript, Smalltalk, or the non-C part of Objective C, dealing with JSON is so easy you barely even notice you're doing it. You have heterogeneous arrays and hetereogeneous dicts, so you can parse JSON to native objects, process them with the usual subscript operators, and generate JSON from them.

In a static language with a strong type system like Haskell or OCaml, it's arguably even easier. You have a recursively-defined ADT which is any of the base types, an array of this type, or a dict mapping strings to this type. You can parse JSON to instances of that ADT, process it with the usual subscript operators, generate JSON from them.

Even without ADTs, C++ templates are powerful enough to achieve the same idea, albeit more verbosely.

Whichever way you get there, your collections are real collections that can be handled by the same duck-typed, monadic, or STL functions as any other types. Duck typing or type inference works exactly as you'd expect—e.g., when you call foo on every member of bar and bar[1] is a string, you get foo<string>(bar[1]). The dynamic version gives you a TypeError exception (or calls out to an application-supplied hook) if you try to do something illegal, like JSON-ifying a collection with a function or socket in it. The static versions are even better: anything that could conceivably be caught at compile time is a compiler error, so you only have to check for runtime errors for bad data, not for code errors.

But Java's type system can't even come close here. Unlike C++ templates, Java generics are no help at all. Even besides the lack of inference, it's just not possible to describe the types you need. The best you can do is store a dictionary or array of "variant" objects, which basically means you cast everything to void* and back, and then fake dynamic types on top of that, then use checked casts to do all of the type checking Haskell or C++ would do explicitly, and at runtime. This is a gigantic pain.

Of course you can remove some of that machinery and just have unsafe code that crashes with the wrong data and is still a big pain. Or you can try to build opaque JSON-related types with special methods to access and manipulate them, which means the objects aren't even collections at all anymore. But there's nothing you can do that doesn't suck.

The joke is that languages like Java give you the safety of dynamic typing with the flexibility of static typing, but the reality is even worse than the joke; a dynamic language with properly duck-typed APIs is a lot safer than a static language that has to cast.

From what I can tell, Swift is just like Java here. To deal with JSON, you effectively fall back to ObjC and its dynamic types, and then either explicitly cast values, or call special accessor methods, to get back to static-land.

Accumulate

Getting back to the first place where I ran into this problem: I've been trying to convert Python's itertools module to Swift, more as an exercize in learning the language than for any particular purpose, and I've run into a few stumbling blocks. The first insurmountable one was with accumulate.

Accumulate takes a Sequence (an Iterable, in Python terms) and a function and generates a running total: x[0], func(x[0], x[1]), func(func(x[0], x[1]), x[2]), etc. In other words, it's a cumulative reduce/fold function. The function is optional, defaulting to addition. Here are examples of the four use cases, including the one that's nonsensical:
    >>> list(accumulate(range(1, 6))
    [1, 3, 6, 10, 15]
    >>> list(accumulate(range(1, 6), mul)
    [1, 2, 6, 24, 120]
    >>> list(accumulate([{1,2,3,4,5,6}, range(5), {i for i in range(100) if i%2}], set.intersection))
    [{1, 2, 3, 4, 5, 6}, {1, 2, 3, 4}, {1, 3}]
    >>> list(accumulate([{1,2,3,4,5,6}, range(5), {i for i in range(100) if i%2}]))
    TypeError: unsupported operand type(s) for +: 'set' and 'range'
In Python, as you'd expect, if you try the nonsensical use case, you get a TypeError. Of course accumulate doesn't have to do anything special; adding two non-addable values always raises a TypeError, and it passes through accumulate because that's the point of exceptions.

What about C++? Well, you could implement this with partial specialization, overloads with either + or a trait, or parameter with a default value of add; thanks to type inference (and SFINAE, in some cases), all of these will generate working code, with no runtime checks, for all three valid uses, and fail at compile time for the invalid use. That's ideal. And all without you having to write the more hideous of the types yourself, thanks to inference.

It's a little harder to compare languages like Haskell, because most of the well-known ones have neither overloads nor default parameter values. But it should be pretty obvious that if you found a way to add some overload system to a language like Haskell (presumably giving up currying) so the four separate functions had the same name, you'd get a compile-time error trying to call the one with the default function with a non-addable type.

In Java or C#, the type system isn't powerful enough to handle this directly, but you can at least fake it and get the Python-style behavior with runtime checking. It sucks, but not too badly.

Swift and accumulate

In Swift, the type system has the same problem as Java's, but you can't even fake it with runtime checking either.

Partly this is because Swift doesn't do exceptions, which are exactly what you want here (if you can't get compile-time errors). Your Sequence can't produce nil, because generate returns GeneratorType, not GeneratorType?. Maybe your Generator could produce nil (although I haven't been able to get that to work), but that would just be wrong; that would mean that you successfully generated an empty sequence, not that you failed. So, the right thing to do is a (runtime) fatal error. In most cases, that seems like the wrong thing, but trying to accumulate a sequence of non-addable objects with the addition function is basically a fatal error in your code.

Unfortunately, there's no way to do that either. Here's the obvious attempt:
    struct Accumulate
            : Sequence, Generator {
        var generator: S.GeneratorType
        var value: T?
        var f: ((T, T)->T)
        init(sequence: S, f: (T, T)->T) {
            self.generator = sequence.generate()
            self.value = generator.next()
            self.f = f
        }
        func generate() -> Accumulate {
            return self
        }
        mutating func next() -> T? {
            let thisvalue = value
            if let nextvalue = generator.next() {
         value = f(value!, nextvalue)
            } else { value = nil }
            return thisvalue
        }
    }

    func accumulate
            (sequence: S, f: (T, T)->T = { $0 + $1 }) -> Accumulate {
        return Accumulate(sequence: sequence, f: f)
    }
But this will just fail with "could not find an overload for '+' that accepts the supplied arguments". Why? Well, you're creating a single generic Sequence type, and a generic function that tries to instantiate that type with a function that adds, no matter what the associated types are. That's illegal. (In C++, it isn't a problem, for two reasons. First, you're defining a schema of separate types, and a schema of separate functions, and instantiating the types that have addable elements is perfectly legal with the adding function. Second, depending on which of the mechanisms you use for defining things, you're going to end up with either a function or a member that will raise a compiler error if instantiated on the wrong type, but that will only happen if you actually try to call accumulate with the default function on a non-addable type; a function you never instantiate never raises an error.)

So, how could you fix this? Well, you can eliminate that error just by adding more restrictions to the types. For example, define a Protocol for Addable, and require T to support Addable in Accumulate, and now everything compiles. But then you can't use Accumulate with non-addable types at all, even with a non-adding function.
Maybe you could define a type-dependent default function, using a trait class that does different things for different types? Nope; that would work with C++ templates, but not with Swift generics. Besides, what would you want the trait-selected function to do for non-addable types? There's no way to force an error if it gets called at compile time, or at runtime.

What about falling back to dynamic (ObjC) types here? Maybe if you took a function of (AnyObject, AnyObject)->AnyObject and converted each generated value to AnyObject and converted back in next you could get a fatal error or nil at runtime somehow. But that's not what you want. For the normal use, you want to be able to take an explicit (T, T)->T function the user has already built, or an inline closure that will be inferred as that type.

What about having a ((T, T)->T)? function, and if it's nil, calling a function that checks the types or converts to and from AnyObject, to hide the attempt to add possibly non-addable types from the compiler? That seems like it should work, but I haven't been able to get close enough to find out, I think because of 1.0-beta issues. For example, at least one of my attempts (either if-let-binding a function constant or calling a function with ! on the function variable, I forget which) crashed the compiler even if the rest of the function was empty. If it did work, we're just back to the question of what should happen here. I guess forcing a fatal error should be doable? Is there an idiomatic way to do that? Anyway, until I can write that, it doesn't really matter.

Solution

The only solution I can see is to define two completely separate functions: accumulate works on any type, but requires an explicit function; cumulative_sum is exactly the same, except it works only on addable types, and has adding as a default function.

It's also worth noting that defining the concept of "addable" isn't trivial in the first place. You'd think there would be some way to make the compiler infer it. But I haven't been able to figure it out. I can write a Protocol and explicitly register all the types I can think of, and explain to my users how to register any additional types. Or I could do a C++98-style traits class, with effectively the same results. But I can't just say "iff x+y compiles when x: T, y: T, T is addable". (Of course this has been a big problem in other languages as well—Concepts were supposed to be the coolest and most important feature in C++11, and instead they got bumped to a future version. But you'd think that designing a language from scratch would make it easier to solve. And there are languages that have solved it. And, of course, half the point of duck typing is to make this problem not come up in the first place…)

Fold/reduce/sum

In fact, even without trying to create a generator, you've got the same problem. Consider a standard fold/reduce/sum function. The fully general version takes a sequence, a combining function, a start value, and a transforming function, like this:
    func reduce(sequence, combine, start, transform) {
        for value in sequence {
            start = combine(start, transform(value))
        }
        return start
    }
But often you don't want to specify all of those values. For example, it's very convenient to sum an array without specifying 0 as the starting value. Or to reduce a list without transforming any of its elements. And so on.

In a language without neither overloads nor default values, your only choice is to figure out all the useful combinations, come up with a name for each, and write a whole slew of separate functions:
  • sum1(sequence)
  • sum(sequence, start)
  • sum1t(sequence, transform)
  • sumt(sequence, start, transform)
  • fold1(sequence, combine)
  • fold(sequence, combine, start)
  • fold1t(sequence, combine, transform)
  • foldt(sequence, combine, start, transform)
But Swift has both overloads and C++-style default values, right? Well, no, that's for methods; for functions, there are no overloads, and default values work like Python instead. But that's fine too. Could you write this all as one function with default values in Python? Sure:
    _sentinel = object()
    def fold(sequence, combine=lambda x, y: x+y, start=sentinel, transform=lambda x: x):
        sequence = iter(sequence)
        if start is _sentinel:
            start = transform(next(sequence))
        for value in sequence:
            start = combine(start, transform(value))
        return start
You might want to split off the sum and reduce cases anyway, just so sum([]) can be sensible (and zero—by specifying a default start of 0 instead of the first element), as Python's stdlib in fact does, but the point is, you have the choice to split things up however you want; you could make them a single function, as Python does with the cumulative iterator version, accumulate. In Swift, you don't have the choice. Let's try:
    func fold
            (sequence: S, combine: (T, T)->T = { $0+$1 }, 
             start: T? = nil, transform: T->T = { $0 }) -> T {
        var gen = sequence.generate()
        var current = (start == nil) ? transform(gen.next()!) : start!
        while let value = gen.next() {
            current = combine(start!, transform(value))
        }
        return current
    }
Notice a few other changes I had to make, from the good through the bad to the worse:
  • Swift's optional values mean I didn't need to define a custom sentinel (which is necessary in Python whenever the usual sentinel, None, could be a valid value in your domain).
  • Swift can't iterate over a generator, only a sequence, so if you want to pop a value off before the loop, you have to replace the for loop with a while-let-next loop. (The average Python programmer doesn't know how to map a for statement to a call to iter and a loop over next; in Swift, it's pretty much necessary information.)
  • Swift won't let you assign to an in parameter, even though that parameter is just a copy of the passed-in value. Parameters might be reference types, in which case you'd be changing the caller's variable, or they might be value types, in which case you'd just be changing a local—and this is pretty much invisible at the point of function definition, because it's up to the parameter type. This seems like an unavoidable consequence of other design decisions in Swift.
  • We can test that start is nil, and we can test that the generator is empty… but what happens if start is nil and the generator starts out empty?
In the code above (if it worked at all, that is), calling fold with no start and an empty generator would be a fatal error. That can't be right. Calling with no function and a generator of non-addable values, sure, that's clearly a type error in your code, but trying to sum up a generator of addable values that happens to be empty is either perfectly reasonable, or an error in the data rather than the code. In Haskell, Python, C++, C#, etc., it would be an exception. Clearly, the intention is that we're supposed to be using optional values a lot more in Swift than we'd use Maybe in Haskell, None in Python, nil in ObjC, etc. But look at the line of code. We can't use an if-let to try to bind current to start, because if that fails we have no way to bind it to gen.next(). Whatever we use, it can't be an expression (unless we cant to make current a T? just so we can check it immediately after binding it and return nil if it's nil and otherwise ! it everywhere). The most concise possibility I've been able to come up with is this hideous mess:
    var current: T
    if start == nil {
        if let firstval = gen.next() { 
            current = firstval
        } else {
            return nil
        }
    } else {
        current = start!
    }
That's 10 lines of code to do one thing: fill in a missing start from the generator, returning nil if empty. And maybe this is a sign of my lack of understanding of the language rather than of the language itself, but I don't think so. Swift is actually a very verbose language, on the level of Java, but it has some syntactic sugar to provide shortcuts in a few cases, like if-let binding or nil propagation, and in cases where they don't apply, you have to write things out the (very) long way. And the fact that these cases come up as soon as you go beyond the examples in the beginner's guide means that even novices are going to have to understand what the shortcuts are doing under the hood right from the start, and treat them as sugar rather than as abstractions.

But let's ignore all that. Does our function work now? Nope: "could not find an overload for '+' that accepts the supplied arguments". The same problem we had with accumulate, even in this simpler case. And again, the only way to fix that is to restrict it (via more where clauses for associated types) to only work on addable values. You can't write a fold function that has a default function for numbers, but not for other types. You have to write two separate functions, with separate names.

I think this is the biggest problem with Swift. The intent was obviously to build a strictly statically-typed language that doesn't rely on exceptions, but without all the complexity of C++ templates or Haskell abstract data types. But the reality is that Java-style generics, especially interacting with C++-style associated types, aren't strong enough to make that actually work. Falling back on dynamic ObjC types instead of always needing casts may make this better than Java (although I honestly haven't tried it enough to know that's true for sure), but it's in the same family, making the same mistakes that should have been obvious before they even started

Anyway, how does this fit into my attempt to port itertools? I guess it just means accumulate has to be split into accumulate and cumulative_sum. And I'll see if there are similar problems later.

2 comments:

  1. In Python, the sum function, when called with no start value, defaults to 0. In C++, it also defaults to 0. How is that possible? Well, it only works on types that are default-constructible, in which case the default is T(), which is the appropriately-typed 0 for any numeric type. (It could instead just literally use 0, in which case it would only work on types constructible from int, but that would be a bad idea—any pointer type is constructible from 0…)

    So, could we do the same thing in Swift as in C++? Sure, just define another protocol, DefaultConstructible. You just need to add "init()" to the protocol, and extension Int and so on to support that protocol, and… compile crash. From playing around a bit, I think this is not actually legal; Int does not actually have a no-parameters init, it has an init with one optional parameter.

    This is a fundamental difference in two ways of expressing constraints. C++ (informally, but in the future formally) does so in terms of expressions that must be valid; Swift, like Java and ObjC, does so in terms of methods that must exist. So, in C++, Foo(int i = 0) matches the constraint Foo(); in Swift, it doesn't.

    What about going the other way, requiring ZeroConstructible, by requiring an init that takes an integer literal instead of an Int? Similar problem as C++; e.g., String(0) is perfectly valid, and it's the string "0".

    So, there doesn't seem to be any way around providing separate sum and sum1 functions.

    ReplyDelete
  2. Oh, and I'm still not sure what sum1 (and fold1) should return for an empty sequence, or how to do so even if I know what I wanted to do (except for fatal error, of course, which is easy).

    ReplyDelete