Bidirectional parsing/prettyprinting · ideas

The core idea is that you define one 'Codec' (AKA 'Grammar' or 'Schema') which is the bidirectional translation to-and-from your datastructure and the external format.
That is, rather than have a separate definition of e.g. "how to go from JSON to Post" and "how to go from Post to JSON", you only specify the structure once.

Qqwy / Marten (Oct 03 2022 at 15:33):

BiMap e a b : { forward : (a -> Result b e), backward : (b -> Result a e)

So you can transform data between an a and a b, but either transformation might fail.

Qqwy / Marten (Oct 03 2022 at 15:36):

Example: If you'd want to parse a float from a JSON AST, you'd have for instance a BiMap e JSON F64, where forward would complain if the JSON does not contain a float, and backward would complain if the floating point value is NaN or Infinity which is not allowed inside JSON.

And then there is a higher-abstraction datatype commonly called 'Codec', 'Schema' or 'Grammar' in which you can combine multiple of these bimaps to use it with your custom datatypes. (i.e. match key-values in the AST with fields in your datatypes), usually written as something along the lines of

Codec r w a : { read : r a, write : a -> w a}

(invalid Roc as-is because it uses higher kindred datatypes. But concrete Codec types can be made by using concrete examples for 'r' and 'w', datatypes containing the appropriate environment to parse an a from resp. print an a into.)

Ayaz Hafiz (Oct 03 2022 at 15:41):

not sure if this is part of what you read, but "A Monadic Framework for Bidirectional Programming" is the title I know best wrt to this: https://poisson.chat/mfbp/poster.pdf

Ayaz Hafiz (Oct 03 2022 at 15:42):

I could have sworn there was a poster at sigplan about this as well last year but I can't find it now

Ayaz Hafiz (Oct 03 2022 at 15:42):

Qqwy / Marten (Oct 03 2022 at 15:43):

Another good example is tomland which is a bidirectional TOML parser-prettyprinter library written in Haskell. (link goes to the blog post explaining its internals).

lue (Oct 03 2022 at 16:10):

BiMap e a b : { forward : (a -> Result b e), backward : (b -> a) }

BiMap e a b : { forward : (a -> Result b e), backward : (b -> Result a e) }

Qqwy / Marten (Oct 03 2022 at 16:10):

Qqwy / Marten (Oct 03 2022 at 16:17):

:+1:
As long as your concrete datatype is fully representable in the serialized format then the backward function indeed does not need to return a Result.

Do you handle examples like Infinity/NaN for floats that cannot be written down in JSON some other way?

Qqwy / Marten (Oct 03 2022 at 16:18):

(Another example: Integers larger than 2^53 are also not portably representable in JSON)

Qqwy / Marten (Oct 03 2022 at 16:19):

Your library looks great by the way. There already is so much well-documented code there 🤯

lue (Oct 03 2022 at 16:32):

I let elm/json handle all the ugliness ;). Which means even I don't know what elm encodes NaN etc. to

Qqwy / Marten (Oct 03 2022 at 16:33):

The cherry on top of these bidirectional definitions by the way, is that you can also read the codec structures directly and create other schema formats from them (e.g. a "Json Schema", a TreeSitter schema, etc.) that could be used when describing an API or to use in external tools (like your IDE) so they can warn for common mistakes immediately. (Like: "This field name is not known" or "the hostname field in your configuration file is only valid if it contains a string that can be parsed as an URL")

Qqwy / Marten (Oct 03 2022 at 16:34):

Now you've made me curious. Time to see how Elm/json does it under the hood :happy:

Qqwy / Marten (Oct 03 2022 at 16:35):

Qqwy / Marten (Oct 03 2022 at 16:46):

At least it matches JSON.stringify in plain JS, so I guess it makes sense :shrug:

lue (Oct 03 2022 at 16:52):

Qqwy / Marten (Oct 03 2022 at 17:45):

By the way: This same pattern can be used to talk about how a datastructure might map to a record in a relational database table!