Scaling up Self-Explanatory Simulators: Polynomial-time Compilation

Self-explanatory simulators have many potential applications, including supporting engineering activities, intelligent tutoring systems, and computer-based training systems. To fully realize this potential requires improving the technology to efficiently generate highly optimized simulators. This paper describes an algorithm for compiling selfexplanatory simulators that operates in polynomial time. It is capable of constructing self-explanatory simulators with thousands of parameters, which is an order of magnitude more complex than any previous technique. The algorithm is fully implemented, and we show evidence that suggests its performance is quadratic in the size of the system being simulated. We also analyze the tradeoffs between compilers and interpreters for self-explanatory simulation in terms of application-imposed constraints, and discuss plans for applications.