Post by @hipsterelectron@circumstances.run

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

build tool is now blocked on file-based checksum and i am L O C K E D the fuck in

15 Replies

6 Boosts

This comment is unavailable — it may have been deleted or is not visible to you.

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

i fervently believe that describing an actual literal parse forest for the file content that comes from actually parsing the data in an application-specific context is the correct way to achieve both data compression as well as integrity.

if the value of a single bit modifies the semantics of the entire rest of the file, that's information you kinda do need to know!

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

i actually refer to it as a "parse graph" to be fully general, because in fact most data serialization formats do not neatly compose into nested paired delimiters and a single "parse tree".

once you describe the relationships between atomic data blocks, you can directly use the parse graph to record checksum values that summarize not just the bits in your data, but what the bits mean.

and you (the application developer with domain expertise) can and should be able to construct a hash function that clearly summarizes the important facets of your data structure

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

"compression" is such a curious problem statement and it deserves some lambasting. see my diatribe on UTF-8 at https://codeberg.org/cosmicexplorer/corporeal.

the reason i prefer the term "coding theory" over "information theory" is that a "code" at least is designed to solve a problem.

the problems of "compression" and "integrity" are quite literally just variant encodings of the same set of assumptions.

Codeberg.org

corporeal

String library that uses corpus dictionaries to produce a more efficient encoding than UTF-8.

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

the reason i got way into this is because it ended up being a corollary of the parsing theory i developed in 2020-2022 because i was pissed off that parsing was so fucking annoying to do

one particular result that astounded me about the "algorithm" i developed (i hate that word) is that once my compiled parser processes any given sequence of tokens (e.g. "abca") in one input, the result of that work (the set of valid sub-parses spanning those tokens) can be directly reused for any later input.

i had never encountered an algorithm which amortized across problem instances before. like globally, across all possible inputs

(cc @somebody)

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

one reason the discussion of hashing kind of terrifies me is that the only other algorithm with this kind of property i'm aware of (where work performed for one input can be shared globally across others)..............

............is the one developed by lenstra using the sunzi remainder theorem to crack the discrete log problem

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

however, math always comes from somewhere. the reason my parser compiler was able to work like that is because i:

identified all possible "states" corresponding to individual tokens (i.e. if "a" is used in two places, it means two different things).
- upon beginning the parse, each token is replaced with the multiplicity of possible states.
identified all possible state transitions (not token transitions, but states) allowed by the user-specified grammar (my grammar language is like EBNF if EBNF just worked and did what you wanted it to do), and codified the transitions between each state using a metric fuckton of stack symbols.
- the stack symbols enable non-local inference by having a positive or negative valence. when you transitioned into case 2 of production A, you would add a positive gensymmed stack symbol, and a transition out of case 2 production A would induce a negative version of that symbol.
- this means that instead of backtracking and actually trying to specify individual paths depth-first, i essentially perform a breadth-first traversal of the entire possible state space corresponding to each token-state

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

to be clear, this was not terribly efficient. i was not looking to be efficient. i was looking to produce a grammar model that would be genuinely better than a switch-table recursive-descent parser.

masaru tomita's GLR parsing method in fact solves the same subproblem that i had to, and he did it much better. so i could steal an optimization from his phd thesis

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

there's a particular reason why it's possible to transfer work performed from one subproblem to another. it's because the input is assumed to arise from the same underlying distribution.

now of course this was achieved by construction with the problem statement i used for my parser compiler--i specifically assumed that all input matches my grammar, and i made "before-the-start" and "after-the-end" into synthetic "states" so that there was no distinction between an infinite stream of tokens and a finite-length message.

and finally, the work i performed was to rule out all interpretations that didn't match a specific token extent.

the point i'm making is that completely by chance, largely for aesthetic reasons, i ended up constructing a problem statement that achieved this incredibly weird global progress mechanism

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

the thing about a parser compiler is that the user describes exactly the grammar they want to match. so they're actually constructing a representation of their desired data structure through the grammar interface--which then also happens to be serializable.

(and yes, you can run the grammar in reverse to generate "random" inputs, but this is actually much harder than it sounds for nontrivial grammars. however, serializing a concrete data structure is very straightforward)

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

but real-world data isn't like that! you can't construct it yourself!

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

however, it turns out there is a corresponding representation in coding theory, although "compression" fuckboys have completely missed it.

for a finite-length string of tokens (symbols of a finite alphabet), the standard fuckboy algorithm is prefix trees (aka "huffman" coding). this optimizes based upon symbol frequencies alone.

the bit that.......nobody? seems to get? is that static symbol frequencies constitute the zeroth derivative of the underlying distribution. when you look at windows of length k, you get the (k - 1)th derivative.

Huffman coding

entropy encoding algorithm used for lossless data compression

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

(side note: when jeremy spinrad gave me an extra credit assignment in freshman year to write code to solve an algorithmic problem and then analyze its runtime, the problem i chose, without knowing anything about it was compression, and i independently developed the exact prefix tree approach that everyone names after the MIT fuckboy david huffman. it's really fucking simple and obvious)

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

so, instead of the exponential branching approach that jarek duda feared would be necessary to optimize compression (see https://circumstances.run/@hipsterelectron/117199544287622811), we actually have this totally distinct methodology where we build up symbol runs of length k and use that to infer the (k - 1)th derivative

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

and the other reason i got pissed off when i realized this was that, of course, this is literally indistinguishable from LLM matrix multiplication

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

except!!!!! then i learned that LLMs actually do not attempt to learn tokens in order at all https://en.wikipedia.org/wiki/Transformer_(deep_learning) since 2024 they just dump all the words in the context window into a histogram

Transformer (deep learning)

machine-learning model architecture first developed by Google Brain