© 2019 Strange Loop
We will show how to encode deterministic and non-deterministic finite automata, push-down automata, and Turing Machines in miniKanren, a domain-specific language for relational (pure logic) programming. In addition to accepting strings for a given language, these relational automata and Turing Machines can generate strings in the language (as well as strings not in the language!). When running backwards, these relations will also generate associated data structures, such as the stack in a push-down automata. A relational implementation of the Chomsky Hierarchy demonstrates the power of relational programming, while providing insight into the working of automata and Turing Machines.
Daniel P. Friedman is Professor of Computer Science at Indiana University. He is co-author of The Little Schemer, The Seasoned Schemer, The Reasoned Schemer, Scheme and the Art of Programming, and Essentials of Programming Languages, 3rd Edition, all published by MIT Press.
William E. Byrd is a Postdoctoral Researcher in the School of Computing at the University of Utah. He is co-author of The Reasoned Schemer, and co-designer of several declarative languages: miniKanren (logic programing), Harlan (GPU programming), and Kanor (cluster programming). His StarCraft 2 handle is ‘Rojex’ (character code 715).