Issues with finite_automaton architecture

[bygu4]

Current design of the finite_automaton module contains multiple cyclic imports, and that is due to a bigger problem: confusing architecture that makes the module hard to maintain. I think inheritance is the right way to design finite automata, but we need to refactor some methods and interfaces to restore a proper hierarchy. For example, to_deterministic abstract method is one of the causes of cyclic imports:

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 596 to 600 in 4f36e28

	def to_deterministic(self):
	""" Turns the automaton into a deterministic one"""
	raise NotImplementedError

And similar situation with this method:

pyformlang/pyformlang/finite_automaton/epsilon_nfa.py

Lines 254 to 281 in 4f36e28

	def remove_epsilon_transitions(self) -> "NondeterministicFiniteAutomaton":
	""" Removes the epsilon transitions from the automaton
	Returns
	----------
	dfa : :class:`~pyformlang.finite_automaton.\
	NondeterministicFiniteAutomaton`
	A non-deterministic finite automaton equivalent to the current \
	nfa, with no epsilon transition
	"""
	from pyformlang.finite_automaton import NondeterministicFiniteAutomaton
	nfa = NondeterministicFiniteAutomaton()
	for state in self._start_state:
	nfa.add_start_state(state)
	for state in self._final_states:
	nfa.add_final_state(state)
	start_eclose = self.eclose_iterable(self._start_state)
	for state in start_eclose:
	nfa.add_start_state(state)
	for state in self._states:
	eclose = self.eclose(state)
	for e_state in eclose:
	if e_state in self._final_states:
	nfa.add_final_state(state)
	for symb in self._input_symbols:
	for next_state in self._transition_function(e_state, symb):
	nfa.add_transition(state, symb, next_state)
	return nfa

I think the right way to handle this, is to make sure that inherited classes don't know anything about their descendants. To do this we can get rid of to_deterministic abstraction, and refactor it's implementations as class methods of the DFA class. And also do the same thing with remove_epsilon_transitions. It might look like this:

class DeterministicFiniteAutomaton(NondeterministicFiniteAutomaton):

    @classmethod
    def from_epsilon_nfa(cls, enfa: EpsilonNFA) \
            -> DeterministicFiniteAutomaton:
        # implementation for enfa

    @classmethod
    def from_nfa(cls, nfa: NondeterministicFiniteAutomaton): # ...

And similarly with remove_epsilon_transitions:

class NondeterministicFiniteAutomaton(EpsilonNFA):

    @classmethod
    def remove_epsilon_transitions(cls, enfa: EpsilonNFA) \
            -> NondeterministicFiniteAutomaton:
        #  implementation

This may require some refactoring to make sure we don't use any protected members, but it seems completely doable.

As an alternative, maybe we could try to somehow get rid of inheritance, or just leave a couple of shortcuts like in the current state of pyformlang, but neither of these seems like a good solution.

Also there there are cyclic imports between Regex and EpsilonNFA so there are more things we need to rework outside of finite_automaton module.

[bygu4]

This should probably be in EpsilonNFA:

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 497 to 544 in 4f36e28

	@classmethod
	def from_networkx(cls, graph):
	"""
	Import a networkx graph into an finite state automaton. \
	The imported graph requires to have the good format, i.e. to come \
	from the function to_networkx
	Parameters
	----------
	graph :
	The graph representation of the automaton
	Returns
	-------
	enfa :
	A epsilon nondeterministic finite automaton read from the graph
	TODO
	-------
	* We lose the type of the node value if going through a dot file
	* Explain the format
	Examples
	--------
	>>> enfa = EpsilonNFA()
	>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1), \
	(0, "epsilon", 2)])
	>>> enfa.add_start_state(0)
	>>> enfa.add_final_state(1)
	>>> graph = enfa.to_networkx()
	>>> enfa_from_nx = EpsilonNFA.from_networkx(graph)
	"""
	enfa = finite_automaton.EpsilonNFA()
	for s_from in graph:
	for s_to in graph[s_from]:
	for transition in graph[s_from][s_to].values():
	if "label" in transition:
	enfa.add_transition(s_from,
	transition["label"],
	s_to)
	for node in graph.nodes:
	if graph.nodes[node].get("is_start", False):
	enfa.add_start_state(node)
	if graph.nodes[node].get("is_final", False):
	enfa.add_final_state(node)
	return enfa

[bygu4]

Also, I think it's a good idea to rename TransitionFunction to DeterministicTransitionFunction, and to create an interface from which both transition function classes would be inherited.

[bygu4]

We should do the same thing with Regex, meaning building Regex from given finite automaton in the Regex class itself. After that we can also get rid of Regexable interface.

[bygu4]

That's how I see a better architecture at the moment:

[bygu4]

I'm not sure we need this method if it just calls PythonRegex constructor. It creates a cycle so maybe we should remove it.

pyformlang/pyformlang/regular_expression/regex.py

Lines 547 to 573 in 4f36e28

	@classmethod
	def from_python_regex(cls, regex):
	"""
	Creates a regex from a string using the python way to write it.
	Careful:
	Not everything is implemented, check PythonRegex class \
	documentation for more details.
	It is equivalent to calling PythonRegex constructor directly.
	Parameters
	----------
	regex : str
	The regex given as a string or compile regex
	Returns
	-------
	python_regex : :class:`~pyformlang.regular_expression.PythonRegex`
	The regex
	Examples
	--------
	>>> Regex.from_python_regex("a+[cd]")
	"""
	return regular_expression.PythonRegex(regex)

[bygu4]

@Aunsiels
Before you fix it yourself, just letting you know that I'm ready to take this issue and wanted to get an argeement with the architecture :)

[bygu4]

I think finite_automaton depending on FST is the right thing:

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Line 392 in 9d576c8

def to_fst(self) -> "FST":

but maybe we can move finite automaton objects to fst module to add type annotations without adding import cycles

[Aunsiels]

@bygu4 If you can deal with all the cyclic imports, I would greatly appreciate it! The changes you proposed make sense.