On Tue, 2007-02-27 at 18:46 -0500, Chris King wrote: > On 2/27/07, skaller <[EMAIL PROTECTED]> wrote: > > Another side to this is that the C++ community has been totally > > unresponsive, if not actively opposed (moderators actually > > blocked some of my news articles). > > IMHO C++ is the wrong target audience. Many (though certainly not > all) users use it simply because it's C++, not because it has > templates/objects/etc. Those who will appreciate the benefits Felix > has to offer would be found more easily in the ranks of users of ML > and compiled Scheme/Lisp variants, who use those languages precisely > because they want an efficient high-level multiparadigm language.
You may be right. But why would an Ocaml programmer use Felix .. when they can use Ocaml? > > The compiler handles most of the basic code ok (barring some > > correctable bugs), but is GADT's are applying some strain to the > > type system, and typeclasses to the optimiser. > > Felix has GADTs?! (I'm not really familiar with GADTs but I presume > this is what type functions accomplish?) Not yet. It has most of what is required for Generalised Algebraic Data Types. They're basically ADT's with constraints, and Felix already has the constraints (they just don't propagate). What's missing is a consistent kinding system: Felix has kinds (meta-types) but the calculus is just a bunch of ad-hoc rules, that is, a hack :) I was part of the way into implementing roughly the model found in Omega when I ran into a couple of technical problems and stopped. Then I decided that since Sourceforge FINALLY to their dang SSH service up and running it was time for another release: GADTS can wait: we haven't release typeclasses yet! The performance tests showed a problem which turned out to be an issue instantiating typeclasses -- by default it is done late, directly by the code generator, and that always leads to a heap call (creating a heap object). Looking at the code I found the reason: there are some hacks that handle virtual function calls as general Felix calls, via heap closures: this is necessary when you don't know to what the virtual will bind. I started fixing that by instantiating virtuals during the inlining process and monomorphising non-inlinable routines to enable that to happen even more often, but then more precise tracking of which things need to be marked for heap calls is required.. somehow in the process not only did I mess up the calculation, some other thing lead to the infinite cloning problem again. The optimisation algorithm is extremely fragile: it took over a year to find a combination that actually worked, and every change destabilises it. > > For example the builtin lexer could be replaced > Hold off on this for about a week... right now I'm taking a course on > automata so this stuff is fresh in my head. LOL. This has been pending for two years or more. The funny thing is the string regexp functions available at run time actually do use Laurikari's C implementation, TRE (TRE is built into Felix RTL at the moment: the C++-ized sources are part of the svn repository). The people that worked on the Ocaml version could probably fix us up in with a couple of days work: it's one of the things I was thinking to spend money on. In fact, Alain Frisch has been very helpful and positive about helping if we wanted tree automata of the kind used in C/XDuce for XML parsing .. and actually his paper uses Ocaml notation, and is quite easy to understand (Frisch is a genius :) TRE is roughly C/XDuce with its nuts cut off: CDuce builds a whole parse tree, rather than merely capturing the last match. But the cost is that it requires a bidirectional iterator whereas TRE only requires an input iterator for a DFA (or a forward iterator for a basic NFA). > I read Laurikari's paper > and it seemed to make sense to me so I embarked on writing a regexp -> > NFA -> DFA converter in O'Caml. It is already done: Ocamllex does it right now. The source is about two pages of Ocaml: look in the Ocaml source code. I just don't understand how it works, because it's not documented: I can't connect some of the constructors with the terms used in the paper. Ocamllex does some extra optimisations, and it builds a DFA with overlapping state vectors as described vaguely in the Dragon book (but for which no coherent algorithm or explanation of how to actually construct them is given). The result will basically be: the Felix DFA engine will add a tag to some transitions that will cause the current pointer into the string input to be stored in a particular slot of an array. That's it. So the run time engine barely needs modification. At the end, pairs of these pointers delimit the matched substrings (or no match if one is NULL). It's actually not clear if this will be faster than a caching NFA engine which does the subset construction to construct DFA states on the fly: the DFA could be very large and so can cause paging so the constant time factor could outweigh the theoretical exponential time required for an NFA. So Felix could actually use TRE directly if Ville Laurikari would permit decoupling the combinator interface (since Felix lexer doesn't want to use string regexps when it already has things in combinator form). But you see my point: this is but ONE small facet of the system. The GLR parser cannot merge parses -- Elkhound can do it but there is no way to do it from Felix (yet). That's another job. I left a lot of these things at the point where the basic functionality worked, to allow users to drive the choice of which ones would provide the most benefits continuing with. The main feedback has been the library development: for example typesets were introduced to allow one to generalise over things like "all C integer types". Typeclasses allow one to write algorithms that require equality on a type variable. The latter works only for primitive types -- it is not clear how to 'derived' arbitrary extensions to general algebraic types: Haskell allows deriving for Eq but as far as I can see it is a totally unprincipled compiler hack. There has been some feedback from users .. I got the basic class system working in a couple of days (which was a MAJOR effort I didn't expect) when someone dropped in and asked for it -- but they were gone by the time it was done and it was only recently someone even tried to use classes (and ran into about 10 problems in a row). Now he's gone too. I'm sure a lot of people see great promise here -- but most don't have the time to do the work to make it happen so they move on. I think it's like a treasure chest: there's heaps of good stuff waiting to be discovered and finished but the map has been torn up into pieces which have been scattered all over the mailing list. -- John Skaller <skaller at users dot sf dot net> Felix, successor to C++: http://felix.sf.net ------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ Felix-language mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/felix-language
