GenI file loading cleanups

OK, so I think the GenI code for loading in input files is a bit better now.  The code is actually longer, not a great sign, but it seems a lot more uniform, composable and easy to modify.

Recalling the problem, I have something like 8 different kinds of input files that I read into GenI and my code was a bit of a mess.  It was heavily factored, but somehow in the wrong way.  Something very fragile and useless feeling about it.  Some things that vary:

• most files read lists of things, but some deal with more exotic objects
• most files are text based, but some have the option of some binary encoding
• most files are with parsed with Parsec, some others with simple line processing, or with JSON
• some files are "mandatory" - if we try to load them and you don't supply them as input, something bad should happen; some files are optional - trying to load them should be a no-op if you don't

change 1: use a typeclass

I haven't changed anything fundamental about how the code works so much as restructure it.  The first big difference is that I now have a typeclass that captures the 3 main things GenI does when it loads some file:

class Loadable x where
  lParse       :: FilePath -- ^ source (optional)
               -> String -> Either ParseError x
  lSet         :: x -> ProgState -> ProgState
  lSummarise   :: x -> String

Having this typeclass has made my code a lot more uniform.  The old approach was to have a generic higher order load function that took lots of other functions and various bits and bobs as input (so it was factored but incomprehensible).  Now I only need to specify that the format I'm loading in is Loadable, and it's implicit that I have access to these three functions.

The main function here is lParse.  There are some implicit decisions here. First, parsing should be treated as something that's done on strings, and not files. I'm not sure if I'll come to regret this. In the future, I may update this decision so that parsing is done on some sort of binary blob instead, but with the core idea that this excludes any of the IO behind it. Second, parsing a file and massaging it is treated as a single cohesive black box. My various parsers used to scatter this in different places, mainly in the bit that updates my program state.

The other functions, lSet and lSummarise are not so important.  They update the program state and provide a count string respectively, something along the lines of "3 elementary trees".

change 2: more composable helpers

Instead of having one big load helper function, I've broken down some of the choices into standalone functions that you can then mix and match.

I now have

• withFlagOrIgnore and withFlagOrDie: extracts the value of some flag and respectively silents ignores if it's not there, or just exits the program
• withLoadStatus: takes a file parsing function and decorates it with "now loading X" and "...n items loaded" output (using the lSummarise function)
• throwOnParseError: takes a parse output and either throws an exception if there is a parse error or returns the value
• lParseFile and lSetState: IO bound wrappers around Loadable

Having these functions separated from each other makes it easier for me to modify behaviour, and also helps me to avoid redundancy when I have subtly different requirements (like the binary file thing).   I can just mix and match them in slightly different ways.  One change that this facilitated was for me to replace a dieOnParseError with throwOnParseError, just a straight shot darcs replace and a tweak on the function.

So, GenI file loading now a lot better.  Not going to win any awards or be a Functional Pearl, but at least it's less horrible than before.

GenI parser cleanups and error handling

I have a piece of code which gives me a nagging feeling of wrongness.   There aren't going to be any answers in this blog post, just an exploration of the problem space.

GenI uses a handful of different input files, a tree schemata file, a lexicon and a test suite.

There are others, but we can focus on that for a moment.  I have this common pattern which I use to work with such files:

1. read configuration setting from program state (IORef): this corresponds to flags passed in from the command line
2. read the file
3. parse the file with Parsec
4. post-process the parsed entries (for example, if it's a list of items, weed out the duplicates)
5. update the program state with the post-processed entries

This is neither rocket science, nor computational linguistics, just your basic IO and dance.  Here is the code that handles this bureaucracy.  The type signatures may be a bit confusing, what with the use of existential types to try to support an heterogeneous flag set (probably severely misguided, and now potentially obsoleted by the really nice magical libraries like cmdargs and cmdlib), but I think you can see the common pattern lurking through this.

Some some reason I've spent the whole time working on GenI walking around with this nagging feeling of Wrong-Wrong-Wrong, the feeling that this should be a lot simpler and tidier than it is; but also that I had far more important things to be doing that worrying about a minor itch.  Unfortunately, the itch has just turned into a rash.  The issue is that the error handling is not useful outside the context of an academic software prototype, a prototype which can afford to crash autistically because its programmer has high priority items to hack on.  If you want to use GenI as a library, crashing on bad input is not going to fly.

Notice that the problem is not the code isn't factored.  In fact, it's probably excessively factored, but just somehow wrongly factored, like I've started barking up the wrong tree. I kind of feel like I need to redistribute the pieces and try again.  Part of this is the natural, organic growth of an academic software prototype.  You just sort of glom on features as your needs change.   The problem now is how to tease apart the necessary and unnecessary bits of complexity:

• error class: missing command line arguments -- notice I have a loadFileOrIgnore for some reason, looks like there are cases where you do want to support a command line argument being missing, but not always
• error class: bad file
• error class: missing file, etc [not really handled]
• use cases: reading from GUI support (if the user supplies bad input from the GUI, pop a dialog box instead of just crashing -- this isn't visible in the snippet but it does do that for some inputs), reading from command line and reading via a library call
• status messages (printing "now loading foo..." to stdout
• wanting to avoid code duplication
• binary file detection - in the case of macros files, we have two file formats, a fast-loading binary file format (probably a bad idea?) and slow-loading text file format.  We want to support the behaviour where we first try to read the file as binary, and if that fails, read it as text.  It's worth thinking about dropping this future, but we don't want to break compatibility with old grammars in the process

There are basically a couple of other issues I'm trying to wrap my head around

1. Can we eliminate the use of a global program state to pass things around in?  It feels so horrible, but every time I make a stab at it I somehow burn my fingers and give up
2. What kind of error handling do I want?  We have a lot of tools at our disposal in Haskell.  For example, parse errors can be differentiated from successful parses in the type system.  Unfortunately, one tool I've been using a lot (for convenience) is fail, a function whose presence in the Monad type class is commonly held to be a mistake in Haskell.
3. From the maintenance perspective, how do I divide the code?  What lines do you factor it along?  This is probably one of those tricky questions it would take years of maturation to answer properly.  What do you make easier at the expense of others?
4. From the usability/API perspective, how I divide the interface?  What should I provide as discrete functions, and what should I ball up into do-everything functions?  

Error handling is a subtle topic with tradeoffs, and I think it is very very easy to get the wrong idea about what to do with errors. For example, Freshman Eric tried to take to heart the idea that code should be defensive and robust with respect to errors but ended up writing a lot of code which just "gracefully" caught errors only to hide them (and yes, before you weigh in, I know that you can catch exceptions selectively).  I'm just saying it's more subtle than one may think... Maybe a more mature Haskeller or a LISPer can come in and smack my head around a bit.  For now, I'm working on this sort of rough basis:

1. expected unusual cases - not actually errors (for example, find me the first entry in the list which satisfies condition foo should return Nothing or Just the item)
2. my errors as a programmer - this-should-be-impossible style error should either be cunningly made inexpressible with the type system (this is the sort of thing I admire in clever Haskellers), or greeted with a CRASH.  The crash is something Freshman Eric would not have understood, "wouldn't you want to be robust?"
3. bad input from other programmers using my code - ??? if I'm division, what do I do if the programmer fails to heed the API  and passes me a zero denominator?  If I'm the head function, what should I do if the programmer gives me an empty list?  The Haskell stdlib crashes in these cases (you should know better), but an alternative option would be to be express the errors with something like Maybe.  But does the Maybe really make sense here?  I can see how you would want to express the idea "this dictionary does not have the entry you're looking for", but saying that 4 / 0 is Nothing where as 4 / 2 is Just 2 seems to imply that 4 / 0 is legitimate.
4. user errors - be as graceful as humanly possible, detect errors at the earliest possible stage
5. completely unanticapted errors - ??? nobody is perfect... you can't predict everything that could possibly go wrong (perhaps unless you're one of these Formal Methods types?)

I don't want to get too general about this, not trying to write a programming book here.  Just saying, this sort of thing can be a bit subtle.  In my case, I have a user error (trying to parse a file that's not in the expected format), and I think actually my code does recognise it as such.  The Parsec library recognises it as an expected usual case (which makes sense), and my code simply takes it out with pattern matching (Left/Right) and blithely exits on parse error.  In a sense I'm doing the right class of things (knowing it's a user error), but I'm doing it in the worst possible way; exiting when I should be giving the user some recourse to action.

That should be a straightforward fix to make... just throw an exception, but I still think this code needs a lot of cleaning.

back to GenI

I have to returned to GenI!

Starting this week, I'll be working 2 days a week with Computational Linguistics Ltd (London) and SRI to develop new features, improve scalability of the generator (hopefully by exploring the notion of equivalence class based packing) and integrated it into an interactive tutoring application.

I'm still working at UoB 2 days a week and at Well-Typed 1 day a week for the moment, so my schedule (and brain) are a bit packed at the moment.   In any case, I am very excited to get a chance to get back to GenI.  Ever since I've left Nancy, I have had this feeling of "unfinished business".  It was slightly relieved when I had a chance two years ago to work in LORIA for a month tidying up GenI (for example, JSONifying a lot of the ad hoc file formats), but still.... there's work to do!

Now I have a somewhat more substantial chance to get back to this unfinished business.  I know GenI could be much much better.  I have slight suspicion that being exposed to a bunch of smart hackers in the open source community (my Darcs hobby) may have equipped me a little bit better to tackle these improvements.

The three areas I'm prioritising at the moment:

1. integration - our current client would like to integrate GenI with their software; anything I can do to smooth this process comes first
2. performance - I want to start working towards a notion of equivalence class based packing, really basic standard stuff in GenI but for the longest time, kind of hard for me to reconcile with a tree-as-basic-unit-of-processing world view.  Now I think I have a workable algorithm, and if I understand correctly, one that is also used elsewhere
3. cleanup - in freshman year of undergrad, I had this lecturer (was it Mitch Marcus?) that said that basically every programmer walks around with a slight feeling of embarrassment about his code.  The cleanup will be essentially motivated by integration and performance needs.  Using GenI as a component in other pieces of complex software means that we're going to have to start thinking a bit more carefully about getting a reasonable API

Naturally, I'll be wanting to blog about the progress as I go along, writing being a thinking tool after all.  See you in future posts!

equivalence-class based packing for GenI - node counting idea

Here's an idea that came to me when I was quite literally sitting around doing nothing.  Ah yes, the whole business of getting ideas for things you are not working on.

