Emacs SLIME(http://common-lisp.net/project/slime/) には、 slime-media という拡張機能があり、REPL バッファ内に画像を表示できます。SLIME をリモートサーバ上の Lisp プロセスに接続して使用しているばあい、少し処理が必要だったので記録しておきます…

書いておかないと時間が経って後でどうしようもなくなることが分かったので、断片でも書くようにする。 目標 簡潔でメンテナンス可能なネイティブSCHEMEコンパイラ。フルの RnRS を実装する。n が幾つかは状況による。 SECD マシンになるか、"An Incremental…

(1) で示したパターンは、Haskell で既に状態モナドとしてパターン化されている。GHC 7.0.4 では状態モナドは以下のように定義されていた。 GHCi, version 7.0.4: http://www.haskell.org/ghc/ :? for help (略) Prelude> :module Control.Monad.State Prelu…

状態モナドを理解するために、記号表を更新するシナリオを考えた。 環境 文字と整数のタプルからなる、単純な連想リスト構造を考える。 type Name = String type Value = Int type Env = [(Name, Value)] この連想リストを変数名とその変数の値からなる環境…

github にあげた。 https://github.com/cranebird/secdhs Haskell 勉強用のトイプログラムで、以下のみサポート。 Parsec を使ったパーズ。 SECD マシンへのコンパイルと実行。 SCHEME の if, lambda, let, letrec とごく少数の組み込み演算。(fib は動く) …

どこかにバグがあるけど何とか関数適用まで動くようになったので貼付けておく。 「:.」は「.」のつもりのデータ構築子。 -- SECD Machine data SECD = SECD LispVal LispVal LispVal LispVal deriving (Eq, Show) step (SECD s e (LDC x :. c) d) = SECD (x …

Data.Set を排して唯のリストで書き換えている。骨格はこんな感じ。 Ord a 制約が不要となったため、オートマトンを Functor にできた。 α-遷移(文字による遷移)とε-遷移の扱いをシンプルに。 NFA から DFA への変換の際、何が起きているかよく理解しよう。…

すごいHaskell 本を読んだりしながら、オートマトンを書き換えている。http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.9852 "A Taxonomy of Finite Algorithms (1993) by Bruce Watson を参考に、オートマトンは５つ組ではなく、ε-遷移を通常…

DFA/NFA のテストとして、特定の文字からなるランダムな文字列をテストデータとしたい。例えば、アルファベットが文字 a と b のみからなるDFAに対しては、"a", "ab", "aaaababa" などの文字列を生成したい。 しばらく方法が分からず悩んでいたが以下のよう…

"Regular Expressions and Automata using Haskell" を参考に、データ構造を変更した。具体的にはオートマトンの遷移関数を Haskell の関数にするのを止め、状態遷移の集合とした。 data Labelled a b = Labelled a b a deriving (Eq, Ord) data Epsilon a =…

Haskell の QuickCheck. DFA に対する処理が妥当かどうか、という観点で論理的に満たすべき性質、を書いてみた。最初の関数はユーティリティ。QuickCheck がデフォルトで作ってくれる、ランダムな Int の配列を、特定の DFA のアルファベットの配列に変換し…

いろいろ参考にしながら何とか NFA -> DFA の変換まで書いた。 状態とアルファベットを型変数とできた。また、集合は集合として Data.Set を使った。個人的に満足。 以下のような書き方ができることを知ったのが収穫。これが分からず、MultiParameterTypeCla…

さらに書き換えて、よりDFA,NFA の定義通りにして、よりHaskellらしくできた、つもり。 状態 State 型は型変数を取ることにした。これで文字からなる状態も、状態の対からなる状態も、 Data.Set 、つまり集合からなる状態も、同じように扱える。 同じく、文…

まだなんとなくカッコわるいが、NFA から DFA の変換。 powerSet [] = [[]] powerSet (x:xs) = yss ++ map (x:) yss where yss = powerSet xs subset :: Set.Set State -> Set.Set State subset states = Set.fromList (map (\x -> S'' (Set.fromList x)) (p…

状態の集合をほんとうに集合用のデータ構造 Data.Set を使って書いてみた。 module Fa where import qualified Test.HUnit as Test import qualified Data.Set as Set data State = S String | S' (State, State) | S'' (Set.Set State) deriving (Eq, Show,…

Dfa をさらに書き直してよりエレガント?にした。 状態遷移関数は結局、lookup するだけだった インスタンスを生成するための関数を追加した union をより簡潔に。 module Fa where import qualified Test.HUnit as Test -- import System.Environment data S…

状態の合成を扱えるよう、定義を少し変更して、正規演算の和集合演算を書いてみた。 リスト内包表記だと直積がエレガント。教科書の定義そのままに書ける。まだテストしてないけどとりあえず。 data State = State String | State2 (State, State) deriving …

一度クラスを導入してみたが、あまりにややこしくなってしまった。迷走ぎみだが、シンプルに書き換えた。 module Fa where import System.Environment data State = State String deriving (Eq, Show) type Symbol = Char type Alphabet = [Symbol] -- Dfa s…

さらに考え直して、Transition を無くしてみた。あんまり美しくない気がするが、ほぼ DFA の定義通りだ。 module Fa where import System.Environment data State = State String deriving (Eq, Show) type Symbol = Char type Alphabet = [Symbol] -- Dfa s…

オートマトンの続き。先に書いた例は簡潔だけど、状態遷移関数に相当するものがパターンマッチの中に埋め込まれている。このままでは、オートマトンを新しく定義するためには Eval が必要になる、ように思える。Eval を使うのはたぶん良くない。 しばらく考…

Haskell の勉強のため、オートマトン(DFA)を書いてみた。まずは簡単な例として、奇数個の 'a' を受理するオートマトン(http://kurt.scitec.kobe-u.ac.jp/~kikyo/lec/07/automaton/k2.pdf より)。汎用性は全く無視。 module Fa where import System.Environme…

Haskell のパターンマッチを使って SECD マシンを書く。Lisp のコンスセルは、任意の Lisp のデータを対にした構造。Haskell のリストと Lisp のコンスセルは(わたしの理解が間違っていなければ)ちょっと違う。型で言うと、以下の通り。 (:) :: a -> [a] -> …