I feel like SICP would be a perfect text for introductory CS, if there were a "pre-CS" course in high schools that was essentially equivalent to the current 100-level Discrete Mathematics courses.
Come into programming already knowing set theory, graph theory, computational complexity, etc. and SICP will make perfect sense.
It is described here in an excellent talk about the challenges of curriculum design https://youtu.be/5c0BvOlR5gs note the end of the talk he discusses how Calculus is secretly taught to them as well by keeping track of a video game state over time. Going from Bootstrap->SICP would be possible too.
You don't need to already understand programming to be able to use SICP. SICP doesn't need an intro (or to be modified), it is an intro. What you need to already understand, is math. Specifically, the kinds of math that SICP uses in its examples and problems—which aren't taught in high-school, but totally could be (100-level Discrete Maths has very few prerequisites; you could theoretically learn it in elementary school, though practically not, for mental-development reasons.)
SICP is, essentially, a book to teach programming to "mathematicians who have not necessarily ever heard of a computer." It works wonderfully when used as such. But the less mathematical grounding you have, the harder you'll struggle.
It's exactly like a textbook for one of those "Communications for Business" courses. If you're not a business student, then it'll be a bad communications textbook, because all the examples and problems are business-related.
You are right though I wish there was a course that taught set theory and complexity in HS. Anybody interested in learning both at the same time, there are intro discrete math books that also teach intro programming https://cs.wheaton.edu/~tvandrun/dmfp/ but not in the full CS101 coverage of SICP.
Typical introductory discrete math textbooks list high school precalculus as a prerequisite and recommend an introductory calculus course as very helpful additional background. You would have to teach something significantly different to someone with the background of a typical middle school / early high school student, because they are lacking quite a bit of the expected background concepts, terminology, and notation.
These subjects could certainly be taught to elementary school students, but slowly and with a lot of build-up and practice, over the course of years. The limiting factor is not primarily “mental development” (as in, some inherent change of brain wiring that inevitably happens with age) but rather substantial amounts of practice, prior exposure to related ideas, time spent digesting them, stamina/attention span/confidence at solving technical problems, etc.
That is more or less what this was meant to be:
Honestly, I think it is a superior intro-book for genuine beginners, compared to SICP, and a quick perusal of the two will allow most people to come to a conclusion not only about the level at which they are pitched, but which one is pedagogically superior for them in terms of both structure and writing.
Are they? I don't know if I remember hearing anyone complain about those before.
In TXR Lisp, which is quite CL-like in some places and deliberately so, I used the names succ, ssucc, and sssucc for adding 1, 2, 3, and 4. The inverses are pred, ppred, and pppred.
These are vaguely inspired by Hofstader's S0, SS0, SSS0 ... in Gödel, Escher, Bach as well a by caar, cddr, ... plus the dim memory of operators called succ and pred in Pascal).