GenI is a chart generator.  It has a notion of agenda/chart-based control to order operations and sub-tree sharing (basically for free by using Haskell), but what it lacks, crucially is a notion of equivalence-class based packing.  Packing is extremely important because it's what allows you to control the combinatorial explosion of intermediary chart items as you explore the search space.  In particular, in GenI, we're interested in exploring the whole space (enumerating all possible parses), so we're not particularly after any sort of pruning.  Really, the chart is all about making sure we don't do a lot of stupid redundant work.

What you want your equivalence classes to do is partition your set of possible chart items in such a way that lets you compare the subsets with each other rather than the individual items within.  So to illustrate example, imagine you're starting out with 8 items (in classes A, B, C) :

• A: 2 items
• B: 3 items
• C: 2 items

If you were just doing straight parsing without any sort of equivalence classes, you're going to be deriving 2x3x2=12 items.  But if you use the equivalence classes, you only need to do 1x1x1=1.  At the end of the day, you're still going to have 12 items when you expand the set, so what have you gained?  Well, I'm still a bit fuzzy on that to be honest.

Part of my answer is that it saves you work when you have chart items that don't lead to any derivations. If you have say another 4 items that can combine with these 12, that gives something like 48 items to sift through (before you work out that you can only keep 12 of them).  With equivalence-class packing at least, you avoid this sort of explosion.

I'm not sure if that's the whole story.

Anyhow...

There's one way I knew to get equivalence-class based packing for GenI, and that would be to implement a CKY/Earley parser for TAGs.  I tried that during my 2nd year of the PhD, but the whole thing sort of fell apart because my coding sucked (I think now that I know about the Zipper, I can have a much better chance).  Nevermind, it gave me a chance to refactor the hell out of the code.  I still think it'd be good to get back to it... but what if there was a simpler way?

the plan

First, let's make some simplifying assumptions:

• no substitution - we're in an adjuction only grammar (which is easy because GenI does 2-phase generation only)
• auxiliary trees all have the same root node category (we can relax this later on)

The problem I was struggling which trying to work out how packing would work is that it's not just good enough to partition your set of chart items.  What you to do is to partition them in such a way that the result of combining two equivalence classes can be derived from the classes themselves and not the items within them.  Coming up with any old scheme for putting your chart items into bins is the easy part.  Now what happens when you plug two of those bins into each other?  And if you do come up with such a scheme, is it going to chunk your inputs so that you get that factorisation thing going on, or are you just going to partition into a bunch of singleton sets?

And here's the scheme I just thought of:

Two items are in the same equivalence class if they have the same semantics, and the same number of nodes  (of a given category X) which can receive adjunction

If you do adjunction with this scheme, all you have to do is take the union of the semantics (à la Martin Kay) and the sum of the numbers of the nodes (minus 1 or something like that).  And if you want to deal with more than one category, just do it in phases.  First focus on one category, derive everything you have.  Then pick a new category and re-pack everything into a different chart.

I hope that this scheme is broad enough that it actually divides our chart into non-singleton sets. 

Will it work? Will it work? Will it work?

I can't wait to find out.

Too bad I don't actually have time for GenI hacking.

GenI 0.20 released

Here's the official announcement. Heading in the right direction. Not completely there yet, but APIs are getting simpler, documentation is getting written, things are getting clearer. GenI 0.20 is a nice little hop in the right direction... at least, I hope.

Gave my ENLG talk again.

Talked with one of my GenI users, which turned into a great rambling chat about everything and anything.

Nice way to end the trip. Goodbye, Nancy, merci and hello Brighton on Thursday.

fixed the unification bug!

Woo! That was making me pretty unhappy.

It wasn't the core unification algorithm that was at fault (phew!). It was just a simple matter of "oops, I forgot to propagate these replacement values" when doing successive unifications during adjunction. Of course the real problem is that we're doing unification in an overly manual and error-prone fashion. We need to stop doing that. The Prolog hackers are watching and laughing.

I don't think I really need to go as far as having a unification monad (or whatever). Simply replacing all my unify :: a -> a -> (Subst a , a) (yes, I'm fibbing with the types a bit) with unifyWith :: Subst a -> a -> a -> (Subst a, a) would be a step in the right direction. We'd still have to keep track of the new substitutions that pop out of it but at least this fixes the core stupid.

the wrap up that never wraps

Argh, mind spinning with things I want to do in my last few hours of GenI hacking time. Not really being very effective about this, just sort of darting around randomly.

morph progress

In a frenzy of refactoring last night, I've finally kicked the morphological realiser out of GenI and rejiggled the interactions between the two to be completely JSONified.

I still need to:

• print uninflected forms in the enriched output and for each form all the morphological realisations for it (this takes a bit of work actually, lots of cleaning up to do)
  
• output this stuff in geniserver

The pieces are all there, but I can't really work on it right now because there's not much time left and I still haven't looked at the unification bug

genimanual

For no good reason (probably because I was tired), I started trying to sweep up bits and pieces of the wiki into the LaTeX/Literate Haskell manual. I think I want there to be 4 kinds of documentation:

1. Wiki: walkthrough, FAQ, little user-driven notes
2. Manual: reference manual; not meant to be friendly, just complete
3. Literate GenI: still not sure how to do this right, but something that shows you the underlying implementation details but still on a somewhat high level
4. API

The situation is not less bad than it was before this month. For example, I've consolidated the description of the GenI formats (EBNF, etc) into the manual and really tidied the heck out of that module. So at least that bit looks somewhat reasonable. The main thrust of this work has been to clarify the distinctions between the four kinds of documentation, which means I now have a clearer idea of how to write for each context.

