Parsing JSON Objects without intermediate ASTs

JSON is a widely-used data interchange format supported by most programming languages. While many libraries implement JSON parsing using an intermediate representation (IR), such as the AST of the JSON object, this can lead to performance issues due to extra allocation and computation. This article explores an alternative approach to parsing JSON objects without using an IR.

To demonstrate this, I will be using Haskell, a language that supports algebraic data types (ADT) and staged meta-programming. However, the approach presented here can be implemented in other languages that support similar features.

First, let's define the AST type for JSON using a parser combinator library. Then, we can write parsers for each data type we wish to parse from a JSON value using functions that build said data from a JSON value. This separation of parsing and value conversion into domain data makes the code easier to maintain.

Now, let's consider a way to parse JSON objects without an IR. We can represent a partially-initialised value, the domain data, by threading it through the parsing process. For example, we could use a data type where all the fields are wrapped in a Maybe, or a data type with a type parameter indicating which fields are present or not. However, this would still require writing a function like PartialAlbum - Maybe Album, which defeats the purpose of avoiding an IR.

Instead, we can rely on Haskell's laziness and set all the object's fields to undefined, or at least those without a 'default' value. Although this may seem unsafe, it can help the compiler during its optimisation pass. To ensure the domain data type's fields are fully initialised, we can pass around a bit set (e.g., a Word64) that gets updated after each field is set by clearing the corresponding bit.

After parsing, we can check if all fields have been set by examining if the bit set equals 0. If not, we can iterate through the remaining bits in the bit set and build an error message listing the missing fields. For fields wrapped in Maybe, we can set those fields to Nothing and return a success.

The implementation of this approach can be achieved using the flatparse library and Template Haskell to generate specialised parsers at compile time. The source code is available on GitHub, along with the benchmark results evaluated using the Criterion library. The benchmarks demonstrate that parsing objects using this approach is significantly faster than using an IR, confirming the impact of the IR on performance.