Prolog is a powerful pedagogical instrument for theoretical elements of computer science when used as combined description language and experimentation tool. A teaching methodology based on this principle has been developed and successfully applied in a context with a heterogeneous student population with uneven mathematical backgrounds. Definitional interpreters; compilers; and other models of computation are defined in a systematic way as Prolog programs; and as a result; formal descriptions become running prototypes that can be tested and modified by the students. These programs can be extended in straightforward ways into tools such as analyzers; tracers and debuggers. Experience shows a high learning curve; especially when the principles are complemented with a learning-by-doing approach having the students to develop such descriptions themselves from an informal introduction.