I haven’t read Head First Design Patterns yet, but I heard that it’s a worthy book. Therefore, I suspect that they give a slightly more accurate interpretation to “program to the interface” than this article.

See, there are interface and interface. The former is a general concept that designates the external integration points of a component (be it a function, class or anything else), while the later is a keyword in some languages.

The thing is that “program to the interface” rule of thumb uses the former definition of “interface” (a general concept). Therefore, you don’t really need interfaces to follow this rule.

Specifically, in the example in the article, the distinction between ConfigurationStorageHandler and its implementation is not needed and even harmful. You can get rid of the interface and use the specific class wherever you need. In the future, if you indeed want to replace the implementation, you can simply change the internal details of this class. If you really want to keep both implementations (say, for AB testing), you can extract a common interface then (it's a 30 seconds task in a modern IDE).

So, this might be one additional rule of thumb: presence of an interface for a single implementation is a code smell and requires serious justification. "This thing might change in the future" isn't a proper justification, unless it already changed at least once, or it represents an inherently unstable concept in the real-world business domain.