Remaining shortcomings:

• Basic flags not documented: http://trac.haskell.org/GenI/ticket/36
• Manual is in PDF only. Need something like Hevea or Latex2html to convert it
• Ugh, lots more...

the unification bug

I ought to spend the rest of this afternoon just looking at the unification bug. Fixing the morphology stuff would be great, but it's not a release blocker...

wrap-up 2

Spent this morning dithering over the future of GenI's relationship with lex2all. I think the right thing to do is just to merge parsing of CGM lexicons into geniconvert. There may be some code-duplication but the way I figure, one way or another *some* code is going to be duplicated and it's unlikely lex2all is going to use the GenI library to inherent its model of lexicons. So this is the simplemest way forward.

all done?

Otherwise, I think I'm done with all the items on my official TODO list, rah! This means I get to go play :-)

• decided we're dropping the random formula thing: it should just work once it's in the right format, so I'm ignoring it
  
• demo'ed the results of the OT-GenI integration and also the latest state of the Forge
• presented the idea of using virtual machine and a disk image so that future installation procedures can be tested on a clean machine
• advocated geni-users passing to moderate for unsubscribers only (that was easy :-))

Go play...

• Clean up interaction with the morphological realiser - I've now got GenI spitting out lemmata and features in JSON (got JSON-fever, sorry!) and expecting lists of lists of input back. There's still going to be some GenI-specific formats around, but basically anything that can't be expressed purely in idiomatic GenI is going to be JSON with some GenI thrown in (eg. for features). No more making up crappy Erician formats, but no need to subject myself to XML either. My hatred for XML is probably irrational, especially since I seem to be hitting the same kinds of nails with the same kind of hammer. Sue me.
• Fix the darn unification bug! Wah
• Release GenI (but only if I can either fix the unification bug or prove that it already existed in the last release)

GenI wrap-up mode

Pretty satisfying day. Just lots of stuff coming to completion at once:

• INRIA-Gforge stuff is out of the way. I'm using Git-SVN to make Subversion bearable. Once you go decentralised you can't go back. Micro-commiting forever.
• I've completed the integration of the OT ranking code into mainline GenI. If you run it in batchdir mode, you get the rankings and violations in JSON. If you run it just on plain console, you get them pretty-printed. If you run it in a GUI you see them in a separate tab
• I now require UTF-8 input files. I don't have the resources to deal with locales, but I want Unicode support so you're stuck with it. I didn't touch the output, however because I figured I might as well just wait for GHC 6.12 with its locale stuff.

Todo todo:

• Integrate GenI into random formula generator (that's the last of what I'm brought here to do)
  
• Investigate that pesky unification bug. Does it happen with GenI 0.17.4?
• (maybe) look into morphology stuff
  

cluster progress

cluster stuff

Last night and this morning, I polished off the GenI work needed to make it run on the cluster. I also have ppss another look.

One thing that PPSS assumes is that the nodes of the cluster can ssh to the master to ask it things. I wonder how that would work with all these crazy oarsh-or-whatever scripts. Apparantly oarsh is just a super-layer on top of ssh, so maybe there is a way to get at the underlying ssh keys so that PPSS can work.

Working with the local engineer we've now got GenI running on a cluster node. Progress!

unification bug

The universe makes sense after all, but I still have a unification bug. The trick is that I have to turn off optimisations to reveal it. Now I need to check if the bug still exists in GenI 0.17.4

stupid GUI bug fixed!

The week so far:

• Monday: worked on Darcs and a tiny tiny bit on cluster
  
• Tuesday: worked on Darcs in morning, worked on cluster stuff
  
• Wednesday: stymied by unification bug in GenI 0.18; worked on cluster stuff; worked on bug with debugger GUI; implemented geni --version
  
• Thursday: Fixed the GUI bug! This has been going on for maybe a couple years now. It was making the debugger seem totally random (because for some reason junk was being prepended to the list of items in the chart; just the display, not the internal representation)

Basically I was trying to suss out this weird unification bug (why does it only happen on Linux?!). Naturally, I used my debugger to step through the thing so I could work out what was happening... only the debugger was next to useless because of the weird GUI bug. So slight detour as I hack my way through the graphical interface with slightly cleaner code as a result.

Of course, on the way home last night, I realised I don't need to solve the unification bug right now (for purposes of this testing stuff). I could just disable the test case that was triggering it for now so that I could move on to the my task list... but unification bugs are scary! And this being a regression...

guilt

Anyway, I don't intend on feeling too guilty about the Monday/Tuesday bout of Darcs hacking. Just a giant pile of mail in my box and a sort of budding anxiety. Had to polish that stuff all off, get it off my mind. Besides, I have done at least a couple weekends of GenI hacking before coming to Nancy so it /sorta/ evens out. And I'm planning to stay late to catch up a bit today...

So the dream here would be to find a job where you never have to feel guilty about doing any sort of work. Where the job description is just to be productive; doesn't matter who you're being productive for, just go be productive... that's the kind of job I need to land :-P because I know I have the capacity to work on stuff (and more stuff, and more other stuff), and I have a rough idea that said work is more or less net-beneficial to society. Controlling what exactly I'm working on, on the other hand, is not so easy...

unification

HUH? Now that I've fixed my weird GUI bug, the unification bug no longer manifests... also the unification bug never manifested on MacOS.

