Enabling modeling workflows for your DSLs: Introducing the Langium Serializer

This talk introduces the Langium serializer project, aimed at enhancing the serialization process for domain-specific languages (DSLs). The speakers provide insights into the principles of serialization, the generation of abstract syntax trees (ASTs), and the challenges faced in creating an efficient serializer. They elaborate on how grammars are designed for parsers but must also consider the requirements of serializers, particularly in maintaining syntactical correctness and human readability. The discussion includes details about the implementation of a generic serializer that can be customized for specific grammars, emphasizing the need for performance optimization and effective feedback mechanisms for developers. Overall, the session illustrates the complexities involved in DSL development and serialization using Langium, while also highlighting future development plans for the tool.

Yeah, welcome to our next tooling talk. My name is Steven and I'm here with my colleague Johannes and we are talking about the Langium serializer project. So, I will start and give an overview over serialization and Langium in general and then I will hand over to Johannes who gives some details about the current state of the project. Um, this is also the next type fox talk, so

I make this brief. Um, we are motivated a small team from northern Germany uh very much interested in open source and highly active there. So, if you have already heard of Langium or also a Theia or also Open VSX, then you have seen our work. Um, our lifetime achievement award winner is also here, so congratulations Miro. Um, but we are also doing custom-tailored solutions primarily in the

areas of IDEs and domain-specific languages. We are also sponsor of this beautiful conference, so please meet us as at booth three. So, let's start with an uh introductory example um and creating a DSL. Um, usually we start with some kind of specifications where we want to write a language and this can be a couple of lines of code or specification. Uh but as we have heard in

the talk earlier, in the case of PL/1, this could also be uh a few hundred pages of specification. So, we have a developer who is thinking very hard about this language, in our uh with Langium mostly in mind and then he starts writing a grammar, which can take uh some time. From this grammar then we can generate a parser or configure and this parser is then able

to read in some text which is valid according to the grammar and out of this text the parser generates an abstract syntax tree or AST in short, which is basically a semantic model of this text in memory. We can also reverse this direction then and take the AST as input and generate a text again that is then grammatically well-formed according to the grammar. And this direction is

what we in this context usually call a serializer. So this talk will be about Langium and serialization. Okay, let's start with a small example and this is by the way taken from the Langium playground, so you can go online and play around with it yourself. We have simple grammar here with an entry model which has two list persons and greetings and then we have two further rules,

a person rule with a keyword person and an identifier to declare persons and also a rule greeting with the keyword hello and then a reference previously declared persons, huh? If we have an instance of text here, then the parser can generate an AST and somewhere down in the AST we have nodes for John and Jane and also the references of the greetings. And in the best case

the serializer can then take this AST and serializes readable human readable text out again. Okay. So it gets more interesting if we actually modify the AST, yeah? So if we just want to generate the same text, we could then use the text from before, but if we make changes to the AST, then things get a little bit more interesting. So let me redraw this image here. The

first part stays the same, then we do a modification and we have a different AST or at least an AST with some differences and then we generate out the text. So we have two main categories of use cases in this case. The first one is we already have an AST and then we make a small change or a bigger change and then we want to regenerate the

text. So for example for refactorings or also code actions, some tooling in your pipeline that wants to generate text or nowadays also we make a change to a model in memory and want to get a textual representation out to an LLM engine agent for example. So one could argue we can all do these kinds of things just by replacing text and uh do the modification on text,

but if we use the serializer then we at least have syntactical correctness and also it's often times easier to change the model instead of changing the textual representation. The other big category of use cases uh cases in which we don't have the AST from the start and we create one programmatically. For example for non-textual editors which sometimes use for example XML or so, but you want to

have a more readable version of your data to store it which also could make it easier for version control systems for example or hybrid languages where we have a graphical representation and we want to create a textual one. And also transformations between languages. So this is actually the reason why we are not going back to previous structure so we can transform from one from an AST from

one language into another language, yeah. Uh in this case if you're using a language for example you would require a separate grammar if you want to generate the parser and the serializer automatically. Um then next let us extend this example here now by allowing multiple persons to be greeted. Uh in this case here we have uh our mandatory person and then an loop with arbitrary many other

