i think i need to make an interactive interface for (prime) group operations and i think the way you do that in C is to make an executable. that's such a cute idea it'll be like https://rosie-lang.org
5
Replies
2
Boosts
@jamiejennings i have decided to create a library/cli/framework to perform safe modern cryptography because i have waited a few years and nobody else is doing it. there are quite a few canards that academic cryptographers propagate endlessly that i feel you would no doubt be familiar with from the immensely uncreative status quo for text searching and matching tools.
@jamiejennings your work remains incredibly inspiring to me. i have (to my surprise) had reason to return to my theoretical investigations of parsing recently, largely as a result of major practical and theoretical flaws in checksum and encryption processes. in particular, it remains completely unheard of for cryptographic tools to make use of the fact that 99% of their use cases are fixed-length messages in process-local writable memory and not completely unstructured byte streams. it's absurd and unserious not to make use of that structure, particularly when it's not difficult to describe a very clear group-theoretical rationale for doing so (i don't believe in "information theory")
@hipsterelectron
I'm just popping up sideways to ask,
1. What are examples of the 99% fixed length messages in memory?
2. All of Information Theory, or just how it applies here? Because I've found it wildly useful in determining genomically interesting regions
@jamiejennings
@jamiejennings most notably, when a checksum is used for software release integrity (which is itself applied on top of a separate archiving and/or compression protocol which is opaque and uncontrolled), the mathematical constructs employed are actively optimized to foil any forensic or explanatory capacity, should a file be modified, because checksums are designed for cryptographic signatures, which are architected to avoid leaking information about the message itself. but this obviously demonstrates cryptography's wartime origins continue to influence its modes of thinking--and it also demonstrates how bizarrely detached the filesystem is from the user and application code.
[filesystems are where i hope i can focus my graduate study]. this particular research i've done with robust checksum trees is i think so perfectly up your alley because it is very specifically derived from my domain expertise packaging software at big and small scale and it makes SUCH a great case study of how archival sciences and HCI are in fact a stronger basis than the field of academic cryptography to base robust ontologies around
@jamiejennings i keep trying to put together a blog post about the similarities between the multi-scale transparent checksum approach for software packaging and your absolute tour de force formalizing backrefs into that really slick generalizable graph representation for rosie.
[i'm going to send you an email this weekend, so feel free to ignore this! :D]
no pressure to reply but i have an idea i really believe in
you mentioned offhand at one point that replacing text is absolutely something a text matching framework should support more fluently, and it took a while for that thought to bloom, but i've been doing a lot of work around filesystem reads vs other forms of IPC along with a very intense ring buffer, and i have an incredibly far-out proposal for how i'd like to design a text matching runtime (like a compiler backend that dispatches basic match operations). it wouldn't be encoding stuff like a DFA at all, and instead it would offer a form of IR to tools like rosie, predicated around establishing anchored match boundaries for literal string matches.
the goal of this work is to reduce dependency upon a monolithic central "engine" which merges frontend and backend concerns
in particular i see three fallacies with the monolithic "regex engine" model that would be fun to work on that i think could be aligned with rosie's goals:
- coupling memory/locality expectations to the automaton model is extremely brittle. sometimes it results in expectations about memory allocation and blocking APIs, furthering regex pattern language ossification (especially if you just expect to iterate your opaque DFA until it fails). rosie of course is already way ahead of this, but this is something that junyer was really interested in brainstorming for what he called "re3".
- having worked on build tools and performed this kind of i/o rework on the scala compiler i want to be clear that am imagining a system that would make this proposed "backend" layer into something more flexible for you the maintainer, not pulling any control away from you. "i/o is important" to me means making i/o more navigable to the user. but i don't really know your needs here at all yet, and "performance" is absolutely not the main goal here (see below =])
hypothesis: bidirectional merging is an extensible model with robust guarantees
one of hyperscan's achievements i was so envious of was how its callback API [i wrote these docs] managed to be the most flexible possible approach while retaining guarantees that users are intended to leverage. in particular, it was able to build PCRE support on top of its (extremely limited) low-level pattern language, because the callback API worked like a coroutine (and provides all match results) and managed its own data reading and queueing.
- in particular, "you can totally run a search in the search callback" was really novel to me--it's the polar opposite of "don't parse HTML with regex".
- i am not terribly interested in spending any time on complex SIMD mechanics like hyperscan. really my hypotheses here are:
- bottom-up bidirectional expansion of sub-graphs should be an implementation detail
- the "build up from seeds across the input" approach does not impose any difficulty in translation (i believe this approach forms a superset of functionality and does not lead to unintuitive behavior)
- coroutine-based parallel matching can produce a simple API that enables users and the rosie compiler to expand functionality to arbitrary complexity without manually managing global parse state
i would have loved to build more on hyperscan itself, but its single callback API wasn't really built for e.g. nested expressions or user-driven parallelism. there's also a huge amount more rosie can do than hyperscan ever could, because it accepts the responsibility of being a real programming language.
performance features that other tools are limited from
(a) in particular, one thing that has always bugged me is learning from andrew gallant (rust regex) that a huge component of user-visible regex engine "performance" revolves around the "prefilter" operation (see e.g. my RE2 docs. but of course, the basic automaton model can only execute that once, before the search begins, because the DFA model can't handle something like merging two sub-matches into a graph/tree. in particular, something like "a.*b" should be able to match both parts of the text separately, with fast SIMD code that doesn't do anything complex.
(b) another thing that is so useful and very difficult for regex users to do themselves is support for non-contiguous searching (this is another of hyperscan's best features, but it really should be more common because this frequently leads to security bugs). "non-contiguous" is actually a very narrow way to consider the issue imho--if you reframe the problem to expand bidirectionally from match "seeds", you don't just get the ability to seek backwards, you also get reparsing after real-time modifications for free.
what this model was designed to solve
this capability isn't magic, it's just something you don't have to explicitly solve for when you design matching around the assumptions:
parsing is about reconciling ambiguities in text input, so forward progress corresponds to absorbing more contiguous input tokens.
- side note: this methodology has convinced me that the standard expectation of having a single top-level ("TOP") production is extremely artificial.
- for programming languages with translation units and modules: makes sense! but enforcing that elsewhere encourages the user to think of parsing in terms of validation logic, not describing the data
- ran into this with coffeescript after google added new semantics without documenting it https://github.com/jashkenas/coffeescript/pull/5474 unfortunately I haven't replaced jison yet
greedy matching semantics (like POSIX alternations, or PEG ordered choice) actively subvert safe composition. non-contiguous matching as well as synchronously returning the first match makes the whole search process non-composeable
- this precise bottom-up parsing and restartable logic was the part that worked immediately with the whole parser compiler i wrote.
- the difficult part ended up being the frontend which performed three graph transformations to flatten the compile-time "stack diff" abstraction into a trie for the non-branching transitions and then statically analyzing the cyclic groups
- and while the theoretical work is one of my proudest achievements, i feel the rosie project embodies everything i wanted out of my own parser compiler frontend and so much more
- hence this proposal!
conclusion
finite automaton models (or god forbid LALR) often fail to understand that their fear of "backtracking" reveals their discomfort with the inflexibility of their own internal semantics!
i believe much of the reason this parallel coroutine approach hasn't been done is because it requires developing a internal protocol to communicate and retain consistency across nested sub-parse graphs, which is necessarily a different problem than the compiler front-end and mid-end (e.g. your backref graph model).
i first envisioned this for two reasons:
- FFI with other languages (hence mentioning buffering and i/o)
- interop with IPC
i really would like text matching tools to be able to interop together more, but that may be reaching a bit too far afield
- i do think that decoupling input/output from match logic (so it can be managed separately is likely to be more directly useful for interop
