Re: Trouble translating a C++ data-structure.

[Shark8 <onewingedshark@gmail.com>]

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 unable
> > to really do so (my C++ is really rusty). 
> 
> Which precise areas are the biggest gaps of understanding?  As pointed out above, this is garden-variety 1970s-era structured-programming non-OO C-language memory allocation from the heap.  There exist a multitude of before & after transliterations from C data structures to Ada from which to borrow various flavors of ideas about Ada-83-era or post-Ada-95-era properness in 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 using the spec-dump flag... I'm unsatisfied with the results, and think I might be missing things due to the rusty C.

> 
> 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 already 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 really dumb to me to use tools that are so error-prone when such errors are avoidable/detectable).

> 
> https://stackoverflow.com/questions/20879589/what-prevents-van-emde-boas-trees-from-being-more-popular-in-real-world-applicat
> 
> One observation though inherent in this data structure independent of skills, (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 of maximum storage-pool size in Ada a key design feature that you are seeking?

Tangentially.
I'm looking into some storage-pool ideas as it occurred to me that an access-type can be regarded as a mapping. Example:

Package EX is
   -- Access to Character.
   Type ACCESS_ID is private;
   Type POOL is private 
   
   Function  Deref( Item : ACCESS_ID; Memory : POOL ) return Character;
   Procedure Alloc( Item : Character; Memory : in out POOL; Result : out ACCESS_ID);

   NULL_VALUE : Constant ACCESS_ID;
Private
   Type ACCESS_ID is range 0..4;
   NULL_VALUE : Constant ACCESS_ID := ACCESS_ID'First;
   Subtype VALID_ID is ACCESS_ID range ACCESS_ID'Succ(NULL_VALUE)..ACCESS_ID'Last;

   -- Statically allocated chunk-o-memory.
   Type POOL is record
      Next : ACCESS_ID:= NULL_VALUE;
      Data : Array(VALID_ID) of Character;
   end record;
   
   Function Deref( Item : ACCESS_ID; Memory : POOL ) return Character is
    ( Memory.Data(Item) );
   Procedure Alloc( Item : Character; Memory : in out POOL; Result : out ACCESS_ID) is
   Begin
    Result := ACCESS_ID'Succ(Memory.Next);
    Memory.Next:= Result;
    Memory.Data(Result):= Item;
   Exception
    When Constraint_Error => Raise Storage_Error;
   End Alloc;
End EX;


(eg New String'("Steve") yields ACCESS_ID'( 128 ), and such.) This is of course 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... 

So, I'd kind of like to be able to use a VEB for at least the tracking a set of used access-values + [quickly] getting the next unused item; a Trie can [possibly] replace the static-array in the above example perhaps enabling a more compact memory footprint. 

There's a lot of otherwise unnecessary restrictions due to the investigation 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/obfuscate M as much as possible by being heap-based.  The more that your Ada design emphasizes drastically different design goals (e.g., overtly showcasing what that other design obfuscates), the more that the Ada way will naturally differ from the C-language representation at that GitHub project.

This is true.

> 
> 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-MUMPS interpreter into a proof-of concept state. (I'm in contact with someone on the MUMPS standard-board, and likely going to be introduced to the rest 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 is used in medical-records [the VA's entire system is MUMPS] and having an implementation 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/Pratt_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 “"functional" programming in Ada” posting's threads, I posted a vision of what one aspect of a drastically-not-GNAT modern Ada compiler could look like regarding multi-stage programming and/or source-code generation via generous amounts of compile-time reflection & some sort of Ada-get-it-right/elegant/not-Boost-C++-MTP analysis/reactions thereof via some sort of compile-time imperative or functional language.  Another 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/analog 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. -- Moreover, we could have the system automatically take care of versioning (ie getting the correct library version needed).

(See: https://github.com/mosteo/alire/issues/1 )

> 
> (For Clang & LLVM displacing GCC at Apple and at FreeBSD, its special sauce seems to be written in modern-OO C++ instead of old clunky C.  GNAT's front end already is written in something far more lucid & OOish than old clunky C, so what is Byron's special sauce instead?  Perhaps a new top-level posting 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 modular/maintainable... I'm going about that in the construction by having two main constructs a "translation"* and a "transformation"** and everything in the compiler being one of these -- thus a Phase is nothing more than a Translation. (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))))" while Lexer could itself be decomposed into various passes resulting in the proper stream of lexemes.)

Yeah, it's a very simple decomposition, but things like semantic-analysis could be done as a collection of simple transformation-functions and validators, 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 decomposed and maintained easily.)


*  Translation: F(Input : T1) return T2;
** Transformation: P(Data : in out T) OR F(Data : T) return T