A flexible framework for visualisation of computational properties of general explicit substitutions calculi

SUBSEXPL is a system originally developed to visualise reductions, simplifications and normalisations in three important calculi of explicit substitutions and has been applied to understand and explain properties of these calculi and to compare the different styles of making explicit the substitution operation in implementations of the ?-calculus in de Bruijn notation. The system was developed in OCaml and now it can be executed inside the Emacs editor within a new mode which allows a very easy interaction. The use of special symbols makes its application very useful for students because the notation on the screen is as close as possible to that on the paper. In addition to dealing the ?-calculus and explicit substitutions calculi in de Bruijn notation, now it is possible to work with the ?-calculus and with several calculi of explicit substitutions using also representation of variables with names. Moreover, in contrast to the original version of the system, that was restricted to three specific calculi of explicit substitution, the new version allows the inclusion of new calculi by giving as input their grammatical descriptions. SUBSEXPL has been used with success for teaching basic properties of the ?-calculus and for illustrating the computational impact of selecting one kind of representation of variables (either names or indices) and a specific style of making explicit substitutions in real implementations based on the ?-calculus. © 2011 Elsevier B.V. All rights reserved.