4 ms·

A sidenote: There is nothing in Java/C++ etc that would stop one from making only legal states representable. It's just easier and more obvious in ML family...

• lomnakkus 12y ago
  That's only true in the most trivial Turing Tarpit sense, though. Ease of use and defaults matter in practice. E.g. you can do compile-time exhaustiveness-checked pattern matching using the visitor pattern in Java/C++, but try doing that in practice and the amount of boilerplate just becomes unbearable -- and actually obscures (rather than illuminate) the essence of the data structure. There's also the lack of higher-kinded types. (Or just plain syntactic pain of using HKTs e.g. in Scala.)
  • fsloth 12y ago
    Very true. I usually avoid complex constructs in C++ - especially in production code and strive to strike a balance between KISS and YAGNI. KISS comes first unless there is some obvious boilerplate that can be avoided... Encoding only valid states in subareas of code can be done within C++ without extravagant constructs. Ie. instead of passing around a Car with a Car::isDriving member implement a DrivingCar class and use that where this state of car matters. It's not as neat as ADT:s in ML but provide the same Lego-block static composability with minimum amount of moving parts. I would not use pattern matching as such in C++.
  • tel 12y ago
    Additionally, the Turing Tarpit doesn't apply in the level of the type language. These languages actually differ significantly in power since they're not Turing complete. Thus, there are certainly non-trivial and interesting static invariants which you can encode in Haskell and cannot in Java. The most critical and strong common one is probably parametricity.
    • lomnakkus 12y ago
      Oh, certainly. I was just alluding to the futility of the comparison :). Interestingly[1], the power of the type system seems to conflict somewhat with type inference. Or, at least, that a Turing Complete type-level language like in Shen or Idris does require you to spell out increasing amounts of type information. Obviously, this has to do with undecidability of TC languages, but I kind of think it's interesting that e.g. Haskell seems to occupy a kind of "sweet spot" in terms of inference and being able to tell the programmer when it needs a type ascription. AFAICT that would be impossible in a language whose type system is a-priory undecidable, correct? (Just to spell it out: In Haskell, the compiler knows that if you want feature X, Y and Z, then constructs A, B and C become undecidable... and can tell you so.) [1] Well, I found it interesting, but I'm a layman at best.
      • tel 12y ago
        Absolutely! The more information a type system can express the less likely it is to guess correctly at what you want just based on your value-level representation of intent. Which is really fascinating when you think about it. It basically expresses (what we all know) that your code captures only a fragment of the intent of your efforts. Good types can capture much more intent. So to that end, people explore interactive development. In this scenario, you provide a (potentially partial) type corresponding to the programmatic intent you desire and the compiler conducts proof search to find programs which satisfy that type! The types are actually more informative than the programs and it provides some evidence that we'd really rather be writing at higher-level typed languages and letting the implementations fall out naturally rather than writing the implementations and hoping that inference can build the proper types. Or something like that.
        • lomnakkus 12y ago
          Yes, I've found some of the published Idris videos quite instructive in this regard. Sometimes it can even infer the program fragment that you were supposed to write (given unification and uniqueness constraints), but it seems limited only to demo-level code and frankly at this point I'd be wondering if I got the types wrong and let the compiler infer bad code! (As opposed to getting the program wrong!) Programming is weird.