News for hackers. Stuff that matters.
Re:Curry-Howard, the Ontological Ultimate by rbehrends on Wednesday October 15, 2014 @11:59AM (#8459118)
One problem with this talk (and many other talks about static typing) is that it seems to take at faith value the common claim that static typing is a net benefit for program correctness because it prevents programs from compiling that would otherwise create runtime errors (e.g., at around the 13 minute mark and again after the 18 minute mark). [1]

This seems like it's just common sense, but common sense claims do not always hold up in science and (as with many other claims regarding software engineering benefits that presumably derive from this or that language feature), it has rarely been tested.

This is not surprising: most computer science departments don't have the infrastructure to do work that involves human test subjects (unlike, say, psychology departments). Not only is there an ethics review board that has to sign off on such tests (no matter how harmless they may seem), creating meaningful tests involving non-trivial programming tasks can be pretty involved (a talk by the author of the first paper I discuss below was that one problem with the study was that it had been very expensive).

But at least some such tests have been done, and the conclusions are not necessarily what common sense would tell us.

Consider for example, the following series of papers:

Hanenberg, S. An Experiment About Static and Dynamic Type Systems - Doubts About the Positive Impact of Static Type Systems on Development Time. In Proceedings of OOPSLA/SPLASH 2010. ACM, Reno 2010. [2]

From the conclusion: "In this paper we presented results of an experiment that explores the impact of static and dynamic type systems on the development of a piece of software (a parser) with 49 subjects. We measured two different points in the development: first, the development time until a minimal scanner has been implemented, and second the quality of the resulting test cases fulfilled by the parser. In non of these measured points the use of the static type system turned out to have a significant positive impact. In the first case, the use of the statically typed programming language had a significant negative impact, in the latter one, no significant difference could be measured."

Now, that is one data point that only relates to the initial development of a piece of software, too (and as we'll see in a moment, it's not as though dynamic typing is a free lunch, once we look at maintenance tasks), but it does contradict common sense: The defect rate of the statically typed software is not actually better (at least not in a statistically significant way). Earlier studies had also shown that statically typed languages (unsurprisingly) did have benefits over languages that performed neither compile-time nor runtime type checks (such as ANSI C vs. K&R C w.r.t. function arguments).

Now, a follow-up paper:

Kleinschmager, S.; Hanenberg, S.; Robbes, R.; Tanter, É. & Stefik, A. Do static type systems improve the maintainability of software systems? An empirical study. IEEE 20th International Conference on Program Comprehension, ICPC 2012, Passau, Germany 2012, S. 153-162. [3]

Three conclusions from this paper on the effect of static type systems on software maintenance: (1) "Static type systems help humans use a new set of classes." (2) "Static type systems make it easier for humans to fix type errors." (3) "For fixing semantic errors, [...] no differences with respect to human development times [was observed]."

The paper also references a number of other studies with related results that may be interesting.

A second follow-up paper was the following:

Spiza, S. & Hanenberg, S. Type Names without Static Type Checking already Improve the Usability of APIs (As Long as the Type Names are Correct) - An Empirical Study. Proceedings of the ACM Conference on Aspect-Oriented Software Development, AOSD '14, Lugano, Swizerland 2014. [4]

From the abstract: "This paper describes an experiment with 20 participants that has been performed in order to check whether developers using an unknown API already benefit (in terms of development time) from the pure syntactical representation of type names without static type checking. The result of the study is that developers do benefit from the type names in an API’s source code. But already a single wrong type name has a measurable significant negative impact on the development time in comparison to APIs without type names."

What we're seeing is that while there do seem to be measurable benefits from static typing, the actual nature of these benefits may not be what one may expect on the basis of common sense alone (it's actually even more complicated than I can convey in this brief summary).

[1] To be clear, the talk makes many other immensely sensible points, and I don't think there's even enough material to conclusively say this one is right or wrong; my point is that it's essentially unproven either way, and that there is evidence that our intuition may be wrong here.

[2] https://courses.cs.washington.edu/courses/cse590n/10au/hanen...

[3] http://pleiad.dcc.uchile.cl/papers/2012/kleinschmagerAl-icpc...

[4] http://dl.acm.org/citation.cfm?id=2577098