people as you want to greet separated by a comma. And we have actually two variants here. So, grammars are not necessarily equally easy to understand for all participants. For a human, depending on your taste, this looks pretty much the same. Some people like the mandatory element up front. Some people like them at the back. for the parser, I would also argue that this is for most parsers

not such a big problem today because the comma is pretty strong separator of the elements. For the serializer in this case, might be more difficult to understand the second version because we must know that there's a mandatory element following and we cannot put all elements from the list in the arbitrary loop here. what developers tend to have in mind when they write the grammars is usually the

parser perspective. Yeah, if you want to write a parser, at least this is our experience, we have mostly the grammar, we have mostly the parser case in mind and not necessarily what might be difficult for serializer later to serialize text from. So, what are some other challenges? The first point here is serialization is not just print AST. If you want to print out the AST from this

example and you can actually do look at this also with your own grammar and the play ground for example, it would look somehow similar to this here. Um, for Langium at least. So, we have our person John and Jane in there and also the references to the greeting, but it's not what we expect as a human being to get if we want to get some human readable

form out of this model. Usually, we expect this one, but the AST is not telling the serializer that this is not also a good version or also this according to the grammar, we can't read persons before we declare them. So, the AST is not giving us much information about the structure. And actually, if you use uh Langium, we have another data structure, and we heard it in

the talk earlier, which is a useful data structure, the concrete syntax tree, who actually holds information about already passed elements, and uh for example, also comments and stuff like this. And also, if we do not have a passed AST, then it's still expected that the civilization comes out in a human-readable form, which is, in this case, most likely the first example, and not the the other two.

Apart from the formatting challenges, there are also all sorts of other grammar challenges, uh depending on the feature set of your grammars. We already have seen alternatives, and loops, and there are also optional tokens, and all combinations of these, which makes it uh ambiguities in the grammar, and the list goes on and on, depending on what your tooling is capable of. Speaking of ambiguities, there are also

different kinds of ambiguities. So, in the in this example now, we have two lists, person and people. And if I now have an input text "Hello Jane", it's not clear if you want to pass this to person or people. So, this is ambiguous for the parser, if multiple past paths exist to consume the input. But for the serializer, we also have ambiguities. So, if you already have

Jane in our set, and we have a grammar that allows, for example, here the keywords "Hello" and "Hi", then it's also not clear. And this this grammar is then ambiguous for the serializer, because we have multiple concrete syntaxes that we can use for the same model. In this case, we can resolve it quite easily, because there's only one person in the greeting anymore, so we can just

uh store also the information. If it's a good friend, then say "Hi." And if it's someone else, just say "Hello." So, we we uh before I uh hand over soon to Johannes, let's look at some more patterns. The first one you've already seen. So, here the orders are quite arbitrary, so the parser can read in all of these. So, we declare John and Jane, and then we

can greet them, or just declare John and greet uh John and then Jane, or say hello to them before we even know they exist, and the serializer can use uh any of these versions to actually actually print out the text again. If we restrict this a little bit in the in the middle example, then we only have one list persons, four persons and greetings, and then uh

the input is still arbitrary, but the order is set. So, the serializer cannot jump between the different versions, yeah? The disadvantage with this version is if you're only interested in the persons, then you might have to filter out the greetings, because they all exist in one list now. And the last example is uh set regarding the order. So, the these two versions are no longer possible, because

we have to declare the persons before we greet them, yeah? So, it's uh the most restricted language. So, I'm not saying any any of these are better than the others, but you should think about your grammar design, and this can of course make the job of the serializer also simpler. Langium had a spiritual uh predecessor, Xtext. How did they do it? They created a state machine for

every context in this case meaning every rule and then during serialization search for a path through all the context that are involved in the particular input and then there was a rather sophisticated stack to handle different kind of elements. So you don't have to understand all of this year. This is more to show that there is a rather sophisticated stack involved to resolve all of the different

features in the grammar. For example, there are stuff like semantic sequencer and syntactic sequencer and hidden tokens for the assigned and unsigned elements and vice versa and not even the whole complexity is shown here because in Xtext there are also things like transient value services and um other stuff. The the message of this slide is though Xtext came with a serializing solution but it and it was

