When I posted that comment I thought someone might respond this way.
The extent to which HM type inference falls short of Turing-completeness is a bigger difference between it and Prolog than almost any other conceivable language feature. I'm pretty sure you can't emulate an LBA with HM type inference. You can't emulate a PDA or even a DPDA, as far as I know. You don't even have definite iteration (for i = 1 to 10).
I'd be on pretty shaky ground saying you can't emulate a FSM with HM type inference, but I also don't see how to do it.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
(no subject)
Date: 2009-12-27 06:07 pm (UTC)The extent to which HM type inference falls short of Turing-completeness is a bigger difference between it and Prolog than almost any other conceivable language feature. I'm pretty sure you can't emulate an LBA with HM type inference. You can't emulate a PDA or even a DPDA, as far as I know. You don't even have definite iteration (for i = 1 to 10).
I'd be on pretty shaky ground saying you can't emulate a FSM with HM type inference, but I also don't see how to do it.