> even python might be too far from the CPU to be a good introduction to computing
That depends on what one considers to be the best way to introduce computing. I personally think kids are a lot less likely to be engaged by a bottom-up approach (start with "this is what hardware does") than a top-down approach (start with "you can make cool things with it").
> AIUI, in this case, the major issue is that it is very tempting to try to impose a constraint that all intermediate states the code passes through are semantically valid. However while superficially appealing this turns out to be a crippling constraint.
This really isn't much of an issue in a language with holes as a first class concept, like Agda or Haskell.