Re:Curry-Howard, the Ontological Ultimate by bkirwi on Wednesday October 15, 2014 @12:57PM (#8459750)
Just took a quick look at paper #2, which is quite fascinating -- to try and isolate the effects of static / dynamic typing, they developed two slightly different programming languages which varied along only this axis.

I have some sympathy with this approach, but I'm not convinced you can actually separate things in this way. The type systems I actually find useful are not just a static analysis layer, but have significant impacts on the semantics of the language and the way libraries are designed. I'm not sure you could just 'turn off' the type system in Haskell and have anything even remotely sensible, for example.

I sometimes wonder if there's enough mature open-source projects in the wild now to be able to draw some statistical conclusions about the long-term effects of language choice, but that would be quite a project...

Re:Curry-Howard, the Ontological Ultimate by StefanKarpinski on Wednesday October 15, 2014 @01:22PM (#8460040)
> I'm not sure you could just 'turn off' the type system in Haskell and have anything even remotely sensible, for example.

You can actually do exactly this:

https://ghc.haskell.org/trac/ghc/wiki/DeferErrorsToRuntime

Of course, the type system doesn't vanish but checking types is deferred until runtime, turing Haskell into a dynamic language with an unusually elaborate tag system.

Re:Curry-Howard, the Ontological Ultimate by jules on Wednesday October 15, 2014 @05:01PM (#8461705)
It's still not comparable to a dynamic language however. Simply constructing a list [1, "Hello"] will already produce an error. Dynamic languages usually allow this, and only signal errors when the values are used in an erroneous manner, like 1 + "Hello". It does exactly what it says on the tin: it displays type errors that were found at compile time with the same type system that regular Haskell uses, but the actual displaying is deferred until run time. There is no actual tag checking going on at run-time.
Re:Curry-Howard, the Ontological Ultimate by CHY872 on Wednesday October 15, 2014 @02:18PM (#8460581)
It does make Haskell a dynamic language, but also isn't really what's meant. Generally when people compare statically typed languages and dynamically typed languages, what they are doing is comparing the various ways in which the type system imposes restrictions.

The way in which Haskell differs most strongly and obviously from Ruby is not that it catches the type errors at compile time - but that the type errors can be caught at compile time. This in general allows smarter tools - compare Eclipse for Java and the 'type hierarchy', 'find method calls', many refactoring calls and the far less rich tools available for Python.

Re:Curry-Howard, the Ontological Ultimate by zwieback on Wednesday October 15, 2014 @12:28PM (#8459398)
Thanks so much for this point. I think the key here is conclusion (3) about semantic errors.

I remember endless discussions about the Liskov Substitution Principle and how it relates to subtyping/subclassing. I think what people easily forget that static types do almost nothing for semantics and the notion of "behavioral subtyping" is a lot more interesting but also a lot more elusive.

And I say all this as a lifelong static typer, by the way, and not even of the fancy Haskell variety. I know what not to expect from static type checking so I'm a lot happier with what it does provide me.

Re:Curry-Howard, the Ontological Ultimate by jhpriestley on Wednesday October 15, 2014 @01:01PM (#8459798)
Before even loading up the papers I knew they'd be using some horseshit type system like Java's.
Re:Curry-Howard, the Ontological Ultimate by rbehrends on Wednesday October 15, 2014 @01:08PM (#8459895)
The programming tasks did not require complex data structures (such as a scanner and parser), so one would not expect Java's type system to be a limiting factor.
Re:Curry-Howard, the Ontological Ultimate by mej10 on Wednesday October 15, 2014 @03:37PM (#8461162)
This comment alone is enough to make Haskellers (or other proponents of good type systems) not take this seriously.

Anything trying to cast broad strokes about the usefulness and effectiveness of type systems can't use a language with a type system like Java's.

Re:Curry-Howard, the Ontological Ultimate by AnimalMuppet on Wednesday October 15, 2014 @06:48PM (#8462286)
And your comment is enough to make people not take you seriously. You sound like a stuck-up jerk rather than a thoughtful person.

Perhaps you could explain exactly what it is about Java's type system that makes it not worth even discussing. That would be a comment that was actually useful. (And don't say something like "because Java doesn't have higher-kinded types". We know that it doesn't. What about that lack makes it not even worth discussing?)

Re:Curry-Howard, the Ontological Ultimate by mej10 on Wednesday October 15, 2014 @07:31PM (#8462446)
I stated the problem with citing that research when trying to appeal to people familiar with Haskell-like type systems (as in the linked blog post).

My real point is that you can't really draw strong conclusions from this research when talking about type systems in general. If you wanted to say "It doesn't seem like type systems like Java's improve productivity" then I wouldn't have any issues, and would probably even agree.

> You sound like a stuck-up jerk rather than a thoughtful person.

I will agree that I phrased what I said a little harshly, but damn.

Re:Curry-Howard, the Ontological Ultimate by AnimalMuppet on Wednesday October 15, 2014 @08:04PM (#8462563)
OK, now you sound like a thoughtful person that I can actually have a conversation with. And I probably responded a bit overly harshly, too.

But I keep seeing this "Java's type system is essentially worthless" idea, tossed off glibly as if it was God's own truth, and I've never seen a justification for it. I get that it's not Hinley-Milner. I get that it doesn't have higher-kinded types. Why does that make Java's type system worthless?

Re:Curry-Howard, the Ontological Ultimate by rntz on Wednesday October 15, 2014 @11:19PM (#8463185)
As a type system, purely formally speaking, Java is... well, it's just kind of OK.

It has parametric polymorphism. It gets subtyping & co-/contra-variance right -- for generic types only, not arrays, and requires explicit annotations ("extends", "super"). It can express higher-order functions. Its primary formal weakness compared with, say, Haskell98 or SML, is the lack of higher-kinded types (ignoring for the moment the issue of Haskell-style typeclasses or ML-style modules & functors), which is a pretty big weakness but not a game-killer (see: Rust, Elm).

But pragmatically, it's a pain in the ass to work with. (Possibly this has improved since I worked with it. I hope it has!) It has a weird "everything must be an object" view of the world; it requires a file for every type I wish to define (barring nested classes, and anonymous classes - the latter of which is a notable but late improvement). Expressing HOFs is possible, but very unpleasant (AIUI it's gotten better lately). And just to top it all off, it doesn't have type inference, which just makes everything a chore.

The way I see it, Java is playing catch-up with the innovations introduced by more forward-thinking languages. It seems doomed to being forever a middle-of-the-road language. Which is... well, it's just kind of OK.

But it's not gonna inspire devotion, and people who worked with it when it really did suck (perhaps it still does, I dunno) are gonna remember that and hate it.

Re:Curry-Howard, the Ontological Ultimate by AnimalMuppet on Friday October 17, 2014 @12:37PM (#8471805)
Thanks for the answer. But could you clarify something for me? What's the difference between higher-order functions and higher-kinded types?

And, yeah, Java's type system... I'm not going to claim enthusiasm, merely that it seemed adequate for what I wanted it to do.

Re:Curry-Howard, the Ontological Ultimate by dragonwriter on Friday October 17, 2014 @12:54PM (#8471926)
> But could you clarify something for me? What's the difference between higher-order functions and higher-kinded types?

roughly, the relation is:

(type constructor):(simple function)::(higher-kinded type):(higher-order function)

That is, a higher-kinded type is a type which takes a type constructor as one of its parameters, in the same way that a higher-order function is a function that takes a function as one of its parameters.

Re:Curry-Howard, the Ontological Ultimate by zak_mc_kracken on Wednesday October 15, 2014 @10:01PM (#8462905)
Obviously, it's not worthless, that's just hyperbole, but it's sad to see people who would probably be the first to say that they are reasonable, evidence-based, pragmatic computer engineers fall into the manichaean trap that is extremism: either something sucks (Java) or it's awesome (Haskell).

The truth is that Java's type system is a bit in-between. It's a reasonable type system that's tractable for a huge portion of the developer community (hence its success) but which falls short of some required qualities to be able to show proofs by applying the Curry-Howard isomorphism.

Re:Curry-Howard, the Ontological Ultimate by rntz on Wednesday October 15, 2014 @05:22PM (#8461850)
Parsing, at least, absolutely can benefit from a powerful type system: consider Haskell's Parsec library, which uses monads & monad transformers to express a powerful parser combinator system.
Re:Curry-Howard, the Ontological Ultimate by rbehrends on Wednesday October 15, 2014 @06:33PM (#8462216)
Writing a parser combinator library does not require a powerful type system, especially not a custom one for a specific task (the students who were doing the scanner/parser task were limited to an environment where they had no access to third-party libraries, not that any existed for the language they were given). For a simple parser combinator implementation from scratch you require nothing more than basic types and the type of whatever AST you're generating. Parametric polymorphism is useful when you want to write a reusable parser combinator library, something that wasn't necessary, but even then you don't really need more than that (see other existing parser combinator libraries).

Higher order functions can make your life easier, but note that the students had access to a Java-like language (of which there was both a statically and a dynamically typed version) with Ruby-style closures, so that wasn't an obstacle.

Re:Curry-Howard, the Ontological Ultimate by rntz on Wednesday October 15, 2014 @11:01PM (#8463121)
Fair point.
Re:Curry-Howard, the Ontological Ultimate by dragonwriter on Wednesday October 15, 2014 @05:46PM (#8461996)
> Parsing, at least, absolutely can benefit from a powerful type system: consider Haskell's Parsec library, which uses monads & monad transformers to express a powerful parser combinator system

But AFAICT, you don't really need type-system support to use monads or monad transformers -- Haskell's purity, static typing, and use of monads for IO forces Haskell users to become familiar with monads, which may encourage Haskellers to develop the skill to use them for other purposes, but there is nothing stopping you from using monads and monad transformers in a dynamically typed language.

Re:Curry-Howard, the Ontological Ultimate by rntz on Wednesday October 15, 2014 @10:56PM (#8463100)
No, you don't. But the question at hand isn't using a dynamically vs. a statically typed language, it is, given that you are in a statically typed language, is a Java-style one sufficient?

Indeed, this is one of the benefits of dynamically typed languages: you're not restricted to any particular type discipline; you don't have to worry that the type system of the language you're in is too restrictive.

OTOH, if you want it to be easy to write reusable code, having static typeclasses with type inference can be quite useful. You could write a monad transformer stack in a dynamically typed language, but you can't always write code that's generic across any monad without explicitly passing around an object that represents the monad in question. (Racket's "units" might be a reasonable solution to this problem, though.)