Re: S-expression I/O in Ada

[Shark8 <onewingedshark@gmail.com>]

Sorry about the empty-reply earlier... I think I double-tapped the
reply/send button

Earlier you wrote this:
Consider these two objects:

L--A--tcp-connect
   |
   L--A--host
   |  |
   |  A--foo.example
   |
   L--A--port
      |
      A--80

and:

L--A--tcp-connect
   |
   L--L--A--host
      |  |
      |  A--foo.example
      |
      L--A--port
         |
         A--80

"I'm sure we can agree on the fact that these are two different and
non-
equivalent objects: not the same topology and not even the same number
of nodes. So I'd say a proper S-expression library has to be able to
deal with both of them without mixing them up."


These aren't valid representations of the LISP-like structure --
Remember that it [a list] is defined as a single item followed my a
list OR a single item alone. Therefore, *all* internal nodes in the
previous drawings should be A-L type and the leaf-nodes should be the
[terminal] A-type node.


> What I find surprising is that you seem to include type information in
> the Node type (which actually represent a S-expression atom, while S-
> expression nodes usually include lists too). Is it a typical Ada way
> of doing it?

I'm tempted to say 'yes' but I'm a newcomer to the language (from a
Pascal/Delphi background); so take that with a grain of salt. In my
opinion types are your friends {they give you information about what
your datum/variable *is*} and you shouldn't strip type-information
without good reason. That was my main reasoning for making the node-
type carry information about its contents; you *could* use arrays-of-
bytes/bits but, unless you need to, why?

> I find it surprising because the underlying S-expression format (as
> standardized by Rivest, I know almost nothing about cons pairs or
> lisp) cannot encoding that information. I would expect a S-expression
> object in memory to reflect only what can be encoded to and decoded
> from S-expression files.


My data-type can exactly represent any encoding that is in an S-
expression text-file [excepting an null-list], which by the LISP-
definition doesn't exist. An empty-list could be simulated with a
single-node containing the null-string "array (1..0) of Character." As
it stands you can think of my SExpression_type, when the List_Size
discriminant is /= 0, as being "everything within that [balanced]
parentheses-pair."

>
> In fact, one can consider S-expressions as a heterogeneous container,
> in that each atom can represent an object of any type (while losing
> the type information, which has to be retrieved from somewhere else),
> in contrast to thing like vectors, whose items are all of the same
> type. Does anybody know an example of heterogeneous container in Ada?
> I'm not sure how Ada generics can be leveraged in such a case.

You can simulate them, as I have done, by isolating "all the types it
could be" and making a variant-record type that ANY Ada container
could then hold. The "big disadvantage" is that the elements cannot
have the same name; that is to say that you cannot have a record with
an element named 'Data' which changes it's type on what discriminant
was passed.


> Another interesting point is that you chose arrays to represent S-
> expression lists. Your code seems currently unable to represent empty
> lists (which are legal at least in Rivest's S-expressions) but I guess
> I can't be too difficult to correct. But it raises the question of
> array vs linked list for a S-expression object implementation.

Well, I showed you how it could be simulated.

> I'm not sure S-expressions would ever be used in a time-critical
> application, so the usual argument of cache-friendliness of arrays is
> pretty weak here. S-expressions are meant to be used for I/O where the
> bottleneck is most likely to be.

*nod* - I didn't choose arrays for I/O cache at all; I chose them
because the number of elements is known [we've either parsed it into
memory or are building it in-place], and that all elements of that
list would have the same type -- basically a non-null pointer to some
other SExpression_type --and that SExpression could be either a list
itself or a terminal node. Add to that that Ada has nice array
manipulation facilities and I think that's enough justification to use
them.


> Ada arrays are statically sized, which can be an issue for parsing,
> because S-expression format doesn't encode list length,

That can be handled by the parser; after all it has to figure out list
lengths in order to produce the list-object, right?
Using the streams provided is a way to cut out the parser altogether,
if that's an issue, and you can just load the SExpressions directly...
think of it as being able to save/load the parse-structure that the
GCC back-end takes, you would then have a way to "compile" a program
without having to parse its source code again. {Not a very useful
feature when the program text is oft changed and would have to be re-
parsed, but for a configuration file which might remain unchanged over
the life of the application it's attendant to the story's a bit
different.}

> so a list has
> to be built by pushing nodes one after the other until encountering
> the end-of-list marker.

You're confusing parsing the list with the finished/internal list-
structure itself, I think.
Parsing is just a way of saying "I'm reading this [in order to produce
this structure]."

> But I think that should be easily worked
> around by using vectors for unfinished S-expression lists, and once
> the list is completely parsed build the array from the vector, and
> reset the vector for further list parsing.

Sure you could do that too. The Append & Prepend procedures do just
that -- without involving a vector as an intermediate.

> However for S-expression objects dynamically created into memory, the
> static size of arrays might make some operations much less efficient
> than with linked lists.

I doubt that; like you just mentioned you could wait until the entire
list has been read into-memory before converting it to a static array.

> Any idea I'm missing about this implementation choice? Would it be
> worth to try and make such a package generic over the container type
> (array vs linked list vs something else?)?

I don't know; like I said, I'm a newcomer to Ada and while I really
like it and the underlying ideology it would be foolish of me to claim
that I have the deep-understanding of a lot of the nuances.

> Thanks for your code example,
> Natacha

You're welcome.