自由モノイドのイテレーター(9)

自由モノイドプログラミング言語の作成(Python版 4)

構文に対応するクラス

以下のようになります。

from abc import ABC, abstractmethod
from functools import reduce
from itertools import chain, islice
from typing import Callable, Iterable, List, Optional, Sequence, Union
from typing import TypeVar
from FreeMonoid import FreeMonoid
from Env import Env

T = TypeVar('T')
U = TypeVar('U')

class FreeMonoidUnion:
    def __init__(self, item: "Union[Number, FreeMonoid[int]]"):
        if isinstance(item, Number):
            self.domain_value = item
            self.monoid_value = FreeMonoid[int].zero()
            self.ismonoid = False
        else:
            self.domain_value = Number.zero()
            self.monoid_value = item
            self.ismonoid = True
    def __str__(self):
        if not self.ismonoid:
            return str(self.domain_value)
        else:
            return str(self.monoid_value)
    def __repr__(self):
        if not self.ismonoid:
            return f"FreeMonoidUnion({repr(self.domain_value)})"
        else:
            return f"FreeMonoidUnion({repr(self.monoid_value)})"

# 構文に対応するクラス

class Evalutable(ABC):
    @abstractmethod
    def eval(self, env: Env[FreeMonoidUnion], prog: "Program") -> FreeMonoid[int]:
        pass

class DomainEvalutable(ABC):
    @abstractmethod
    def eval(self, env: Env[FreeMonoidUnion]) -> "Number":
        pass

class CodeGenerator(ABC):
    @abstractmethod
    def print_source(self) -> str:
        pass
    @abstractmethod
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        pass

def list_print_source(sep: str, list_: "Sequence[CodeGenerator]"):
    return sep.join(list(map(lambda x: x.print_source(), list_)))
    
def list_generate_python(y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str], sep: str, list_: "Sequence[CodeGenerator]"):
    spc = "    " * (i if ic else 0)
    return sep.join(list(map(lambda x: spc + x.generate_python(y, t, i, ic, perf), list_)))
    
def list_str(sep: str, list_: 'List[T]'):
    return sep.join(list(map(str, list_)))
    
class Program:
    def __init__(self, block: "List[Statement]"):
        self.block = block
    def __str__(self):
        return list_str(";\n", self.block) + "\n"
    def __repr__(self):
        return f"Program({self.block})"
    def print_source(self) -> str:
        return list_print_source(";\n", self.block) + "\n"
    def generate_python(self, t: bool, perf: Callable[[str], str]) -> str:
        return list_generate_python(False, t, False, 0, perf, "\n", self.block) + "\n"
    def eval(self) -> "FreeMonoid[int]":
        env: Env[FreeMonoidUnion] = Env[FreeMonoidUnion]()
        mon: FreeMonoid[int] = FreeMonoid[int].zero()
        for st in self.block:
            mon = st.eval(env, self)
        return mon
    def find_definition(self, name: str) -> "Optional[Definition]":
        for st in self.block:
            if isinstance(st, Definition) and (st.name.name == name):
                return st
        return None
    
class Statement(CodeGenerator, Evalutable):
    pass

class Definition(Statement):
    def __init__(self, name: "Identifier", paramlist: "List[Identifier]", exp: "Expression"):
        self.name = name
        self.paramlist = paramlist
        self.exp = exp
    def __str__(self):
        return list_str(", ", self.paramlist) + f") = {str(self.exp)}"
    def __repr__(self):
        return f"Definition({repr(self.name)}, {self.paramlist}, {repr(self.exp)})"
    def print_source(self) -> str:
        return f"def {str(self.name)}(" + list_print_source(", ", self.paramlist) + f") = {self.exp.print_source()}"
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        # y が true のときは yield
        # 関数定義の式の中では yield
        return f"def {str(self.name)}(" + list_generate_python(y, t, i, ic, perf, ", ", self.paramlist) + f"):\n{self.exp.generate_python(True, t, True, ic + 1, perf)}"
    def eval(self, env: Env[FreeMonoidUnion], prog: "Program") -> FreeMonoid[int]:
        return FreeMonoid[int].zero()
    
