Fix architecture issues

[bygu4]

Some modules of pyformlang have a strange design that makes this project hard to maintain and develop, and we should think about what we can do to make the architecture cleaner and more concise.

[bygu4]

This should be in EpsilonNFA:

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 497 to 504 in 176a609

	@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

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 531 to 533 in 176a609

	"""
	enfa = finite_automaton.EpsilonNFA()
	for s_from in graph:

[bygu4]

We have to get rid of this abstract method, otherwise we are bound to have cyclic imports:

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 644 to 648 in 176a609

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

[bygu4]

This shouldn't return None:

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 688 to 702 in 176a609

	def to_state(given: Any) -> State:
	""" Transforms the input into a state
	Parameters
	----------
	given : any
	What we want to transform
	"""
	if given is None:
	return None
	if isinstance(given, State):
	return given
	return State(given)

[bygu4]

Probably should be for Any type, because we cast these parameters to State and Symbol anyway:

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 46 to 49 in 176a609

	def add_transition(self, s_from: State, symb_by: Symbol,
	s_to: State) -> int:
	""" Adds a transition to the nfa

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 77 to 81 in 176a609

	"""
	s_from = to_state(s_from)
	symb_by = to_symbol(symb_by)
	s_to = to_state(s_to)
	temp = self._transition_function.add_transition(s_from, symb_by, s_to)

[bygu4]

Same as previous:

pyformlang/pyformlang/finite_automaton/finite_automaton.py

Lines 121 to 124 in 176a609

	def remove_transition(self, s_from: State, symb_by: Symbol,
	s_to: State) -> int:
	""" Remove a transition of the nfa

[bygu4]

Maybe it's a good idea to rename TransitionFunction to DeterministicTransitionFunction, and also create an interface TransitionFunction from which we can inherit both transition function classes

pyformlang/pyformlang/finite_automaton/transition_function.py

Lines 17 to 22 in 176a609

	class TransitionFunction:
	""" A transition function in a finite automaton.
	This is a deterministic transition function.

[bygu4]

I think it would be better to make an overload for this method, as it's output type is different depending on the number of input parameters:

pyformlang/pyformlang/finite_automaton/transition_function.py

Lines 123 to 126 in 176a609

	def __call__(self, s_from: State, symb_by: Symbol = None) -> List[State]:
	""" Calls the transition function as a real function

Also probably should return Set rather than List

[bygu4]

Iterable[Any] as we cast it to Symbols:

pyformlang/pyformlang/finite_automaton/epsilon_nfa.py

Lines 121 to 123 in 176a609

	def accepts(self, word: Iterable[Symbol]) -> bool:
	""" Checks whether the epsilon nfa accepts a given word

[bygu4]

Add same method for TransitionFunction (but it always returns True):

pyformlang/pyformlang/finite_automaton/nondeterministic_transition_function.py

Lines 149 to 152 in 176a609

	def is_deterministic(self):
	""" Whether the transition function is deterministic

[bygu4]

I think we can try moving this to NFA and making it a classmethod (like NondeterministicFiniteAutomaton.remove_epsilon_transitions(enfa))

pyformlang/pyformlang/finite_automaton/epsilon_nfa.py

Lines 253 to 266 in 176a609

	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:

[bygu4]

Same here with DeterministicFiniteAutomaton.from_epsilon_nfa(enfa)

pyformlang/pyformlang/finite_automaton/epsilon_nfa.py

Lines 332 to 341 in 176a609

	def to_deterministic(self) -> "DeterministicFiniteAutomaton":
	""" Transforms the epsilon-nfa into a dfa
	Returns
	----------
	dfa : :class:`~pyformlang.finite_automaton\
	.DeterministicFiniteAutomaton`
	A dfa equivalent to the current nfa

But it will require some refactoring to make sure we don't use protected enfa members

[bygu4]

Same story:

pyformlang/pyformlang/finite_automaton/nondeterministic_finite_automaton.py

Lines 118 to 127 in 176a609

	def to_deterministic(self) -> "DeterministicFiniteAutomaton":
	""" Transforms the nfa into a dfa
	Returns
	----------
	dfa : :class:`~pyformlang.deterministic_finite_automaton\
	.DeterministicFiniteAutomaton`
	A dfa equivalent to the current nfa

[bygu4]

Cyclic import here between Regex and EpsilonNFA

pyformlang/pyformlang/finite_automaton/epsilon_nfa.py

