Reversible Functions

Currently writing a JSON Importer and creating some POJOs based on the data. I also have a requirement to write an JSON Exporter which take the information in the POJOs and exports a JSON doc.

To me I would like to reuse the the same code if possible. Does such a thing exist where you can reverse the function/method? i.e I could (depending on what I pass it) process it in the correct order and output the desired result, using the same code?



Yes, this is definitely possible.

  • Invertible syntax descriptions: Unifying parsing and pretty printing by Tillmann Rendel and Klaus Ostermann is one fairly well-known approach for parsing/unparsing (which is kind of what you are doing) based on partial isomorphisms.

The paper also points to other approaches based on

  • Arrows (Polytypic compact printing and parsing by Patrik Jansson and Johan Jeuring),
  • BiArrows (There and back again: arrows for invertible programming by Artem Alimarine, Sjaak Smetsers, Arjen van Weelden, Marko van Eekelen, and Rinus Plasmeijer, note that this is about invertible programming in general, not just parsing/unparsing or serialization/deserialization), and
  • An injective language for reversible computation by Shin-Cheng Mu, Zhenjiang Hu, and Masato Takeichi, a full calculus for reversible programming in general.

I can think of three major reasons why it is generally not possible to programmatically invert an arbitrary function in most general programming languages:

  1. Only a one-to-one function (aka a “bijection”) can be inverted even in principle. That means the function must produce a unique output value for every single possible combination of inputs. In practice most functions are not one-to-one, nor would it make any sense for them to be. For instance, a correct JSON parsing function will produce the same POJO for many different strings.

  2. The function would have to be composed entirely of operations/functions that have known inverses. Even the basic arithmetic operations are not quite invertible (due to overflow, underflow, rounding errors and the division by zero problem), and as far as I know the built-in methods of most languages are largely non-invertible (concatenating strings, accessing array elements, taking substrings, etc are all not one-to-one).

  3. It doesn’t make sense to talk about inverting a function which has side effects. What is the opposite of sending data over a network connection, saving data to a hard drive or printing a character to a screen? In some contexts these operations may be undoable, but you can’t un-print a character before any characters have been printed, whereas you can decrement an integer without incrementing it first.

However, it is theoretically possible to design a language (or a DSL within your favorite language) that consists solely of strictly invertable operations, in which it would be possible to programmatically invert any function. The links in Jörg’s answer cover this far better than I can.

For the purposes of your JSON importer/exporter, it’s likely that simply writing two separate code paths would be a lot less work than constructing an invertable DSL with all the string building and object constructing operations needed to do what you want.


Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *