Discussions related to Visual Prolog
Martin Meyer
VIP Member
Posts: 298
Joined: 14 Nov 2002 0:01

Presenters, Symbols, Grammars (WAS: Variables Pending in Debugger Window)

Unread post by Martin Meyer »

(WAS: Variables Pending in Debugger Window).

When you told that the issue has to do with presenters, I remembered that I am using them in a slightly unusual way. I suppose my construction provokes the pending variables display. I want to note however that in build 906 it had worked out well. Let me explain what I am doing:

My code contains an Earley-style parser. The parsing method invented by Jay Earley works with any context-free grammar and can thus parse all context-free languages. The greater parsing capability in contrast to the limitations of a LALR parser has however to be paid for by higher computational costs.

An Earley parser will typically be slower by a factor compared to a LARL parser for a language which they both can parse. To compensate for that I have put efforts in speeding up my parser as much as possible.

One trick which I am using to speed up my Earley parser is, that my terminals have type positive rather than symbol. The main advantage of positive over symbol is that a look-up with a positive key can be accomplished very fast in constant time. I.e. when the data is held in an array.

However when stepping through the code with the debugger, numbers for terminals are not really pleasant to read. Thatfore I am giving them a presenter to display them in text form:

Code: Select all

domains     terminalNum = positive [presenter(terminalsSupport::present_terminal)].
Moreover, at the same time there can be multiple instances of the parser with different grammars. Thus there exist potentially many terminalNum to text translations at the same time. Which translation to use in the presenter depends on the grammar from which the particular terminals are.

For each grammar I keep its terminalNum translation in an object of type terminals. To switch the decoding of the terminal numbers respectively to the grammar in focus I am introducing a fact:

Code: Select all

class facts     presentingInstance_terminals : weakReference{terminals} := erroneous.
The fact is used in the terminalNum presenter:

Code: Select all

clauses     present_terminal(TNum) =         if Terminals = notErroneous(presentingInstance_terminals):tryDeref() then             Terminals:instancePresent_terminal(TNum)         else             present_terminal_uniform(TNum)         end if.
My solution of switching the decoding of the terminal numbers via a class fact is way clumsy, but it is the best that I have found.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1245
Joined: 28 Feb 2000 0:01

Re: Presenters, Symbols, Grammars (WAS: Variables Pending in Debugger Window)

Unread post by Thomas Linder Puls »

Very interesting. I am not sure how much of this that has direct influence on the debugger.

However we strongly recommend that presenters doesn't have side effects (like asserting facts and the like). The problem is that presenters are called during debugging in any number of times in any order and more over they may be terminated by an exception that the debugger code raise to avoid long presentations.

The thing with the order of presenter invocation may also mean that your fact is set for one grammar while symbols for another one are shown (perhaps that may cause indexing our of array boundaries, or at least wrong symbols).

symbols are hashed (by definition/nature): two symbols have same value iff they save same location/pointer. Subsequently they are highly suitable for hash tables (using defaultHash as hash function):

Code: Select all

clauses     run() :-         HashMap = mapM_hash::new(collectionSupport\hashSupport::defaultHash),         S = hasDomain(symbol, "startSymbol"),         HashMap:set(S, "some information").
While hash maps are not as efficient as arrays, they do have O(1) look-up, and (amortized) insert.

Another alternative you may consider is to have the information directly in your terminals:

Code: Select all

domains     terminal = terminal(string Name, terminalInfo Info).
This is a very simple and efficient way to store the information. The downside is that comparison of terminal symbols is more expensive. Unless you make sure that a canonical terminal-struct is used everywhere for a certain terminal. Our comparison always start by comparing the pointer values, if the pointer values are the same the values are also the same.

So your "grammar" may have a "terminal" map to obtain the canonical terminal struct:

Code: Select all

clauses     getTerminal(Name) = terminalMap:get_defaultLazy(Name, {  = terminal(Name, terminalInfo::new(This, Name)) }).
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 298
Joined: 14 Nov 2002 0:01

Re: Presenters, Symbols, Grammars (WAS: Variables Pending in Debugger Window)

Unread post by Martin Meyer »

My presenter doesn't have side effects. Inside my presenter the fact presentingInstance_terminals is queried, but not asserted. The translation of a terminal number into its text is very fast and cannot cause an overly long presentation.

If a program contains more than one (of my) parsers, it is not possible to set the fact always hundred percent satisfactory. When terminals from different grammars are displayed in the debugger at the same point in time, it's inevitable that some terminals are presented by wrong texts (in native view the display is but correct) - that's a drawback of the construction. Having to set the fact in many code places is also a nasty drawback.

When a terminal number cannot be translated to text because the number is greater than the maximal terminal number of the grammar (which can happen when the presentingInstance_terminals fact points to the wrong terminals object), then I don't produce an exception, but present the terminal uniformly by its number.

As far as I see, my construction may be somewhat unusual, but in principle there is nothing illegal about it.

You are right that there are alternatives to positive terminals and arrays. But after all, my first concern is speed. The speed gain of positive terminals outweigh their handicapped presentation. The user of my program cannot see how the debugger presents terminals, but he will experience the time it takes to parse his input.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1245
Joined: 28 Feb 2000 0:01

Re: Presenters, Symbols, Grammars (WAS: Variables Pending in Debugger Window)

Unread post by Thomas Linder Puls »

I agree that there is nothing wrong with your presenters. And as said I am not sure how much this influences the debugger. This kind of problem has a higher probability to happen in a multithreaded program.

I appreciate that speed is your main concern. And I believe that using a canonical object representing a token is as efficient as using an unsigned. In the actual parser algorithm the only operation you need on tokens is equality test, and for objects that is exactly the same as for unsigned (in 64 bit it corresponds to unsigned64). At the same time you presenter problem is completely solved.
Regards Thomas Linder Puls
PDC
Post Reply