- This is a reworking of a similar scheme discussed in Cifl/Protocifl/Name-encoded_trees is one possibility for a byte-string representation. That encoding is designed specifically for S-expressions with a list at the root and only byte strings and other lists as elements.
For various purposes, it will be useful to convert an S-expression into an unambiguous string of bytes.
A simple base encoding provides for the serialization of three kinds of element:
- A list, which is a sequence of zero or more other elements
- An atom, which in this instance is a string that contains zero or more bytes and where the value 0x00 is a valid byte and not a terminator
- A deser (or deserialization operator), which is a cue for a deserializer to treat the following list specially.
An abstract alphabet
The serialization uses an alphabet of 261 possible symbols. A symbol is any byte or one of the following non-byte values:
- An atom terminator, ‡ in this description
- A list starter, ↓ in this description
- An list terminator, ↑ in this description
- An abbreviation for ↑↓, ↕ in this description
- A deser operator, € in this description
Note that these symbols are abstract and not intended to have any association with their Unicode values.
Consider the list
(alpha #(+ 4 8) mu #(= 1 5) omega)
We do not wish to serialize unresolved function calls, so those calls are forced. The result is something like
( alpha #( $((SYSTEM number) "parse-canonical") "12" "1" ) mu #( $((SYSTEM boolean) "parse-canonical") "false" ) omega )
The values "alpha", "mu", and "omega" evaluate to atoms. The other two items are neither lists nor atoms but extended data type values—for the types (SYSTEM number) and (SYSTEM boolean), respectively.
Consider the possibility that each type has a "parse-canonical" function (this name may or may not be fictional) that accepts a sequence of zero or more simple values, where a simple value is an atom or a list of zero or more simple values. The function ideally rejects as invalid any input that is not exactly of a unique form (for example, accepting "false" but rejecting "FALSE").
The human-readable serialization of an extended data type value is a call to its type's "parse-canonical" function. Unfortunately, this only substitutes more unresolved function calls for the previous ones (and adds a layer of variable resolution on top).
For the machine-readable serialization, we might introduce a fictional sigil, which we'll call "¢", that cannot represent function calls in general but can represent a type's "parse-canonical" call specifically. Then, the above might be represented
( alpha ¢( (SYSTEM number) "12" "1" ) mu ¢( (SYSTEM boolean) "false" ) omega )
This is sufficient for us to proceed.
This pseudocode covers initial serialization.
function serialize_list(stream, list) output ↓ to stream for element in list if element is a list serialize_list(stream, element) else if element is an atom output bytes of element to stream output ‡ to stream else # element is extended data type value output € to stream let t = list expressing data type name of element # e.g. t = ["SYSTEM", "number"] let p = list expressing deser parameters for element # e.g. p = ["12", "1"] let d = copy of p with t prepended as a single value # e.g. d = [["SYSTEM", "number"], "12", "1"] serialize_list(stream, d) output ↑ to stream interface deser_marker property parameters is an appendable list function deserialize_list(stream) let stack be a mutable stack push  onto stack while stream can be read let current_atom = "" read symbol from stream while symbol is a byte append symbol to current_atom read symbol from stream if symbol is ‡ let t = item at top of stack append current_atom to t else if symbol is ↓ let l =  let t = item at top of stack append l to t push l onto stack else if symbol is ↑ pop stack assert that stack is not empty (otherwise, too many ascents) else if symbol is € read symbol from stream; assert that it is ↓ let d = new deser_marker let t = item at top of stack append d to t push d.parameters onto stack pop stack let all = top of stack pop stack assert that stack is empty assert that all contains exactly one element let l = all assert that l is a list return l # Traverse result to resolve deser markers as needed
Now, consider this list:
(hello #(int 12) fizz #(false) (a "" () b c))
As before, the first thing to do is resolve the function calls, inserting the bogus ¢ sigil as needed:
(hello ¢((SYSTEM number) "12" "1") fizz ¢((SYSTEM boolean) "false") (a "" () b c))
The following is equivalent; some of the implicit quotes have been added:
("hello" ¢((SYSTEM number) "12" "1") "fizz" ¢((SYSTEM boolean) "false") ("a" "" () "b" "c"))
Serialization would go something like:
# The root ( "hello" ¢ ( ( SYSTEM number ) "12" "1" ) "fizz" ¢ ( ( SYSTEM boolean ) "false" ) ( "a" "" ( ) "b" "c" ) ) # Convert byte strings to terminated form ( hello‡ ¢ ( ( SYSTEM‡ number‡ ) 12‡ 1‡ ) fizz‡ ¢ ( ( SYSTEM‡ boolean‡ ) false‡ ) ( a‡ ‡ ( ) b‡ c‡ ) ) # Convert ascents and descents ↓ hello‡ ¢ ↓ ↓ SYSTEM‡ number‡ ↑ 12‡ 1‡ ↑ fizz‡ ¢ ↓ ↓ SYSTEM‡ boolean‡ ↑ false‡ ↑ ↓ a‡ ‡ ↓ ↑ b‡ c‡ ↑ ↑ # Convert the construction indicator ↓ hello‡ € ↓ ↓ SYSTEM‡ number‡ ↑ 12‡ 1‡ ↑ fizz‡ € ↓ ↓ SYSTEM‡ boolean‡ ↑ false‡ ↑ ↓ a‡ ‡ ↓ ↑ b‡ c‡ ↑ ↑ # The same displayed without spaces ↓hello‡€↓↓SYSTEM‡number‡↑12‡1‡↑fizz‡€↓↓SYSTEM‡boolean‡↑false‡↑↓a‡‡↓↑b‡c‡↑↑
function compress_serialized_list(symbols) with symbols # deser implicitly descends twice replace all instances of €↓↓ with € # a non-empty byte string implicitly ends at the next non-byte remove all instances of ‡ that immediately follow a byte and immediately precede ↑, ↓, or € # the root is implicitly a list remove one ↓ at beginning # the list is implicitly fully closed remove all ↑ at end # adjacent lists are partly abbreviated replace ↑↓ with ↕ return symbols
# (changes are called out with angle brackets) # Replace €↓↓ with € # (constructor implicitly starts with two descents) ↓hello‡<€↓↓>SYSTEM‡number‡↑12‡1‡↑fizz‡<€↓↓>SYSTEM‡boolean‡↑false‡↑↓a‡‡↓↑b‡c‡↑↑ ↓hello‡<€ >SYSTEM‡number‡↑12‡1‡↑fizz‡<€ >SYSTEM‡boolean‡↑false‡↑↓a‡‡↓↑b‡c‡↑↑ ↓hello‡€SYSTEM‡number‡↑12‡1‡↑fizz‡€SYSTEM‡boolean‡↑false‡↑↓a‡‡↓↑b‡c‡↑↑ # Wherever ‡ follows a byte and precedes [↑↓€], omit it as implicit. # (Note that it must actually follow a byte—this doesn't apply with an empty string.) ↓hello<‡>€SYSTEM‡number<‡>↑12‡1<‡>↑fizz<‡>€SYSTEM‡boolean<‡>↑false<‡>↑↓a‡‡↓↑b‡c<‡>↑↑ ↓hello< >€SYSTEM‡number< >↑12‡1< >↑fizz< >€SYSTEM‡boolean< >↑false< >↑↓a‡‡↓↑b‡c< >↑↑ ↓hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↑↓a‡‡↓↑b‡c↑↑ # Remove initial ↓ and final ↑+ # (root is implicitly a list and is implicitly closed at any depth at the end) <↓>hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↑↓a‡‡↓↑b‡c<↑↑> < >hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↑↓a‡‡↓↑b‡c< > hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↑↓a‡‡↓↑b‡c # Replace ↑↓ with ↕ hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false<↑↓>a‡‡↓↑b‡c hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false<↕ >a‡‡↓↑b‡c hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↕a‡‡↓↑b‡c
To encode exclusively with characters in the set [A-Za-z0-9_], this algorithm is provided:
Assign these values to the elements of the alphabet:
- A byte as its numeric value (0 .. 255)
- ‡ as 357 (i.e., 260 + 'a')
- ↓ as 358
- ↑ as 359
- ↕ as 360
- € as 361
Replace any value outside [A-Za-z_] with its long form, where the long form is a digit [0-9] followed by an uppercase letter [A-Z] and is determined as follows:
- The value cannot be in [A-Za-z_]; these cannot be encoded in long form.
- Add 250 - '0'; i.e., add 202. (This maps '0' to the coded value 250.)
- Take this value modulo 260.
- Let the digit index and the letter index be the value modulo 10 and the value integer-divided by 10, respectively.
- The digit and the letter are '0' + the digit index and 'A' + the letter index, respectively.
Because of the second step, the digits [0-9] are encoded as themselves followed by 'Z' (i.e. '0Z' .. '9Z').
The values assigned to the special symbols would be the long forms of lowercase letters if those were allowed as input.
This result can be compressed slightly: Replace ([0-9])Z with \1 unless it is followed by [A-Z]. A digit in the input that is not followed by [A-Z] can simply imply the 'Z'.
Naturally, decompression reverses compression:
- Replace all ↕ with ↑↓.
- Add a ↓ at the beginning.
- Add a ↑ at the end.
- This is needed for the following step to work in all cases.
- Insert a ‡ after any byte value that is followed by ↑, ↓, or €.
- Replace all € with €↓↓.
- Finally, add an additional ↑ at the end for each remaining open list.