Zenn
🦁

プログラミング言語理論について

2023/07/18に公開
言語開発
tech

形式言語

形式言語は、特定の形式的規則に基づいて生成または認識される一連の文字列です。
コンピューターサイエンスにおける形式言語の理論は、プログラミング言語の構文設計やパーサーの作成に直接適用されます。
また、形式言語は

  • レギュラー（正規）言語: レギュラー言語は、レギュラー表現や有限オートマトンによって認識・生成される言語です。レギュラー表現は、文字や記号、演算子などを使ってパターンを表現する方法です。例えば、正規表現はレギュラー言語を表現するためによく使われます。
  • コンテクストフリー言語: コンテクストフリー言語は、コンテクストフリー文法によって認識・生成される言語です。コンテクストフリー文法は非終端記号と終端記号から構成される規則の集合で、代表的なものとしてバッカス・ナウア記法（BNF）があります。プログラミング言語の構文などは一般にコンテクストフリー言語として表現されます。
  • コンテクストセンシティブ言語: コンテクストセンシティブ言語は、コンテクストセンシティブ文法によって認識・生成される言語です。コンテクストセンシティブ文法は、規則の適用が左辺と右辺の文脈に依存する文法です。
  • リカーシブ列挙可能言語: リカーシブ列挙可能言語は、チューリングマシンやその他の等価な計算モデルによって認識・生成される言語です。リカーシブ列挙可能言語は最も複雑な言語クラスであり、一般の計算問題を表現できます。

など、異なる複雑さのクラスに分類されます。

オートマトン

オートマトンは、内部状態と、それらの状態間を移動する規則に基づいて動作する抽象的な機械または計算モデルです。
オートマトンは、状態（ステート）と遷移（トランジション）から構成されます。
状態はシステムの内部状態を表し、遷移は状態間の移り変わりを表します。
入力を受け取ることによって、オートマトンは現在の状態から別の状態への遷移を行います。
例えば、有限オートマトンはレギュラー（正規）言語を認識します。

  • 有限オートマトン（Finite Automaton）：有限の状態と遷移を持つオートマトンです。正規表現や正規言語の表現、パターンマッチングなどに使用されます。
  • プッシュダウンオートマトン（Pushdown Automaton）：スタック（プッシュダウンスタック）を持つオートマトンです。文脈自由文法や文脈自由言語の解析に使用されます。
  • チューリングマシン（Turing Machine）：記号列を操作するモデルで、計算可能性理論や形式言語理論の基礎となるモデルです。チューリング完全性を持つため、一般的なコンピュータの計算能力を表現できます。

チューリングマシン

チューリングマシンは、プログラム可能な汎用計算モデルで、どんなアルゴリズムでもシミュレートできます。
実際のコンピュータは、チューリングマシンが持つ理論上の計算能力を具現化したものと見なすことができます。

テープ

チューリングマシンは、無限に長いテープを持っていると考えます。テープはセルに分割され、各セルには記号（通常は0と1、または空白）が記録されます。

ヘッド

チューリングマシンは、テープ上の特定のセルを読み書きするヘッドを持っています。ヘッドはテープ上を左右に動きます。

状態

チューリングマシンは、一連の状態を持っています。最初の状態は開始状態と呼ばれ、特定の状態はハルト（停止）状態と呼ばれます。

遷移関数

チューリングマシンの動作は、現在の状態とヘッドが指すセルの記号に基づいて決定されます。
これらを入力として、遷移関数は新しい状態、ヘッドが書き込むべき新しい記号、そしてヘッドが左に動くべきか右に動くべきか（または動かないか）を出力します。

これらの要素により、チューリングマシンは任意の計算を実行できます。具体的な計算の例として、次のような遷移関数を持つチューリングマシンを考えてみましょう：

  • 状態Aでは、セルが0なら1を書き込み、右に移動し、状態Bに遷移する。
  • 状態Bでは、セルが1なら0を書き込み、左に移動し、状態Aに遷移する。

このチューリングマシンは、状態Aと状態Bの間を無限に往復し、テープ上の数字を反転させる動作を続けます。

ラムダ計算

ラムダ計算は、全ての計算を関数の適用と抽象化によって表現する数学的な形式体系です。
多くの現代の関数型プログラミング言語は、ラムダ計算の影響を受けています。

  1. 変数: x、y、zなどの識別子です。
  2. 関数抽象: ラムダ記法（λ）を使って関数を定義します。例えば、λx.xは、引数をそのまま返す関数を表します。
  3. 関数適用: 関数とその引数を組み合わせます。例えば、(λx.x) yは関数λx.xに引数yを適用したものを表します。

また、実際のプログラミング言語、特に関数型言語（Haskell、Scala、Clojureなど）では、
このラムダ計算の概念が直接的にまたは間接的に使用されます。
これらの言語では、関数が第一級のオブジェクトとして扱われ、変数にバインドしたり、他の関数に引数として渡したり、結果として返したりすることが可能です。

Discussion