You have the dependency graph wrong. There's a script that uses both wc and grep and it depends on both of them. At the lowest level they are just streams of characters, but that doesn't mean anything. If you change the output format of wc or grep in any significant way then you will break every script that depends on them. Which is impossible, and that's why Unix commmands don't change. (Unless it's a new flag or something like that.)
In a well-designed system where the interfaces between components isn't actually public, you can change the API by finding all the usages and fixing them. And frequently you have to do so because the API is not a frozen standard - it's still being worked on.
There are some functions that never change their functionality. The expression "1 + 1" will always equal "2". The functionality of "+" might be expanded, for instance to cover complex numbers, but it will never be incompatible with previous versions.
So if the API of "+" is not expected to change, why do you expect the API of other components to change? Why assume that an API of a service has to be mutable?
I'd argue that an API can be immutable if the component is simple, by which I mean a component that only attempts to do one thing. The function "+" is simple, because it does only one thing: add numbers together. Because it is simple, the API doesn't have to change.
If your API of each individual component is frozen, this means they can be considered to be independent. You might have components that use other components, but if their APIs are frozen, unchangeable, then you might as well consider them as entirely separate applications.
In my opinion, a web service of 100K+ LOC indicates that the interfaces between components are not frozen, that the components are not simple, and to me this just seems like bad design.
Well sure, and if we wrote programs that have no bugs then we'd never have to debug them. Your position is seriously naive.
Getting an API right the first time is hard. For example, most languages get date libraries wrong the first time (for example, see Java and Python), even with a lot of design effort up front. And most library designers are not that good, especially when they're only part-time library designers whose main concern is writing an app.
Getting an API right is hard, but if your API is simple, then by definition there are fewer things that can be changed, and that means there's less need to refactor.
I'd rather create 3 simple APIs and throw away the two that didn't work well, than create 1 complex API that needs to be constantly refactored. Small, immutable, simple components are preferable over large, mutable, complex components.
Saying I am "seriously naive" implies I don't have experience with designing components in this way, but it is precisely because of my experience that I advocate this position in the first place. The APIs I've had to change and refactor have been complex; the APIs I have not had to have been simple. Over the past few years, I have been slowly moving away from complex APIs, and there has been a dramatic decline in the amount of refactoring work I've done.
This is not to say that it's easy to create simple APIs, but good design is never easy, and I don't think it's naive to say that if you want good design, you need good designers.
In a well-designed system where the interfaces between components isn't actually public, you can change the API by finding all the usages and fixing them. And frequently you have to do so because the API is not a frozen standard - it's still being worked on.