Re: S-expression I/O in Ada

[Natasha Kerensikova <lithiumcat@gmail.com>]

On 2010-08-18, Ludovic Brenta <ludovic@ludovic-brenta.org> wrote:
> Space efficiency and human readability are antagonistic goals. S-
> Expressions are not meant to be space-efficient. If you want space
> efficiency, pipe the S-Expressions through zlib :) OTOH, a raw memory
> dump is not human-readable, hence the optional hex-encoding.

Actually a pretty good space efficiency can be attained with Rivest's
S-expressions, in what he defined as the canonical form: the overhead of
each list is two bytes (the opening and closing parentheses), there is
no per-element overhead in lists, and the overhead in atom encoding is
logarithmic (the raw binary data is inserted into the stream as-is, with
only a header containing its size in ASCII-encoded decimal, followed by
a colon). Of course that's assuming the atom content is already
space-efficient.

I think space-efficiency vs human readability should not be a choice at
the S_Expressions package level. It should rather be a choice at the
object-level, or maybe better at the application level, choosing between
different representations provided by the objects.

>> Yes, and that's exactly what I would do if I was forced to hide Atom
>> type definition; except I wouldn't use String as an intermediate value,
>> rather Storage_Element_Array or Stream_Element_Array, because I allow both
>> string and binary contents in atoms.
>>
>> Which then raises the question, why not use array-of-octet directly, to
>> avoid issues when Storage_Element or Stream_Element are not octets.
>
> Sure, that's an option. I used Storage_Element but I might as well
> have used Interfaces.Unsigned_8.

So are Storage_Element or Interfaces.Unsigned_8 better in some way then
the user-defined Octet in my S_Expression package?

>> But then I could make a public array-of-octets type, and provide
>> functions to "convert" back and forth between the private Atom type and
>> public array-of-octets type. Would that be acceptable?
>
> Sure. The only problem would be that you probably want the external
> representation to be human-readable, so you'd still need some sort of
> conversion.

As I said, in my opinion it should be an application-level choice.

However Rivest's standard does provide way of encoding atoms in
different more or less human-readable formats.

I described above the canonical form, which uses the so-called verbatim
encoding (raw data prepended by the size).

When the atom content is limited to a certain subset of octets, which
is basically ASCII letters, digits and a few punctuation marks, there is
the "token encoding" which is putting the contents directly, separated
by whitespace. That's the encoding of all atoms in my example (even
though technically Rivet's standard forbids tokens beginning with a
digit, all my parsers handled them well).

When the atom content is more complicated text, there is the
quoted-string encoding, which allows almost anything, but backslash and
double-quote have to be escaped.

When the atom content is binary, but the S-expression has to be
text-based for some reason (be it readability, or transport over a
test-based protocol (e.g. SMTP)), there are hexadecimal and base-64
encodings, which should be self-describing enough.

And  when you want the space-efficiency or unicity or ease-of-parse of
the canonical form but have to send it over a text-based channel, there
is the brace-encoding, which is a full S-expression (not a single atom)
encoded in base-64 and surrounded by braces.

However all these encodings allowed by Rivest's standard represent the
same atom contents. So design-wise, it seems best for the package to
expose an octet-sequence interface for atoms, and the encoding and
decoding being handled internally along with I/O. There would only
options set by the application to guide the package into the preferred
choice of encoding (e.g. Use_Token_When_Possible, Canonical_Form,
Brace_Encode, etc).

While the S-expression decoding part is tedious but quite easy, I found
it quite fun to write the S-expression "pretty printer" (and it was no
small part of the fun to define what is "pretty").


Thanks for your comments,
Natacha