I reserve judgment till I see an actual proof of that.
As far as I can tell, several things can explain how they fit a whole library in a single book (assuming 50 lines per page, 400 page books, 10.000 books in a library). First, the use of dedicated languages instead of C and C++ seems to explain 2 orders of magnitude. The 2 remaining ones are explained by feature creep and plain lack of reuse (in the Franck system for instance, they use a single library to draw everything, from characters in a word processor to the frames of the windows.)
They also claim specific achievements: a full self-implementing compilation stack in less than 2Kloc, on top of which implementing something like Javascript or Prolog takes less than 200 lines (see http://piumarta.com/software/maru for actual code). A Lex/Yacc equivalent in 400 lines or so (see http://www.tinlizzie.org/ometa/ for actual code). A Cairo equivalent that run with acceptable performance in about 500 lines. A TCP-IP stack in 160 lines, stable enough to run a web site.
If half of that is true, we can effectively talk about a silver bullet. That bullet won't kill the complexity werewolf of course, but it will seriously cripple it.
DoAwesomeStuffJustLikeILikeIt();
Don't get me wrong, there's some cool stuff there - but the claims of 4 orders of magnitude seem exaggerated to me.I know it's unbelievable. But other personal experiences make me think they're probably right. I have written equivalent OCaml and C++ code where the C++ version were 5 times larger (both where optimized for clarity). In my day job, I routinely divide substantial portions of C++ code by 2 through light refactoring.
VPRI's miracle doesn't only come from the awesomeness of their ideas. It also comes from the awfulness of current systems. A full desktop in 20.000 lines may not be so small, if you consider that current ones are way too big.
Addendum: I omitted a rather important detail: while the STEPS project aims to build a full desktop system, along with networking, publishing, messaging, and programming capabilities, it makes no attempt be compatible with anything (except the hardware on which it has to run). It doesn't do HTTP nor HTML, for instance.