- Boost - lists.boost.org

Template Metaprogramming I/O (well, O anyway)
by David Greene 29 Dec '04

29 Dec '04

I asked this question a year or two ago on the list. Has anyone come up with a good way to dump template metaprogramming information at compile time? I'd like to be able to do this both in a "print" sense (compiler warnings) and an "error" sence (compiler abort). I hacked something together last week that sort of does the job. There's a print<Message, FileLine> class that has a constructor with an unused variable declared. gcc gives a nice warning with -Wall. I also have some hacked macros to pass file and line number information to the printer. The printer will dump a warning if its constructor is ever instantiated. The use of all this appears in my last post in the "Named Template Parameters" thread. But this is really terrible. I don't like it much so I'm hoping someone else has a better solution. In particular, it's almost useless if there are any errors in the code because compilation will stop before instantiation happens. Unfortunately, this is _exactly_ the case where one really wants to get this information and figure out what's causing the compiler abort. I know this is useful functionality, practically required for any large metaprogramming project. I'd like to see if Boost can make something really good. -Dave

3 6

Re: Interest in a fast lexical analyser compatible with Spirit
by Dave Handley 28 Dec '04

28 Dec '04

Hartmut Kaiser wrote: >Since tokens have to be copied around in a typesafe manner I'd have >expected >to have something similar to the boost::variant, but maybe I've got you >wrong... How do you plan to achieve this? Copying through a base class >won't >work AFAICT? In my experience, copying around tokens is a major source of slow-down in lexers. The last lexer I wrote, I had to abandon the token class and use a C style union containing ints, doubles and std::string pointers. At the time, I was a little restricted in the amount I could use boost by my company, so I couldn't use boost.variant. Since then I've been putting a lot of thought into this problem and come up with one solution. We haven't completed integration testing with Spirit and other libraries yet using this technique (and I can foresee some issues already :-( ). The solution uses flyweighted tokens. The actual token exists in the rule, and during parsing, if the token has an assigned value, this is copied into the flyweight, then the token is passed around by reference/pointer. When you come to use the token in the parser you have a number of options: 1) Use it and then throw it away as soon as you call the ++ operator on the token_iterator. 2) Get the data out and do something with it - for example put it in a list/deque, etc. 3) Copy the token and use the copied version. For this final option, the token supports a virtual clone function to create copies of the flyweighted version for use elsewhere. An implementation point here is that the iterators contain a pointer to the token so that the iterator can be copied, or have the equals operator called, etc. There are some other potential solutions. However, any other solution leaves the problem of how to allocate and deallocate tokens on the heap very fast. I considered using Alexandrescu's small object allocator from the Loki library, and have also briefly looked at a boost.pool, but I am not comfortable with either of these solutions, because I am convinced that it will add too much of a burden to token creation. In my last lexer I found one or two orders of magnitude of speed improvement when I removed the token class and replaced it with a union. Since our first priority on this project is speed, I do not want the framework to slow down the DFA at all. The critical path in execution should definitely be the DFA. Dave Handley

1 0

Re: Interest in a fast lexical analyser compatible with Spirit
by Dave Gomboc 28 Dec '04

28 Dec '04

