The DSL to implement the Reading Coroutines

Greetings,

this will be about the DSL I implemented to solve the issue about wirting those coroutines described in the first post .

As mentioned in the presentation roadmap, I will not use the implemented internal DSL, because this DSL requires a number of additional concepts and issues to be solved. I would like to avoid these. I will overall use a Java or C-like-language with a little quirk. I will throw in numbers in pointy parenthesis which denotes “Buffer this many bits here and execute the following statement, providing the buffered bits in a 0-padded byte-buffer called buffer”.

We will now examine three to four examples, in order to see regular statements, conditionals and loops. These constructs are sufficient as a complete base for a programming language, and I did not implement more than these intially. We discovered further constructs of this language via refactoring later on.

For example, assume we are supposed to read an 8-bit integer, assuming that the canonical byte form is defined to be 8 continuous integers in 2 complement form. Think about this intuitively for a second. I arrive at something like “Well.. buffer 8 bits, convert them somehow and write that into some output variable”. In the DSL implemented, we can write this as:

<8> output = convertToInt(buffer[0]);

Looking at this, this means: Buffer 8 bits (“<8>”) and execute the statement after it, with the buffered bits in the byte-array buffer. In other words, we arrive at: Buffer 8 bits, convert these 8 bits into an integer and store the result in the output variable. At first, I think it is nice how close this is to my intuitive idea how to do this. Second, note how this code is virtually oblivious about buffering issues. Do the bitsarrive in a block of 8? In two blocks of 4? In single bits? I don’t know. I don’t need to know.

You are unable to see this here, because I am using pseudo code, but the DSL in itself does not define basic statements, such as primitive types, integer operations and so on. This decision was made, because the problem in itself is a control flow problem. In other words: The primitive operations C integers provide are perfectly fine for processing the contents of a buffer, once it is buffered. The primary issue to solve is actually getting this buffer filled and then executing these C-statements in order to process the contents of this buffer.

Taking it one step further, we get conditionals. Assume that we have two possible types, which both serialize into 16 bits and are converted by two conversion function, call these convertA and convertB. Which type is transmitted is transmitted with a single byte preceding the 16 bits of the actual data. If this bit is 1, it is the type which requires convertA, otherwise (if it is 0), the type requires convertB. Again, think about this intuitively. I arrive at something along the lines: “Well, I need to read a single byte, check this to be 1 or 0, buffer 16 more bytes and call the correct conversion function”. In the DSL, this translates into:

<1> if (buffer[0] == 1) 
        <16> output = convertA(buffer[0], buffer[1])
else
        <16> output = convertB(buffer[0], buffer[1])

Let’s walk through this precisely. We have an if, which is annotated with a buffer size. This means that a single byte is buffered, the rest of the buffer is padded with 0 and “the if is executed”. That means, the condition of the if is evaluated and the right path is taken. The statements in the branches should be familiar: The translate to “Buffer 16 bit, call convertA (or convertB) and store the result in the output”. So overall, this translates into: “Depending if the first buffered bit is 0 or 1, buffer 16 more bits and convert them in the right fashion”.

Note that padding in this case means that all bits in the buffer are in a well defined state (buffered or 0). This padding is independent of padding in the serialized byte sequence, which is used for example to byte-align the various data fields in order to enhance the readability of the serialized byte sequence with a hex editor.

Finally, there is the loop. Assume we need to read a sequence of 8 bit chunks. The first bit of a chunk is 1 if there is another chunk and it is 0 if the current chunk is the last chunk in the sequence of chunks. Of each chunk, the remaining 7 bits are some data we store and collect. Think about this intuitively again. I arrive at something along the lines: “Well, read a bit, check if it is 1 or 0, and if it is 1, read data and continue, and otherwise stop.” In the DSL, this translates into:

 while(buffer[0] == 1)  storeData(buffer[0]);

Examining this, we get: Read a bit, and if this is 1, read 7 more bits, store these and continue, otherwise, if the read bit was 0, stop. Again, no need to care about buffering and everything. I just need to focus on the description of the byte sequence and I can translate these into clean code, which should do the right thing in a very clear way. Considering that serialization an deserialization is a pretty tricky topic, I think this is a very strong property, because now, it is very easy to verify if this code does what it wants. I am doing it all the time for you.