a generic solution but it required quite some time and resources to get there. So the lessons up to now is the development is time intensive and the grammar design actually affects the serial- serialization as well and we also have to take care of existing text structure if we are passing from an existing um version. What's also in our vision at least it's not implemented right now is

that because developers tend to focus more on the parser perspective, it would be quite nice if we can give back feedback to the developer as early as possible. For example, while the developer is working on the we want to give already diagnostics so that issues don't accumulate later on. And something from other reports before also suggest that serialization should not become a performance bottleneck, especially if you

have um complicated expressions. This can also lead to some kind of state explosion that might become a performance issue later. Regarding Langium, so last slide before I hand over to um why wasn't Langium shipped with a serializer from the start? Basically boils down to business reality. So, please correct me, Mirko, and if I'm wrong. Um so, DSL projects uh do not always require a serializer, and if

they do in some cases, then it's also possible to provide a specialized one. uh also creating and parsing DSLs was is the main priority during development, and Langium was also planned as a lightweight solution or successor for Xtext from the start. Yeah. And as we have seen earlier, it's it's not trivial to develop a serializer. However, the use case does occur sometimes. And luckily, we are now

here and plan to extend this uh tooling of Langium, and Johannes will now give you some more details on how we are planning to do this. Thank you. >> Yeah. >> Thanks. >> Yeah, and with all these considerations, we started to design a serializer for Langium. So, a generic serializer, since we want to reduce the effort, uh if uh for client concrete uh, grammar you don't need

to write a whole serializer from scratch. And therefore, for the two use cases we saw, when we have complete new AST without CST information, we want to provide a default serialization for given grammar out of the box. And to ease developers' work as much as possible, because in a lot of cases it's obvious how to serialize an AST. Um, in cases, for example, of ambiguities, you want

to provide some heuristics, since even in more cases, uh, you can say, probably, in most cases, you want to serialize it in that way. But of course, uh, there's no approach fits all cases, all grammars, so therefore it's important to provide customizations where heuristics are not enough, or even where the default serialization, um, has some limitations. So for the second use case, when you have, uh, an

existing AST with formatting, with comments, and you change it programmatically in place, then you additionally want to ensure also that comments and formatting is kept, so no user will, uh, uh, will say, "Yes, I like it," if their comments are lost. So for example, we need to merge existing, um, CST information, uh, with new AST parts, and for example, that could be done to incrementally serialize only

those parts of an AST which changed, which would be also uh nice uh to improve the performance. And in this talk today, we focus on the first use case and show for a given grammar how the default serialization looks like and how we can customize it in in case it's uh not enough for our specific DSL. Let's come back to our Hello World example and I took

the easiest uh of the three variants um where you have uh where you need to define all persons uh up front before you can greet them. directly jump into how uh uh serialization um could work. And that looks like a lot of code, but it also focuses only on the persons part here we have uh the person keyword and a single assignment and what we do during

the serialization, we just uh trans- serialize uh the elements as defined in the grammar one after another. So, we um uh serialize the assignment and after the assignment, we serialize the keyword and when we are done with the body of the person rule, then we join the results. Uh we decided to serialize in backward serialization in backward uh direction, so it's completely inverse to the parsing uh

step which has some um uh improvements uh internally and uh makes the development internally uh easier, so regarding functionality, uh big benefit. Um Yes, when we want to serialize the person keyword, then it's quite obvious. We just take the person string uh and return this uh string. For the assignment, it's a bit more complex. We take the current value uh from the node property in our AST

node and serialize it according to the terminal rule called ID. And as you can see, it's a straightforward serialization of the contents of the grammar. Of course, it's longer than the grammar definition, but that's dedicated But in the end, it's more or less a one-to-one mapping, so it's easy to see what is going That was the most easiest case. We already saw we need to traverse the

whole AST when we want to serialize it, and our approach in order to speed up is not to plan all possible paths in advance how the grammar could be serialized could be traversed to serialize the given AST, but to decide as late as possible if I have two alternatives, I decide which of the branches to choose when I I'm directly in front of the alternatives. So, when

