> What's the complexity of that?

Probably huge, but very reasonable for the subset of code people normally write (this again the analogy of Rice's theorem vs static analyzers). I don't know off the top of my head, but I'm sure there's pathological cases that trigger cases where normalization becomes the same thing as full-on evaluation.

But it doesn't show up in practice (see e.g. dhall as a working case), because you have to write pathological code. This is similar to the case with many statically typed programming languages (e.g. Java, Haskell, etc.) that have worse-than-exponential blow-ups in their type systems that essentially never show up in practice. I'm not sure any programmer alive has ever accidentally written a Java program that took days to compile (which could easily be possible with the right pathological behavior). EDIT: I forgot about Turing completeness in Java and Haskell's type systems; I meant leaving those tricks aside.

> But that's often the case in Turing-complete languages, too. Moreover, the easy cases are usually not harder to detect in those languages.

Yes if you program in a fragment of a language you're fine. We're trying to disincentivize users from stepping outside the fragment or at least let them be aware when that happens. One way of doing that is to make it off-limits to step outside that fragment. Another is a stratified language (e.g. Hume). Another way is an analyzer separate from the language. Yet another is community convention.

> Any benefits can't be true in general because it is trivial to transform any program to an "effectively equivalent" FSM.

By arguments analogous to this and the usual ones about Turing completeness this statement is always true in some form for any claimed benefit about any programming language. By this standard all programming languages are indistinguishable at a general level (which is true, but not very useful).

> A claim that could be true is that in restricted languages, many more programs people write happen to be easier to analyse than the programs they would have written to do the same thing in an unrestricted language. That's certainly a very interesting empirical claim, but it requires empirical evidence.

That is at the end of the day the contention behind any programming language. Yes I agree that this means that almost any proponent of a language talking about how it's "objectively" better is wrong. I also agree that this turns the entirety of programming languages into essentially an art-form rather than anything approaching a science. But such is the current state of things (yes also I happen to agree with your usual contention that this is a huge problem with the value proposition of PLT).

Barring this, we have weak (but not unusually so for the field of programming) evidence, in the form of user communities of Turing-incomplete languages today, that people aren't generally creating heat-death style code on accident. They're doing it on purpose to get around restrictions of the language.

EDIT: The name of the game when creating programming languages is to target code that "a normal user would write." Completely restricting the entire language is just another lever in that process.