Finally, there is a last concept about buffering: not buffering. Confusion aside, consider the following definition: A sequence of bytes, terminated by a 0 byte. This should be an issue given your current knowledge, bcause the condition of a loop appears to consume the byte it examines. However, in this case, we just need to inspect the byte for the condition and hand it to the body of the loop in order to process it further. Are we lost? Well. No. In this situation, we decided to define that a buffer size of 0 requires that no buffering occurs, and the buffer of the last buffering is reused. So, we can implement the issue from above as:

<8>while(buffer[0] != 0) <0> storeData(buffer[0]);

This reads as: Buffer 8 bits, and if these are not 0, store these 8 buffered bits somehow. Obviously, if there is no buffering before a 0-buffering, the buffer will be undefined. This has not posed a problem for us until now. I am overall not entirely sure about this decision, even though it is working pretty well. At the time we decided this, it was a pretty pragmatic decision and the more I think about it, the more I like it, but somehow, I don’t get into the state of loving it. I mean, it obviously does make sense that no buffering reuses the previous buffer, but on the other hand, it still feels like a little hack. On the other hand, it works. I guess, a clean solution would be to decouple the buffering from individual statements and expressions and allow separate buffer statements. However, this will result in trickery in the loops again.

So, this is the overall DSL, on a high level. You just pick C, add some buffering directives here and there and you have this DSL, with very little surprises.

The problem to solve with reading coroutines.

Greetings,

in this post, I will explain the problem I encountered and which I solved with the reading coroutines. This DSL is a part of the code generator in a compiler. This compiler reads a certain type description and produces serialization and deserialization code for values described by the type description. This reading coroutine simplifies generating the deserialization code. Let’s go through this step by step.

At first, there is the type description. The current type description is a condensed form of a parsed XSD. Basically it contains a number of elements with a name and a type, and the type defines what kind of values are valid. You can think of this as a variable declaration with a certain type in Java. In Java, you see something along the lines “int numberOfCats;” and you know that numberOfCats holds a numeric value from Integer.INT_MIN to Integer.INT_MAX without any fractions. The only difference is that the type description is more flexible than this. For example, if you define a numeric type, you can (optionally) specify the number of fraction digits, the total number of digits, the minimum value and the maximum value. Overall, this type description is (because it is derived from XSDs) very general and contains fun things such as:

• lists with an optional maximum length
• unions of types
• numbers with optional limits and precision
• strings with optinal maximum and minimum length

In short, it would be easier to list things this type description cannot represent.

Given this description, we need to generate a serialization and deserialization function. We use the term serialization in order to describe the transformation of a value of a given type into a well defined bit sequence, while deserialization describes the transformation of a well defined, well formed bit sequence into a value again. In other words, the serialization of a boolean is implemented by either writing a 1 if the boolean is true or writing a 0 if the boolean is false, or the serialization of an integer is implemented by writing the two complement bit representation of this number. For a sequence, for example, we absuse the fact that we know a lot about the value, because we know the type of this value and thus, we can implement the serialization of a value of a sequence type by applying the serialization for each member value of the sequence one after each other.

The problem in this situation occurs once you consider the context where the generated code is supposed to be used. The generated code is supposed to be part of a communication stack on an embedded system (well, also on an enterprise server, such that you have a consistent communication stack on all parts of the system implemented). Given this, you cannot assume that you receive the entire bit sequence for a value in a single go, deserialize the value and go back to sleep after this. Such an embedded system usually recieves data in chunks, whereas the size of the chunks is determined by the receive buffer size. Furthermore, we cannot precompute how long the byte sequence for a type will be, so we cannot require the client to prebuffer enough data (consider the union of a list without a length resctriction and a boolean, for example). Thus, we overall needed a way to handle the deserialization of such a segmented byte sequence.

The first way we considered was to try to deserialize the current buffer and either produce a value or reject the buffer. If the buffer is rejected, the user has to buffer more data and retry the deserialization with more buffered data. If a value is produced, the user has to process it. This approach has the problem that overall, a lot of redundant deserialization attempts will happen and the client has to store a lot of buffered data he actually does not want to store.