we want to serialize the model rule, we first need to serialize all the persons, and uh we don't plan in advance just before directly before how often we visit the person loop. Of course, here quite simple. We need to count how many persons are stored in our current model, and that's the number of iterations for these for loop in the end. but these might become more complex,

and also these decision needs to be done, and for that we analyze the grammar once before the first serialization to see, okay, we need to count the per the entries of the person attributes. That's our decision criteria criterium for the for loop. And then we cache it and apply it during serialization to make it very fast. So we have some startup time. And so the resulting code

again the main element is a while loop. we have a decision which returns a boolean to control how often do we want to visit the while loop. So the decision is directly done when we want to serialize the person's attribute. Yes, the complexity is hidden in this screenshot in the decision itself and we will see later a glimpse on how that could work and what are might

also be the limitations of it. Let's go a step back and look how does the general architecture look like to make such a serialization What we see is a generator based serializer which directly takes the AST as input and gives text as output and nothing more. So there is no grammar as input at all. All the structure of the grammar is represented by the generated code we

saw. But that means these code needs to be generated from a grammar. So we need another component a generator which generates a generator based serializer. And that requires lots of input information among others the grammar. We need to analyze the grammar with a grammar analyzer regarding possible paths regarding possible assignments which we might use to decide. These decisions are done in the decision provider and we already

saw these uh names for the methods with they are provided by the key calculator. So, there are uh a lot of stuff going uh on, but this logical is done once and uh not for each uh serialization. A completely different approach would be to serialize in an interpreter-based Uh just to show an alternative design decision. There we have only one component, not two. The interpreter-based serializer, it

takes directly the AST as input, uses at runtime during the serialization all the information from the grammar and the analyzer. Again, the information is cached um so it's not calculated so it can be calculated on demand and returns the text. Always in the box can be implemented once and provided by Langium, so that's generic and everything outside the grammar, the text, the ASTs, and also the uh

generated uh serializer, they are specific for your DSL. And therefore, looking at the customization we also want to achieve for an interpreter-based serializer since it's generic uh provided by Langium, we need some hooks for customization, but in this talk we focus on the generator-based uh version since it's easier to uh show on slides and uh we are now investigating how we can customize it. Um usually you

want to as uh customize not everything but a single element, uh a decision is slightly wrong or incomplete uh or a terminal needs to uh deal with formatting or um encoding issues, and uh so there are usually cases where you need want or need to serial- uh customize the default And the main idea is to put all the logic we saw before and take it not as

function but as method inside a class. Um so the class my generator in the middle that contains all the default serialization methods for the single elements of the grammar. It inherits from a base class which provides some utilities that's not that interesting here. But if you want to customize the default generation, you create a new class, extends the generated class and then you can override as many

or as less methods you want you want. You can also even use the super implementation. in that case you don't need to manually adapt the generated code but you can simply customize what you want. That's also the motivation why we are generating so many methods. Could condense them? Yes, but that would make not that fine grained as we can do it with this approach. Um it's also

possible to customize for example the key calculation to provide some better keys if you like. We enable that by lightweight dependency injection. That's the same mechanism we use in Xtext and which is very successful there. and now we switch to a short live demo to show you when you are developing a grammar DSL and you want to deal with a serialization for your end users, you reuse

default serialization and you also want to customize it so that you get a feeling um how that would look like in practice. Okay, let's again start Hello World example as starting point. These examples are very small and they might look simple, they are not, but they need to be small to be shown on a single screen. So, the generated code is just TypeScript code. We all already

saw, so there are in the end one method for each element in the graph. We had some that's also the reason why we need 200 lines about for Yeah, well, I mean 20 lines of code because for each rule, for each assignment, if you have loops, then then even more methods and which enables you to do these fine-grained uh uh these fine-grained customization. So, for example, we

said, "Okay, the main logic for the Sorry, when we want to decide how often we want to visit these person's Um that's hidden in the code and let's have a small look on that. Here again, we are at the loop and the decision for that it's also provided in its own method to make it customizable. And what we do in the end, we also need for some

