Ask HN: Please Review My Metalanguage

https://github.com/kstenerud/kbnf/blob/master/kbnf_v1.md

by kstenerud • 3 years ago

72 40 3 years ago

kstenerud11• 3 years ago

Hi all!

While developing a text and binary data format (https://concise-encoding.org/), I ran into trouble building a formal description for them. Many formats use EBNF or ABNF, or just embed their own BNF-style metalanguage in the spec itself (I started taking cues from the XML spec).

But describing a binary format is deceptively complex, and eventually I had to split out the metalanguage. KBNF is the result.

I want it to be useful for other people, so I've decided to release it standalone here: https://github.com/kstenerud/kbnf/blob/master/kbnf_v1.md

I'd really appreciate some proofreading, as right now the only way I'm able to effectively find issues is to let it sit for a couple of weeks so that I can look at it from a fresh viewpoint, and even then I'm not confident that I'm discovering as much as multiple eyes could.

Cheers!

unwind• 3 years ago

This looks really interesting, thanks for doing all that work and sharing.

Two minor points of feedback:

- The name is "strange", since "Backus-Naur" is already labelling the form as being theirs, adding a possessive to the front kind of clashes, for me.

- There's a tiny typo in the Non-Greedy example, "terminaor" is missing a "t". :)

Good luck with the project(s), of course!

robertlagrant• 3 years ago

Yes, I came to say the same. Is Backus okay with you naming a metasyntax after him?

kstenerud11• 3 years ago

Yes, TBH I'm a little stuck coming up with a name. I want it to be evident that this follows in the footsteps of the Backus-Naur form (for familiarity's sake), but I don't want to do something crass like call it "Ultimate Backus-Naur form" or something. We already have "Advanced Backus-Naur Form" and "Extended Backus-Naur form" and will eventually run out of superlatives...

aardvark179• 3 years ago

When you give an example of things being non-greedy by default why does

   azzzbzzzczzz

represent a document with 3 records rather than 3 documents? We intuitively understand why, but without defining document as special, making it consume records eagerly, or defining anchors for the start and end of the data, I think the example may be incorrect.

kstenerud11• 3 years ago

Whoops you're quite correct! It needs an end anchor or something.

mkl• 3 years ago

What can you do with it? Do you have a parser generator or grammar validator?

Is the & really necessary? It seems to me like they could be removed without losing anything (but it is late at night here so I may be missing something).

Related to the previous question, if & is necessary are there typos in "byte(type) byte(bind(length, ~)) & byte(~){length};" and "'(' & TOKEN_SEP item TOKEN_SEP & ')';", which are missing some?

kstenerud11• 3 years ago

There's no parser generator; its primary purpose is to document how a format looks and works (similar to what ABNF and EBNF do). I am trying to make it consistent enough that tools could be made for it, however.

The & is something I added later, and I thought I'd updated all of the examples but I must have missed some. Using whitespace as an operator was just causing too much trouble and making the more complex grammars harder for a human to follow, which is why I opted to make every operation require an actual symbol, and leave whitespace without semantic value.

anentropic• 3 years ago

Have you seen this? https://kaitai.io/

(Disclaimer: I've never needed or used it, but stumbled upon it a while back and just filed it away for future reference)

teddyh• 3 years ago

Isn’t specifying binary formats exactly what ASN.1 is made for?

fjfaase2• 3 years ago

A long time ago, I started working on something similar. There are some binary editors that support writing grammars. I worked on reverse engineering several binary file formats. When working on Quark Express file format, I discovered you do need two layers of grammars, as the file contains a header followed by allocated blocks, where the bocks are linked (by indices) and chains of linked blocks contain streams of data. I remember that there are also file formats, that simply have pointers to certain sections of the data contained in the file. I once implemented a memory mapped file data storage where all pointers to allocated blocks where represented by an offset from the start of the file. (I later, came up with a better idea and that is to make them relative to the location of the pointer, such that you do need to know the offset at which the memory mapped file is placed in memory. So basically, there are lots of 'pointers' in the file and you can only read the data in the file following those pointers.)

Links: https://www.iwriteiam.nl/Ha_BFF.html https://www.iwriteiam.nl/Ha_HTCABFF.html https://www.iwriteiam.nl/D0205.html#13MMF

noduerme• 3 years ago

Lord. I still have whole books I laid out in QuarkXPress for commercial printing that I can't open. Reverse engineering the file format was not something that had occurred to me.

fjfaase2• 3 years ago

I have made the code available on GitHub, The code was developed on Windows and makes use of some Windows specific functions. But I think that dependency can be removed.

https://github.com/FransFaase/ReadingQuarkXpress

aeneasmackenzie• 3 years ago

Unity asset files killed my attempt at a comprehensive binary encoding format spec language. There’s a header containing a list of block pointers. The blocks are compressed and the (several) files are sequential. Typically the first file is a resource containing a block of metadata describing object type formats, then object references keyed to the specified formats. The objects can have transparent references (PPtrs) to other objects in the resource file, or other files in the asset, or other files or objects in in other asset files. One asset file usually contains the master list of what object is in what file.

None of this is a true blocker, but your format has to contain sigma types and at that point you’re just writing a parser normally.

JaumeGreen2• 3 years ago

EDIT: I misunderstood how it works, read the reply to see why I was in the wrong.

I haven't read it all (and probably won't, these kinds of works are not my forte), but there's something that doesn't look that nice.