> "The Hapy library would not exist if Spirit would generate correct > parsers by default..." > > Whoa. Them's fightin' words! I believe the author is referring to incomplete backtracking (not backtracking past an accepted token when there's a failure later on). It's something the Spirit gurus have taken into consideration for Spirit 2, AFAIK. Dave

2 1

Interest in a fast lexical analyser compatible with Spirit
by Dave Handley 28 Dec '04

28 Dec '04

Since I get the mailing list in a digest, it looks like I have a lot of questions to answer. Sorry for the long(er) post, but I'm answering them all in one post: Darren Cook wrote: >There seems some interest currently in alternatives/improvements to Spirit, >so I thought I'd mention Hapy: > http://hapy.sourceforge.net/ I'll have a look at Hapy and see whether we could interface to that as well. Joel de Guzman wrote: >Some more things to note: >* why use lexeme_d on the lexer stage? >* the comment rule can be rewritten as: > '#' >> *(anychar_p - eol_p) >> eol_p; >* stringLiteral can be rewriten similarly. >* word can be rewritten using chsets. I used lexeme_d because the VRML grammar uses whitespace to separate ints and floats. Without the lexeme_d, ints could merge into one. The other optimisations are all valid, but unfortunately, don't make any difference to the stopwatch. This is because comments, stringLiterals and words don't occur too often in a VRML file - most of the time is spent parsing floats and ints. Joel de Guzman wrote: >Sure, no problem. But watch out, Spirit-2 will have a speed improvement >in the 10X-20X range over classic Spirit ;-) I already have some test >cases, and this does not touch on predictive parsing and lexing. Joel, I would be really keen to try running my VRML test case through Spirit-2. Given that I've now got the Spirit-1 parser running at about 6-7 seconds, if you get a 10x speed improvement on this file, then it could make the case for separate lexing much harder to support! I may also need a bigger file to start doing test cases on - millisecond test timings don't make for accuracy in my view :-) Joel de Guzman wrote: >Anyway, as I said, I'm very interested with your lexer. >Would you be interested in a collaboration? Yes, we would be very interested in a collaboration. Hartmut Kaiser wrote: >How do you specify production rule's? Your above sample specifies how to >use >the recognition part only ;-) >The numbers are the token ID's, I assume? The production rules are wrapped up in the different (and extensible) concept of a token. The token_float for example will match a float, then store the matched number as a float inside the token. The normal token stores nothing since something like a keyword match you don't need the overhead of the original text, but the token_string stores the string that was matched. I am contemplating an interface that allows you to use a functor to perform some basic string manipulation before the token is stored - for example dropping the enclosing quotes or similar. Although this is clearly similar to functionality already available in Spirit. Yes the numbers are token IDs - I have contemplated using const char * template parameters as well, but at present I haven't done that because of the added difficulty of ensuring that your names have external linkage. Perhaps in the final version we can support both. >Is your token type a predefined one or is it possible to use my own token >types instead? >I'm asking, because Wave in principle allows to use any token type for its >work, but it requires the tokens to expose a certain (very small) >interface. In the system as stands, all token types must inherit from a base version. This base version provides lots of useful virtual functions that derived token types can work with. The iterator interface then returns the token_base from its de-reference function. You can define new token types, but accessing the specific interface on the derived token means doing one of: 1) Ensuring the interface is exposed in the token_base. 2) Using polymorphic despatch to get the correct type, through a visitor for example. 3) If only a single token type is used in the lexer then use a static_cast. 4) Using a dynamic_cast. You can also define new rule classes - at present we have written a rule class for conventional tokens, and another rule class for tokens that have a dynamic (run-time) ID rather than the static (compile-time) ID in the template parameter. Dave Handley

3 2

[GUI] some random thoughts on GUI libs
by Christopher D. Russell 28 Dec '04

28 Dec '04

Some random thoughts on GUI libraries: Message filtering, dispatch: Somewhere buried in Joel de Guzman's Spirit or Phoenix docs I recall mention of functional programming techniques being useful for working with graphical user interface library organization. This comment stuck in my head as I generally dislike the organization of message dispatch and filtering code in libraries like the MFC and the WTL. I've been interested in the idea of leveraging Spirit to implement event processing systems for some time (here we parse event streams - not characters, using Spirit's grammar to encode state machine transition logic, and dispatching specific state-bound actions via Spirit's semantic actions). In the context of a GUI library, it's occurred to me that Spirit might be employed to "parse" streams of mouse, keyboard, and graphic subsystem notification events via a custom Sprit scanner. This of course implies that mouse, keyboard, and graphic subsystem hooks are abstracted in some platform independent manner but that's doable. In essence, this is just another way to encode complex state machines. But I think it would be cool to encode the message filtering and dispatch logic in EBNF! Message routing: signals / slots? Window / subwindow hierarchy: Given that typical GUI applications have many "windows" that are typically created and destroyed in response to (a) user input (b) non-graphical subsystem events, a succinct mechanism is needed to keep track of parent / child windows hierarchies. This information is used to calculate / transform drawing coordinates, and affect changes to message dispatching / routing / filtering. I think this information should be modeled using the BGL so we can customize the overall behavior of the system using graph algorithms. One could go a step further even and use a top-level graph to model the windowing hierarchy and another graph associated with vertex properties to encode an arbitrary closed polyline to represent non-rectangular windows. Threads: It's useful to be able to associate a "window" with a thread for high-performance GUI drawing. This is somewhat of a pain under Windows for legacy reasons but it's possible (I've done it within the context of the WTL). Here you simply blast the video subsystem with draw requests from multiple threads and place the onus of optimizing the call sequence on the driver and the underlying hardware. It would be useful to take this into account explicitly and build multithread support directly into the library. Placing the burden of this on the library user will invariably limit the portability of any application written against the lib I think. Just my two cents worth - Chris

6 10

[gui] On Native Controls
by Alan Gutierrez 28 Dec '04

28 Dec '04

* I don't think it matters much, to the user, if the button they click is a Motif button or an Aqua button, so long as their form is processed. Go to Amazon. All the buttons there are images. * Dealing with Win32 GDI controls is pain. Because they consume a Win32 window they are not going to place nice a more complex layout like a grid or a document. They are so few an simple, it is trivial to replicate them. The Win32 GDI is going to be a real problem, and it will put unnecessary design constraints on the GUI library if its poor behavior is enabled. * It is an aspect of the View of MV[PC] and the developer must be able to choose the View that suits their application. I think native controls should be supported in the case of PalmOS, where you can't overlay them anyway. Or in the case of windowing libraries that allow their controls to be clipped, where the native controls will behave properly when overlayed, and thus can take part in a complicated layout. -- Alan Gutierrez - alan(a)engrm.com

7 11

RE: FYI Lambda Question
by Brian Braatz 28 Dec '04

28 Dec '04

> -----Original Message----- > From: Powell, Gary [mailto:powellg@amazon.com] > Subject: RE: FYI Lambda Question > > So I'm checking now but I believe we set a typedef for the use of > "boost::result_of" > http://www.boost.org/libs/utility/utility.htm#result_of > > > -Gary- Thank you for your help that looks like EXCATLY what the doctor prescribed :) We MIGHT have some missing files? I am about to convert to boost 1.32 I am still on 1.31. In the 1.31 zip file I downloaded (and am using), the header does not exist in the utility dir. I grepped the boost tree for result_of and only found one comment in transform_iterator.hpp which is stated as a question ("do we need to adjust the way function_object_result is computed for the standard proposal (e.g. using Doug's result_of)?") (line 64). The link to the web page you sent me points to a HPP file. This file does not seem to exist in utility. For experimenting, I copied the file referenced in the page below to boost\utility. It complained on the line #include <boost/mpl/has_xxx.hpp> That has_xxx.hpp does not exist. Is it possible the file got dropped somehow? (it would be a shame for such a useful template to be "lost") Thanks again for your help. Brian

2 1

Interest in a fast lexical analyser compatible
by Dave Handley 28 Dec '04

28 Dec '04

Hartmut Kaiser wrote: >I'd be willing to write the interfacing stub to plug your library into >Wave. Thanks - I think this should be relatively easy because we currently use a forward iterator across the tokens in order to generate suitable output for Spirit. Clearly one of the requirements for the Boost community to accept this library in general will probably be meeting the Standard requirements for forward iterators - and I note that this is one of your key requirements in Wave. >The two different lexers I was using in the Wave library were a re2c based >lexer (static switch based lexer, extremly fast and compact) and a SLEX >based lexer (runtime generated DFA). I haven't done serious speed >measurements, but the numbers I've got so far showed similar timings for >both with a slight advantage for re2c (as expected). I'd expect your >library >to be very similar in speed as well. But just out of curiousity I'm very >interested in seeing the static DFA generation version :-) Can these lexers be effectively used with any Spirit grammar? I'll download Wave over the next few days and have a look at how much overlap there is between our library and the lexers within Wave. My plan for the static DFA version (which we haven't fully discussed in our internal design discussions yet so may change significantly), is to use the memento pattern to reflect the internal state of the DFA, along with the production rules. These could then be saved or loaded, or serialised to a C++ file, in a rather similar way to flex. This would mean that the lextl classes would be both an inline and an offline tool. In principle this gives some very desirable advantages: 1) The API remains the same in both compile-time and run-time versions. 2) You can very easily swap between run-time and compile-time versions - for example during development you may use run-time creation to speed up the process of developing a complex grammar, then switch to compile-time for your production release. 3) You have a number of options for compile-time versions. The grammar can be in a configuration file, or compiled into the program directly. >at least you could have used the symbol parser ... <snip> I've changed the Spirit grammar to use the symbol parser, and dropped the time from 40-50 seconds to about 6-7 seconds. Thanks for the tip. >Is there any documentation available? No, I'm sorry, we don't have any documentation at present, because we are still only a little beyond a prototyping stage. We still have to refine the API a little, and complete some optimisation work before we publish an early Alpha. As I said in my original post, I'm trying to gauge interest at the moment, and I'm pleased to see that we are generating a little interest. As a flavour, the current API would result in some code looking like: syntax<> mySyntax; mySyntax.add_rule( rule<token<1> >( "Group" ) ); mySyntax.add_rule( rule<token<2> >( "Separator" ) ); mySyntax.add_rule( rule<token<3> >( "Switch" ) ); // Lots more symbols for the rest of VRML... mySyntax.add_rule( rule<token_float<69> >( "([-+]?((([0-9]+[.]?)|([0-9]*[.][0-9]+))([eE][-+]?[0-9]+)?))" ) ); mySyntax.add_rule( rule<token_string<70> >( "#[^\\n\\r]*[\\n\\r]" ) ); mySyntax.add_rule( rule<token_string<71> >( "\"[^\"\\n\\r]*[\"\\n\\r]" ) ); mySyntax.add_rule( rule<token_string<72> >( "[a-zA-Z_][a-zA-Z0-9_]*" ) ); mySyntax.add_rule( rule<token<73> >( "[ \\t\\n\\r]+" ) ); lexer<> myLexer( mySyntax ); std::ifstream fsp( "test.vrml" ); myLexer.set_source( fsp ); // Also it will have a char iterator interface lexer<>::token_iterator iter = myLexer.begin(); for ( ; iter != myLexer.end(); ++iter ) // Do something with the tokens... ; Essentially you create a syntax to which you add rules. These rules explain the token that will be created by the rule, and a regular expression to be matched. Special versions of tokens exist that will automatically generate a float, int or string from the matched expression. You then construct a lexer off the syntax, set a suitable source input, and then iterate over the tokens. The tokens are polymorphic so you can easily access the type and data, they are statically typed so you can use types to match the tokens, or you can dispatch tokens to functions through a visitor framework. You can also use dynamically typed tokens as well if you want - although you lose much of the benefit of strong typing. I especially like the idea of using visitors to distinguish between tokens. This means that in my example of a VRML file, the long float lists can be handled with a visitor that contains visit functions for a float token, a comma token (note that in vector lists in VRML the elements in a 3D vector are separated by whitespace, and the 3D vectors themselves separated by commas) and a list termination token (eg a "]"). The visitor would then automatically store the floats in a suitable data structure - like a list of 3D vectors. Dave

3 2

Interest in a fast lexical analyser compatible
by Dave Handley 28 Dec '04

28 Dec '04

Dick Hadsell wrote: <snip> >disappointed, because I was hoping to use Spirit or something like it, >to give me some independence from Lex/Yacc's dictatorial control of the >input source. >Your project sounds like it would solve the worst of the problems I have >in trying to move to Spirit. The current API we are working with templatises the input so that in theory it will work with any character like input, in much the same way as std::basic_string<>. We are still working on getting the DFA to work generically, rather than just explicitly with char and wchar_t, but I think we should have some success. At present the lexer is strongly typed from this character type in the same way as std::basic_string<> but I don't necessarily see that as a problem. >I broke up the problem into 3 steps. In the first phase the program >uses a Spirit grammar to generate a list of tokens with info similar to <snip> Depending on the type of grammar I think you should easily achieve a 6x or greater performance boost. If the input has long repetitive sections, you could probably further optimise the stage so that the lexer does most of the work - for example if you have long lists of numbers or similar. I'm not sure how well this would work with Spirit until I try it, but it should be possible to switch control part way through a parse to a very quick and efficient parser that just throws the tokens at a visitor until a particular section is finished. I'm sure this could probably be done by writing a new parser type in Spirit. The idea would be to process long lists of numbers or strings or similar, where those lists have a clearly defined end token. Dave Handley

3 2

Interest in a fast lexical analyser compatible with Spirit
by Dave Handley 28 Dec '04

28 Dec '04

Christopher Diggins wrote: >Would you please post the grammar productions you used for Spirit? Would >you >consider testing the yard parser as well, http://yard-parser.sf.net ? Are >there other advantages of your tool over Flex, other than providing a nice >interface to Spirit? The grammar for Spirit was (in a slightly cut down form): keyword = str_p( "Group" ) | str_p( "Separator" ) | //etc.; comment = lexeme_d[ ch_p( '#' ) >> * ( ~chset_p( "\n\r" ) ) >> chset_p( "\n\r" ) ]; stringLiteral = lexeme_d[ ch_p( '\"' ) >> * ( ~chset_p( "\"\n\r" ) ) >> chset_p( "\"\n\r" ) ]; word = lexeme_d[ ( alpha_p | ch_p( '_' ) ) >> * ( alnum_p | ch_p( '_' ) ) ]; floatNum = real_p; vrml = *( keyword | comment | stringLiteral | word | floatNum ); I've cut down the keywords because there are over 60 of them. I would be interested to know if there was any obvious ways to optimise the Spirit parser. Regarding writing a comparitive test for YARD, I will certainly consider it, although I have no experience of using YARD. I've written quite a lot of flex/bison parsers, written a number of Spirit based parsers, and hand coded a number in my time, but I would need to spend a little time learning the YARD framework first. There are a number of advantages over Flex (including a nice interface to Spirit). The key ones are: 1) An extensible object oriented approach to writing the entire system. This can be very useful if you want to handle something like say the parsing of a filename in the lexer. You can simply write a new token type that will split the incoming filename into path, extension, name, etc. This can massively simplify the production of a final parser - allowing you to deal with grammar issues at that stage. 2) DFAs can be created at run-time, or eventually compile-time. 3) The code is considerably less obfuscated than the code produced by flex. Don't get me wrong, I like flex a lot, but the pre-processor directives, and look-up tables in the generated code are pretty unreadable IMHO. Dave Handley

4 3