From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD, FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,24d7acf9b853aac8 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!postnews.google.com!y11g2000yqm.googlegroups.com!not-for-mail From: Shark8 Newsgroups: comp.lang.ada Subject: Re: S-expression I/O in Ada Date: Fri, 13 Aug 2010 14:48:31 -0700 (PDT) Organization: http://groups.google.com Message-ID: <4b177e75-e387-47ed-b17c-bf1d69b1bc8c@y11g2000yqm.googlegroups.com> References: <547afa6b-731e-475f-a7f2-eaefefb25861@k8g2000prh.googlegroups.com> <203526c0-f031-4dfe-b3e0-cd5156de14b8@z28g2000yqh.googlegroups.com> <97ddc8e7-8e18-4d07-aaff-534ead00f4b9@d8g2000yqf.googlegroups.com> NNTP-Posting-Host: 174.28.232.29 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 X-Trace: posting.google.com 1281736111 23424 127.0.0.1 (13 Aug 2010 21:48:31 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Fri, 13 Aug 2010 21:48:31 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: y11g2000yqm.googlegroups.com; posting-host=174.28.232.29; posting-account=lJ3JNwoAAAAQfH3VV9vttJLkThaxtTfC User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.2.8) Gecko/20100722 Firefox/3.6.8 ( .NET CLR 3.5.30729; .NET CLR 4.0.20506),gzip(gfe) Xref: g2news1.google.com comp.lang.ada:13247 Date: 2010-08-13T14:48:31-07:00 List-Id: 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.