Be more explicit about expected return types for parsing algorithms

[mnquintana]

I just ran into an issue with step 13 and 14 of the parse a note value algorithm (https://w3c.github.io/mnx/specification/common/#note-value-syntax) when trying to implement the time signature parsing algorithm:

13. If fractional is true, set base value to (1 / base value).
14. Return base value and number of dots.

I took step 13 to mean "actually perform the computation of 1 / baseValue", meaning that the expected return type of baseValue in step 14 would be a floating point number.

Buuuut then as I was implementing the time signature parsing algorithm (which has a dependency on the note value parser), I came across this step:

6.3.1. Replace the denominator in each element of fractions with the denominator of nv.

And this step:

6.3.4. Append the fraction composed of numerator and the denominator 1 to fractions.

Which both suggest that the return type of baseValue in the note value parser must be some representation of a fraction and not a float (otherwise you'd have to do extra work to derive the denominator in 6.3.1).

Proposal

I think there's too much ambiguity in all the micro-syntax parsing algorithms as they stand right now, which will lead to error-prone implementations. Here's what I'm thinking would help:

1. Be more explicit about the expected return types of each parsing algorithm.
   1. e.g. What should fractions and sharedDenominator actually be in the time signature parsing algorithm return value?
   2. I'm not sure if the W3C has a standard type language for describing cross-implementation return types like this, but if they do, we should consider adopting it.

2. Give full example test cases – both valid inputs and expected outputs given those inputs, not just example inputs.

   1. An example from the spec with a completely made-up type syntax (but just to give you an idea):

      3/4 => {
        fractions: [Fraction(3, 4)]
        sharedDenominator: true
      }
      
      Three-quarters time

What do y'all think?

[adrianholovaty]

Thanks @mnquintana! That makes sense — it does indeed seem too ambiguous as written.

That part of the docs is still in the "old" spec, which I'm planning to migrate to our new docs system. Let me take care of that first, after which point we can tweak the wording to make it more explicit. I've just added this issue to our V1 milestone so we don't lose track of it. Thanks!

[notator]

@mnquintana: I agree with you that the micro-syntax algorithms in the Draft Spec are error-prone and problematic. (This applies to the whole of §5, not just to the Note value syntax.) My solution would be to replace them by more concise, formal definitions, in the form of Regular Expressions. These can be used in the schema to verify MNX files. The details of how to parse such strings should be left to individual applications, since that can be handled differently in different languages. Here's an extract from my current Draft Schema:

    <xs:simpleType name="noteValueType">
        <xs:annotation>
            <xs:documentation>
                An optional '1' character
                followed by
                {
                EITHER  (maxima, long, breve)
                    a "*" character followed by one of the strings "8", "4", "2"
                OR (whole to 1024th)
                    a "/" character followed by one of the strings "1", "2", "4", "8", "16", "32", "64", "128", "256", "512", "1024"
                }
                followed by zero or more "d" characters.
            </xs:documentation>
        </xs:annotation>
        <xs:restriction base="xs:token">
            <xs:pattern value="(1)?((\*(8|4|2))|(/(1|2|4|8|16|32|64|128|256|512|1024)))(d*)"/>
        </xs:restriction>
    </xs:simpleType>

[joeberkovitz]

Since I wrote the original (and overly loose) parsing algorithms let me say that the intended return value of the parsing algorithm was not a floating point number, but a rational number: a tuple of (M, N) with M and N both integers and having the conventional mathematical meaning of the exact fraction M/N.

Regular expressions are excellent for defining syntax but they are semantics-free, so they do not suffice to map a string onto a fraction. (For example, d* does nothing to explain the effect of each d on the rational number denoted by the syntax). Hence the need for an algorithm of some kind — preferably clearer than the one that is there now.

[notator]

All I'm saying is that its simpler and more rigorous to use Regexes to describe the structures of the strings in §5 than to describe them using parsing algorithms.

Note that

1. Regexes are going to be needed later, when writing the MNX schema, so they might as well be used in the Draft Spec.
2. the Draft Spec is due to be phased out fairly soon, so maybe we shouldn't be spending too much time polishing it. Especially, as in this case, where its intentions are very clear.

To answer @joeberkovitz anyway: Yes, agreed, the meanings of the strings' sub-strings (their semantics) still have to be described. For example, §5.1 Note value syntax describes a string having three sub-strings:

1. A '*' or '/' character that defines an operation (multiply or divide)
2. A string of numerical characters that can be parsed as a single unsigned integer
3. An optional string of 'd' characters

As it stands, §5.1 describes how to use these three strings to calculate base value (a fraction) and number of dots (an integer), but it does not say how to combine these values to return a single fraction (rational number). The description of that calculation is given in §4.10 Note values. Since the syntax can be defined in a single Regex, both the syntax and semantics could be described in §4.10, and §5.1 could be deleted. Something similar could also be done for the other sections in §5, so that §5 could be completely deleted.

[adrianholovaty]

Just adding some quick research for this... I searched through some W3C specs and found this algorithm, which is in essentially the same style as the MNX parsing algorithms.

I'm not aware of any formalized/standardized way of including type information in this written-algorithm approach, but this is definitely not my area of expertise! Suggestions welcome. The easiest thing would be to make some tweaks to the wording of our current algorithms to disambiguate.

[joeberkovitz]

I copied the general style I found in W3C specs overall, particularly Web Audio which I worked on also. Types are sometimes a bit squishy in specs, since we are not assuming any particular programming language or hardware architecture.

Easy problem: The original spec did include a section defining the meaning of rational numbers. I think I fell down in some places where I should have defined quantities like note value parsing results explicitly as rationals. Those can be cleared up with word tweaking and adding the words "rational number" where appropriate.

Harder problem: in other places like chromatic pitch syntax, we have quantities that can be either floating point or rational. This is kind of problematic for implementors and for the exact meaning of certain constructs. Suggestion: eliminate these mixed cases, and arrange for them to always be rational numbers by mandating the conversion of decimal numbers (NOT floating point, but numbers of the form d.dddd) to rational numbers. So 0.25 becomes 25/100 which reduces to 1/4, while 0.31013 becomes 31013/100000. We simply don't allow things like 0.453E-11 and so forth.