The swapped function seems strange, mostly because you treat 1 as a special case which reverses the content.

I would either have a reverse function or use negative numbers to reverse those chunks, like this:

    uint(16,0xc01f) matches big endian 0xc01f (bit sequence 1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1).
    swapped(8, uint(16,0xc01f)) (bit sequence 0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0).
    swapped(-16, uint(16,0xc01f)) (bit sequence 1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1).
    swapped(-8, uint(16,0xc01f)) (bit sequence 1,1,1,1,1,0,0,0, 0,0,0,0,0,0,1,1).
    swapped(-4, uint(16,0xc01f)) (bit sequence 0,0,0,0, 1,1,0,0, 1,1,1,1, 1,0,0,0).

There might be better solutions, I just dislike exceptions in rules, if it can be helped.

kstenerud11• 3 years ago

Swap reverses all bits in chunks of the granularity size. So given bits = ABCDEFGHIJKLMNOP, you get:

    swapped(8, bits) -> IJKLMNOPABCDEFGH
    swapped(4, bits) -> MNOPIJKLEFGHABCD
    swapped(2, bits) -> OPMNKLIJGHEFCDAB
    swapped(1, bits) -> PONMLKJIHGFEDCBA

So the full bit reversal when granularity = 1 is emergent phenomena rather than an exception.

JaumeGreen2• 3 years ago

Ok, that is more understandable. If there were some more examples in the page then this emergent behaviour could be seen faster.

Nothing to add then

porcoda• 3 years ago

You might be interested in Guy Steele’s talk “It’s time for a new old language”. He talks about similar notations and the problem of inventing new ones (although most of his talk is about things other than BNF-like notations : he just talks about them for a bit in the beginning). It’s an interesting talk and is useful in thinking about proposing new notations.

YouTube: https://youtu.be/7HKbjYqqPPQ

If you search for the talk title you can find the PDF of the slides.

UncleEntity3• 3 years ago

There’s also The Next 700 Data Description Languages https://www.cs.princeton.edu/~dpw/papers/700popl06.pdf

UncleEntity3• 3 years ago

Not really a fan of using ‘&’ as the concatenation operator instead of the traditional EBNF way. The examples show both ways with the TOKEN_SEP (? space I guess) not seeming to need it.

Also the string rules look like they don’t allow an empty string, maybe intentionally as that’s probably a bug in someone’s grammar.

About as far as I got on a quick glance, got distracted by the mathematical operators and other things like concatenation sharing the same tokens and started thinking how hard it would be to parse it.

yardstick• 3 years ago

Small suggestion: put an example at the start, maybe a reference to the IP spec, or maybe something smaller if you’ve got one.

It’s always nice when I can see upfront at a glance what the language looks like, rather than first going through all the grammar spec.

kstenerud11• 3 years ago

Will do, thanks!

HelloNurse4• 3 years ago

You are conflating, in a typical model/metamodel confusion, numbers in the data structures you are describing, with their machine representations that you are modeling decently, and numbers in your language, which should probably be just integers without complications.

The former are are patterns in the data, e.g.

rpm = float(32, -1000~1000);

which specifies a subset of the 2^32 floating point values, and the latter are actual numbers, e.g.

identifier = 'a'~'z'{5~8};

which shouldn't worry about rounding, signed zero, NaN values etc.

