人工知能的代数学(7) - エレファント・ビジュアライザー調査記録

マグマの計算

「マグマの左単位元と右単位元」の問題の構文解析を ChatGPT でやってみるため以下のように入力しました。
「マグマ(二項演算をもつ代数的構造)の構文解析をするプログラムを書いてください：
演算子は * とします。
かっこを使えるとします。
生成元は変数(先頭が大文字の文字列)と定数(先頭が小文字の文字列)とします。
結果は構文木を返してください。」
すると「Lark ライブラリ」を使ったプログラムが返ってきました。そこで「Lark ライブラリ」について ChatGPT で調べながら改造しました。
「type が multiplication のときは Multiplication(左の演算数を変換したもの, 右の演算数を変換したもの) を返し、Token の type が VARIABLE のときは Variable(変数の名前) を返し、Token の type が CONSTANT のときは Constant(定数の名前) を返すようにするにはどのようにすれば良いですか」
と入力してそれらしいクラスを作ってもらいましたが、これはこのままでは使えないので改造しました。
「2つのマグマの式の変数を他の式で置き換えたときに一致するかどうかを調べるもので、そのやり方はユニフィケーションによって最小の置き換えを求めるプログラムを書いてください」
と入力してユニフィケーションを行うプログラムを書いてもらおうとしたのですが、あまり使えるところがなかったのでほぼ全面的に改造しました。
「等式には変数を使うことができるとし、変数には任意の式を代入することができるとします。式には演算 + を使うことができるとします。このような等式の集合の推移閉包を求めるプログラムを書いてください」
と入力してみましたが、この結果も使えそうにないので、今回はいったんユニフィケーションを行うだけとします。

class Exp:
    pass

# Multiplication クラス
class Multiplication(Exp):
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __repr__(self):
        return f"Multiplication({self.left}, {self.right})"

# Variable クラス
class Variable(Exp):
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return f"Variable({self.name})"

# Constant クラス
class Constant(Exp):
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return f"Constant({self.name})"
    
from lark import Transformer, v_args

@v_args(inline=True)  # 引数をリストではなく個別の要素として受け取る
class CustomTransformer(Transformer):
    def multiplication(self, left, right):
        return Multiplication(left, right)  # Multiplication オブジェクトとして返す

    def term(self, item):
        return item

    def atom(self, item):
        return item

    def VARIABLE(self, name):
        return Variable(str(name))  # Variable オブジェクトとして返す

    def CONSTANT(self, name):
        return Constant(str(name))  # Constant オブジェクトとして返す
    
# グラマー定義
grammar = """
?start: expression

?expression: term
    | expression "*" term -> multiplication  # 二項演算子

term: atom
    | "(" expression ")"  # 括弧を使った演算

atom: VARIABLE
    | CONSTANT  # 変数と定数

VARIABLE: /[A-Z][a-zA-Z_]*/  # 大文字で始まる変数
CONSTANT: /[a-z][a-zA-Z_]*/  # 小文字で始まる定数

%ignore " "  # 空白を無視
"""

class Unifier:
    def __init__(self):
        self.substitutions = {}  # 置き換えのマップ

    def unify(self, expr1, expr2):
        if isinstance(expr1, Variable):
            if expr1.name in self.substitutions:
                return self.unify(self.substitutions[expr1.name], expr2)
            else:
                self.substitutions[expr1.name] = expr2
                return True
        elif isinstance(expr2, Variable):
            return self.unify(expr2, expr1)
        elif isinstance(expr1, Constant):
            return isinstance(expr2, Constant) and expr1.name == expr2.name
        elif isinstance(expr1, Multiplication):
            return isinstance(expr2, Multiplication) and self.unify(expr1.left, expr2.left) and self.unify(expr1.right, expr2.right)
        else:
            return False

# 構文解析
from lark import Lark
parser = Lark(grammar, parser="lalr")
custom_transformer = CustomTransformer()
tree1 = parser.parse("X*e_r")
expr1 = custom_transformer.transform(tree1)
tree2 = parser.parse("e_l*Y")
expr2 = custom_transformer.transform(tree2)

unifier = Unifier()
res = unifier.unify(expr1, expr2)
print("結果:", res)

# 置き換えの結果
print("Substitutions:", unifier.substitutions)