YAML Parser/Emitter Library for Koka

[syaiful6]

I played with this project lately, and need a YAML parser functionality. So, I created one here: https://github.com/syaiful6/yaml.kk It also can be used as reference how to call FFI, especially C. I also learned a lot. But, to my surprise it far more easier than writing OCaml FFI. 👍

It still not completed, currently it will yield libyaml event for the given file. I am still tinkering how the API will look like. It will be nice, if we can serialize/deserialize it into our struct/data type.

[TimWhiting]

Glad to see you were able to figure out the C ffi, looks great!

Yeah, API design is hard in general, but with no standard "idiomatic" reference for Koka it is even harder to figure out what the API should look like. I agree that since the primary purpose will likely be using it to serialize into a type it might be best to focus on that. In particular, it looks like it currently supports a streaming API, but I don't think that will be the most common usage pattern. (Streaming is very useful when you need it, but overkill when you don't). I know that the C library is oriented around that.

For streaming based APIs that encapsulate resources I've liked using first-class named effects. https://github.com/koka-lang/koka/tree/dev/samples/handlers/named. (I used this pattern for an http parser here: https://github.com/TimWhiting/koka/blob/llhttp/lib/llhttp/llhttp.kk).

[osa1]

In particular, it looks like it currently supports a streaming API, but I don't think that will be the most common usage pattern. (Streaming is very useful when you need it, but overkill when you don't). I know that the C library is oriented around that.

Streaming events is great because it allows the users to skip parts of the parsed thing, or generate different ASTs based on use cases.

The problem is that you have to implement your parser in a way that allows suspending parsing and resuming later, which makes it slower than some of the alternative designs.

With effects you can have a "push style" API that calls event callbacks of a listener (instead of generating events in a stream) which keeps the parser code simple and fast. When you need a stream, you can then invoke a "yield" effect in the callbacks and invert the control flow. Example: https://ocaml.org/manual/5.3/effects.html#s%3Aeffects-sequence.

I wrote about the push vs. stream APIs here (with the use cases they support): https://osa1.net/posts/2024-11-22-how-to-parse-1.html (see also follow-up posts)

It's not easily possible to layer abstractions without losing performance unless you monomorphise. In the end in Koka (and many other languages) the best performing one will be a parser that directly (no callbacks, no streams) generates the AST that you need.

I think staging (as in multi-stage programming) could potentially help here, by generating parser code that inlines callbacks for the events (which is what Rust does in my blog post above), but I'm not aware of any previous work that explores this.

[TimWhiting]

Maybe my statement was a bit strong in a sense. I do think that streaming is good for many parsers. But I see yaml mostly used in config files where often the whole AST is needed, not partial pieces. (Not that there couldn't be use cases where streaming would be useful even in the case of yaml).

As far as parsing in general:
Another advantage of the loose coupling of event-driven interfaces as opposed to iteration or direct AST generation is that it could be easily parallelized (e.g. lexer on one thread pushing events to a parser in another). I'd also like to see a "structured lexer" to do some basic matching of braces and things as well for better incremental parsing. Whether that should be done with a state-based lexer or something in-between the lexer and parser is an open question in my mind. (I guess we've been thinking along the same lines: https://osa1.net/posts/2024-11-02-structural-editor.html).

Also, like you mention, inlining is crucial to performance. I'd really like to do a static analysis that can inline effect operations.

[syaiful6]

@TimWhiting I am not sure how to use named handler yet.

So, I end up completed the basic parser and represents the yaml nodes that user can rely on to construct their struct. I end up using this:

pub type yaml-value
  Scalar(anchor: anchor, tag: tag, value: string, style: style, plain-implicit: bool, quoted-implicit: bool)
  Alias(name: anchor-name)
  Sequence(tag: tag, anchor: anchor, members: list<yaml-value>, implicit: bool)
  Mapping(tag: tag, anchor: anchor, members: list<(yaml-value, yaml-value)>, implicit: bool)

then I have a parser that will take list<marked-event> to <div> either<string, list<yaml-value>>. The div effect introduced, since it use recursive. I tried create a parser on effect handler, but it seems harder. Since the yaml document expected to be small, collecting all events seems ok.

If we have something like derive or macro, then we will able to automatically create an implementation for deserialization and serialization. But it seems not matter, we can provide combinator to built that latter.

Next step, is probably convert yaml-value to json-value. I defined the json-value at the library too:

/**
* yaml-json is subset of a Yaml document that is compatible with JSON. This
* type should be enough to convert to any json library that Koka will have
* in the future.
*/
pub type yaml-json
  YamlNull
  YamlBool(b: bool)
  YamlDouble(double: float64)
  YamlString(string: string)
  YamlSequence(sequence: list<yaml-json>)
  YamlMapping(mapping: list<(string, yaml-json)>)

Probably need to keep anchor map we built, then resolve Alias to correct node.

So far, I ended liking this language! I think we need more basic OS operations. sync functions is ok I think, since not all application need async. ie, spawn process with config like environment, current cwd etc is missing