「真理値表」:関数型プログラミングの初級問題 -40問目- （約2時間）

　論理についての練習問題と答案です。問題は、OCaml公式ページのものを使いました。答案の作成時間は、約2時間でした。

問題40.

　以下のように変数を含むブール式について小規模な言語を定義する。
type bool_expr =
| Var of string
| Not of bool_expr
| And of bool_expr * bool_expr
| Or of bool_expr * bool_expr

　これにより二変数の論理式をポーランド記法により記述することができる。例えば、$${(a \lor b)\land (a \land b)}$$は、
And (Or (Var "a", Var "b"), And (Var "a", Var "b"))
と表される。

所与の二変数の論理式について真理値表を生成する関数table2を書け。

※ 例えば、table2 "a" "b" (Or (And (Var "a", Not (Var "b")), And (Not (Var "b"), Var "b")))は、[(true, true, false); (true, false, true); (false, true, false); (false, false, false)]になります。

答案

本問の解き方

　本問を解くにあたり最も重要な処理は、式の評価です。
　本問の式には、変数Varと、論理式Not, AndおよびOrがあります。
　このうち論理式は、OCamlの論理演算に一対一で対応させることにより評価することができます。
　一方、変数を評価するには、何らかの仕組みが必要になります。
　本答案では、所謂環境を使用します。環境は、変数の名前とその変数に割り当てられた値との組からなります。
　具体的には、環境は変数名と「値」とからなるタプルのリストで構成され、各タプルの「値」が、変数の評価値になります。
　
　後は真理値表についてのくだらない処理です。

コード

type bool_expr =
 | Var of string
 | Not of bool_expr
 | And of bool_expr*bool_expr
 | Or of bool_expr*bool_expr

let rec value_of key = function
 | [] -> raise (Failure "value_of")
 | (k, v)::tail -> if k = key then v else value_of key tail

let rec eval env = function
 | Var (s) -> value_of s env
 | Not (e) -> not (eval env e)
 | And (e1, e2) -> (eval env e1) && (eval env e2)
 | Or (e1, e2) -> (eval env e1) || (eval env e2)

let rec expand =
 let rec append e = function [] -> []
  | head::tail -> (e::head)::append e tail in

 function [] -> []
  | head::[] -> [[(head, true)]; [(head, false)]]
  | head::tail -> (append (head, true) (expand tail))@(append (head, false) (expand tail))

 let rec to_triple = function [] -> []
  | [a; b; c]::tail -> (a, b, c)::to_triple tail
  | _ -> raise (Failure "to_triple")

 let table2 a b expr =
  let rec boolean = function [] -> [] | (_, b)::tail -> b::boolean tail in
  let rec table = function [] -> [] | head::tail -> ((boolean head)@[eval head expr])::table tail in

 to_triple (table (expand [a; b]))

　関数value_ofは、環境において変数keyに割り当てられた値を返します。
　関数evalは、bool_exprの評価関数です。
　関数expandは、変数のリストを環境の入れ子リストに変換する関数です。入れ子リストの要素は、各変数にtrueまたはfalseが割り当てられた環境です。入れ子リストは、真理値表における全ての割り当てを含みます。
　関数to_tripleは、三要素のリストからなる入れ子リストを、三要素タプルのリストに変換する関数です。

感想

　今回の問題は、定義された言語が小さすぎて消化不良です。できれば関数も言語で定義したかったのですが、問題通りにOCamlで定義しています。
　そのため、とてもチグハグな感じがします。

　また、変数の数も何故か二変数に限定されています。つまり、結果のリストが三要素タプルのリストになっています。タプルを使う意図が理解できません。
　変数の数を限定すると却ってややこしいコードになるので、本答案では多変数を前提にプログラムを作成しました。
　
　些か物足りなくはありますが、言語処理そのものには興味が湧きました。
　なので処理系を自作するのもよいかもしれません。その際は命題論理ではなく述語論理を対象にしたいです。そうLKのゼクエンツあたりで。

　次回は、第41問です。今回から出題分野が論理になりました。論理というよりは言語処理でした。