Compression, synchronization and backup systems often use rolling hash to implement "content-defined chunking", an effective form of deduplication.
In optimized implementations, Rabin-Karp is likely to be the bottleneck. See for instance https://github.com/facebook/zstd/pull/2483 which replaces a Rabin-Karp variant by a >2x faster Gear-Hashing.
> I would love to hear of other low(er) barrier-to-entry ways to use LaTeX, because it’s a pretty steep commitment for someone who isn’t a professional writer.
I have been working on and off on a fork of LaTeX with real-time feedback: you can see the document and error messages rendered and updated live. It also supports SyncTeX (going from a source line to the corresponding output and vice-versa).
I added vim support recently, you can see it in action there: https://github.com/let-def/texpresso.vim
There is also emacs support in the main repo (https://github.com/let-def/texpresso). That's all quite experimental, but I hope to do a first release next year. It should work on most unix, I test with Linux and macOS.
I think what you suggest is possible, derivation might even be well suited for this application, however I can't tell if it would be better than existing approaches.
There are some chances that it might be interesting in practice, since it seems that this application of derivatives has not been much studied, but that's highly speculative.
> Does there exist a regex engine I can try that uses derivatives and supports large Unicode classes and purports to be usable for others? :-)
I don't know any besides ocaml-re that Drup already linked, sorry :).
And sorry that my comment is hard to decipher. I think the core point is that the "character set" can be an abstract type from the point of view of the derivation algorithm.
So it doesn't matter how they are represented, nor "how big" a character set is.
With Antimirov's derivative (which produces an NFA), there is no constraint on this type.
With Brzozowski's derivative, you need at least the ability to intersect two character sets. So the type should implement a trait with an intersection function (in Rust syntax, `trait Intersect fn intersect(self, Self) -> Self`). That's necessary for any implementation generating a DFA anyway.
And if you also want to deal with complementation, then a second method `fn negate(self) -> Self` is necessary.
I don't think you should be worried about Unicode in particular. Although the derivation formula on paper is parameterized by a character, you don't have to compute the derivative for every character separately.
It's actually easy to compute classes of characters that have the same derivative (it's done in the linked "Regular-expression derivative re-examined" paper, although their particular implementation favors simplicity over efficiency), and it's not even necessary when using Antimirov's partial derivatives.
Actually, the complexity of the derivation is independent of the size of the alphabet. You could even define derivation on an arbitrary semi-lattice, not necessarily a set of characters. (Or a boolean algebra if you care about negation/complementation).
The difficulty in handling unicode has more to do with the efficiency of the automaton representation and manipulation rather than in turning the RE in an NFA or DFA.
Of course, this is nitpicking :). For all practical purpose, this O(log n) is O(1).
If you are interested, I can try to recover the proof that the rotation step can be done in O(n), thus allowing to apply the master theorem on the main recursion and getting the O(n log n) result.
I wrote a similar sorting algorithm around 14 years ago (fast, inplace, adaptive merge sort algorithm using rotation/swap, and I think, stable). This is all I remember from the time...
I was able to prove (on paper) that the whole algorithm was actually O(n log n). The moves seems to have a bad recursion pattern, but assuming my proof was right, it is possible to have a well behaved implementation in practice.
However, the recursion pattern didn't fit the master theorem, I remember having to do a taylor expansion of some formula giving an upper bound on the number of computation steps to prove the O(n log n) bound.
And runtime measurements graph were showing the expected O(n log n) curve, as in your cases. So maybe they are not O(n log n ^ 2) as you feared...
I did not keep much information from that time :P.
> having the circle not reset after every color change is probably not feasible unless the module order is fairly convoluted right?
Not necessarily no. The thing is that you could have an early module that implements a framework to manage state.
For the circle rotation, it is quite easy, it is a single number.
You could do something like:
"The rotation of the circle is represented by a float initialized to 0".
Then even when your module is reloaded, the hypothetical framework takes care of preserving this piece of state.
Both the synchronous and asynchronous frontends preserve as much state as possible (all untouched modules are kept). They differ in the control flow they permit (the asynchronous one being more expressive).
I will try to make a parallel with a simple Makefile-driven project.
In the initial build, all files are built, following a topological ordering of the dependencies.
For the Makefile it means invoking some unix command for each intermediate artefact.
For Hotcaml, it means parsing, typing, compiling and loading each module.
After that, build is incremental: when a file is modified, only this file and its reverse dependencies need to be rebuilt.
Make will keep the existing artifacts that are not out of date.
Hotcaml will keep the existing modules that are not out of date. And their state is preserved.
Now, the synchronous frontend is quite like a regular Makefile: a build step is considered done when the build command finishes.
The asynchronous frontend allows command to run in the background, like a Makefile that would spawn processes/daemon using the shell & control operator.
In Hotcaml, these threads continue executing concurrently with the reloading process. They can be notified that their "host" module has been reloaded by registering with some runtime service (via a module named Hotlink).
There is actually some notion of persisting state in it. Reloading is done at the granularity of a module. The reverse dependencies of a module that changed are also reloaded, but the dependencies are not. The runtime state of all modules that are not reloaded is persisted.
The dependency graph is roughly: system layer -> renderer -> slideshow
The system layer initializes the window (with SDL) and an OpenGL context.
The renderer allocates resources (buffers, fonts, ...).
The slideshow only defines the content to be drawn.
In the live code, only the slideshow is modified, so the system and renderer states are not affected.
Doing reloading at the module granularity meshes well with ML semantics: it is a straightforward extension of the "hyperstatic environment" and it preserves type safety and modular abstraction.
A static language that is designed with hot reloading in mind could do better, the generative nature of ML type definitions is not ideal.
I guess that structural type systems permit a finer grained notion of reloading. Actually, a finer-grained notion of persistence and state migration could be built as a library (with some macros) on top of Hotcaml. The important step is to be able to reify type definitions and then to define some notion of "type compatibility" (between old and new modules) by induction on the structure of types.
This is a lot of work, but could be built on top of Hotcaml foundations.
The output is a bit underwhelming. You might be interested in https://codinuum.github.io/gallery-cca/
It is not based on tree sitter , the parsers they use are quite impressive. Yet a difficult part is computing large tree diff (it is O(n^3) if I remember well), the authors devise heuristics that are efficient in practice and should be adaptable to tree sitter.
Indeed. GADTs provide type equalities and existentials. This example involves neither, only sub-typing (which is quite strong and interesting in Typescript)
