News for hackers. Stuff that matters.
Re:Dynamic type systems are not inherently more open by UglyToad on Sunday January 19, 2020 @08:16AM (#22091277)
I think there's a perhaps irreconcilable disconnect between 2 camps here, but I also think that's ok and different people are allowed to like different things.

My experience, having gone from dynamic typing to static typing and now pining for more expressive type features in my chosen language is that static typing changes where you have to spend the cognitive complexity budget.

To my mind if I return to a piece of dynamically typed code written any time other than in the same session I have to load a whole mental model of the entire code, what types all the variables are, what expectations are attached to them, what mutation, if any, each method call performs. I suppose the trade-off is that advocates say you can prototype things more easily when requirements are not known.

With static typing I only need to load 2 things, the high level goal, what I need to achieve, and the local context where I need to make the change. The rest is taken care of by static typing, I can encode all that cognitive complexity in the types and I never need to think about it again. But as I say, that's how my brain works, yours might work differently and that's fine.

Re:Dynamic type systems are not inherently more open by pron on Sunday January 19, 2020 @10:12AM (#22091804)
Not all untyped languages are the same. E.g. Clojure now encourages specifying assumptions with spec annotations, some of them are stronger than those that can be expressed by Haskell's type system: i.e. they can succinctly express more about the "entire code" than Haskell's types. Types are not the only way to write formal assertions and assumptions about code. The difference between the two is in the level of sound inference that can be made (stronger with types) and the strength and expressivity of the assertions (stronger with contracts).

Of course, one could say we should have both, and some languages -- like Java with JML, C with ACSL, and SPARK, as well as some research languages like Whiley and Dafny -- do. But this could add complexity, and the interesting question is, if you could just have one, what are the relative merits of either? My guess is that types would be better for enforcing code organization and for tooling (more efficient AOT code generation, safe automatic refactoring, code completion), because automatic transformations require automatic and sound inference, while contracts are better for correctness because they can more easily express stronger properties of interest, and require less effort to verify them (types require formal deductive proofs, while contracts can use those or a range of other techniques that vary in their cost and their soundness).

In short, types are not the only form of formal specification, but the different forms do have different practical characteristics. What matters is not just what we want to know about the rest of the code, but how we want to use that information and how certain we need to be. Unfortunately, theoretical results tell us that we cannot have a perfect system that is always correct, cheap to use, and can allow us to express rich properties.

Re:Dynamic type systems are not inherently more open by chrisdone on Sunday January 19, 2020 @06:36PM (#22094950)
Techniques like Ghost of Departed Proofs are the most exciting thing to me as a casual correctness enthusiast. It acts as a means of combining static types with contracts.

Types are sound mostly because they are a stupid mini language, so easily enforced, like you said. Contracts are practical and convenient because you tend to write them in the language or a subset thereof that you’re checking. That’s hard to ignore.

GODP has you write a runtime check in regular code, and return as a result a proof value. Put that code in a module boundary. Then you have upstream functions expect a proof argument along with the value the proof is about. They’re tied together with a unique type variable (rank n or existential are the mechanisms of delivery for Haskell, but may differ in other languages).

head :: NonEmpty n -> Named n (List a) -> a

In this way you started from a dynamic, runtime piece of code, and ended up using a static type system to just ensure everything is passed around correctly which is trivial.

A single proof in this technique is nominal in the type (e.g. not null or positive or sorted ascending/descending), but combining them is done at the value level so there’s flexibility.

The bang for buck potential is large. I’m more interested in stuff like this than the dependent types direction that people are pushing for in GHC. If I wanted dependent types I have Agda, Coq, Isabelle, Idris, etc. to play with.

Re:Dynamic type systems are not inherently more open by dwohnitmok on Sunday January 19, 2020 @10:32PM (#22096105)
Actually techniques like the Ghost of Departed Proofs are precisely the reason I'm excited about dependent types (although with the caveat that you need some way of talking about erasure).

Contract systems in general have the problem that it is difficult to express higher-order properties about how functions should interact with each other or repeated invocations of themselves. For example, it's rather convoluted to express associativity with a contract system. Contract systems are very well-suited for imperative contexts (see e.g. Hoare Logic), where you have procedures rather than functions and you usually don't think about e.g. whether a procedure is associative or not. They work for functions, but are not as great a fit.

Dependent types allow for further expressivity, and, crucially, as long as you separate theorems from code (that is as long as you don't take Curry-Howard too seriously), there's no reason you're forced to prove a theorem with the type system if you find it too difficult.

Imagine:

concat : List a -> List a -> List a

concat = ...

concatSumsLength : (xs : List a) -> (ys : List a) -> size (concat xs ys) = size xs + size ys

concatSumsLength = proofByPropertyTest concatPropertyTest

concatPropertyTest = (1000 different lists concatenated together and then checking that their sizes add up)

There's no reason that concatSumsLength needs to be satisfied by a true implementation, unless you require that its value be usable at runtime. However, as Idris 2 shows, there's no need for that to be true (or even Coq with Prop vs Type). You can just annotate it as erased at runtime.

If you have a way of ensuring that certain values are never used at runtime, then there is no reason that your proof obligations must be met through satisfying the type checker.

Re:Dynamic type systems are not inherently more open by chrisdone on Monday January 20, 2020 @05:01AM (#22097759)
That's an interesting angle. Another way of saying it might be that GoDP on the face of it can make one-off proofs for a value. Proofs for a function requires making proofs about all possible inputs, which is where your property test comes in handy. I could have `Named a (List x -> List x -> List x)` as the function I'm proving things about.

With some template-haskell you could run the property test at compile-time, and then use that proof later (e.g. for an instance of Semigroup which would require a argument proof of associativity), in languages like Unison that never run the same test suite twice (due to Content addressable code), this would be feasible. Or just run the property in your test suite and hope that the developer runs the test suite often. GHC erases data types that aren't actually evaluated in many contexts, so we even have erasure too.

I like your angle!

Re:Dynamic type systems are not inherently more open by pron on Monday January 20, 2020 @06:20AM (#22098071)
> Contract systems in general have the problem that it is difficult to express higher-order properties about how functions should interact with each other or repeated invocations of themselves

Contract systems can express anything that can be expressed about a program. Some allow you to specify separate lemmas (e.g. see http://www.eecs.ucf.edu/~leavens/JML/jmlrefman/jmlrefman_toc...) . The difference between dependent types and contract systems is that contract systems can be verified by deductive proofs, or by a host of unsound techniques, while dependent types require deductive proof (or, in some experiments, other sound techniques like model-checking). If dependent types would accept unsound proofs, the soundness of the entire type system would be compromised to the point of undefined behavior.

The problem is that deductive proofs have so far shown significantly worse scalability than other formal methods, which is why most of formal methods research is looking elsewhere.

If dependent types could be made more flexible, they will be as good as contract systems.

Re:Dynamic type systems are not inherently more open by dwohnitmok on Monday January 20, 2020 @09:00AM (#22098817)
> If dependent types would accept unsound proofs, the soundness of the entire type system would be compromised to the point of undefined behavior.

This seems like too strong of a statement. Every language that allows for nontotal functions has a type system allowing for unsound proofs. This does not mean the type system is compromised to the point of undefined behavior.

Dependent Haskell is explicitly going to be unsound even in the presence of totality (type in type). Idris allows for partial functions by default (although you do need to annotate if you want to use it at the type level and the compiler doesn't know it's total). Dependent type systems are not required to be sound by any means.

If you lie to the type system you just blow up at runtime, e.g. with an exception. Same as in any other language.

Leaving that aside, my point is that as long as you don't need your proofs at runtime, you don't have to use a deductive proof with dependent types! Substitute the property check thing there with a model checker if you want 100% assurance, but you don't even need a sound verification! If you're okay with just 99% confidence instead of 100% then just do the property test and be done with it (that's my example with concat and chrisdone is talking about when you would run the property test). If you're feeling really adventurous just assert the statement without proof and move on. If you don't run it at runtime how you prove something or even if you do is up to you.

Also out of curiosity, how do you express that, say, a static method with two arguments is associative in JML or any other contract system, Hoare Logic based or otherwise? I suspect you can, but I also suspect it looks annoying and hacky where you essentially encode a function application counter in your ambient state and have to basically make an inductive statement. EDIT: ah ha in JML you have the keyword pure that extends Hoare Logic so I suppose you do an assert with pure? But then how do you express the general notion of associativity? By requiring purity as a precondition and then writing out the condition again? Can you specify purity as a precondition? I'm not sure how you do that, presumably you'd need JML to be able to recognize a SAM class and then be able to tie purity to that, which seems hard if not built-in.

Whereas with dependent types it looks very similar to the usual notation.

  (x, y, z : A) -> x `op` (y `op` z) = (x `op` y) `op` z
For

  op : A -> A -> A
More generally you can express associativity itself with:

  isAssociative : (op : a -> a -> a) -> ((x, y, z: a) -> x `op` (y `op` z) = (x `op` y) `op` z)
Re:Dynamic type systems are not inherently more open by pron on Tuesday January 21, 2020 @05:54AM (#22105823)
> If you lie to the type system you just blow up at runtime, e.g. with an exception. Same as in any other language.

That depends on the runtime type system. If you can switch an int for a string (which is not hard in a dependent type system -- rely on the output of some silly arithmetic function that you only tested and omit a proof and use it in some function that indexes types by integers, and you just might cast an int to a string), you will more likely get some UB and quite likely a security problem.

That's why I think that when it comes to correctness contracts are superior to types, and when it comes to tooling and organization, types are superior to contracts. Functional correctness is one area where flexibility is crucial, and soundness is never required because it's impossible anyway. Types, which are used for automatic transformation and code generation is one area where soundness is quite important; we shouldn't mix the two.

> Also out of curiosity, how do you express that, say, a static method with two arguments is associative in JML or any other contract system, Hoare Logic based or otherwise?

I don't know the arcana of JML, but I see no reason why, at least in principle, you couldn't do the same thing:

     pure
     \forall A x,y,z; foo(x, foo(y, z)) == foo(foo(x,y),z)
There's also no reason not to define a predicate `isAssociative`.

However, there is a difference -- not between specification with dependent types and contract systems, but between the semantics of the language where expressions mean something similar to "partial functions" (or even something similar to functions) and a language where they mean something else (like predicate transformers). In the latter, we don't in general represent computation as functions, so specifying something like associativity would normally be done as follows: define `isAssociative` on functions (not computations), and then specify that a computation computes a function (that is associative). That's how I would do it in TLA+, for example; I think that in Why3 as well.

Finally, it's important to remember that the very concepts can be different among languages. For example, all specifications of "higher-order" computations in functional languages (i.e higher order subroutines) become first order when you describe them in TLA+ (https://pron.github.io/posts/tlaplus_part3#higher-order-comp...). Lamport had this to say:

> Comparisons between radically different formalisms tend to cause a great deal of confusion. Proponents of formalism A often claim that formalism B is inadequate because concepts that are fundamental to specifications written with A cannot be expressed with B. Such arguments are misleading. The purpose of a formalism is not to express specifications written in another formalism, but to specify some aspects of some class of computer systems. Specifications of the same system written with two different formalisms are likely to be formally incomparable… Arguments that compare formalisms directly, without considering how those formalisms are used to specify actual systems, are useless.

The difference here is, then, not between specifying with types or with contracts, but between different formalisms.

Re:Dynamic type systems are not inherently more open by dwohnitmok on Wednesday January 22, 2020 @02:40AM (#22115454)
Well sure if you lie to your specs all bets are off. Buffer overflows, bounds checking, use after free (if you're in a non-GCed language), resource leakage, etc. You're always at the mercy of your runtime system as soon as you lie about your pre-runtime checks, no matter what system you use, types or otherwise.

That's different than UB in the type system itself, which if you lie to it at worst just becomes inconsistent, but although that sounds quite scary, it's not really a big deal if you're not using dependent types as a theorem prover and you know where the inconsistency stems from.

Now perhaps your contention is that dependently typed systems tend to have weaker runtime checking, which I still disagree with. You do have weaker runtime guarantees with Idris 1's native code generator and of Agda's code extractor, but this is not true of Idris 1 on JS or its other code generators, which inherit their hosts' runtime systems, or Idris 2's native code generator, which inherits Chez Scheme's runtime system.

RE computations and functions yeah I definitely overreached. I somehow completely forgot that Hoare Logic has the ability to have unrestricted first-order logic. I got too fixated on JML, where in retrospect the difficulties only come from the awkward way that Java tries to handle higher-order methods like reduce (that was my initial impetus, verification of parallel reduce). I totally forgot I've done the isAssociative property in Dafny before and there it's exactly as you say, it's a function that you then put on top of a method (Dafny's notion of "computations").

The Lamport quote is a good reminder not to poo-poo different formalisms, but I've had a great time with systems like Dafny. I don't think dependent types are the holy grail of verification. My contention in fact is that the gulf between dependent types and contracts is not as large you're making it out to be.

Dependent types break down if you have pervasive mutability, i.e. as in an imperative language, for which Hoare Logic is very well-suited for. You have to express the mutability at a type level that's also is transparent enough to the type system to make assertions which makes things very annoying. (And no I don't use mutability/imperative as dirty words, most of my day-to-day work is in imperative languages and that's just fine by me, a lot of algorithms flow more naturally as imperative ones).

But if you have a language where everything is immutable, dependent types are fantastically expressive. And as long as you don't use the type inhabitants at runtime, their "proofs" or lack thereof are also very flexible. Hell, you could even generate a runtime assertion from a dependent type if you wanted to and have the compiler automatically insert those in place! You could even do that generation in a user-defined library without compiler support if dependently typed languages supported typecasing and didn't impose parametric polymorphism in all cases (useful in a non-dependently typed language, less useful in a dependently typed one). They don't, but that's a different story (for all my excitement about dependently typed languages, there's so many other ergonomic hurdles to get over first, as is true of a lot of the current state of code-based verification tools).

Indeed, dependent types and contracts converge in many ways if you have pervasive immutability. The main difference is that dependent types are more integrated into the language and don't have as many contract-isms. An invariant required by a function becomes just another argument. A lemma is just another function. Those contract-isms are necessary in a mutable environment (it would be rather painful to try to drum up some sort of type-indexed loop monad to try to express the notion of a loop-invariant in a dependently typed language, especially if the loop accesses non-local resources), but are not so much in an immutable one.

Oh BTW, speaking of limitations of formalisms, I'm pretty sure you're right on Twitter that Hillel Wayne's hyper-property isn't actually truly a hyper-property and can be described with the temporal quantifiers TLA+ has. A better example (that I don't think can be expressed in TLA+) is something like "variable independence," the statement that for any behavior where a variable "a" takes on some trace, there is another behavior such that "a" has a different trace, but all other parts of the behavior are the same. That is you can delete "a" from your spec and nothing would look different, no behavior would ever change (this requires either quantifying over all predicates or manipulating behaviors directly). Another example would be something like "x 'usually' takes n steps" for some definition of usually (mode, median, average, anything that's not a strict upper bound). Even expressing "n steps" in TLA+ is kind of wonky, but do-able with an additional counter variable (although that makes TLC unable to check termination).

Oh and of course since you've linked your own TLA+ link, many many thanks for your TLA+ series. It was an invaluable source right alongside Lamport's own materials when I was learning TLA+ on my own.

Re:Dynamic type systems are not inherently more open by Silhouette on Sunday January 19, 2020 @01:54PM (#22093133)
My guess is that types would be better for enforcing code organization and for tooling ... while contracts are better for correctness

I see what you're getting at, but there is one other crucial difference: the types we're talking about here are usually checked at compile time, whereas the contracts we're talking about here are usually checked at run time. Although the latter may be more expressive if other things are equal, other things are very much not equal in this respect.

How much that matters depends on the nature of the software and how it is to be deployed and used. If you're writing a program for your own use, it might not matter much at all. If you're writing a program that is going to control a satellite and software maintenance after launch is extremely expensive if not impossible, it might matter a great deal.

Re:Dynamic type systems are not inherently more open by pron on Sunday January 19, 2020 @03:54PM (#22093997)
> whereas the contracts we're talking about here are usually checked at run time

No, they can be checked in many different ways, hence their power. They can be checked "statically", i.e. at compile-time, or dynamically. One approach is sound but requires more effort, while the other is cheap yet unsound -- and there is a spectrum in between the two extremes.

> If you're writing a program that is going to control a satellite and software maintenance after launch is extremely expensive if not impossible, it might matter a great deal.

Such programs often use formal methods that precisely use such contracts. Rich type systems (like Idris's) are virtually never used in practice in those cases. If you've heard of SPARK, it's a language that provides static verification of properties specified as contracts, not as part of the type system, and it is used in some safety-critical realtime applications.

Re:Dynamic type systems are not inherently more open by Silhouette on Sunday January 19, 2020 @05:46PM (#22094675)
No, they can be checked in many different ways, hence their power.

Sure, but the more dynamic ones that drift away from what a (good) static type system offers are exactly the ones that aren't amenable to automated proofs and so tend to be checked at run time.

Such programs often use formal methods that precisely use such contracts. Rich type systems (like Idris's) are virtually never used in practice in those cases.

As someone who has worked on relatively high-reliability systems, I can say with 100% confidence: it depends. This too is an area with a whole spectrum of possibilities, and some of those involve a degree of formal proof of algorithm properties but not a mechanically verified translation of those algorithms into implementation code. In such cases, a powerful static type system certainly can be a useful safeguard against introducing defects during the translation.

Re:Dynamic type systems are not inherently more open by pron on Monday January 20, 2020 @06:24AM (#22098085)
> Sure, but the more dynamic ones that drift away from what a (good) static type system offers are exactly the ones that aren't amenable to automated proofs and so tend to be checked at run time.

Not really. What contract systems allow you to do is to separate specification from verification. Type systems require that all of your specifications be verified with deductive proofs. This means that some deep properties either require a lot of work (using a type system such as Idris's) or are excluded from the type system at all. Contracts allow you to check a property in unsound ways, too.

As far as correctness is concerned, contracts do everything a type system can, but more flexibly. Type systems, however, have advantages related to tooling and efficient code generation by an AOT compiler.

> This too is an area with a whole spectrum of possibilities, and some of those involve a degree of formal proof of algorithm properties but not a mechanically verified translation of those algorithms into implementation code.

Even when formal proofs are used, the specification is done in a contract system, not a dependent type system.

Re:Dynamic type systems are not inherently more open by Silhouette on Monday January 20, 2020 @01:36PM (#22101043)
What contract systems allow you to do is to separate specification from verification. Type systems require that all of your specifications be verified with deductive proofs.

I think you're making the same point that I am, but perhaps from the opposite direction.

Of course contracts are more general, but the aspects of a contract that you can prove automatically in advance are similar to what you can typically do with a good static type system, and the limits of a decent static type system fall around the point that contracts become more powerful but only at runtime. This isn't an accident, it's a fundamental equivalence.

For example, you mentioned SPARK before. One of the interesting things about SPARK is the extra flexibility you have when adding constraints on integer data types. The proof system can verify certain properties (or warn you that it can't). That can provide safeguards against, among other things, some very common logic errors like out-of-bounds access to data structures.

However, the fact that we're dealing with integer values is very helpful in this respect. Lots of behaviour is fully specified no matter how much we manipulate those values. For the same reason, dependent type systems can often provide similar guarantees. The curious property of C++ templates that they allow integer as well as type parameters has allowed for all kinds of handy metaprogramming tricks along similar lines.

Now, suppose we're working in the much less convenient world of floating point values. It's still helpful to have warnings about, for example, potential underflow or overflow conditions, for all the same reasons. However, given the inherent imprecision of floating point data, it is impossible to prove such conditions in advance in almost any non-trivial case. You can certainly have a precondition on a relevant function that, for example, adding two input values must not entirely lose the smaller value due to loss of significance, but you won't find out about inputs that violate the contract until you run your program.

Even when formal proofs are used, the specification is done in a contract system, not a dependent type system.

You can do the specification in any number of ways. Unless you want to classify all of mathematics as "a contract system", which is true in a sense but so general as to lose any useful meaning of the term, your statement above is too strong.

Re:Dynamic type systems are not inherently more open by capableweb on Sunday January 19, 2020 @10:17AM (#22091827)
Also, the following part isn't necessarily because of dynamic typing vs static

> what types all the variables are, what expectations are attached to them, what mutation, if any, each method call performs

But more about what the language offers. Clojure for example, goes beyond types with it's abstractions (like seq, that can be applied to strings, lists, maps and so on) and normally stays away from mutation, but when needed, makes it really explicit and easy to find those mutations.

Re:Dynamic type systems are not inherently more open by yakshaving_jgt on Sunday January 19, 2020 @10:30AM (#22091905)
> Clojure for example, goes beyond types with it's abstractions (like seq, that can be applied to strings, lists, maps and so on)

Goes beyond types? Statically-typed languages can have polymorphism.

Re:Dynamic type systems are not inherently more open by roenxi on Sunday January 19, 2020 @04:05PM (#22094064)
Spec is at heart a data modelling system. So for example,

  (s/def ::integer integer?)
is very explicitly not a definition of an "integer" type. It is preparation to model some data x and check that the data will evaluate to true if someone uses the predicate (integer? x). However, this is obviously enough to implement a type system.

But you can also do some very loose things with spec that aren't done in a type system (I speak with a cheerful ignorance of type systems). Eg, I can spec a function so that one argument is smaller than the second. This allows my testing system to automatically generate the correct data to test my function.

So spec can used to implement a type system but also to implement things that aren't type systems.

Re:Dynamic type systems are not inherently more open by candeira on Sunday January 19, 2020 @07:54PM (#22095319)
> But you can also do some very loose things with spec that aren't done in a type system (I speak with a cheerful ignorance of type systems). Eg, I can spec a function so that one argument is smaller than the second. This allows my testing system to automatically generate the correct data to test my function.

Check out dependent type systems. These allow you to define, mindbreakingly enough, types that __depend on the values you assign at runtime__, and functions whose type depends on the values passed as arguments.

Don't ask me how it's done; it's all dark magic to me. All I know is that people who use dependent type systems claim they are very good at certain uses involving incoming streams of unknown data, like parsing binary protocols.

https://en.wikipedia.org/wiki/Dependent_type

Re:Dynamic type systems are not inherently more open by leshow on Sunday January 19, 2020 @12:30PM (#22092597)
Commented elsewhere here but static languages can do this also via ad hoc polymorphism or bounded polymorphism.
Re:Dynamic type systems are not inherently more open by pron on Sunday January 19, 2020 @10:19AM (#22091841)
Java's JML contract system [1] allows you to explicitly state which mutations a method performs as part of its contract.

[1]: https://www.openjml.org/

Re:Dynamic type systems are not inherently more open by fanf2 on Sunday January 19, 2020 @10:32AM (#22091918)
Why is seq “beyond types”? Isn’t it like a Rust Iterator trait?
Re:Dynamic type systems are not inherently more open by hopia on Sunday January 19, 2020 @10:39AM (#22091968)
What do you mean with going beyond types? Is it possible to define some unique compile time constraints on Clojure not related to the type system?
Re:Dynamic type systems are not inherently more open by dllthomas on Sunday January 19, 2020 @01:56PM (#22093152)
When spec was proposed I remember some talk of compile-time checking of some annotations. I don't know whether anything came of that, but in theory it would allow what you're talking about. That has no relation to seq, though, which is the kind of thing supported by many statically typed languages.
Re:Dynamic type systems are not inherently more open by nhumrich on Sunday January 19, 2020 @10:33AM (#22091929)
Your comment is spot on. But the opposite can also be true. I totally have the same issues you do at times by trying to understand types (which I feel type hinting, editors, and good variables names go a long way to help with). But I also find myself using a lot of cognitive load trying to get a correct type definition, etc (for the non simple tasks). Whether its trying to figure out how to get a certain object, because of the interfaces, factories, etc. Or trying to create a new object and trying to map things correctly. What if I just want to have a hash map full of varying object structures? (I am not saying its not possible, I am saying its a use of cognitive load)
Re:Dynamic type systems are not inherently more open by UglyToad on Sunday January 19, 2020 @10:48AM (#22092001)
Agreed, perhaps it's something like the difference between top-down vs bottom-up learning in teaching. People don't all use the same mental models and allowances need to exist for both groups. But I suspect this is true of most contentious topics in programming.

For what it's worth I definitely agree there can be a lot of overhead added by typed code especially in Java or C#, but I suspect it might have less to do with the type system and more with the enterprise-ness or otherwise of those code-bases. Designing a good typed API for other people maintaining the same code-base is difficult

Re:Dynamic type systems are not inherently more open by amelius on Sunday January 19, 2020 @08:54AM (#22091425)
Yes. Perhaps this is an indication that we actually need automated type annotation. E.g. you initially write/prototype your program in a dynamically typed form, then you click a "magic" button, and a tool converts your program into statically typed style.
Re:Dynamic type systems are not inherently more open by chongli on Sunday January 19, 2020 @09:11AM (#22091502)
This already exists in Haskell. Firstly, Haskell has type inference so you can write entire programs without any type annotations. Second of all, since type annotations actually help to document your code, it’s recommended as good Haskell style to annotate all top-level definitions.

To aid you in the latter task, you can press a key in your editor to fetch an automatically-inferred type for the name under the cursor and insert it into your code, then refine it as necessary if you find it to be too general (inference always gives the most general type possible).

Re:Dynamic type systems are not inherently more open by pron on Sunday January 19, 2020 @10:28AM (#22091892)
Type inference does not automatically "typify" your code. The type system -- whether the type annotations are explicit or the types are inferred -- determines which expressions are "well-formed" (i.e. syntactically correct), and so you can't write arbitrary code. E.g., in Haskell, you can know for a fact that at one call site a Maybe instance is Just, but whether you annotate your types or rely on inference, the type system will still force you to match on the constructor even though you don't really have to from a correctness perspective.
Re:Dynamic type systems are not inherently more open by PhineasRex on Sunday January 19, 2020 @01:01PM (#22092794)
If you're talking about the fact that you have to unbox the Maybe, that's not really related to type inference or static types but how "null" values are represented in the language.

If you're talking about exhaustiveness checks, you can disable those and use `-fdefer-type-errors` to compile programs which don't type-check.

Although I will say that most of the time when you have a Maybe instance that you know is Just, it means you're branching in the wrong part of your program.

Re:Dynamic type systems are not inherently more open by pron on Sunday January 19, 2020 @03:51PM (#22093979)
> If you're talking about exhaustiveness checks, you can disable those and use `-fdefer-type-errors` to compile programs which don't type-check.

Right, but if you were using, say, Idris, the program would type check. It's just that Haskell's type system is too weak. Disabling type checking is not what the question was about. The program is type-correct, yet not in Haskell's particular system.

> Although I will say that most of the time when you have a Maybe instance that you know is Just, it means you're branching in the wrong part of your program.

Perhaps, but that doesn't change the fact that if you write it in some way that is perfectly correct, Haskell's particular type system will still not accept your program.

Re:Dynamic type systems are not inherently more open by firethief on Sunday January 19, 2020 @01:30PM (#22092984)
If the reason you know your Maybe T is a Just _ is that you tested it locally: in any language that favors the Maybe pattern, the idiomatic way of performing that test makes the result available to the type system (destructuring / combinators / 'nads). On the other hand, if you know your Maybe is a Just because of non-local information, you will eventually turn out to be wrong :)
Re:Dynamic type systems are not inherently more open by pron on Sunday January 19, 2020 @03:49PM (#22093967)
No, you can know -- and even prove -- that at a certain callsite, a Maybe would be a Just, and if you were using a dependent type system, you can prove that in the type system (although it probably won't be automatically inferred -- you may have to work hard for the proof), but Haskell's type system is too weak to express such properties and such proofs, at least in the general case.
Re:Dynamic type systems are not inherently more open by hopia on Sunday January 19, 2020 @10:00AM (#22091740)
On what editor setup you get this kind of functionality with Haskell? I mean the auto-insert of the inferred types.
Re:Dynamic type systems are not inherently more open by chongli on Sunday January 19, 2020 @10:10AM (#22091795)
I’ve been out of the game for a number of years but I used something called ghc-mod [1] with its associated vim plugin [2] to get this functionality. Moving forward, it seems that all of the effort has moved over to Haskell IDE Engine [3]. It looks like this exact feature hasn’t been brought over yet but it is planned. In the mean time you could still use ghc-mod though.

[1] https://github.com/DanielG/ghc-mod

[2] https://github.com/eagletmt/ghcmod-vim

[3] https://github.com/haskell/haskell-ide-engine

Re:Dynamic type systems are not inherently more open by hopia on Sunday January 19, 2020 @10:19AM (#22091842)
Thanks for the tip! Haskell IDE engine is exactly what I've been using til now and would've been very pleased to find out it had such a convenient feature.

Ghcide is on my list to try next as it's gotten a lot of attention lately.

Re:Dynamic type systems are not inherently more open by jose_zap on Sunday January 19, 2020 @02:39PM (#22093469)
Yes, it already has a code command to automatically add top level type annotations. The caveat I that it can only work if you add -Wall to your compilations flags.
Re:Dynamic type systems are not inherently more open by danidiaz on Sunday January 19, 2020 @10:14AM (#22091817)
Re:Dynamic type systems are not inherently more open by hopia on Sunday January 19, 2020 @10:20AM (#22091851)
Template Haskell not working on ghcide has sadly been holding me back with it. I've heard great things about it otherwise
Re:Dynamic type systems are not inherently more open by jose_zap on Sunday January 19, 2020 @02:39PM (#22093474)
You can use HIE. It supports template Haskell
Re:Dynamic type systems are not inherently more open by pwm on Sunday January 19, 2020 @02:31PM (#22093415)
Recent ghcide can do it now as well as https://github.com/mpickering/apply-refact for hlint
Re:Dynamic type systems are not inherently more open by zitterbewegung on Sunday January 19, 2020 @08:58AM (#22091439)
Using Type inference[1] on a language could be able to figure out types in most situations.

[1] https://en.wikipedia.org/wiki/Type_inference

Re:Dynamic type systems are not inherently more open by azhenley on Sunday January 19, 2020 @09:50AM (#22091688)
Yes, but "Type inference has usability problems".

http://web.eecs.utk.edu/~azh/blog/typeinference.html

Re:Dynamic type systems are not inherently more open by leshow on Sunday January 19, 2020 @12:46PM (#22092695)
I'm curious why you quote this like it's a fact when it's an opinion. The understanding of type inference used as the basis for making the argument in that blog post is superficial. Type inference doesn't just allow you to leave off type information from variables. A good inference engine will infer the most generic type for variables (and functions!), it's a discovery that you can query the compiler for in order to do type driven development.

A full rebuttal of this blog post would take much longer, but suffice to say inference does the exact opposite of what they are claiming; it increases readability and usability.

Re:Dynamic type systems are not inherently more open by azhenley on Sunday January 19, 2020 @12:50PM (#22092730)
I quoted the title of my blog post. Do you have any evidence for your claim that it increases readability or usability?

A few human-subjects studies from different labs have recently been ran on this and the findings mostly agree with my opinions. Papers forthcoming.

Re:Dynamic type systems are not inherently more open by sweeneyrod on Sunday January 19, 2020 @04:40PM (#22094305)
If type inference damaged readability, we would expect companies/projects that use languages such as OCaml and Haskell where type inference is possible but not mandatory to have policies against it in their style guides. In my experience with OCaml, the widely agreed on style is to only annotate types of functions that are part of some public interface (although since this annotation is necessary to define the public interface of a library, it's not even necessarily true that type inference impairing readability is the primary reason for this).

Also, if lack of type annotations were a common problem, you would expect Java programmers who switch to Python to frequently want to annotate all their types. But as far as I know this is not the case: even now that mypy is becoming popular, people only annotate the types that it can't infer.

Re:Dynamic type systems are not inherently more open by azhenley on Sunday January 19, 2020 @05:19PM (#22094527)
Companies do have policies against using type inference (e.g., the use of var in C#).

But how would companies/people know if it damaged readability? There has been little research on this (a few studies are currently in peer review!) and our intuition about such things is often inaccurate. There are so many other confounding factors that it is hard to isolate just type inference/annotations.

Re:Dynamic type systems are not inherently more open by yawaramin on Sunday January 19, 2020 @06:36PM (#22094947)
> Companies do have policies against using type inference (e.g., the use of var in C#).

That's a language that historically has not had type inference. Any examples of companies mandating type annotations in historically type-inferred languages?

Re:Dynamic type systems are not inherently more open by azhenley on Sunday January 19, 2020 @06:42PM (#22094987)
Yes! Any company that has adopted MyPy or TypeScript often have policies for this. One team I spoke to at Facebook said that any new code should have type annotations. I believe Dropbox had a nice blog post about new code should have type annotations too. It is hard to get these details from companies/teams (and be allowed to talk about it).
Re:Dynamic type systems are not inherently more open by yawaramin on Sunday January 19, 2020 @07:32PM (#22095221)
That's because (a) these are not historically type-inferred languages–runtime typechecking doesn't count as type inference–and (b) the gradual typechecking approaches like Mypy and TypeScript often have a lot of type inference issues which force people to try to overcome them with manual annotations.

In languages with even reasonably good type inference you'll find that the idiom is not to annotate types at the very least inside function bodies. And in OCaml, which has principality of type inference i.e. the types it infers cannot be overridden and corrected by manual annotation, the idiom is to not annotate implementation files at all.

Re:Dynamic type systems are not inherently more open by sweeneyrod on Sunday January 19, 2020 @06:50PM (#22095029)
Do they mandate that only function types (and any ambiguous ones) should be annotated, or that all types (i.e. including those of local variables which mypy can infer) should be? I strongly suspect the former, which implies that they view type annotations more as a necessary evil to allow type checking rather than a benefit in their own right. After all, there was nothing stopping people putting "type annotations" in Python 2.5 code if you wanted, by writing `x = get_thing_count() # int`. But AFAIK no-one did that until annotations could actually be used to check type safety.
Re:Dynamic type systems are not inherently more open by leshow on Saturday January 25, 2020 @12:23PM (#22147306)
Typescript will infer the 'any' type by default in a lot of cases, that's the reason teams will mandate type annotations. It's really just not the same thing. These are bolt on type systems to dynamic languages where if you fail to put a type annotation you're actually losing information. That's not the case in Haskell, type inference causes no loss of precision for types.
Re:Dynamic type systems are not inherently more open by pwm on Sunday January 19, 2020 @02:44PM (#22093513)
I don’t agree with readibility (there are pros and cons, ie. terser code vs. implicit types) but, at least in Haskell, it improves usability by inferring the most generic type to your expression.
Re:Dynamic type systems are not inherently more open by leshow on Sunday January 19, 2020 @03:56PM (#22094021)
Agree on what? "Type inference" is a broad feature, feel free to post the resources.

edit: In Haskell it goes beyond just locally inferring variables, it enables a new type of development with typed holes that feels more like a back and forth conversation with the compiler. I don't see how "I can leave the types off my C# variables" has anything to do with that.

Re:Dynamic type systems are not inherently more open by yawaramin on Sunday January 19, 2020 @03:19PM (#22093746)
In practice, not really. A good type inference system like Hindley-Milner infers the most general type of any expression you give it. This usually makes your code more polymorphic i.e. generic than if you would have manually written down the types.

You talk about cognitive load of looking up type info but there's also a cognitive load to having to parse every type annotation over and over again whenever you read the code. And since code is read more often than it's written, that's really just optimizing for the wrong load. As you re-read a codebase over time you'll get familiar with its types. And then the annotations start to get in the way. This is in fact one of the reasons people prefer dynamic typing.

> My response? Go refactor your hideous code.

To what? Would be very interesting to see your suggested refactor of that code.

> Before every language designer blindly accepts type inference as a good thing, I propose that some research be conducted.

What would be the research question(s) specifically?

Re:Dynamic type systems are not inherently more open by amelius on Sunday January 19, 2020 @09:06AM (#22091480)
Yes, some programming languages take this approach but I don't think that prototyping is as easy in such languages as it is in a dynamically typed language (e.g. Haskell vs Python).
Re:Dynamic type systems are not inherently more open by yakshaving_jgt on Sunday January 19, 2020 @09:40AM (#22091640)
In my experience (currently writing Haskell professionally, previously writing Ruby professionally) prototyping is easier in Haskell.

How many systems have you prototyped in Haskell?

Re:Dynamic type systems are not inherently more open by dllthomas on Sunday January 19, 2020 @02:04PM (#22093187)
> prototyping is easier in Haskell

That's very much my experience, as well. Assuming - and it's a very big assumption - that your use case has equivalent library support.

Re:Dynamic type systems are not inherently more open by rwmj on Sunday January 19, 2020 @09:18AM (#22091534)
When writing OCaml, if I'm unsure of the type I set the type to some impossible value, compile it, and the compiler tells me what the type really is.
Re:Dynamic type systems are not inherently more open by hnra on Sunday January 19, 2020 @09:37AM (#22091622)
I Haskell you simply put a "_" in the annotation and the compiler suggests the correct type.
Re:Dynamic type systems are not inherently more open by dllthomas on Sunday January 19, 2020 @02:07PM (#22093218)
You can also do this with values, asking "what goes here?" - it's great.
Re:Dynamic type systems are not inherently more open by andrepd on Sunday January 19, 2020 @10:51AM (#22092017)
Alternatively, merlin can tell you the type of the expression under your cursor, besides also flagging type mismatches like your situation.
Re:Dynamic type systems are not inherently more open by hopia on Sunday January 19, 2020 @10:13AM (#22091808)
Productivity can be really subjective. Those that are used to modeling the problem domain with the type system find that their most productive approach, even with prototyping.
Re:Dynamic type systems are not inherently more open by dllthomas on Sunday January 19, 2020 @02:06PM (#22093204)
Right, and the type system is such a big help in refactoring - especially in small projects - that you don't have to be all that right in your first N cuts at the model. You can write code and find out where you're wrong, and fix it fast.
Re:Dynamic type systems are not inherently more open by pwm on Sunday January 19, 2020 @02:51PM (#22093546)
It’s even more help in larger projects :) The dividends of type-checher aid refactoring really start paying off once the project is above a a certain size/age.
Re:Dynamic type systems are not inherently more open by dllthomas on Tuesday January 21, 2020 @05:04PM (#22112161)
Yeah, I think I was unclear. Given a need to refactor, it's a bigger help on a bigger refactor.

But a large refactor on a large project is still a pain. By the time you get there, you still want your model stable and/or flexible enough that you don't need to do that much.

On a small enough project, every refactor is easy enough that you can lean into it. Make a bunch of assumptions you're not confident about, setting up the types so you're sure you'll know what needs fixing when they're wrong. Then you test those assumptions as you write - and run - more code.

Re:Dynamic type systems are not inherently more open by zitterbewegung on Sunday January 19, 2020 @09:43AM (#22091661)
What would be neat is if you could take a Python program and run type inference on the program and it would output a type annotated version of the code.
Re:Dynamic type systems are not inherently more open by duckerude on Sunday January 19, 2020 @11:35AM (#22092264)
I don't have experience with it, but pytype can do that: https://github.com/google/pytype

After typechecking it leaves provisional stubs in .pytype/pyi/, and it has a tool to merge them into the original code.

mypy has stubgen: https://mypy.readthedocs.io/en/latest/stubgen.html

As far as I know it's less powerful since mypy isn't really built for unannotated code and pytype is.

Re:Dynamic type systems are not inherently more open by pron on Sunday January 19, 2020 @10:32AM (#22091915)
Unless your type system is very weak -- and in effect, an untyped language can be considered to already be doing what you said only in a type system that has a single type -- this is generally impossible (halting problem and its extensions). So you have the choice of something that's not very useful or something that's impossible -- take your pick.

Type inference, as others have suggested, does not do what you want. If your program is well-typed according to a particular type system which you must have in mind while writing the program, they'll save you from writing explicit type annotations, but they cannot come up with "correct" type for a correct program that's not written for that particular type system.

Re:Dynamic type systems are not inherently more open by IggleSniggle on Sunday January 19, 2020 @02:27PM (#22093376)
TypeScript can come close to this, especially with the latest release with Assertion support. You make assertions about your code, and the downstream types are inferred based on your assertions. Thus, the runtime behavior of your code gives you progressively enhanced type-checking. If you do these assertions at the borders, your "correctness" is dependent on the strength of your runtime assertions.
Re:Dynamic type systems are not inherently more open by ken on Sunday January 19, 2020 @09:31AM (#22091587)
You mean a compiler?
Re:Dynamic type systems are not inherently more open by zmmmmm on Sunday January 19, 2020 @04:34PM (#22094265)
> To my mind if I return to a piece of dynamically typed code written any time other than in the same session I have to load a whole mental model of the entire code, what types all the variables are

This is one reason my favorite model is the "egg model" - hard outer shell (static typed signature) of a function with a soft gooey center - dynamic code internally. It lets you use the convenience of dynamic typing but confines the scope of the mental budget to understanding just a few lines of dynamically typed code. Languages like groovy are pretty good for this type of code.

Re:Dynamic type systems are not inherently more open by kazinator on Sunday January 19, 2020 @11:25AM (#22092205)
If you don't have to think about what mutation each method performs, if any, when switching to static typing, you're not just switching to static typing.