class ExpressionStatement(Statement):
    def __init__(self, exp: "Expression"):
        self.exp = exp
    def __str__(self):
        return str(self.exp)
    def __repr__(self):
        return f"ExpressionStatement({repr(self.exp)})"
    def print_source(self) -> str:
        return self.exp.print_source()
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        # y が true のときは yield
        # 式のステートメントの中では yield
        e = self.exp.generate_python(False, t, False, ic, perf)
        # 実行コードに変換
        return perf(e)
    def eval(self, env: Env[FreeMonoidUnion], prog: "Program") -> FreeMonoid[int]:
        return self.exp.eval(env, prog)
    
class Expression(CodeGenerator, Evalutable):
    def __init__(self, termlist: "List[Term]"):
        self.termlist: "List[Term]" = termlist
    def __str__(self):
        return list_str(" & ", self.termlist)
    def __repr__(self):
        return f"Expression({self.termlist})"
    def print_source(self) -> str:
        return list_print_source(" & ", self.termlist)
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        # y が true のときは yield
        if y:
            return list_generate_python(y, t, i, ic, perf, "", self.termlist)
        else:
            return list_generate_python(y, t, i, ic, perf, " & ", self.termlist)
    def eval(self, env: Env[FreeMonoidUnion], prog: "Program") -> FreeMonoid[int]:
        monlist = map(lambda e: e.eval(env, prog), self.termlist)
        return FreeMonoid[int](chain.from_iterable(monlist))

class Term(CodeGenerator, Evalutable):
    pass

class Function(Term):
    def __init__(self, name: "Identifier", explist: "List[Expression]"):
        self.name = name
        self.explist = explist
    def __str__(self):
        return f"{str(self.name)}(" + list_str(", ", self.explist) + ")"
    def __repr__(self):
        return f"Function({repr(self.name)}, {self.explist})"
    def print_source(self) -> str:
        return f"${str(self.name)}(" + list_print_source(", ", self.explist) + ")"
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        # y が true のときは yield
        # 関数呼び出しの中は yiled はしない
        if y:
            return f"yield from {str(self.name)}(" + list_generate_python(False, t, False, ic, perf, ", ", self.explist) + ")"
        else:
            return f"{str(self.name)}(" + list_generate_python(False, t, False, ic, perf, ", ", self.explist) + ")"
    def eval(self, env: Env[FreeMonoidUnion], prog: "Program") -> FreeMonoid[int]:
        definition = prog.find_definition(self.name.name)
        if definition is None:
            # 最初から定義されている関数を実行
            if self.name.name == "zipsum":
                valuelist = list(map(lambda x: x.eval(env, prog), self.explist))
                return valuelist[0].zip_with(lambda x, y: x + y, valuelist[1])
            elif self.name.name == "tail":
                valuelist = list(map(lambda x: x.eval(env, prog), self.explist))
                return valuelist[0].tail()
            # 定義されていなかったとき
            return FreeMonoid[int].zero()
        else:
            namelist = list(map(lambda x: x.name, definition.paramlist))
            valuelist = list(map(lambda x: x.eval(env, prog), self.explist))
            unionlist = list(map(lambda x: FreeMonoidUnion(x), valuelist))
            env = env.define_list(namelist, unionlist)
            return definition.exp.eval(env, prog)

class DomainFunction(Term):
    def __init__(self, name: "Identifier", explist: "List[DomainExpression]"):
        self.name = name
        self.explist = explist
    def __str__(self):
        return f"{str(self.name)}(" + list_str(", ", self.explist) + ")"
    def __repr__(self):
        return f"DomainFunction({repr(self.name)}, {self.explist})"
    def print_source(self) -> str:
        return f"{str(self.name)}(" + list_print_source(", ", self.explist) + ")"
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        # y が true のときは yield
        # 関数呼び出しの中は yiled はしない
        if y:
            return f"yield from {str(self.name)}(" + list_generate_python(False, t, False, ic, perf, ", ", self.explist) + ")"
        else:
            return f"{str(self.name)}(" + list_generate_python(False, t, False, ic, perf, ", ", self.explist) + ")"
    def eval(self, env: Env[FreeMonoidUnion], prog: "Program") -> FreeMonoid[int]:
        definition = prog.find_definition(self.name.name)
        if definition is None:
            return FreeMonoid[int].zero()
        else:
            namelist = list(map(lambda x: x.name, definition.paramlist))
            valuelist = list(map(lambda x: x.eval_domain(env), self.explist))
            unionlist = list(map(lambda x: FreeMonoidUnion(x), valuelist))
            env = env.define_list(namelist, unionlist)
            return definition.exp.eval(env, prog)