Lines 398 to 421 in 176a609

	def to_regex(self) -> "Regex":
	""" Transforms the EpsilonNFA to a regular expression
	Returns
	----------
	regex : :class:`~pyformlang.regular_expression.Regex`
	A regular expression equivalent to the current Epsilon NFA
	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)
	>>> regex = enfa.to_regex()
	>>> regex.accepts(["abc"])
	True
	"""
	from pyformlang.regular_expression import Regex
	enfas = [self.copy() for _ in self._final_states]

[bygu4]

I think it would be better to make an overload for this method, as it's output type is different depending on the number of input parameters:

pyformlang/pyformlang/finite_automaton/transition_function.py

Lines 123 to 126 in 176a609

	def __call__(self, s_from: State, symb_by: Symbol = None) -> List[State]:
	""" Calls the transition function as a real function

Also probably should return Set rather than List

Same in NondeterministicTransitionFunction and FiniteAutomaton

[bygu4]

We should also rework DoublyLinkedList because Node can access List

pyformlang/pyformlang/finite_automaton/doubly_linked_node.py

Lines 6 to 20 in 176a609

	def __init__(self,
	list_in,
	next_node=None,
	previous_node=None,
	value=None):
	self.next_node = next_node
	self.previous_node = previous_node
	self.value = value
	self.list_in = list_in
	def delete(self):
	"""Delete the current node"""
	self.list_in.delete(self)

[bygu4]

This is strange, probably should be in PythonRegex:
https://github.com/Aunsiels/pyformlang/blob/4f36e28492a529d67129dcecaf9d07ca69fb0cf6/pyformlang/regular_expression/regex.py#L546-L573
No, actually we can just remove it

[bygu4]

I think we could rework Regexable to be inherited by FiniteAutomaton, and it should contain not a method turning it to Regex straightaway, but rather a bunch of methods that would allow to turn it to Regex in the Regex class itself. Or we could just get rid of Regexable

[bygu4]

https://github.com/Aunsiels/pyformlang/blob/4f36e28492a529d67129dcecaf9d07ca69fb0cf6/pyformlang/finite_automaton/deterministic_finite_automaton.py#L448-L453
self._start_state could be empty here. Property should return Optional[State].
And _start_state should be renamed to _start_states really

[bygu4]

pyformlang/pyformlang/regular_expression/regex.py

Lines 310 to 327 in 176a609

	def _get_production(self, current_symbol, count=0):
	next_symbols = []
	next_productions = []
	for son in self.sons:
	next_symbol = "A" + str(count)
	count += 1
	# pylint: disable=protected-access
	new_prods, count = son._get_production(next_symbol, count)
	next_symbols.append(next_symbol)
	next_productions += new_prods
	new_prods = self.head.get_cfg_rules(current_symbol, next_symbols)
	next_productions += new_prods
	return next_productions, count
	def __repr__(self):
	return self.head.get_str_repr([str(son) for son in self.sons])

self.head may be None here, maybe we can set it as Empty Symbol in the constructor

[bygu4]

Probably that's better. It's pretty unclear what Regexable should mean, and it's used only for finite automata anyway

[gsvgit]

@bygu4

• What the reason to add from_epsilon_nfa to DFA? If we support the chain of transformations, let it be an explicit chain always: EpsilonNFA -> NFA -> DFA.
• Why to_epsilon_nfa, not from_regexp for EpsilonNFA? Just for uniformity.
• I'm not sure that I realize hierarchy on Regex*. Why not just functions like from_string or from_python_regex?

[bygu4]

@gsvgit

• Yes, I think that's reasonable.
• We could turn the dependency one way or another, maybe it would be easier to leave to_epsilon_nfa for Regex since it already stores ENFA as a member. But ultimately, we need to think what would make architecture more straightforward. Also we should see what are the relations between regular_expression and cfg.
• Should we rework regular_expression too? PythonRegex already inherits Regex, doesn't seem like any problems there.

[gsvgit]

• We could turn the dependency one way or another, maybe it would be easier to leave to_epsilon_nfa for Regex since it already stores ENFA as a member. But ultimately, we need to think what would make architecture more straightforward. Also we should see what are the relations between regular_expression and cfg.

The idea to store ENFA in regex looks strange. Conversion of regex to ENFA is just yet another conversion, similar to ENFA to NFA conversion and so on.

Yes, analysis of relations between CFG, Regexps, RSM, and automata required before final architecture proposal.

• Should we rework regular_expression too? PythonRegex already inherits Regex, doesn't seem like any problems there.

Maybe not now, but why not. The final goal is to make whole pyformlang better.

[bygu4]

• What the reason to add from_epsilon_nfa to DFA? If we support the chain of transformations, let it be an explicit chain always: EpsilonNFA -> NFA -> DFA.

I thought more about it, and maybe it's better to leave from_epsilon_enfa to avoid unnecessary copying. It's already implemented in a suiting way, and that's probably what the maintainer would want.

[bygu4]

Maybe it's better to move it to cfg module:
https://github.com/FormalLanguageConstrainedPathQuerying/pyformlang/blob/master/pyformlang/pda/cfg_variable_converter.py

[bygu4]

This is meant to return StackSymbol, but pda.Epsilon is not it. Probably should rework pda object design

pyformlang/pyformlang/cfg/pda_object_creator.py

Lines 30 to 41 in 176a609

	def get_stack_symbol_from(self, stack_symbol):
	"""Get a stack symbol"""
	if isinstance(stack_symbol, cfg.Epsilon):
	return pda.Epsilon()
	if self._inverse_stack_symbol[stack_symbol] is None:
	value = str(stack_symbol.value)
	if isinstance(stack_symbol, cfg.Terminal):
	value = "#TERM#" + value
	temp = pda.StackSymbol(value)
	self._inverse_stack_symbol[stack_symbol] = temp
	return temp
	return self._inverse_stack_symbol[stack_symbol]

[bygu4]

I would suggest building context free grammar from PDA in the CFG class

pyformlang/pyformlang/pda/pda.py

Lines 332 to 358 in 176a609

	def to_cfg(self) -> "cfg.CFG":
	""" Turns the language L generated by this PDA when accepting \
	on empty \
	stack into a CFG that accepts the same language L
	Returns
	----------
	new_cfg : :class:`~pyformlang.cfg.CFG`
	The equivalent CFG
	"""
	self._cfg_variable_converter = \
	CFGVariableConverter(self._states, self._stack_alphabet)
	start = cfg.Variable("#StartCFG#")
	productions = self._initialize_production_from_start_in_to_cfg(start)
	states = self._states
	for transition in self._transition_function:
	for state in states:
	self._cfg_variable_converter.set_valid(
	transition[INPUT][STATE],
	transition[INPUT][STACK_FROM],
	state)
	for transition in self._transition_function:
	for state in states:
	self._process_transition_and_state_to_cfg(productions,
	state,
	transition)
	return cfg.CFG(start_symbol=start, productions=productions)

[bygu4]

This class is used both for converting PDA to CFG and for intersecting CFG with a deterministic FA. To prevent ambiguity, let's use it for converting PDA only. Also, for simplicity, I would suggest removing CFG/DFA intersection, leaving an option of turning CFG to PDA:

pyformlang/pyformlang/cfg/cfg.py

Line 791 in 176a609

def intersection(self, other: Any) -> "CFG":

With that we could get rid of importing Regex. I think regex module depending on cfg is the right way to go

[bygu4]

I think it would be better to define intersection of PDA with DFA explicitly:

pyformlang/pyformlang/pda/pda.py

Line 445 in 176a609

def intersection(self, other: Any) -> "PDA":

And then we can use Regex -> ENFA -> DFA transition chain

[bygu4]

This class is used both for converting PDA to CFG and for intersecting CFG with a deterministic FA. To prevent ambiguity, let's use it for converting PDA only. Also, for simplicity, I would suggest removing CFG/DFA intersection, leaving an option of turning CFG to PDA:

On other hand, that would mean converting CFG to PDA and back again, so maybe we can just use less strict annotations for the variable converter

[bygu4]

_delta should probably be Dict[(State, Symbol), Set[(State, Symbol)]]:

pyformlang/pyformlang/fst/fst.py

Lines 120 to 123 in 176a609

	if head in self._delta:
	self._delta[head].append((s_to, output_symbols))
	else:
	self._delta[head] = [(s_to, output_symbols)]

[bygu4]

If it returns IndexedGrammar maybe we should define intersection in the IndexedGrammar class

pyformlang/pyformlang/fst/fst.py

Line 209 in 176a609

def intersection(self, indexed_grammar):

[bygu4]

We should define this for FST only, and then transition chain Regex -> ENFA -> FST can be used:

pyformlang/pyformlang/indexed_grammar/indexed_grammar.py

Line 335 in 176a609

def intersection(self, other: Any) -> "IndexedGrammar":

[bygu4]

pyformlang/pyformlang/rsa/recursive_automaton.py

Lines 79 to 83 in bffade7

	@property
	def boxes(self) -> dict:
	""" The set of boxes """
	return self._nonterminal_to_box

set(self._nonterminal_to_box.values()) if we want to return a set of Boxes