SIGH

I guess I really should go back to an older GenI and see if I can reproduce the bug there. It was pretty darned systematic.

GenI warnings, gui and morphology

warnings

Before leaving work last night, I polished off the outputting of warnings in batch mode. This also gave me a chance to refactor the GUI code so that it was no longer looking for warning conditions by itself but simply picking up the warning strings from the program state. That made me happy. Nothing pleases me more than getting rid of code.

I still have some warnings that I'm outputting via unsafePerformIO. I need to look into them probably changing the return type of my functions to make everything nice and pure.

Let that be a lesson: kludges hurt. You can do them for expediency, but never delude yourself into thinking that you won't find yourself having to clean up after them in the future.

MacOS X installation

One of my personal priorities is to make GenI easier to install on MacOS X. Ultimately, I want cabal install -fgui GenI to just work. It's not currently the case; there are still a couple of post-install hoops you have to jump through, which are all the more agacant because you have to do them each time you reinstall GenI. The desiderata are:

1. Ability to call GenI from the command line the same way you would under Linux
   
2. No adding junk to paths.
3. No manual intervention after cabal install (right now, need to call macosx-app on the binary)
   
4. No need to be super-user.
5. Possibility of installing in --global
6. Fancy custom app bundles (in the future)

After chatting on #haskell and doing a bit of Setup.hs hacking in the afternoon, I have finally, finally -- argh I'd been itching to fix this for years and now it's done -- worked out a solution to the problem. Thanks to advice from the #haskell IRC channel (it takes a village to write a script), the next release of GenI will be as easy to install on MacOS X as it is on Linux.

