So today I’m just going to say a few words about a little project that I’m working on and possibly going to use as a demonstration when teaching next term: a compiler from a simple language with arithmetic, branching, and loops to a Turing machine.
The reason why I’m doing this is that I want to try and make the connection between “computation as what computers do” and “computation as recognizing membership in a set” a little more apparent. I know that, for me, I cut my theory teeth on lambda calculi and primitive vs. partial recursion. It was very obvious, in that case, how these models of computation were related to what a computer did. For this course, however, in order to be prepping them for the next course in the sequence I need to follow a trajectory that starts with simple automata and ends with Turing machines. The underlying theme of that path is about recognizing languages, i.e. being able to decide whether a string belongs to a set. Now, that is about computation-as-what-computers-do if you think of the string as being a program and the language as the set of valid programs in language X that execute correctly but I know that, for me, that wasn’t a very obvious connection when I first really learned about Turing machines. I’m hoping to make it a little more concrete to students with this project.
You can find my code-in-progress here. The whole thing is written in Haskell because that, and Agda, are the languages I’m most comfortable with and there’s at least a chance my students will have seen some Haskell code at some point.
The basic pipeline so far is that it translates from the AST of this simple language, to a stack machine, and then to the initial tape of a Turing machine that emulates the stack machine behavior. Since I’m primarily a math person, there’s some odd gaps in my education: for example, I’ve never written a compiler start to finish. That’s why, actually, I chose to translate to a stack machine. It seemed much more straight forward than trying to fake a register machine and then emulate that on a Turing machine.
I’m not finished, though, but what I’m doing is writing an interpreter at each stage and I’ll probably have QuickCheck tests or the like to make sure that the different pieces agree. What I have to left to do is
- finish the definition of the stack-machine emulating TM
- write the translation of a list of stack-machine instructions to a tape configuration
- test. test. test.