Python 3.5 introduces the ** type hint ** feature, which makes you aware of types. However, you rarely see code with type hints. At first, I was skeptical that "Does Python need static typing?", But when I added a type hint to my code, "[oh my (py)!](Http: // blog) .zulip.org/2016/10/13/static-types-in-python-oh-mypy/) ", and I wanted to spread it, so I decided to write this article.
From now on, we will implement field extension in Python in three parts, using type hints. For implementation, I referred to the article "Introduction to Algebra with Swift" by taketo1024.
By the way, the author is not familiar with algebraic extension (as much as I read "Mathematics Girl / Galois Theory" by Hiroshi Yuki), so if there are any mistakes, I will tell you. I would appreciate it if you could.
Algebraic extension is carefully written in taketo1024's article and other web pages, so I won't go into much mathematical talk in this article, and let's focus on ** how to do it with Python **. I think.
One of the bases of type hints is to write the code ** Function Annotation (PEP 3107) **. This is used to explain the arguments and return values of a function.
The following is an example of annotation taken from PEP 3107.
def compile(source: "something compilable",
filename: "where the compilable thing comes from",
mode: "is this a single statement or a suite?"):
The content of the function annotation does not affect the execution result of the program, but there are attempts to use the function annotation to inspect the code offline.
Since PEP 3107 does not specifically specify the content of annotations, various annotation styles may be scattered due to inspection tools. However, that would halve the benefits to the programmer, so from Python 3.5 ** type hints (PEP 484) ** A standardized framework called, has been introduced, and a related typing module is provided.
The following is an example annotation taken from PEP 484. For variables and strings, specify the class or type name instead of the description.
from typing import List
Vector = List[float]
def scale(scalar: float, vector: Vector) -> Vector:
return [scalar * num for num in vector]
I will write it again, but the behavior of the program does not change or the annotation method is not forced depending on the annotation content. Also, it is not always necessary to follow this annotation method. However, standardization unifies the rules, and we can expect cooperation between programmers.
Just because a type hint framework is in place doesn't mean that inspection tools are provided as part of Python, so you need to choose one. In this article, we will use ** mypy **, which is currently the de facto standard for PEP 484.
You can install mypy with the pip command as follows (note that it is mypy-lang, not mypy).
$ sudo pip3 install mypy-lang
Actual use will be done later in this article.
Now let's make a "number".
First is the monoid. A set that meets the following conditions is called a "monoid".
Closed for binary operation $ \ star $
- The associative law holds ($ x \ star (y \ star z) = (x \ star y) \ star z $)
- The identity element exists ($ e $ exists such that $ x \ star e = e \ star x = x $)
For example, natural numbers, real numbers, square matrices, etc. are monoids for "products".
To express this in Python, first create a ** abstract base class ** for monoids. Add metaclass = ABCMeta to make it an abstract base class.
from abc import ABCMeta, abstractmethod
class Monoid(metaclass=ABCMeta):
@abstractmethod
def __mul__(self, x):
pass
@abstractmethod
def identity(self):
pass
@abstractmethod
def __eq__(self, x):
pass
def testAssociativity(self, a, b):
return (self * a) * b == self * (a * b)
def testIdentity(self):
return self * self.identity() == self
Since we want all monoids to implement at least "binary operation $ \ star $", "identity element" and "equal", we declare an empty method with @abstractmethod decorator in the abstract base class. I will. As a result, ** if these three methods are not defined in the class that inherits Group, an error will occur during instantiation **.
The operation $ \ star $ substitutes for the Python operator *. To define the operator * for a class, define the __mul__ method. An instance of a class in which this operator is defined can be used to create an expression by connecting other objects with the * operator. For example:
class A(object):
def __init__(self, data):
self.data
def __mul__(self, x):
return self.data * x.data
a = A(5)
b = A(10)
print((a * b).data) # -> 50
When evaluating an expression, the connected objects are assigned to x in __mul__ and calculated, and the return value is the evaluation result of the expression. __eq__ corresponds to the operation==.
However, this alone does not represent that the monoid is ** closed ** for the operation $ \ star $. That's where the ** type hint ** comes in. Type hints can express the types of function arguments and return values **. Let's look at an example with type hints.
from typing import TypeVar
MonoidType = TypeVar("MonoidType", bound="Monoid")
class Monoid(metaclass=ABCMeta):
@abstractmethod
def __mul__(self: MonoidType, x: MonoidType) -> MonoidType:
pass
@abstractmethod
def identity(self: MonoidType) -> MonoidType:
pass
@abstractmethod
def __eq__(self, x):
pass
def testAssociativity(self: MonoidType, a: MonoidType, b: MonoidType) -> bool:
return (self * a) * b == self * (a * b)
def testIdentity(self: MonoidType) -> bool:
return self * self.identity() == self
Each argument of the function is followed by a : and a type signature. There is also a signature at the end of the def statement, following the-> . Here is a type hint.
Type hints allow you to give type information to function arguments, return values, and other variables. These are treated in the same way as comments when actually running the program, but they are useful information when using the type checker.
In each place, a variable called MonoidType is declared and used. This is called a ** type variable **, and variables annotated with the same type variable must be of the same type.
In the declaration of MonoidType,bound = "Monoid"is used. In this way, you can limit variables with MonoidType to instances of subclasses of Monoid.
Here, no type hint is given to __eq__. __eq__ is defined in ʻobject`, which is the basis of all classes, and if you give a different type hint, an error will occur.
A "group" is a monoid plus the inverse condition.
Closed for binary operation $ \ star $
- The associative law holds ($ x \ star (y \ star z) = (x \ star y) \ star z $)
- The identity element exists ($ e $ exists such that $ x \ star e = e \ star x = x $)
- There is an inverse element ($ x ^ {-1} $ exists such that $ x \ star x ^ {-1} = x ^ {-1} \ star x = e $)
The abstract base class of the group inherits the monoid, and the inverse element is defined by the method ʻinverse. In addition to defining the inverse element, it's a good idea to do the division definition truediv` here as well.
GroupType = TypeVar("GroupType", bound="Group")
class Group(Monoid, metaclass=ABCMeta):
@abstractmethod
def inverse(self: GroupType) -> GroupType:
pass
def __truediv__(self: GroupType, x: GroupType) -> GroupType:
return self * x.inverse()
def testInverse(self: GroupType) -> bool:
return self * self.inverse() == self.identity()
In particular, a set that forms a group for an operation called "additive group" is called an "additive group". Since the additive group assumes commutativity, we set four conditions as follows.
The operation $ \ oplus $ is closed and
- The associative law holds ($ x \ oplus (y \ oplus z) = (x \ oplus y) \ oplus z $)
- The identity element exists ($ x \ oplus 0 = 0 \ oplus x = x $ exists, $ 0 $ exists, zero element)
- Inverse element exists ($ -x $ exists such that $ x \ oplus (-x) = (-x) \ oplus x = 0 $, minus element)
- Commutative ($ x \ oplus y = y \ oplus x $)
Similar to the case of groups, but the code example is as follows. Instead of defining division in groups, define subtraction.
AdditiveGroupType = TypeVar("AdditiveGroupType", bound="AdditiveGroup")
class AdditiveGroup(metaclass=ABCMeta):
@abstractmethod
def __add__(self: AdditiveGroupType, x: AdditiveGroupType) -> AdditiveGroupType:
pass
@abstractmethod
def zero(self: AdditiveGroupType) -> AdditiveGroupType:
pass
@abstractmethod
def __neg__(self: AdditiveGroupType) -> AdditiveGroupType:
pass
def __sub__(self: AdditiveGroupType, x: AdditiveGroupType) -> AdditiveGroupType:
return self + (-x)
@abstractmethod
def __eq__(self, x):
pass
def testAdditiveAssociativity(self: AdditiveGroupType, a: AdditiveGroupType, b: AdditiveGroupType) -> bool:
return (self + a) + b == self + (a + b)
def testZero(self: AdditiveGroupType) -> bool:
return self + self.zero() == self
def testNegative(self: AdditiveGroupType) -> bool:
return self + (-self) == self.zero()
def testAbelian(self: AdditiveGroupType, a: AdditiveGroupType) -> bool:
return self + a == a + self
Looking at self + (-x), I realize once again that I am defining an operation.
Groups and monoids set conditions for only one operation. The "ring" defines the conditions for two operations.
The operation $ \ star $ called multiplication and the operation $ \ oplus $ called addition are closed.
- Monoids about multiplication $ \ star $
- Abelian group for addition $ \ oplus $
- The distributive law holds between multiplication and addition ($ x \ star (y \ oplus z) = x \ star y \ oplus x \ star z $)
When defining a ring class, simply inherit the monoid and additive classes and implement the distributive law test code.
RingType = TypeVar("RingType", bound="Ring")
class Ring(Monoid, AdditiveGroup):
def testDistributive(self: RingType, a: RingType, b: RingType) -> bool:
return self * (a + b) == self * a + self * b
You can finally implement the ring of integers. Inherit the abstract base class Ring of the ring and override the method declared in @ abstractmethod. Also, define the __repr__ method so that the contents of the ʻInteger` class can be displayed on the Python console.
If it is true, it would be nice if we could extend ʻint by writing only ʻidentity and zero, but unfortunately Python cannot do that, so we will define each method steadily.
class Integer(Ring):
def __init__(self: "Integer", v: int) -> None:
self.v = v
def __repr__(self: "Integer") -> str:
return str(self.v)
def __mul__(self: "Integer", x: "Integer") -> "Integer":
return Integer(self.v * x.v)
def __add__(self: "Integer", x: "Integer") -> "Integer":
return Integer(self.v + x.v)
def __neg__(self: "Integer") -> "Integer":
return Integer(-self.v)
def __eq__(self, x):
if not isinstance(x, Integer):
return NotImplemented
return self.v == x.v
def identity(self: "Integer") -> "Integer":
return Integer(1)
def zero(self: "Integer") -> "Integer":
return Integer(0)
Z = Integer
Now, let's use Z as an alias for ʻInteger`.
Each method specifies the ʻInteger type as a string. This is a forward reference because the definition of the ʻInteger class is not finished at the time of method definition. Use string literals instead of symbols when referencing forwards with type hints.
After implementing the integer, let's check the code with mypy. To check, simply specify the file name in the mypy command and execute it.
$ mypy ./field_extension.py
If there are no problems, no error will be displayed.
Now, let's try removing the __mul__ method from the ʻInteger` class and checking it.
$ mypy ./field_extension.py
field_extension.py:174: error: Cannot instantiate abstract class 'Integer' with abstract attribute '__mul__'
...
Rings for which multiplication is not defined will result in an error. This error will occur when you instantiate the ʻInteger` class without using mypy.
Next, let's change the argument type of the __mul__ method from ʻInteger to ʻint.
def __mul__(self: "Integer", x: int) -> "Integer":
return Integer(self.v * x)
If you run mypy in this state, you will get an error that the types do not match.
$ mypy ./field_extension.py
field_extension.py: note: In class "Integer":
field_extension.py:91: error: Argument 1 of "__mul__" incompatible with supertype "Monoid"
At this point, we have abstracted the monoids, groups, and rings, and successfully implemented the ring of integers.
Next time, after touching on the field, I plan to make rational numbers, modulo rings, and finite fields.
Recommended Posts