News for hackers. Stuff that matters.
Re:Prolog's Eternal September (2017) by klodolph on Saturday May 10, 2025 @03:21PM (#43948145)
“Arbitrary prolog in Haskell’s type system” is overselling it.

There are a lot of GHC extensions out there, so maybe some combination of extensions can bring this statement closer to reality. But, as stated, it’s pretty far away. There’s an important common thread shared by Prolog and type certain systems, which is unification, but Prolog gives you a lot of tools to control what happens when you go forward and backward:

      +---+
  >---|   |--->
      |   |
  <---|   |---<
      +---+
Prolog is, after all, Turing complete by design. I don’t know if Haskell’s type system is Turing complete with enough GHC extensions enabled, but if it is, then it’s by accident.
Re:Prolog's Eternal September (2017) by syrak on Saturday May 10, 2025 @04:44PM (#43948845)
You need very little to make a Prolog-like language Turing-complete (lists and recursive predicates). And so Haskell's type system only needs one (or two) extensions to be Turing-complete, `UndecidableInstances` (and maybe `FlexibleInstances` or `MultiParamTypeClasses`). It is no accident. The name "undecidable" shows that the authors of that extension were well aware that it enables Turing-completeness.
Re:Prolog's Eternal September (2017) by klodolph on Saturday May 10, 2025 @08:49PM (#43950290)
Exactly—Haskell’s type checker can be made Turing-complete, but that won’t make it much like Prolog.
Re:Prolog's Eternal September (2017) by fc417fc802 on Saturday May 10, 2025 @04:55PM (#43948920)
I'm not sure how useful it is in practice but even C++ templates are turing complete. https://rtraba.com/wp-content/uploads/2015/05/cppturing.pdf

> I don’t know if Haskell’s type system is Turing complete with enough GHC extensions enabled, but if it is, then it’s by accident.

Undecidable instances? I don't think that's an accident. https://stackoverflow.com/questions/42356242/how-can-undecid...

Also see. https://github.com/seliopou/typo

Re:Prolog's Eternal September (2017) by chuckadams on Sunday May 11, 2025 @09:24AM (#43953675)
True, I'm not sure you're going to get anything like cuts in a type system. I know with Haskell (GHC really, but that's kind of a given these days) and C++ you can make matching abort early, but only with an error.