Doesn't MIT's Scratch [1] accomplish this? I was going to default to this. I'm wondering how much reading, writing and math my kids need to have before starting this. Reading complex sentences and addition and multiplication of single digits? (Wrong thread to get started on what EWD [2] thinks on this...)
Yes! My oldest is 4.5, and I'm thinking about how to assemble a text-only machine to force typing, learning commands, navigating the file system, etc. Might as well start him off with linux and bash instead of DOS and batch, though. :-)