Given this, I figured we could use a coroutine with a statemachine in order to solve these problems. The coroutine could read the current segment of the bit sequence and remember all necessary information and potentially produce a value. If no value is produced, well, no value is produced and the buffer is consumed and can be reused. If a value is produced, the value can be processed and the remainder of the buffer is fed into the coroutine again. This approach has the advantage that the user of the generated code can buffer a natural amount of bits (pretty much the receive buffer size of his system) and feed this into the coroutine. This means that there will be no redundant deserialization attempts, because every bit of the input bit sequence will be considered exactly once and no information will be stored redundantly, because the coroutine stores just the information it needs and nothing more. The buffer can be discarded after the coroutine consumed it’s contents.

However, writing these coroutines is a fairly tricky part. Overall, you need to keep a static variable to contain the current state, you need to remember how many bits to buffer in order to execute the next deserialization step, you need to remember a lot of technical overhead (updating the buffer size, the remaining unconsumed bits) and overall, you need to write a lot of C-Code in order to do this. Thus, I wrote a prototype for such a coroutine, got a headache from that and decided that I cannot have unexperienced C programmers write such nontrivial code. Thus, I decided to solve this problem with a DSL.

The presentation roadmap of the reading coroutines.

Greetings,

it has been requested that I talk about the generation of the reading coroutines in C a bit more. This first post will operate as a roadmap and also as a collection of links to the other posts about this matter, easening the navigation in addition to the categories.

I will overall present the code in the current state and try to elaborate why I implemented things in this way and not in another way. I might sometimes wonder and ramble about some design decisions and my missing knowledge about software design, and I might make up theories about design which might make sense or not. If you disagree, I will be happy, because then we can discuss.

The overall presentation will consist of the following steps:

At first, I will present the overall problem we will try to solve. This post should be read by everyone who wants to continue further, I think, because otherwise, terms will become pretty hard to understand.

Second, I will present my take on a DSL to solve this problem. I will present a pretty pragmatic view on this which I presented to the users of the DSL. I am going to keep this view abstract from the actual code really used to implement this, because those classes contain the solution of one or two more problems I encountered which overall add a bit of understanding trouble which I would like to avoid.

Third, I will present one half of the foundation of everything: the datastructures. The datastructures are overall a big composite pattern. I will explain why I implemented this as datastructures with vistors, opposed to, say, regular objects with methods. I will also present some implementation details for immutable classes we discovered as beneficial.

Fourth, I will present the other half of the foundation of this overall layer: The vistor part of the datastructure+visitor-implementation. I will present the general way we chose to implement the visitors, the way we removed a number of redundancy and the way we tested the visitors. The third and the fourth part would overall benefit a reader who sometimes ends up with a lot of operations on few datastructures, because I think that we overall reached a point where our datastructures are strong and usable and implementing visitors is quite easy and painless.

Fifth, I will explain how we solved the issue with variable names. It took around three iterations which I mostly forgot again, but my git log will probably help me on that. Overall, we reached a strong solution, which is a bit arcane, but once you get it, the light is bright (as a teaser: you basically annotate run time values with objects in order to identify value flow in order to add variables). I will also show you a nice way to add extensibility in this DSL.

Sixth, I will explain the abstract, high level plan for the generation, including the structure of the C method we want to generate. For those theoretically inclined, I will also discuss the overall abstract model of this language. This is the point where the theoretical description from part two will become relevant and this is the point where I had some headaches to solve for a day or two, but I managed to solve it
Overall, to have some terms handy to explain part seven and eight, we transform the code tree into a code graph and convert this graph into some while-switch-statement in order to implement the state machine, which is the model of the domain specific language.

Seventh, I will explain how the transformation from the code tree into the code graph. This was overall pretty tricky, but manageable. I will also elaborate why I think I need this. This should be a short, but interesting post.

Eigth, I will demonstrate how the code emitting is implemented. This is not exactly difficult, but kind of tricky, because there are all so little nitpicks that can go wrong.

Ninth, I will discuss how I managed to get this entire beast tested. Yes, it is fully unit tested, which is very, very nice.

Finally, I will wrap this up and consider if implementing this DSL was worth it, what could have gone better and so on.

Wow, so we got a lot of fun in front of us. Let’s begin. If someone would like to recieve the entire code from me, I will be happy to provide it.