The facade approach is discussed in the article, along with some of its issues. I call it "extending the visitor pattern" following the paper the article refers to several times.
Unlike the Visitor pattern, the Facade pattern does not require any help on the side of the thing being extended -- no interface required. That is the primary contributor to the problems described in the article, right? that someone must explicitly provide a backdoor? And in some cases, multiple things must be modified to support extension due to the nature of the backdoors?
With a Facade, one writes a new, additive layer, sometimes directly mimicking the API they are wrapping. To extend Expr, I make MyExpr, and I call upon Expr within MyExpr. The tradeoff is API repetition/delegation, which can be mitigated with compile-time or run-time code generation, depending on the language.
Generally, this approach is used to coerce external APIs into an API that is more appropriate for the domain. For example, suppose I have a choice of three different XML packages: one package has great features for parsing and validating XML but has no interface for building XML; another lets me build it but not read it; a third provides some obscure namespace feature that I wish the builder had, but it is otherwise the slow performer in the set. I can unify these three packages under one package that delegates to the three appropriately.
I would also use this approach for extending existing functionality. For example, suppose I am depending on some foo(V) in an ML-style language that dispatches on V of type X and Y; usually, adding dispatch for something of type Z would require modifying the original code, right? But I can instead write a my_foo(V) that handles Z and defers all other dispatching to foo(V). I may introduce whatever complexity I need for my specific problem without needing the original source code of the thing I am extending. Acknowledged tradeoff: complex dispatch order may require reinventing the wheel to some extent.
My intuition suggests that this approach works well for most languages without requiring language-enforced extensibility on all the things.
Again, great article! It really does cover a lot of ground and comparisons.