finl is not LaTeX

Revised definition of commands/environments

November 6, 2021 by Don Hosek

From the readme for finl_parse, some thoughts on how commands and environments are defined.

Input text

Input text is assumed to be in NFD normalized format.

Commands

You indicate a command with \ followed by either a named command or a command symbol.

Named commands consist of one or more letters. Letters are defined to include all characters in the categories letter, non-spacing mark and combining mark. Inside user-defined macros only, _ can be considered as part of a named comand

A command symbol is a single non-letter. A single non-letter is defined to include symbols which may be represented by multiple code points but a single output grapheme, For example, the symbol 🇨🇦 is actually represented by the input sequence U+1F1E8, U+1F1E6. Since this is generally invisible to the user, it’s most ergonomic to handle these sequences as if they were a single code point.

A command may have zero or more parameters.

Parameters

Each parameter has a format and a type

Parameter formats

Parameters are one of the following formats:

• * an optional star indicating some alternate behavior for a command. (Corresponding to xparse s)
• optional arguments delimited with […] (corresponding to xparse o/O)
• required arguments consisting either of a single token or multiple tokens delimited with {…} (corresponding to xparse m)
• required arguments with mandatory braces
• arbitrary required argument where either the delimiters are {…} or will be delimited by the first non-space character after the command and the next occurrence of that character. This argument may not be broken across lines. (corresponding to xparse v)

Possible future enhancements:

• optional argument indicating style override delimited with <…>
• something akin to the xparse r/R type but allowing arbitrary delimiters (for dealing with TeX-style argument handling)
• something akin to the xparse d/D type but allowing arbitrary delimiters to an optional argument (I probably won’t do this one)
• something akin to the xparse e/E embellishment mechanism.

Parameter types

Parameters can have one of the following types:

• parsed tokens. The passed argument will be parsed and passed to the command implementer as a list of tokens

