Hacker News Reader

Comment by imtringued | Hacker News Reader

It would be a CS breakthrough if it could... You're asking a lot...

This breakthrough happened already. This is called bidirectional or invertible parsing. See it discussed here https://news.ycombinator.com/item?id=16392654

And this paper https://dl.acm.org/doi/10.1145/1863523.1863525 "Invertible syntax descriptions: unifying parsing and pretty printing"

And this Haskell library https://hackage.haskell.org/package/roundtrip among others

I might be missing something - why would this be a breakthrough? It sounds complicated to generate the interfaces, sure, but is there a theoretical problem blocking this, or just practical?

I've looked at this problem quite a bit over the years...I agree with you completely. there isn't anything fundamental here, just the normal cultural adoption issues, usability, etc. There may be some compilation/complexity issues around formats with variable length fields and self-description, but certainly less problematic than general purpose programming.

I really wish though that there were more traction here, as I really believe that we should be quite prepared do deal with bits and not protobufs by default. nothing wrong with protobufs for quite a number of uses. I just don't know why people are so afraid of and/or biased against bit strings.

Through this thread I really feel like I’m missing something.

Are we not talking about writing binary files that conform to the spec?

Like, in the case of a GIF: simply writing valid garbage data should produce a file that presents as a valid GIF with noise for the image. Similarly: reading the file through the parser and writing it out unmodified should create an identical file (assuming no stenography).

Right?

You're right. The person saying this would be a breakthrough doesn't understand what this is doing.

There are already similarly declarative tools which can accomplish this. Haskell has binary parsing libraries which work similarly and give you both reading and writing capabilities.

I honestly don't get it either. The inverse of the read spec is the write spec. My guess having not dug deeply is that they don't distinguish between required and optional fields, that said, they should still be able to write what they have based on the read spec but could potentially be still an invalid file.

It's a really interesting idea! I'm also surprised there hasn't been much traction here. I've started a Rust library for this: https://github.com/sharksforarms/deku

It's a declarative bit-level symmetrical reader writer generator library.

Yeah I was also confused. I wrote a bidirectional parser/writer layer for yaml in a haskell program I had at work. The yaml structure mappings were all declarative in the code and even allowed documentation for the structures to be printed out. It's not that hard once you define the primitive bidirectional (higher-order) mapping function to go from a `Configurable a` to a `Configurable b`, the rest kind of unfolds from there.

Binary file formats can be vastly more convoluted than YAML. For example, consider roundtripping ZIP archives or PDF documents, or both at the same time (see https://www.alchemistowl.org/pocorgtfo/).

How exactly would it be a cs breakthrough? Are you sure you understand what this does?

Are we talking about different things?

ASN.1 does more or less what I was hoping Kaitai can do. Where's the breakthrough?

I just want to be able to describe network protocols in some "language" and generate code that can serialize/deserialize it.

Kaitai is designed to describe arbitrary, preexisting binary formats. You can’t do that with ASN.1.

Err. I'm not sure what asn.1 is missing for this? I've seen lots of people use asn.1 exactly for this (i.e. writing a grammar for an arbitrary pre-existing binary format not readily described in asn.1).

asn.1 distinguishes between schema and encoding; there are many binary encodings and you can technically devise a custom one that would let you describe the high level structure with an asn.1 grammar and then lay out the actual bits with a custom encoding format so that it matches the pre-existing format you're writing the new serde for). This may work as many formats have this leveled approach. E.g. the lowest level of the spec may tell something about how to encode integers (all integers are 32-bit big endian, or varlen encoded ...), sequences (ength prefixed, or terminated by a sentinel.

Any chances you have some reference to what you saw?

Right I think we were working with PER (tagless) to match a complex multi-layer protocol. Can't share the exemple but let's say asn.1 helped generate saner code than the handrolled one AND allowed other languages to decode...

I understand what you're saying though. Memories of using this were... unpleasant. I think the 'best' alternative for me would be RecordFlux. Ada-like syntax, generation of AoRTE-provable SPARK code, and recently the expressivity of the tool has increased. And the whole thing is in python, easily extensible to build things from the type description: generators, fuzzers, advanced specific parsers (need only one field and want the control fields' positions and sizes), wireshark plugins, Postgres extensions...

I really like what they're doing there. Might be the one of the low-effort (for the user!) lead-bullets for safer software.

I know, I was just using it as kind of an example of what I want and of a similar problem. Maybe not the right example.

I think I'm missing something, but rust's `serde`?

Is this a known theoretical CS problem?

Reply on news.ycombinator.com