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

マグマの計算(2)

「マグマの左単位元と右単位元」の続きです。「推移閉包を求めるプログラム」は使えそうにないので、推移律を一回だけ適用するように変更しました。

class Exp:
    pass

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

    def __str__(self):
        if isinstance(self.left, Multiplication):
            left_str = "(" + str(self.left) + ")"
        else:
            left_str = str(self.left)
        if isinstance(self.right, Multiplication):
            right_str = "(" + str(self.right) + ")"
        else:
            right_str = str(self.right)
        return left_str + " * " + right_str

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

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

    def __str__(self):
        return self.name

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

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

    def __str__(self):
        return self.name

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

class Equation:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.left) + " = " + str(self.right)

    def __repr__(self):
        return f"Equation({self.left} = {self.right})"
    
    def reverse(self):
        return Equation(self.right, self.left)
    
from lark import Transformer, v_args

@v_args(inline=True)  # 引数をリストではなく個別の要素として受け取る
class CustomTransformer(Transformer):
    def equation(self, left, right):
        return Equation(left, right)  # 等式

    def multiplication(self, left, right):
        return Multiplication(left, right)  # Multiplication オブジェクトとして返す

    def expression(self, item):
        return item

    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: equation

equation: expression "=" 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, x1, expr2, x2):
        if isinstance(expr1, Variable):
            if (expr1.name, x1) in self.substitutions:
                val_expr, val_x = self.substitutions[(expr1.name, x1)]
                return self.unify(val_expr, val_x, expr2, x2)
            else:
                self.substitutions[(expr1.name, x1)] = (expr2, x2)
                return True
        elif isinstance(expr2, Variable):
            return self.unify(expr2, x2, expr1, x1)
        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, x1, expr2.left, x2) and self.unify(expr1.right, x1, expr2.right, x2)
        else:
            return False

    def value(self, expr, x):
        if isinstance(expr, Variable):
            if (expr.name, x) in self.substitutions:
                val_expr, val_x = self.substitutions[(expr.name, x)]
                return self.value(val_expr, val_x)
            else:
                return expr
        elif isinstance(expr, Multiplication):
            return Multiplication(self.value(expr.left, x), self.value(expr.right, x))
        else:
            return expr

class TransitiveClosure:
    def __init__(self, equations):
        self.equations = equations
        self.relations = []
        for eq in self.equations:
            self.relations.append(eq)
            self.relations.append(eq.reverse())

    def next_transitive_list(self):
        # 推移律を1回使う
        next_transitive = []
        for eq1 in self.relations:
            for eq2 in self.relations:
                unifier = Unifier()
                res = unifier.unify(eq1.right, 1, eq2.left, 2)
                if res:
                    exp1 = unifier.value(eq1.left, 1)
                    exp2 = unifier.value(eq2.right, 2)
                    next_transitive.append(Equation(exp1, exp2))
        return next_transitive

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

# 入力として等式のリストを提供
equations = [eq1, eq2]
print("元の等式のリスト")
for eq in equations:
    print(eq)

# TransitiveClosureクラスを使用
transitive_closure = TransitiveClosure(equations)
new_equations = transitive_closure.next_transitive_list()
print("結果のリスト")
for eq in new_equations:
    print(eq)

結果

元の等式のリスト
$X * e_r = X$
$e_l * X = X$

結果のリスト
$(X * e_r) * e_r = X$
$X * e_r = X * e_r$
$(e_l * X) * e_r = X$
$X * e_r = e_l * X$
$X = X$
$X = (X * e_r) * e_r$
$e_l = e_r$
$X = e_l * (X * e_r)$
$e_l * (X * e_r) = X$
$e_l * X = X * e_r$
$e_l * (e_l * X) = X$
$e_l * X = e_l * X$
$e_r = e_l$
$X = (e_l * X) * e_r$
$X = X$
$X = e_l * (e_l * X)$