class DomainExpression(Term):
    def __init__(self, termlist: "List[DomainTerm]"):
        self.termlist = termlist
    def __str__(self):
        return list_str(" + ", self.termlist)
    def __repr__(self):
        return f"DomainExpression({repr(self.termlist)})"
    def print_source(self) -> str:
        return list_print_source(" + ", self.termlist)
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        # y が true のときは yield
        return list_generate_python(y, t, False, ic, perf, " + ", self.termlist)
    def eval(self, env: Env[FreeMonoidUnion], prog: "Program") -> FreeMonoid[int]:
        return FreeMonoid[int].unit(self.eval_domain(env).number)
    def eval_domain(self, env: Env[FreeMonoidUnion]) -> "Number":
        number_list = list(map(lambda e: e.eval(env), self.termlist))
        return reduce(lambda x, y: x + y, number_list)

class DomainTerm(DomainEvalutable, CodeGenerator):
    pass

class Identifier(DomainTerm, CodeGenerator):
    def __init__(self, name: str):
        self.name = name
    def __str__(self):
        return self.name
    def __repr__(self):
        return f"Identifier({self.name})"
    def print_source(self) -> str:
        return self.name
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        # y が true のときは yield
        if y:
            return f"yield {self.name}\n"
        else:
            return self.name
    def eval(self, env: Env[FreeMonoidUnion]) -> "Number":
        val = env.value(self.name)
        if val is None:
            return Number.zero()
        else:
            return val.domain_value

class Number(DomainTerm):
    def __init__(self, name: str):
        self.number = int(name)
    def __str__(self):
        return str(self.number)
    def __repr__(self):
        return f"Number({self.number})"
    def print_source(self) -> str:
        return str(self.number)
    def generate_python(self, y: bool, t: bool, i: bool, ic: int, perf: Callable[[str], str]) -> str:
        # y が true のときは yield
        if y:
            return f"yield {self.number}\n"
        else:
            return f"{self.number}"
    def eval(self, env: Env[FreeMonoidUnion]) -> "Number":
        return self
    @classmethod
    def zero(cls) -> "Number":
        return Number("0")
    def __add__(self, n: "Number") -> "Number":
        return Number(str(self.number + n.number))

Python コードの生成

構文解析から Python コードの生成は以下のようになります。

from lark import Lark
parser = Lark(grammar, parser="lalr")
custom_transformer = CustomTransformer()

src = "def fib(x, y) = x & fib(y, x + y);\nfib(0, 1)"
prog: Program = custom_transformer.transform(parser.parse(src))
count = 20
perf: Callable[[str], str] = lambda x: f"print(take({count}, {x}))"
print(prog.generate_python(True, perf))
exec(prog.generate_python(True, perf))

prog.generate_python(True, perf) は以下のコードを生成します。

def fib(x: int, y: int) -> Iterable[int]:
    yield x
    yield from fib(y, x + y)
print(take(count, fib(0,1)))

exec(prog.generate_python(True, perf)) はこれを実行します。C# では実行できなかったのですが Python では実行できます。

src = "def fib(x, y) = x & y & $zipsum(fib(x, y), $tail(fib(x, y)));\nfib(0, 1)"

と変更すると以下のコードを生成して実行します。

def fib(x: int, y: int) -> Iterable[int]:
    yield x
    yield y
    yield from zipsum(fib(x, y), tail(fib(x, y))) 
print(take(count, fib(0,1)))

ここで使った take、zipsum、tail は以下のように定義します。

def take(n: int, gen: Iterable[T]) -> Iterable[T]:
    return list(islice(gen, n))

def zip_with(func: Callable[[T, T], T], gen1: Iterable[T], gen2: Iterable[T]) -> Iterable[T]:
    for x, y in zip(gen1, gen2):
        yield func(x, y)

def zipsum(gen1: Iterable[int], gen2: Iterable[int]) -> Iterable[int]:
    return zip_with(lambda x, y: x + y, gen1, gen2)

def tail(gen: Iterable[T]) -> Iterable[T]:
    istail = False
    for x in gen:
        if istail:
            yield x
        istail = True

Rustで作るプログラミング言語 —— コンパイラ／インタプリタの基礎からプログラミング言語の新潮流まで

初等整数論入門 (ちくま学芸文庫)

オイラーとリーマンのゼータ関数 シリーズ ゼータの現在

可換環論の勘どころ (数学のかんどころ 32)

集合と位相(増補新装版)(数学シリーズ)

新版 集合と位相 そのまま使える答えの書き方 (KS理工学専門書)