Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement Incremental Automaton #28

Open
DavePearce opened this issue Dec 10, 2015 · 0 comments
Open

Implement Incremental Automaton #28

DavePearce opened this issue Dec 10, 2015 · 0 comments

Comments

@DavePearce
Copy link
Member

After the work done on developing the IncrementalAutomatonMinimiser, it has become clear that closer integration with Automaton would be very helpful. See #19 for more.

Therefore, this issue proposes to rework Automaton in order to ensure all operations are incremental and do not do work proportional to the number of states. To make this happen requires:

  1. Maintaining parent pointers for all states. This is necessary for all incremental algorithms and, in particular, enables incremental minimisation and compaction.
  2. Resolving the issues of dangling cycles. That is, after a rewrite a set of states forming a cycle may not be garbage collected. Since the automaton is rooted, we can consider least common ancestors as one alternative approach.
  3. Resolving the issue of making substitute() incremental. This algorithm is currently not incremental and I'm not sure how best to make it so.

These issues are really central to improving the overall performance of the compiler.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant