Live data from Hacker News

Dynamic type systems are not inherently more open

lexi-lambda.github.io

261–270 of 286 posts

Re: Dynamic type systems are not inherently more open

#261
post #230

Earlier quoted context omitted.

> the boundary between programs is dynamically typed Many interfaces have declared, enforced static types. I don't have to write any code to handle SELECT birthdate FROM employees WHERE id = ? returning "fish" because the database would never let it happen.

You know that but your compiler doesn't (generally speaking).

Hence ORMs. It's possible to do much better than ORMs though. The object/relational type system mismatch is a property of how technology evolved, it's not fundamental.

Re: Dynamic type systems are not inherently more open

#262
post #258

Earlier quoted context omitted.

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…

> 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 depende…

> 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

#263
post #5

I've come to the conclusion that the benefit dynamic typing brings to the table is to allow more technical debt. Now of course technical debt should be repaid at an appropriate moment but that appropriate moment isn't always "as soon as possible". Let me illustrate, say you're adding a new feature and create lots of bugs in the process. Static typing will force you to fix some of these bugs before you can test out th…

Static types enforced by a compiler catch more bugs in logic that can be encoded in the type system at build time. How costly are these bugs? It probably depends on context. For a business app/SaaS, is the compiler going to prevent your broken business rules from allowing -100 items to be added to a basket, crediting the "buyer"? I would say a developer who knows how to interpret requirements is more important here. On the other hand, a compiler is probably an amazing place for static types, but I don't write compilers and I'd wager most jobbing devs don't either.

Predicate assertions instrumented to run during development catch an equivalent amount and more, since they can evaluate data at run-time.

Dynamic types combined with argument destructuring allows for very loosely coupled modules. I can see it being similar to row polymorphism, but then you have to ask whether it's worth the extra time? In many business apps a significant portion of LoC is mapping JSON/XML to DTOs to Entities to SQL and back. If everything starts and ends with JSON coming from an unverified source, forcing it into a "safe space" statically typed business program is almost ignoring the forest for the trees, possibly even giving a false sense of security. It's (over) optimising one segment of the system; it's not necessarily a waste but it's probably time which can be better spent elsewhere.

Re: Dynamic type systems are not inherently more open

#264

Earlier quoted context omitted.

> You can consume arbitrary data using a program written in a statically typed or dynamically typed language. Really? Okay, below is something that meets the definition of "arbitrary data". Can some static program process it and evoke its full meaning without the programmer having to develop an ad-hoc dynamic typing system? (defun defset-expander (env macform name params newval setform) (with-gensyms (getter setter a…

Yes. A program written in a statically-typed programming language can parse the lisp you have written above.

I believe that such system cannot fully process the data, as is written in that data's specification, without providing the type system that is in that specification.

The requirement for dynamic typing can either come from the language, or it can be "Greenspunned", or some combination of the two.

For instance, in that data we can construct objects, and we can write expressions which interrogate an object's type.

Thus, that is an example of input data whose processing requires dynamic typing.

Re: Dynamic type systems are not inherently more open

#265

Earlier quoted context omitted.

Yes. A program written in a statically-typed programming language can parse the lisp you have written above.

I believe that such system cannot fully process the data, as is written in that data's specification, without providing the type system that is in that specification. The requirement for dynamic typing can either come from the language, or it can be "Greenspunned", or some combination of the two. For instance, in that data we can construct objects, and we can write expressions which interrogate an object's type. Thus…

I'm quite sure it's not. Statically-typed programs can recursively parse data, and they can also monadically (sequentially) parse data. The same is true of dynamically-typed programs.

Re: Dynamic type systems are not inherently more open

#266
post #166

Earlier quoted context omitted.

If you think it helps to quickly write some code without types (I don't really agree with that in general, maybe in some specific cases), but you want to, when you're happy with the design, just add the types, there are many languages that support that! On the top of my head: * Dart (just don't give a type and the variable is dynamic) * Groovy (add @CompileStatic or @TypeChecked when you're ready) * Racket (start usi…

Look at this C++ code: std::vector > s; s.push_back(Pair ("a", MyInt(1))); s.push_back(Pair ("b", MyInt(2))); s.push_back(Pair ("c", MyInt(3))); Gross. I'm being punished. Look at this Rust code: let mut s = Vec::new(); s.push(Pair::new("a", 1)); s.push(Pair::new("b", 2)); s.push(Pair::new("c", 3)); Both are statically typed, but one uses inference. It practically feels like Python everywhere except where type declar…

You mean this C++ code?

  std::vector> s;
  s.push_back({"a", 1});
  s.push_back({"b", 2});
  s.push_back({"c", 3});
I mean let's compare apples to apples here.

Re: Dynamic type systems are not inherently more open

#267

Dynamic type systems are inherently more open. This article really bends over in strange ways to say otherwise. Fact is: dynamic typing is all about making fewer claims in your code about what you expect about the world around you. With dynamic types, to load a property you might just have to say the property name and receiver. With static types, you usually also have to say the type of all other properties of the re…

> Static type systems will typically require you to state the full type of o. This is not the case for languages with support for structural typing (as the article mentions in the appendix), and most modern statically typed languages have some degree of support for abstract interfaces of some sort which also support writing functions with only partially known information about the type. I think one of the core insigh…

Structural typing doesn’t save you unless you add other stuff to it.

Example:

    var o = ...; // Value comes from somewhere, doesn’t matter where so long as it’s opaque
    if (p)
        ... = o.f
    else
        ... = o.g
In dynamic typing, we only assert that o has f on the then, and only assert that o has g on the else.

Structural typing or abstract base classes or whatever would only save you here if you were very careful about giving o some top type and then casting. But that’s more work - so the tendency is that the static types version of this program will assert that o has both f and g at the point of assignment. And that represents a tighter coupling to whatever produces o.

Re: Dynamic type systems are not inherently more open

#268
post #258

Earlier quoted context omitted.

> 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 depende…

> 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 uns…

[deleted]

Re: Dynamic type systems are not inherently more open

#269

Earlier quoted context omitted.

I believe that such system cannot fully process the data, as is written in that data's specification, without providing the type system that is in that specification. The requirement for dynamic typing can either come from the language, or it can be "Greenspunned", or some combination of the two. For instance, in that data we can construct objects, and we can write expressions which interrogate an object's type. Thus…

I'm quite sure it's not. Statically-typed programs can recursively parse data, and they can also monadically (sequentially) parse data. The same is true of dynamically-typed programs.

Likewise academically speaking, statically typed programs can simulate Universal Turing Machines, QED.

If the detailed requirements describing the inputs require dynamic typing, then the statically typed program has to whip up a facsimile of that dynamic typing. It's not an implementation detail; it shows up in visible, testable system behaviors.

And then, there you are, with the possibility of errors that are not caught at your compile time.

Re: Dynamic type systems are not inherently more open

#270
post #259

Earlier quoted context omitted.

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.…

> 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 e…

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.

Post reply on HN