Towards translating formal definitions into efficient interpreters

Abstract

Designing a programming language ought to involve formally defining the language. The formal definition benefits users of the language because it enables the designer to provide precise guarantees about the users' code, and it benefits the designer because it guides how they implement the language. Even more, the cost of formally defining the language can be shared with the cost of implementing the language: many tools can translate the textual form of a definition into an implementation of the language, commonly an interpreter. But these interpreters perform poorly.

In this talk, I present preliminary results on preventing these interpreters from performing poorly. I've built a tool, Jam, that translates a common style of formal definition into an interpreter, and the resulting interpreters improve performance by compiling programs to optimized native machine code at run-time.

To begin to assess the generality of this approach to improving performance, I've defined a variety of languages using Jam, and I've compared the performance of the resulting interpreters to existing ones where possible. My largest definition's interpreter performs, on average, one to two orders of magnitude slower than a mature implementation of the same language. But all is not lost: a similar interpreter produced by an earlier prototype of Jam--- which supported a less general style of formal definition---performed identically to that mature implementation on some small benchmarks, while on others it was up to an order of magnitude slower.

Please join meeting in Sococo VH 209. Login: tuftscs.sococo.com.

Join with Zoom meeting: https://tufts.zoom.us/j/91600075407

Password: please see colloquium email

Dial-in option not available.