reasons to count how often we already visited the uh the body of the for loop and what we do is we check um how many elements do we have and uh are there some elements remaining to serialize? So, in that case, it's Yeah, quite quite uh simple. do our first change in the grammar. So, let's say we don't uh want to we want to enforce that we

have at least one person. Uh we need to regenerate our code. And uh the difference compared to before, we now call the serialization of a single person twice, once before the once uh inside the loop. So, we always serialize at least one value. So, uh no other changes are required uh that can be provided out of the box. Now, let's say we want to to uh Now,

let's say we want to have another person. So, now we need at least uh let's switch back here to the star. That would be an alternative to say uh we want to have at least one person. And we see in our decision the main logic is that now uh we also need to compare how many mandatory assignments to this feature are done outside. And the interesting part

here uh one uh in line 117 uh which represents the mandatory assignment outside. So, uh yeah, it's it's some code. It's a bit longer than it needs to be, but that makes debugging uh easier. This also works out of the box. And um to show a complete different example, let's make the first one uh with a question mark. And uh that would be an example for ambiguity

in the serialization because when you have a uh one person in total in your node then you could either store it here in the first optional one or in the loop, and then it's not obvious to do. And uh when you try to generate code at the moment, you'll get uh some some issues that uh it does not work. You So, here you see it's not possible

to generate an automatic uh one. It's it would be also possible to, for example, to collect such issues in a report uh or whatever. Okay, then let's make it different because the usual pattern with uh this uh that you want uh that you want to uh sorry. Provide an arbitrary number of persons with some separators in between, and the usual pattern for that is uh all are

optional at uh if you like, as the first one inside these optional group is an mandatory, and the four each next person you have to add a comma in between before. Now, you would say, "Okay, again, you have two optional things. The first one is uh optional since the whole group is optional. And the four loop uh yeah, it's the same as before, so it's not decidable,

or there's an ambiguity again. But, when you are looking at the four loop, when you reach the four loop then the first one becomes mandatory, so there there are cases not to reach the loop at all, yes, but if you reach the loop again, so then the person is mandatory. That shows we check the current path, but only the current path. We don't check any possible paths

to calculate it here. Let's do it. Okay, that's fine. let's look at this in the decision. again, you have the minus one here for the mandatory one, which is mandatory in case you reach the loop, but if you don't reach the loop, we don't care. For the next one, we want to show an example where we need some customization. Let's say we have also a string token,

provides um Well, let's make it easier. Um you can have descriptions for your uh surrounded by double colons, so you can add a hint. we generate the code. Of course, when we try our usual example, then we get some failures because we said uh the hint needs to be mandatory, so we need to make it uh happen. and uh when we are testing this, of we say

we expect these additional informations in the output again. Let's test it. Oh, and we are surprised it fails. Why does it fail? Okay, a token error. I did wrong. I expected an error, but another All right. Um we still have here the changes from before. do it in this way. Again, an error. something went wrong with the double colons. relatively new to Langium, so maybe we don't

know what is going on. We have no idea. Okay, let's What do we do in that case? We do debugging. Okay, let's debug what is wrong. We We assume that something went wrong with the new string terminal rule, so let's check what is going on with uh the string rule. Now we are happy that uh we have these fine-grained um We could also set the breakpoint in

the usual code. Um That's it. Makes it easier here for the moment. We see the value. Okay, double colons are missing. Let's also look a bit into the serializer We see the value here extracted from the hint property of our current node, which is chain. Yeah, the double colons are missing and at some point uh you will notice that uh Langium has some built-in functionality to deal

with uh string tokens and it removes the double colons for you to get only the value uh inside the path. But during the serialization, we need to make these uh inverse. So, we have to add uh the double colons here. So, we need a customization for that. We just add the double colons around the value we found from the in the AST. Let's try it again. And

everything is green again. Yes, that's very simple, but it shows uh the the main procedure what is going on and you might uh say, "Yeah." it it's very complex, but uh I also tried uh an example during the development from a customer project with a grammar of 700 lines and except from parser ambiguities, uh it was possible to use this approach in general for the Okay, next