• verbatim text. The passed argument will be treated as verbatim and passed to the command implementer without further processing. Depending on the delimiter style, it may require braces or brackets to be balanced within the argument, e.g., if an optional argument is treated as verbatim text, the user cannot do something like

  \foo[ [ ] 

  I’m undecided as to whether to allow any sort of workaround for this, like

  \foo[{[}] 

  or just not allow that use case at all.

• boolean values. For * arguments, this will simply pass true if present false if absent. Possibly a required or optional argument can have a boolean expression in them, although this might be something reserved for commands called within macro definitions.

• key-value lists. This will be a list of keys (which must conform to UAX31) followed by a value with = separating the keys and values. Leading and trailing spaces will be ignored and an outer set of braces will be stripped off so that, e.g.,

  foo = { e } , bar = kappa , baz=3 

  will set foo to e, bar to kappa and baz to 3. All values are treated as token lists and cannot contain undefined commands. If a command is found when searching for an identifier, it must be a user-defined macro and expand to valid key-value list data.

  Trailing commas in the key-value list will be ignored.

• Macro definition token lists. This applies only to macro definitions. All spaces are ignored, ~ puts a space into the token list, and _ can appear in a named command. I don’t know if I’ll allow extensions and document types to create new commands with this as a parameter type.
• Math mode.

Possible future types:

• JSON. Perhaps with a proviso that allows dropping the enclosing braces on a JSON object, so, e.g.,

  \foo{ this: true, that: 3.1 } 

  rather than

  \foo{ { this: true, that: 3.1 } } 

  and perhaps also dropping brackets from an array so:

  \foo{ 1, 2, 3, 4, 5 } 

  rather than

  \foo{ [1, 2, 3, 4, 5] } 

  This will possibly also require a definition of the actual data types used in the JSON, or maybe not, I’m still not decided.

Environments

Environments work similarly to commands but have an additional declaration of the contents of the environment. A first parameter of * indicates that we’re also providing for a *-form of the environment.

I think that environment names must conform to UAX31 (so finl would be stricter than LaTeX on this front¹).

Environment bodies can have the following types:

• Parse token list
• Math
• Verbatim²
• YAML³

1. This is perhaps not a big deal though—a quick grep on the LaTeX directory indicates that only a handful of existing packages use environment names that don’t conform to UAX31 with a couple having internal dashes and one package defining + versions of some math environments.
2. The finl version of the verbatim environment will be able to “see” the indentation of the \end{verbatim} command and strip that indentation from all lines automatically.
3. Worth remembering that YAML is a superset of JSON. The JSON shortcuts mentioned for arguments will not be supported in an environment body, but environment implementer are free to manage this themselves by taking input as verbatim and parsing it however they like.

At long last code

October 5, 2021 by Don Hosek

The first piece of code (something relatively trivial) for finl is now on crates.io: finl-charsub is the character substitution module for finl. It may have use outside of finl when fixed character sequence replacements are needed in a text stream.

Future enhancements: I’m pretty sure that there’s room to optimize the hash map implementation that’s currently in use for building the trie. Right now, I’m using FnvHashMap, but I have to believe that there’s a way, perhaps by eschewing Swiss Tables, to get still better performance for this use case. Since I’ll likely be implementing at least one more trie in the  code (if I remember correctly, the TeX hyphenation algorithm, which I plan to shamelessly steal also uses a trie internally), there will be a chance to return to this for future optimization of the code.

Building a trie in Rust—optimizations

September 30, 2021 by Don Hosek

A trie is a variation on a tree whose purpose is to show the result of a sequence of values, something that I’ll be using a lot in finl. For example, TeX has a number of input conventions implemented via ligatures (plus an active character) that I’ll be making optionally available through a character substitution mechanism. The trie for this looks like:

The implementation of this is to have each node in the trie consisting of a map of characters to nodes and an optional substitution text. 

The obvious choice of what to reach for as a map is a hash map of some sort, but Rust makes things interesting in that the hashing function is easily configurable¹ so I decided to do some experimenting since the default hasher is heavier weight than I need and with the char sub algorithm, nearly every single character in the file will end up getting hashed at least once.² I don’t need to worry about hash DOS attacks or cryptographic strength in this situation so the default hasher SipHasher13 is overkill. The recommended alternative for short keys is FNVHasher from the fnv crate, so I set up a benchmark that runs a collection of Dickens stories in TeX format against the TeX character substitution table to run benchmarks. As expected, I saw an improvement of 24%. But I wondered if I could do better. In particular, since my keys are a simple type and guaranteed to be less than 24 bits. Perhaps even an identity hasher would make sense in this case.

And then writing that last sentence, I remembered, hash collisions. I once interviewed for Amazon³ and having heard they liked to ask a lot of data structure books, I read a data structures book the week before the interview, so I have a good idea of what happens below the hood with a hash map: Essentially, you’re creating an array of keys and pointers to your stored data and you take the hash value, mod it the size of the array, then look at the resulting point element in the array. If it’s empty, there’s no match. If it’s not, you then check the keys for equality. Here’s where things get tricky: If they’re equal, you’re done, but if they’re not, you need to then iterate through the array until you either get equality, reach an empty element in the array or finish the array.

And Rust’s implementation of this is… not great in this respect. For an application like my trie, I want to fail fast on lookup, but Rust will happily fill its entire capacity before resizing on insert. This is one place where Java wins: It allows users of HashMap to specify a load factor (0.55 by default) so that rather than resizing when the capacity is filled, it resizes once you have capacity × load factor elements inserted. Since I’m expecting most lookups in the trie to fail, it’s better to fail faster. I boosted the initial capacity of the map to 64 and the benchmark improved by 53% (one small optimization I made was to only specify an initial capacity for the root map of children. For this application, at least, once we’re starting down a trie, the possible matches are a smaller set and there’s less danger of there being a significant cost to false positives).

But one more thing. My keys are short and of constant size. Maybe I could get better performance with a simpler hashing function. I tried creating a simple null hasher that just used the value passed in:

impl Hasher for NullHasher {
    fn finish(&self) -> u64 {
        self.0
}

    fn write(&mut self, bytes: &[u8]) {
        self.0 = bytes.iter()
            .take(7)
            .rfold(0u64, |acc, x| acc * 256 + *x as u64);
    }

    fn write_u32(&mut self, i: u32) {
        self.0 = i as u64;
    }
}

and was surprised to discover that, in fact, things slowed down, apparently because of cleverness in the Swiss Tables algorithm that I don’t fully understand. So, without doing a full hash table algorithm using a simple mod trick, it looks like FNV + capacity is my best bet for performance at the moment. 

1. Coming from Java this is a bit of a shock since Java’s HashMap can only use the hash() function of the key. If you want a custom hasher for a key, you need to create a custom class for the key with a new hash() function. But since common key types like String or Char are declared final, you can’t just subclass the type and override hash, you need to create a wrapper class instead. 
2. One of the interesting challenges in writing the char sub algorithm was dealing with mappings like A→a, ABC→b where an input like ABD should get mapped to aD which meant that in that instance, we need to backtrack on the input and A and B end up getting hashed twice in that scenario.
3. They said no.