  Many abstract interpretation frameworks and analyses for Prolog have been
proposed, which seek to extract information useful for program optimization.
Although motivated by practical considerations, notably making Prolog
competitive with imperative languages, such frameworks fail to capture some of
the control structures of existing implementations of the language.
  In this paper we propose a novel framework for the abstract interpretation of
Prolog which handles the depth-first search rule and the cut operator. It
relies on the notion of substitution sequence to model the result of the
execution of a goal. The framework consists of (i) a denotational concrete
semantics, (ii) a safe abstraction of the concrete semantics defined in terms
of a class of post-fixpoints, and (iii) a generic abstract interpretation
algorithm. We show that traditional abstract domains of substitutions may
easily be adapted to the new framework, and provide experimental evidence of
the effectiveness of our approach. We also show that previous work on
determinacy analysis, that was not expressible by existing abstract
interpretation frameworks, can be seen as an instance of our framework.
