プログラミングの基礎理論 第2回 言語の帰納的な定義

はじめに Twitterにてこのようなツイートを見かけたので、内容を確認してみた。 これまでインターネットや書籍で軽く触れられてきた内容に切り込んでいくものだったので、理解を深めることができた。 その内容をまとめていく。 概要 言語は文法で定義される。 例えば、MLの一部の式は以下のように定義される。 <exp> ::= <id> // 変数 | <n> | <S> | true | false // 自然数(n), 文字列(S) その他定数 | fn <id> => <exp> // 関数式 | <exp> <exp> // 関数適用 | ... プログラミング言語の理論ではより抽象的な定義を行うため、変数や定数を「与えられた集合」とし、これを代表するものをメタ変数と呼ぶ。 ラムダ式では以下の集合とメタ変数を導入する。 変数(Var)に対するメタ変数をxとする 定数(Const)に対する

[mitsuyoshi4]

かいた