What is the origin of "Program to an interface, not an implementation" -- does it originate from Design Patterns, 1994, by GoF, or from a computer scientist or from some concepts in computer science earlier?
"Program to an interface, not an implementation" is succinct way of describing a process by which to build software, and this formulation is largely attributed to the Gang of Four.
However, the process they were describing has its roots far earlier, and originates from Kent Beck and Ward Cunningham who came up with the idea of using "pattern languages" (a concept attributed to Christopher Alexander, an architect) to write object-oriented programs.
From their OOPSLA-87 talk, "Using Pattern Languages for Object-Oriented Programs":
We propose a radical shift in the burden of design and implementation, using concepts adapted from the work of Christopher Alexander, an architect and founder of the Center for Environmental Structures. Alexander proposes homes and offices be designed and built by their eventual occupants. These people, he reasons, know best their requirements for a particular structure. We agree, and make the same argument for computer programs. Computer users should write their own programs. The idea sounds foolish when one considers the size and complexity of both buildings and programs, and the years of training for the design professions. Yet Alexander offers a convincing scenario. It revolves around a concept called a "pattern language."
A pattern language guides a designer by providing workable solutions to all of the problems known to arise in the course of design. It is a sequence of bits of knowledge written in a style and arranged in an order which leads a designer to ask (and answer) the right questions at the right time. Alexander encodes these bits of knowledge in written patterns, each sharing the same structure. Each has a statement of a problem, a summary of circumstances creating the problem and, most important, a solution that works in those circumstances. A pattern language collects the patterns for a complete structure, a residential building for example, or an interactive computer program. Within a pattern language, patterns connect to other patterns where decisions made in one influence the others. A written pattern includes these connections as prologue and epilogue. Alexander has shown that nontrivial languages can be organized without cycles in their influence and that this allows the design process to proceed without any need for reversing prior decisions.