steps are at the moment we started in autumn uh last year with experiments and prototyping supporting the first use case. We have a new AST. We want to serialize it uh with a default serialization and we plan to uh pro um imple um to publish a version 0.1 with this feature. This is the first presentation today and the next upcoming step would to be to support the

second use case to also consider formatting and comments when we change ASTs in place. At the moment we are planning to provide the serializer in the usual language language repository as a language package so written in TypeScript available on GitHub and open source licensed the same as we are doing for language when we when you say okay you need some features early talk to us we are

open for open source development. our objective with a generic serialization is to provide default serialization out of the box to in verse the parsing step and order to enable much more use cases for language which engineering at the moment we are starting with text providing an AST and going forward from the AST. But there are many use cases which uh which have a data structure in memory

as starting point and we want to text back in particular for working with the data with LLMs. we aim to have a fast approach. It cannot support everything but therefore we want to provide an easy customization for that. It's an ongoing effort and we are looking forward to your feedback for your ideas for example how to provide information about serializer ambiguities in a file or even as

diagnostics in the diagram editor. We are also very curious whether you prefer generator based approach or approach or you say both okay uh we are looking forward to that and now uh ask questions what are your ideas on serialization? Thank you very much. >> [applause] >> No, not you. >> [laughter] >> Yeah, please. >> You talked about defaults in Langium, like removing quotes, and for the user

it might be hard to figure that out because it's hidden logic. it would be nice if the reverse rule that needs to be could be figured out automatically, let's say by AI. >> I mean, at the moment I would say for the starting point you need to know what is going on as a otherwise the AI I'm not sure whether it will get it. At the moment

Langium value converter for these cases for the single direction for for the parsing step. So, at the moment there's no API to just implement the backward transformation during the serialization. We could think about to add that to make the two inverse transformations at the same place. >> But I guess in general it will be relatively hard to cover all or implement all reverse rules that are needed

based on the existing Langium code bases because Langium is a framework it's not only rule based like in the grammar. It's not declarative in all positions or places. But you can also provide conditional code that might change the behavior depending on the outer world or whatever. So, reverse rules are in general hard to implement and you need to think about that if I understood that right. >>

The value converter is designed in Langium. It's imperative just TypeScript and there are some default imperative code for the string case. So, usually in the DSL projects you have special tokens, special strings and keywords. You have to write the transformation even for the parsing usually on your own and it might contain loops and if cases. Now, the additional challenge is so that's not a new thing. The

additional challenge is you have to provide an inverse transformation for the for the serialization. Yes. And yeah, if you are really bad then this transformation is not bidirectional and then you have to think what to do. So, probably then you will or you will get some more ambiguity regarding the serialization. You have to discuss with your customer. Maybe it's okay if you enable for example strings with

double or single colons. That's the serialized code always uses double >> Thank you. >> More questions? If you have some >> Thanks for the presentation first and foremost. It's a very interesting technological challenge in serialization. Um one of the design goals was that it will be uh fast. That's what you mentioned. Um can you say something about the algorithmic complexity for the serialization logic like um when

it comes to ambiguities? So, are we quadratic or cubic or what do you expect? >> Um so, the serialization has uh uh to be fast. So, you follow the directly the way you would trans uh uh um traverse the grammar during the uh parsing, but uh um but with less um Now, look uh look at it. Um the main complexity is designed not to be in the

serializing step, but in the analysis uh analysis uh upfront. And uh there it's at least quadratic. Uh for example, um for alternatives, you have to compare um alternative branch with each other to find some unique decision criteria which branch is a correct one for a given AST node. So, uh there is a performance uh might be very bad and uh with naive implementations and uh lots of

um alternative paths at this uh or options at the single point, we also had uh first experience uh times of several seconds. I think uh that can be uh improved when going to production ready, but it also might be a hint to go to the generator-based approach um all these upfront uh logic is um uh is serialized uh serialized uh in generated code. So, you have nearly

no startup time during the serialization. Uh have before no startup time before the first realization. So, this is actually the one of the main reasons that we opted for the generator based approach for now, but that's not set in stone yet. Okay, and if you are more interested, visit us at us at our booth. We are open for your ideas. You also should be fun when you

are designing a DSL and its realization. >> [music]