An adaptive interpreter for a programming language adapts to particular applications by learning from execution experience. This paper describes PROLEARN, a prototype adaptive interpreter for a subset of Prolog. It uses two methods to speed up a given program: explanation-based generalization and partial evaluation. The generalization of computed results differentiates PROLEARN from programs that cache and reuse specific values. We illustrate PROLEARN on several simple programs and evaluate its capabilities and limitations. The effects of adding a learning component to Prolog can be summarized as follows: the more search and subroutine calling in the original query, the more speedup after learning; a learned subroutine may slow down queries that match its head but fail its body.