Now, if we could get the wxHaskell installation problem solved (and it's well on its way to being so), installing graphical GenI will no longer be painful!

morphology

Spent the early afternoon talking with another GenI user and got some nice tickets out of the process:

• #28 - output to 3rd party morph generator should include variables
  
• #29 - genisrever should output morph features and lemmas
  
• #30 - break morphological realiser out of geni executable
  

How silly of me not to have been using a proper bug tracker for GenI from the very beginning.

GenI batch processing update

It's nice to have customers that know what are the right things to ask for.

I've enhanced the basic batch processing mode in GenI so that it dumps a 'derivations' file with for each sentence

• the sentence generated
• the derivation steps as a list of (operation, child, parent, site)
• the lexically selected items as a list (item name, traces)

Instead of making up my own format, I just used JSON. Great stuff, I finally have something I can tolerate (ie. not XML), something which is vaguely human-readable but still easy to process via third party libraries. In principle, we can now get a stagiere to run over this with a little Python script or something.

Have also converted the chart statistics (don't get excited; by this I mean "number of iterations", "number of lexically selected items", etc) to JSON.

Next up: modify GenI so that warnings are stored in the program state instead of being printed to screen and also dump them in a file.

darcs stuff

Spent the whole morning in a big meeting with collaborative editing folks here in the lab, showing darcs and talking about possible links between darcs theory and operational transforms. Only I don't really understand darcs theory well enough. But hopefully we can invite more of an expert to Nancy.

XMG GenI demonstrator progress

chat

Not such a productive day. Spent first part of the morning settling in with the new machine, a few creature comforts like xmonad and my vim configuration files. Also spent the afternoon chatting with folks I haven't seen in a while. It was good :-)

demonstrator

I've got the demonstrator pretty much squared away. Have done an about-face re: installing software in a private package DB. Now the install script simply does the installation for you. The way I figure:

• If you're using the demonstrator, it's because you likely want to have the software on your system anyway for your own work
• If you're afraid of clobbering your version of the software, don't run the install script.

I'm still bundling things that I don't yet know how to automate fetching, namely XMG and associated tools.

Anyway, I've spent a little bit more time making the documentation more helpful. I hope it really does help. Will have to test it on some users.

forge

One of the questions on my mind is how to distribute the demonstrator. Here are the features some sort of forge type site could offer:

• Homepage: We want a nice (simple) homepage with information and links
  
• Package hosting: We need a place where people can download our stuff and also where we can upload our stuff.
  
• Release management : Slick interface for downloading latest version, but also for going back and picking older releases
• Version control integration : My ranking is darcs > git > SVN (given SVN, I would just roll up my sleeves and deal with git-svn). I don't care all too much because I don't think this is the sort of thing where the choice of version control system has a big impact on developer convenience. Take darcs away from me and I would be crippled for GenI, but for the demonstrator, eh.
  
• Issue tracker: trac is a natural choice for this, but I don't think we have the human resources to manage a trac instance. It'd have to be ready made.
  

What I think we all agree is that it would be silly to migrate XMG and GenI, attempting to centralise them on the one true forge. We're just going to have to accept that we're working in a heterogenous environment, combining tools from several outsiders. The fact that the outsiders happen to be former insiders is irrelevant. Someday in the future, the demonstrator may have to point to Somebody Else's really cool NLP tool, so we're going to have to accomodate outside forges one way or the other.

For now I guess the best candidates are the INRIA GForge instance and Sourcesup.

documentation migration

I'm now looking to see if my Pandoc Mediawiki work can be used to help migrate documentation from the LORIA wiki to the new trac-based on projects.haskell.org. I'll bet I can get away with just converting to MoinMoin syntax instead of writing a Trac writer. My first job is to see if I can first retrieve a list of pages that start with "GenI".

Edit Oh wait: I don't think LORIA wiki is a late enough version to support the mediawiki API.

documentation problem

I need a good policy on documentation. Right now we have (i) literateGenI - which isn't all that useful except for deep technical questions (ii) no manual (iii) sort of a wiki walkthrough that needs migration. I think I intend to flesh (ii) out using literate Haskell (where the documentation is the manual) because I think that's easier to maintain. Will have to look into something like latex2html to put it on the web. I wish I had a gitit instance to play with. That would make wikis more convenient.

loria day 1

First day back at the LORIA.

wxHaskell

Last night, I tried again to install wxHaskell using the new recabalised wxcore. This time for no apparent reason, it all magically worked! I can even run sample applications with it. Very encouraging. This means that we are one step closer to cabal install GenI just working with graphical interface and all.

admin

Today I've been doing paperwork and very shyly saying hello to people from the lab... or sometimes not and just hiding behind my screen instead.

integration

I've started rebuilding XMG-GenI integration (the Makefile of Doom) from first principles. I've learned a few things about integrating lots of software components from my Brightonian hacking so I'm hoping that these experiences will make things a lot smoother and more reproducible. I'm pleased to say that I now have an install.sh script which appears to work.

The thing I'm aiming for most is stability: this means that everything is set to a fixed known last-working version which I bundle with the tool chain or constrain with an installer version. With the exception of Mozart and the Haskell platform, I am only installing software in the toolchain's dist directory and not on the machine. We want things to be reproducible and self-contained. I tried hard to make them so in the PhD years, but I failed, partly because I was also trying to do disparate tasks ("experiments"). Now that the experiments pressure is off, I can focus on just a simple task of making the damned thing run. Hopefully with the whole thing rebuilt from scratch we can go back to thinking about how to do "experiments" from there. The integration problem isn't easy. The whole thing is about tradeoffs that you don't know you're making. It takes a lot of experience and burning of fingers to realise what those trade-offs are.

Tradeoff: The experiments tried to be varied + self-contained but at the price of duplication. Duplication is the root of all evil. Because of duplication, my users had the experience of 10 million Makefiles (all self-contained) none of which worked very well. I started trying to explain why things were so bad, but I don't think I was very successful; it sounded more like I was trying to make excuses, which you never want to be doing. Now I'm going for the other side of the trade-off. I want things to be self-contained with minimal duplication, but this means there's going to be less variety. We'll figure the variety out later.

Tradeoff: To save time, the toolchain did all sorts of fancy things like cutting down the metagrammar to just the pieces that we want to recompile. But these fancy things create complexity and a maintenance hassle. Things break because of it. You can't win. Either you have something fast and ugly or you have something slow and nice. Hrmph. Getting grumpy.

installing stuff

I'm squatting a desk with Ubuntu Jaunty. Installing the Haskell Platform on it is no walk in the park sadly. It's super easy on Windows (I believe) and on MacOS X, but on Ubuntu you have to:

• install GHC binary
• install OpenGL stuff (libglu-dev, I think)
• install editline (libedit-dev, I think)
• patch the installer because of bug #84
• and finally install the platform

I'll still require the platform. It's just easier in the long run, when that beautiful future arrives where HP is available on your favourite distribution. We're getting closer and closer. Haskell with batteries included.

off to France! (for a month)

It will be good to do some legitimate GenI hacking for a change.

I'd better make the most of it. I'm a bit anxious that I won't deliver the goods.

unification bug

I just discovered/fixed this bug in a fit of insomnia-based hacking. My unit tests need to be extended accordingly. Should probably send a small advisory to the mailing list:

Basically the question is what happens when you unify [?1, ?2, ?3] with [?2,?3,X].

module Main (main) where

import NLP.GenI.Btypes

main =
 do print $ head $ unify left right
    print $ head $ unify right left
 where
  left  = map (GVar . show) [1..3]
  right = drop 1 left ++ [GConst ["X"]]

Output

([?1,?1,X],fromList [("1",X),("2",X),("3",X)])
([?2,?3,X],fromList [("1",X),("2",X),("3",X)])

What's wrong with that? First, unification should be symmetrical. Second, we should be retroactively propagating results.

Should be

([X,X,X],fromList [("1",X),("2",X),("3",X)])
([X,X,X],fromList [("1",X),("2",X),("3",X)])

I realise I ought to be treating unification bugs more seriously than this, but I don't think this is a big deal in practice. The fix was fairly simple: just rerun replace after unification (which is what the code tends to do in practice anyway, just not on the low level). I'll bet the bug is my fault. Will have to dig up and study some 2004 code, hopefully with the old unification still intact. But stuff like this is why I want an abstraction over unification (eg. Prolog).

Think I need to look into my tests also, maybe try SmallCheck out.

GenI unification

These thoughts should probably go on the bug-tracker somewhere. Probably weekend relaxation hacking or more likely September work. Anyway, I was thinking this morning before getting out of bed that there could be some ways to make the unification stuff in GenI cheaper.

Reductionist performance tester

Too much of GenI performance hacking is done by trial and error. One of the reasons is that GenI is a complex piece of software (for me anyway); many things going on and interacting, so it's not always clear how to boil things down in chunks. This doesn't mean the chunks/units aren't there, just that I need to get better at recognising them. I want to move more in the direction of studying individual bits of GenI without all the intervening junk. For example, I ought to have a performance tester that lets me do unification on two GeniVal lists with (say) a 1000 unique variables each. How much does that cost? Once I figure out how to make such a list (ie. what elements to populate it with), I can start experimenting with some other ideas.

Just in time substitution - Avoid repeated replacement traversals

I suspect this is making unification very expensive. You unify two GeniVal, and whatever variable substitutions come out of them, you need to propagate throughout any structure that may contain said GeniVal. And these are complex structures: chart items (a) which contain lists (b) of nodes (c) which contain feature structures (d) which consist of attribute-value pairs (e) where the values are (f) the GeniVal we're looking for.

Incidentally is why for my Haskell 2006 paper, I was so happy to have type classes; they do a really great job of capturing this idea of "all these different things have something in common". After getting some advice from Neil, I'll be using these type classes in a more generic way (half the code!) and when Uniplate affords the performance I need, just switching to that altogether. Attending Your Favourite Language User Groups meetings is a good idea. If I hadn't been to that LondonHUG talk, "find out what generic programming is" would have been stuck on my list forever.

Anyway: one thing I was thinking is that what ends up happening is that I am doing a lot of traversal. Because I do a lot of unification, I end up building up a lot of "replace X with Y on structure A", followed by "replace Y with Z on structure A"... Unless I misunderstand the fusion/deforestation stuff (which is very likely), these can't be detected on compile-time [because it's replace; do something else; replace] so aren't going to be magically smooshed down into "replace X with Y then Y with Z on structure A"

So instead I need to explore an idea of just in time replacement. In a sense, I already do this by hand. When I have to adjoin two TAG trees for example, and I do feature structure unification on the adjunction site top feature, I only propagate the variables to the foot and adjunction site bottom because I'm going to unify them. I don't waste my time propagating them throughout the whole tree. Of course, I'm going to have to have to propagate them sometime just not right now. Not until I've had a chance to coalesce my replacements (X with Y, Y with Z becomes X with Z, Y still with Z). I want to generalise this idea somehow and make it automatic.

unifyPending

First I want to replace my unify :: [GeniVal] -> [GeniVal] -> Maybe ([GeniVal], Subst) with some sort of unifyPending :: Subst -> [GeniVal] -> GeniVal -> Maybe ([GeniVal],Subst) function. The difference between these two functions is that whereas unify applies substitutions on the future elements of the list as soon as it gets them, unifyPending will instead build up a list of pending substitutions and only apply them as it visits the next item. The crucial difference here is that this affords us the chance to coalesce transitive substitutions (X directly Z). See what I mean? Anyway, the reason why I want to have unifyPending is so that I can generalise to unification within a larger structure

pending substitutions in chart item

Perhaps the chart items need to keep track of the pending substitutions so that we can do the unifyPending trick across chart generation steps.

Unification monad transformer

It's been a couple years now that I've been wanting some sort of unification monad. The problem with unification and my hand-written-just-in-time stuff is that it's very error prone. It's far too easy to perform a unification and then forget to propagate the variable substitutions onto other parts of your structure. And that's silly. We're Haskellers; and Haskellers don't expose themselves to making silly mistakes that could be easily be caught by a computer on compile-time.

In this case, we don't even want to catch the mistake; we just want to rearrange the universe so that mistake isn't even possible in the first place. So yeah, I keep thinking that the pending substitutions should be stored in something like the state transformer monad and that I should supply a unification function within the unification monad, one that applies the pending substitution on the next unification. You want a transformer because you need another monad to capture the idea of failure (Maybe if you just want to know the answer, Either String if you also want to know why you couldn't get an answer).

If I do things right, the unification monad will not only keep my code clean and less error-prone, but also give me just-in-time substitutions for free.

Conclusion

So I don't know if any of this will actually work or if I'm just rambling incoherently. But perhaps one day when I have some GenI time, I can explore this better.

That's the problem with working on stuff. You spend 4 years where you're supposed to do stuff, but you're not able to because you just haven't absorbed enough stuff yet, not enough Haskell, not enough GenI , not enough generation, not enough chart parsing, not enough breadth/depth, your head spins with all the things you don't have a clue about. Now 4 years later, your head hasn't stopped spinning but at least you have a somewhat better idea about Haskell and about GenI and you still want certain things done (particularly, getting to the bottom of this performance stuff)... just that you're not supposed to anymore. Argh! :-)

I guess none of this GenI-hacking counts as really researchy either. Well too bad. It needs doing and if I do it right, then other people can do researchy things with it... which is about the best I can hope for.

See you in September.

the na "phase" - slight dissapointment

So, I was pretty excited about the new intermediate null-adjunction phase I was going to add to GenI because I could see in my mind's eye how this would cut down on a lot of work for the surface realiser.

I did manage to implement this (along with a GUI refactor and a tweak to have the debugger status bar tell you what generation phase it was). I didn't use a separate chart generation phase at the end of the day. Instead what I had a simple filter that gets applied during the switch from the Substitution to the Adjunction one. It appears to work, although I'll still need to hack on it some more so that it propagates info to the GUI and also so that you can tick a box to disable/enable the optimisation at will.

The results aren't all that great. There does appear to be a bit of an improvement
Here's two heap profiles, one using the plain old algorithm (smaller example):
And using the improved algorithm:

On the other hand, things look a bit better on a somewhat larger example. Here's with the old algorithm:
We manage to save about 5 MB of max heap usage with the new algorithm:
Hope not entirely lost yet. Perhaps the effect is more pronounced with bigger auxiliary trees and with more adjunctions (ambiguity?). I'll still need to add the GUI code so that I can see what this thing is actually doing (I make the graphical debugger for me not my users; I wouldn't be able to get a feel for GenI without stepping through that and studying the trees).

Or maybe somehow this optimisation is pointless because blah-blah handwave Haskell laziness gesticulate wildly. I do wish I had a better idea on how to write good fast Haskell software. Slowly learning things. It's interesting to look at these heap profiles. It's like there's three phases: substitution, adjunction and then what? Printing out the results? Is that what that spike is, as all the accumulated work from adjunction/substitution actually has to be performed? What's the effect of this optimisation? It looks like we're forced to pay a lot of the substitution costs up front instead of at the very end. But where?

That's one of the reasons why I've been obsessively working on this lately. Like the ugly unification code, my persistent inability to understand what makes GenI tick (performance wise) just gets under my skin. I HAVE to know why it's slow. Maybe I'll never be able to make GenI faster, but I just hate the uncertainty. Is it supposed to be like this? Probably not. 50% of time spent doing garbage collection can't be good.

Anyway, I guess I'd better put GenI away and start doing some real work over the week. I've just been a bit performance-obsessed lately. I bet we can do better than this.

GenI hacking - unification refactor

Oh, this feels good. This scratches an itch. I've been pretty embarrassed about the state of GenI's unification code for a long time. The new code does the same thing, and while it may not exactly be something to be proud of, I reckon that it's got about 64% less Suck.

We should play "spot the difference" in the comments:

Eric thinks this code sucks less for 5 reasons. What are they?
I'll note that the only reason I have been able to reduce the Suck in this code comes from my participation in open source projects. I may still be a crap programmer, but imagine how much worse the situation could be if I wasn't osmosing all those ideas by reading other people's code. If you want to code better, you have to watch how other people do it. I don't think I can recommend this enough if you have to code on the job. If your job does not already involve a lot of hacking with people who are way better at it than you are, then you absolutely have to join an open source project.

the new code

unify :: Monad m => [GeniVal] -> [GeniVal] -> m ([GeniVal], Subst)
unify [] l2 = return (l2, Map.empty)
unify l1 [] = return (l1, Map.empty)
unify (h1:t1) (h2:t2) =
case unifyOne h1 h2 of
Failure -> fail $ "unification failure between " ++ show h1 ++ " and " ++ show h2
SuccessRep v g -> prepend `liftM` unify t1b t2b
                 where
                  s   = (v,g)
                  t1b = replaceOne s t1
                  t2b = replaceOne s t2
                  prepend = (g:) *** prependToSubst s
SuccessSans g  ->  first (g:) `liftM` unify t1 t2

data UnificationResult = SuccessSans GeniVal
                    | SuccessRep  String GeniVal
                    | Failure

unifyOne :: GeniVal -> GeniVal -> UnificationResult
unifyOne g GAnon = SuccessSans g
unifyOne GAnon g = SuccessSans g
unifyOne (GVar v) gc@(GConst _) = SuccessRep v gc
unifyOne gc@(GConst _) (GVar v) = SuccessRep v gc
unifyOne (GConst v1) (GConst v2) =
case v1 `intersect` v2 of
 []   -> Failure
 newV -> SuccessSans (GConst newV)
unifyOne x1@(GVar v1) (GVar v2) =
if v1 == v2
  then SuccessSans x1
  else SuccessRep  v2  x1

the old high-suckage code

unify (h1:t1) (h2:t2) | h1 == h2 = unifySansRep h1 t1 t2
unify (GAnon:t1) (h2:t2) = unifySansRep h2 t1 t2
unify (h1:t1) (GAnon:t2) = unifySansRep h1 t1 t2
unify (h1@(GVar _):t1) (h2:t2) = unifyWithRep h1 h2 t1 t2
unify (h1:t1) (h2@(GVar _):t2) = unifyWithRep h2 h1 t1 t2
 -- special cases for efficiency only
 unify ((GConst [_]):_) ((GConst [_]):_) =
 fail "unification failure"
 -- end special efficiency-only cases
unify ((GConst h1v):t1) ((GConst h2v):t2) =
 case h1v `intersect` h2v of
 []   -> fail "unification failure"
 newH -> unifySansRep (GConst newH) t1 t2

{-# INLINE unifySansRep #-}
unifySansRep :: (Monad m) => GeniVal -> [GeniVal] -> [GeniVal] -> m ([GeniVal], Subst)
unifySansRep x2 t1 t2 =
 do (res,subst) <- unify t1 t2    
    return (x2:res, subst) 

{-# INLINE unifyWithRep #-}
unifyWithRep :: (Monad m) =>  GeniVal ->  GeniVal -> [GeniVal] -> [GeniVal] -> m ([GeniVal], Subst) unifyWithRep (GVar h1) x2 t1 t2 =  let s = (h1,x2)      t1_ = replaceOne s t1      t2_ = replaceOne s t2      ustep = unify t1_ t2_  in s `seq` t1_ `seq` t2_ `seq` ustep `seq`     (ustep >> = \(res,subst) -> return (x2:res, prependToSubst s subst))
unifyWithRep _ _ _ _ = geniBug "unification error"