Tutorial Thursday #3: State machines and mutual-recursion
Автор: William Byrd
Загружено: 2013-05-02
Просмотров: 0
Описание:
Tutorial Thursday: state machines and mutual-recursion.
I demonstrate an old functional programming trick: how to encode a deterministic finite state automata using mutually recursive procedures in Scheme and miniKanren. I begin with a gentle introduction to recursion, mutual recursion, and Scheme's letrec construct, which experienced functional programmers may wish to skip.
Code (Scheme and miniKanren):
https://github.com/webyrd/automata-an...
The deterministic finite automaton (DFA) we translate is the example from the Wikipedia page:
http://en.wikipedia.org/wiki/Determin...
If you find this interesting, you might want to read Shriram Krishnamurthi's 2006 Journal of Functional Programming paper, 'Automata via Macros':
http://cs.brown.edu/~sk/Publications/...
Michael Sipser's overpriced but excellent 'Introduction to the Theory of Computation, third edition' contains the clearest explanation of finite automata I have seen.
Повторяем попытку...
Доступные форматы для скачивания:
Скачать видео
-
Информация по загрузке:
![[PLDI'23] Recursive State Machine Guided Graph Folding for Context-Free Language Reachability](https://imager.clipsaver.ru/IqEv92i-xdE/max.jpg)
