4 ms·
Shen lisp has the world's only turing complete type system (making it even more advanced than Haskell's system).
by hajile 13y ago
Shen lisp has the world's only turing complete type system (making it even more advanced than Haskell's system).
- emiljbs 13y agoDo you really want a turing complete type system? Being turing complete does not necessarily mean more powerful for real world applications.
- read 13y agoThank you for Shen Lisp, I wasn't aware of it. The downside of the phrase Turing complete is that there isn't a practical limitation that instantly comes to mind when you hear that phrase. You don't hear people say "Oh no, that wouldn't be Turing complete". Complete or not, how does it affect a real application?
- pjc50 13y agoFor a type system, being Turing complete is a disadvantage: you can't prove that your typechecker will always terminate.
- chriswarbo 13y agoThe result is even stronger: we can prove that it will sometimes not terminate! Still that's not too bad, since type checking is always conservative: if a program passes, we know it's correct(ly typed). If it doesn't pass, we don't gain any knowledge: it may be incorrect, or it may be correct in a way which the type checker's limited algorithm cannot determine (ie. a Goedel sentence). I'm very concerned whether my programs terminate/coterminate, since having to kill them part-way-through could cause corruption and other nastiness. Whether the type-checker terminates or not I don't really care about; I can just kill it after a certain timeout and keep fiddling with my code until it passes, just like any other type error. Of course, a timeout removes Turing-completeness, but that timeout is under my control at the commandline, rather than being an inherent property of the algorithm.
- hajile 13y agoThis is only partially true. The type system is only unable to prove termination if you choose to use those constructs which may disallow termination.
- chongli 13y agoI don't know about you but I'd rather not have my type checker hang and force me to interrupt the process all the time.
- lmm 13y agoIt's not the only one by any means. E.g. scala's type system is turing complete - http://michid.wordpress.com/2010/01/29/scala-type-level-encoding-of-the-ski-calculus/ http://michid.wordpress.com/2010/01/29/scala-type-level-enco...
- ufo 13y agoYou should check out some dependently typed languages.
- chongli 13y agoWith the downside of undecidable type inference and checking. Haskell's type system really hits the sweet spot between power and decidability.