エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

修練がてら DFA をいろんな言語で書いてみた

アンダースタンディング コンピュテーションを読んでいます。


その「3章 最も単純なコンピュータ」の「3.1 決定性有限オートマトン」に登場する決定性有限オートマトンDFA)のRubyでの実装を他の言語でも実装してみました。

実行結果

実装の詳細は GitHub を見ていただくとして。
実行の手順と結果だけ載せておきます。

実行環境は Mac Yosemite です。

Ruby
$ ruby dfa.rb
a => false
baa => false
baba => true
CoffeeScript
$ coffee dfa.coffee
a => false
baa => false
baba => true
C++
$ g++ --std=c++11 -o dfa dfa.cpp
$ ./dfa
a => false
baa => false
baba => true
Haskell
$ ghc --make dfa
$ ./dfa
a => False
baa => False
baba => True
Io language
$ io dfa.io
a => false
baa => false
baba => true
Prolog
swipl -s dfa.prolog -g 'main'
a => false
baa => false
baba => true
Erlang
$ erlc dfa.erl
$ erl -noshell -s dfa start -s init stop
a => false
baa => false
baba => true
C++ Template Meta Programming
$ g++ --std=c++11 -c dfa_template.cpp 
dfa_template.cpp:107:1: error: static_assert failed "'a' was not accepted"
dfa_template.cpp:110:1: error: static_assert failed "'baa' was not accepted"
dfa_template.cpp:114:1: error: static_assert failed "'baba' was accepted"

static_assert を利用して結果を表示しているので error と出ていますが、実行エラー(コンパイルエラー)なわけではないです。
後ろのメッセージの方を見てやってください。

SQL
$ psql some-database < dfa.sql
CREATE TABLE
INSERT 0 6
CREATE TABLE
INSERT 0 3
CREATE TABLE
INSERT 0 3
 source | accepted 
--------+----------
 baa    | f
 a      | f
 baba   | t
(3 rows)

DROP TABLE
DROP TABLE
DROP TABLE

今回の収穫

  • Prologを経由するとErlangが理解しやすい。Erlangが難しいという方は、先にPrologを使ってみるとErlangの読み書きができるようになるかも。
  • SQLでも再帰プログラミングができることがわかりました。