Re: Ada 'hello world' for Android; success!

[Stephen Leake <stephen_leake@stephe-leake.org>]

Georg Bauhaus <rm.dash-bauhaus@futureapps.de> writes:

> On 02.11.11 16:55, Stephen Leake wrote:
>
>>>> http://www.stephe-leake.org/ada/access_vs_object.html).
>>>
>>> (When the problem domain is grammars, my goal of an application is to allow
>>> the user to build a structure of subprograms that represent a grammar,
>>> so the application can then call the subprogram matching the start symbol
>>> (or other symbols) to parse input strings.
>>
>> I'd love to see your solution to this problem. It's easy to talk about
>> general principles and design goals; only complete actual solutions
>> flesh out all the problems and details.
>
> http://home.arcor.de/bauhaus/Ada/recdecnoptr.ada

Ok. The recursion in the grammar is represented by recursive subprogram
calls.

> This example features:
>
> - a hierarchy of "tokens", though barely: Terminal and Non_Terminal,
> with some info in each, derived from abstract Token.

Sufficient to illustrate the point, but a more complex example would
make the relative costs of the various solutions more apparent.

In particular, the operations in the 'access vs object' example require
a separate stack when using a recursive descent parser (see OpenToken
asu_example_5_10 for more on this). Implementing that stack could easily
require pointers, for complex objects.

> - a handler derived from an abstract handler type, overriding a
> primitive operation. The operation, On_Token, receives an object
> of type Token'Class when some "grammatical event" happens.
>
>       procedure On_Token
>           (Manager : in out Handler;
>            Found   : in Tokens.Token'Class)
>          is abstract;
>
> - a recursive descent parser (exhaustive). The parser is structured
> just as the grammar, which in this demo is
>
>   S -> a S | a

This grammar is rewritten from the original grammar. This is an accepted
technique, but it is a way to introduce errors, so it must be counted as
a cost.

> A similar program using the same parsing technique was
> built around 28 productions. It also had the necessary level of
> abstraction that is absent from the above demo, such as functions
> that would query the state of a token (Image etc.).

I'm impressed.

> No token is ever stored, though the handler types are free to
> do whatever they want with the tokens, including storing them.
> There are no allocators for tokens. The program uses access,
> but for different purposes.

I agree this use of 'access' is different, since it is 'access
procedure', not 'access object'; no allocations are needed. But I
suspect some purists would still object :).

> In a different program, I had used objects separate from tokens
> for keeping more information about the tokens. The tokens and
> the info objects were then associated in a has-a relationship,
> using pointers to 'Class.  But I could have passed these
> additional objects without using pointers, too, just for the record.

But you chose not to.

And that is really the point. There are various solution techniques,
some using 'access object', some not. They have various costs. We each
chose a technique that we fell minimizes the cost while maximizing the
gain. 

In my opinion, this recursive descent style is much harder to
understand. In particular, it is very difficult to see that the program
structure matches the grammar structure.

With OpenToken's data structure approach, it is very easy to see that
the data structure matches the grammar structure. That is one goal of
high level programming; make the solution space match the problem space,
so we can trust the solutions without too much work.

In addition, recursive descent in general requires far more lookahead
and backtracking than LR parsing. See OpenToken asu_example_5_10 for
more on this.

So I see this solution as far more costly than one using 'access
object'.

> In summary, then, I do not see that it is necessity to add pointers
> to a parser interface. 

I said "some form of reference semantics is required to represent the
recursion".

In your program, the recursion is represented by a recursive subprogram
call. I don't think I can twist the definition of "reference semantics"
to include recursive subprogram calls (although the use of 'access
subprogram' gives me some wiggle room), so I'll grant you have proven me
wrong.

> Storing polymorphic objects of polymorphic components seems a
> different subject of a very general nature.

Yes; if we restrict the solution space for the grammar problem to data
structures, then my statement stands.

Thanks for taking the time to implement the example. Perhaps we should
put both on the Ada Programming Wikibook somewhere?

-- 
-- Stephe