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=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.36.68.196 with SMTP id o187mr371491ita.41.1520635484287; Fri, 09 Mar 2018 14:44:44 -0800 (PST) X-Received: by 10.157.68.9 with SMTP id u9mr3593ote.5.1520635484173; Fri, 09 Mar 2018 14:44:44 -0800 (PST) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!border1.nntp.ams1.giganews.com!nntp.giganews.com!peer03.ams1!peer.ams1.xlned.com!news.xlned.com!peer01.am4!peer.am4.highwinds-media.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!r195no445786itc.0!news-out.google.com!a2-v6ni1325ite.0!nntp.google.com!e10-v6no444279itf.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Fri, 9 Mar 2018 14:44:43 -0800 (PST) In-Reply-To: <06ffd998-f5b4-4ffd-a23e-cf922df2681b@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=76.113.16.86; posting-account=lJ3JNwoAAAAQfH3VV9vttJLkThaxtTfC NNTP-Posting-Host: 76.113.16.86 References: <1aac45bf-2baf-4ca5-9cb5-07e1748ff6b4@googlegroups.com> <06ffd998-f5b4-4ffd-a23e-cf922df2681b@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <7a285484-20b5-475e-b252-113b8a803785@googlegroups.com> Subject: Re: Trouble translating a C++ data-structure. From: Shark8 Injection-Date: Fri, 09 Mar 2018 22:44:44 +0000 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Received-Bytes: 9453 X-Received-Body-CRC: 1645164560 Xref: reader02.eternal-september.org comp.lang.ada:50916 Date: 2018-03-09T14:44:43-08:00 List-Id: On Friday, March 9, 2018 at 9:24:39 AM UTC-7, Dan'l Miller wrote: > shark8 wrote: > > I found a data-structure implemented in C++, a van Emde Boas Tree, > > and tried to write the equivalent in Ada, both using the dump-ada-spec > > flag w/ manual fixups AND a from-scratch transliteration, but was unabl= e > > to really do so (my C++ is really rusty).=20 >=20 > Which precise areas are the biggest gaps of understanding? As pointed ou= t above, this is garden-variety 1970s-era structured-programming non-OO C-l= anguage memory allocation from the heap. There exist a multitude of before= & after transliterations from C data structures to Ada from which to borro= w various flavors of ideas about Ada-83-era or post-Ada-95-era properness i= n Ada. Essentially in translating the pointer-manipulations to proper subprograms = with the proper parameter-modes. (ie using procedures where applicable, and= using IN OUT instead of pointers.) -- As I said I did both a by-hand and u= sing the spec-dump flag... I'm unsatisfied with the results, and think I mi= ght be missing things due to the rusty C. >=20 > Depending on how rusty your C/C++ knowledge is, people who reply wouldn't= want to talk condescendingly to you about this matter here which you alrea= dy know when what you need is that matter over yonder. It's been about 10 years since I last touched C or C++... most of which was= in school, and I was *NOT* a fan of either then (it's *always* seemed real= ly dumb to me to use tools that are so error-prone when such errors are avo= idable/detectable). >=20 > https://stackoverflow.com/questions/20879589/what-prevents-van-emde-boas-= trees-from-being-more-popular-in-real-world-applicat >=20 > One observation though inherent in this data structure independent of ski= lls, (as mentioned in the 2nd StackOverflow answer) it seems that the vEBTs= inherently have a maximum universe size built into them: referred to as M= in their Wikipedia article in a prior reply. Is, for example, some form o= f maximum storage-pool size in Ada a key design feature that you are seekin= g? Tangentially. I'm looking into some storage-pool ideas as it occurred to me that an acces= s-type can be regarded as a mapping. Example: Package EX is -- Access to Character. Type ACCESS_ID is private; Type POOL is private=20 =20 Function Deref( Item : ACCESS_ID; Memory : POOL ) return Character; Procedure Alloc( Item : Character; Memory : in out POOL; Result : out AC= CESS_ID); NULL_VALUE : Constant ACCESS_ID; Private Type ACCESS_ID is range 0..4; NULL_VALUE : Constant ACCESS_ID :=3D ACCESS_ID'First; Subtype VALID_ID is ACCESS_ID range ACCESS_ID'Succ(NULL_VALUE)..ACCESS_I= D'Last; -- Statically allocated chunk-o-memory. Type POOL is record Next : ACCESS_ID:=3D NULL_VALUE; Data : Array(VALID_ID) of Character; end record; =20 Function Deref( Item : ACCESS_ID; Memory : POOL ) return Character is ( Memory.Data(Item) ); Procedure Alloc( Item : Character; Memory : in out POOL; Result : out AC= CESS_ID) is Begin Result :=3D ACCESS_ID'Succ(Memory.Next); Memory.Next:=3D Result; Memory.Data(Result):=3D Item; Exception When Constraint_Error =3D> Raise Storage_Error; End Alloc; End EX; (eg New String'("Steve") yields ACCESS_ID'( 128 ), and such.) This is of co= urse covered in Ada's Storage_Pools package, but leaves the implementation = up to the programmer. (A mark-and-release storage pool is one of the basic = examples of using storage-pools I've found...=20 So, I'd kind of like to be able to use a VEB for at least the tracking a se= t of used access-values + [quickly] getting the next unused item; a Trie ca= n [possibly] replace the static-array in the above example perhaps enabling= a more compact memory footprint.=20 There's a lot of otherwise unnecessary restrictions due to the investigatio= n for this being used in a DSA application. -- The main 'distributed' part = of which is/will-be the DB [a distributed B-Tree]. > I mention this because the C-language heap implementation tries to bury/o= bfuscate M as much as possible by being heap-based. The more that your Ada= design emphasizes drastically different design goals (e.g., overtly showca= sing what that other design obfuscates), the more that the Ada way will nat= urally differ from the C-language representation at that GitHub project. This is true. >=20 > Btw, Shark8/Edward, I took a look around your Byron Ada front-end work on= GitHub. Excellent work. Please push ahead as much as time allows. Thank you; I'm going to put some more time into it after getting this DSA-M= UMPS interpreter into a proof-of concept state. (I'm in contact with someon= e on the MUMPS standard-board, and likely going to be introduced to the res= t of the board later this month... there's a chance, slim albeit, that this= could be the new reference implementation -- which could help Ada: MUMPS i= s used in medical-records [the VA's entire system is MUMPS] and having an i= mplementation in Ada would allow for some good interop, thus expanding the = "where's it used" category.) Right now I've isolated the parser -- https://github.com/OneWingedShark/Pra= tt_Parse -- and am testbedding on that to debug the implementation. (There'= s an error in precedence that I'd not been able to crack.) > Along the =E2=80=9C"functional" programming in Ada=E2=80=9D posting's th= reads, I posted a vision of what one aspect of a drastically-not-GNAT moder= n Ada compiler could look like regarding multi-stage programming and/or sou= rce-code generation via generous amounts of compile-time reflection & some = sort of Ada-get-it-right/elegant/not-Boost-C++-MTP analysis/reactions there= of via some sort of compile-time imperative or functional language. Anothe= r drastically-not-GNAT open-source Ada compiler needs some sort of special-= sauce thing that it does better as its killer app to attract people in. One thing I'd *REALLY* like to do is have the IR for my compiler be amiable= to DB-storage; this would allow for the creation of a online-library/analo= g of CPAN... but instead of storing things as text-/source-files (or zipped= -text, rather) and a index-file we could do it entirely in the DB. -- Moreo= ver, we could have the system automatically take care of versioning (ie get= ting the correct library version needed). (See: https://github.com/mosteo/alire/issues/1 ) >=20 > (For Clang & LLVM displacing GCC at Apple and at FreeBSD, its special sau= ce seems to be written in modern-OO C++ instead of old clunky C. GNAT's fr= ont end already is written in something far more lucid & OOish than old clu= nky C, so what is Byron's special sauce instead? Perhaps a new top-level p= osting on comp.lang.ada instead of here.) What do you mean by "top level posting"? Well, I'm aiming for it to be not only HIGHLY portable, but extremely modul= ar/maintainable... I'm going about that in the construction by having two m= ain constructs a "translation"* and a "transformation"** and everything in = the compiler being one of these -- thus a Phase is nothing more than a Tran= slation. (eg "Parser( Input : Lexemes ) return IR", "Lexer( Source : Text )= return Lexemes" and "Reader( Input : File ) return Text" could be combined= as "Frontend(Input : File) return IR is (Parser(Lexer(Reader(Input))))" wh= ile Lexer could itself be decomposed into various passes resulting in the p= roper stream of lexemes.) Yeah, it's a very simple decomposition, but things like semantic-analysis c= ould be done as a collection of simple transformation-functions and validat= ors, perhaps exactly mirroring the LRM. (I haven't gotten into the semantic= analysis, but this idea appeals to me in that it can allow things do be de= composed and maintained easily.) * Translation: F(Input : T1) return T2; ** Transformation: P(Data : in out T) OR F(Data : T) return T