Re: S-expression I/O in Ada

[Natacha Kerensikova <lithiumcat@gmail.com>]

On Aug 10, 5:46 pm, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> On Tue, 10 Aug 2010 05:06:29 -0700 (PDT), Natacha Kerensikova wrote:
> > The first object is the internal memory representation designed for
> > actual efficient use. For example, an integer will probably be
> > represented by its binary value with machine-defined endianness and
> > machine-defined size.
>
> > The other object is a "serialized" representation, in the sense that
> > it's designed for communication and storage, for example the same
> > integer, in a context where it will be sent over a network, can be for
> > example represented as an ASCII-encoded decimal number, or in binary
> > but with a predefined size and endianness.
>
> Why don't you send it at once?

As I said, I can't just insert the raw object in the stream, I need at
least to know its size. I might need further inspection of the
serialized representation in case I want a "smart" chose of atom
encoding, but I'm afraid it wasn't a good idea to mention that point
because it doesn't fit into the simplified concept of S-expression I
have been discussing with you for quite some posts.

However my proposed Sexp_Stream does send it as soon as it gets the
whole representation, and this idea comes from our discussion.

> > This is really the same
> > considerations as when storing or sending an object directly, except
> > that is has to reside in memory for a short time. There is no more
> > conversions or representations than when S-expression-lessly storing
> > or sending objects; the only difference is the memory buffering to
> > allow S-expression-specific information to be inserted around the
> > stream.
>
> This is impossible in general case, so the question why. As an example
> consider a stateful communication protocol (existing in real life) which is
> reacts only on changes. When you send your integer nothing happens because
> the device reacts only when the bit pattern changes. So if you wanted to
> really send it to another side you have to change something in the
> representation of integer, e.g. to toggle some extra bit.

Well obviously S-expressions aren't designed to be transmitted over
such a protocol. The basic assumption behind S-expression that we can
transmit/store/whatever octet sequences and receive/retrieve/whatever
them intact. When the assumption doesn't hold, either something must
be done to make it true (e.g. add another layer) or S-expressions must
be abandoned.

For example, S-expressions small enough to fit in one packet can be
easily transferred over UDP. S-expression parsers (or at least mine)
handle well fragmented data (even when unevenly fragmented) but fail
when data is missing or mis-ordered, which prevent large S-expressions
to be simply spread over as many packets as needed. However one might
solve this issue by adding a sequence number inside the UDP payload,
along with a mechanism to re-send lost packet; however that would be
(at least partially) re-inventing TCP.

> >> What was the problem then?
>
> > The problem is to organize different objects inside a single file. S-
> > expression standardize the organization and relations between objects,
> > while something else has to be done beyond S-expression to turn
> > objects into representations suitable to live in a file.
>
> > [...]
>
> Yes, I don't see how S-expression might help there. They do not add value,
> because the work of serialization or equivalent to serialization is already
> done while construction of the expression object.

There are two things that are to be serialized: objects into atoms,
and relations between objects into S-expression-specific stuff. The S-
expression object is an unserialized in-memory representation of
relations between serialized representations of objects. The writing
of an S-expression into a stream is the final serialization-of-
relations stage.

> There are two questions to discuss:
>
> 1. The external storage format: S-expressions vs. other
> 2. Construction of an intermediate S-expression object in the memory
>
> You justified #1 by an argument to legacy. You cannot [re-]use that
> argument for #2. (OK, since Ludovic had already done it, you could (:-))

I don't re-use that argument. And actually if you followed the
description of my Sexp_Stream, I don't need a S-expression object in
memory, I only need serialized representation of atoms. The rest can
be directly send into a stream.

And while I occasionally feel the need of an in-memory S-expression
object, so far it has never been for writing or sending, it was always
for specific sub-S-expression that are read or received. I believe
this need happens only when I have a variable of type S-expression,
which I consider to be as good a type as String or Natural. It is then
a data-structure choice, which happens at a higher level than
encoding, serialization, I/O or most of what we have discussed so far.

> >> Why do you need S-sequence in the memory, while dumping
> >> objects directly into files as S-sequences (if you insist on having them)
> >> is simpler, cleaner, thinner, faster.
>
> > Because I need to examine the S-sequence before writing it to disk, in
> > order to have enough information to write S-expression metadata. At
> > the very lest, I need to know the total size of the atom before
> > allowing its first byte to be send into the file.
>
> That does not look like a stream! But this is again about abstraction
> layers. Why do you care?

The "verbatim encoding" of an atom, which is the only one allowed in
canonical representation of a S-expression, is defined as follow: a
size, represented as the ASCII encoding of the decimal representation
of the number of octets in the atom, without leading zero (therefore
of variable length); followed by the ASCII character ':'; followed by
the octet sequence of the atom.

You can't write an atom using such a format when you don't know in
advance the number of octets in the atom.

The idea behind S-expressions could be seen as the serialization of a
list of serialized objects. When serializing such a list one much be
able to distinguish between the different objects; to the best of my
knowledge this can only be done either by keeping track of object
sizes, or by using separators. To prevent the restriction of possible
atom contents, the first solution has been chosen.

> > That sounds like a very nice way of doing it. So in the most common
> > case, there will still be a stream, provided by the platform-specific
> > socket facilities, which will accept an array-of-octets, and said
> > array would have to be created from objects by custom code, right?
>
> Yes, if TCP sockets is what you use. There is a hell of other protocols
> even on the Ethernet, some of which are not stream-oriented.

But you were talking about Octet'Read and Octet'Write. Aren't these
Ada Stream based stuff?

> >> In other post Jeffrey Carter described this as low-level. Why not to tell
> >> the object: store yourself and all relations you need, I just don't care
> >> which and how?
>
> > That's indeed a higher-level question. That's how it will happen at
> > some point in my code; however at some other point I will still have
> > to actually implement said object storage, and that's when I will
> > really care about which and how. I'm aware from the very beginning
> > that a S-expression library is low-level and is only used by mid-level
> > objects before reaching the application.
>
> This is what caused the questions. Because if the problem is serialization,
> then S-expression does not look good.

Why? Because it's a partial serialization? Because it serializes stuff
you deem as useless? Because it's a way of serializing stuff you would
have serialized in another way? I still don't understand what is so
bad with S-expressions. While I understand gut-rejection of anything-
with-parentheses (including lisp and S-expressions), you seem way
above that.

> >> You do not need S-expressions here either. You can
> >> store/restore templates as S-sequences. A template in the memory would be
> >> an object with some operations like Instantiate_With_Parameters etc. The
> >> result of instantiation will be again an object and no S-sequence.
>
> > Well how would solve the problem described above without S-
> > expressions? (That's a real question, if something simpler and/or more
> > efficient than my way of doing it exists, I'm genuinely interested.)
>
> The PPN, a simple stack machine. Push arguments onto the stack, pop to
> execute an operation. Push the results back. Repeat.

Does that allows to push an operation and its arguments, to have it
executed by another operation? S-expressions do it naturally, and I
find it very useful in conditional or loop constructs.



Thanks for the discussion,
Natacha