Hacker News Reader

Comment by mnarayan01 | Hacker News Reader

> What is the undecidability result you are referring to?

Just the correspondence between static type safety and the halting problem.

> I kind of have the feeling you are trying to make a point about formal languages being "the same", whereas the article uses "the same language" to mean "a single programming language" that allows, but does not require, type declarations.

Yes this. To me, it felt like the article was making the "stronger" claim, at least until the end when it starts talking about co/contra-variance.

View on HN

> Just the correspondence between static type safety and the halting problem.

I'm not sure if you are saying that there cannot be programming languages with decidable static type systems. Because there are programming languages with decidable static type systems. Typically you cannot encode Turing machines in the type system, so you don't get the kind of problem you seem to be talking about. (But you haven't really explained what you are talking about.)

  // ... Well typed things ...
  if (arbitrary_well_typed_function()) {
    v = 0xF00 + "bar"
  }
  // ... Well typed things ...

Let's say this program is well typed iff `arbitrary_well_typed_function()` is falsy. If a static type checker can not compute `arbitrary_well_typed_function`, it needs to make a trade-off which a dynamic type checker need not.

OK. Yes, static type systems need to make trade-offs. If this was your entire point, your original talk about undecidability was hiding it well.

You got my point in your first comment in this thread. Unless that comment was the result of hours of striving, it doesn't seem as if the point was hidden well. If you did spend hours working at it, then I apologize and commend you on your success.

Reply on news.ycombinator.com