What arithmetic do you expect to need, in practice, at each of the two levels?

real: any value from the set of reals, including qnan and snan unless otherwise specified

You mean floating point, not actual real numbers. Then, even within the IEEE-754 options, you need to specify what variant of floating point.

Note that floating point constants by themselves have ambiguous type: 1.3e5 can be float(32...), float(64...), etc.

Note: Calculations can produce a quiet NaN value under certain conditions in accordiance with the IEEE 754 specification. If different processing is required (such as traps or exceptions), this must be documented in your specification.

This means specifying what to do with NaN results and similar errors: a heavy burden for the user.

unsigned: limited to positive integers and 0 signed: limited to positive and negative integers, and 0 (but excluding -0)

These are floating point values pretending to be integers. You should have actual unlimited precision integers with constraints like explicit maximum and minimum values.

Moreover, "-0" is a IEEE-754 technical detail that has no place in a formal, abstract language.

kstenerud11• 3 years ago

Hmm good point. My plan was to allow concepts such as inf, NaN and negative 0 to be available in the abstract, and then convertible to a concrete implementation such as ieee754. But in actual fact it's mostly muddying the waters, and those kinds of values would be better represented as functions that produce ieee754 values rather than abstract concepts that don't really work abstractly anyway (I was thinking that as an abstract concept it could be passed to a general function for any given floating type implementation such as binary float, decimal float, bfloat, etc).

> unsigned: limited to positive integers and 0 > signed: limited to positive and negative integers, and 0 (but excluding -0)
These are floating point values pretending to be integers. You should have actual unlimited precision integers with constraints like explicit maximum and minimum values.

The idea here is to have all numbers be treated as reals (in the mathematical sense) for abstract calculation purposes, and then use the pseudo-types "signed" and "unsigned" to represent common invariants on those reals (such as "can only be 0 or an integer" or "can only be 0 or a positive integer"). For example, ('a'~'z'{chars_per_record}){char_count / chars_per_record} (where char_count and chars_per_record are bound from another part of the document) is a common enough method used to envelope data in binary formats. But if char_count = 100 and chars_per_second = 3, you can't accept a fractional count (i.e. it would be an indication that the data in this document is corrupt or malformed).

Only the functions `uint`, `sint`, and `float` would convert a number into an actual expression (provided their invariants are respected).

HelloNurse4• 3 years ago

The idea here is to have all numbers be treated as reals (in the mathematical sense)

No. You can't represent, compare etc. most real numbers, so they aren't any good for computational purposes.

Practically usable number types include integers and things that have sufficiently number-like behaviour (e.g. fields) and can be represented with a finite number of integers: rational numbers, rational numbers with field extensions, vector spaces, finite sets, intervals, etc.

In a language for grammars you can probably stop at integers; general purpose programming languages might want more (for instance, Python has rational numbers) but advanced number types can usually be implemented with libraries.

anonymoushn• 3 years ago

If you would like to include unicode support rather than supporting bytes and punting unicode to a library or the end user, it may be good to have opinions about unicode normalization.

napsterbr• 3 years ago

FYI there's a copy-pasta/typo at the very last section. You (probably) meant to type `digit_hex` but typed `digit_bin`.

Expert-0072• 3 years ago

"copy-pasta"? Is that a spaghetti replicator? :) I can reverse that, with XTRAN rules I have to automate removal of GOTOs by structuring code. (It uses XTRAN's code match/replace facility.)

aliqot• 3 years ago

needs syntax above the fold

hyperhello• 3 years ago

Does the format take left recursion into account or leave it undefined?

Expert-0072• 3 years ago

In creating and enhancing XTRAN, my Expert System that knows over 40 computer languages, I got tired of hard-coding parsers, so I created a parsing engine that takes EBNF (specified in more friendly syntax I created), parses the EBNF to an internal format, and then when asked to parse a language, executes its EBNF in order to parse. I would be interested to know if anyone else is executing EBNF to parse.

Since code must come back out after XTRAN rules have created / changed / translated it, I also created a rendering engine that is responsible for rendering XTRAN's internal format of language content out as text source code, complete with extensive styling controls. The rendering engine is also driven by EBNF, which it executes in order to render code content to text source code.

If you're interested in learning more, see WWW.XTRAN-LLC.com. I'll be glad to answer any questions.

Ask HN: Please Review My Metalanguage

Related Stories