sematiser

I was a bad bad boy, yesterday. Stayed at home because I had some ideas for one of my side projects and hacked till 4 in the morning.

So I guess, that puts me at a three and a half-day weekend. Today was mostly spent improving sematiser. Don't really remember why. Just sort of felt like it. I really hope this is what 'work' is like after the PhD... doing stuff because you feel like it.

Writing it in Perl is a pain. There's times I'm tempted to rewrite the whole thing in Haskell. Mind you, it's not a language chauvanism thing or what have you, it's just that one of the tasks that sematiser has is parsing the lexConverter's .lex format. Today, I discovered that one of the bugs was due to me not ignoring comments, so I had to throw in this little piece of stackly code before my chomp()

$in_comment++ if (s/(.*)\/\*/$1/);
$in_comment-- if ($in_comment > 0 and s/\*\/(.*)/$1/);
next if ($in_comment > 0);

If I had Parsec -- hell, I could use Yannick's lexConverter Parsec code -- I wouldn't have to deal with crap like this. But then again, I don't know. Today, I kinda had fun playing around in Perl. Kinda of refreshing to take a break, to just do things the messy, ugly, horrible unsafe way. Not useful, but sorta amusing at times, assuming you don't get ticked off dealing with stupid runtime errors that your compiler should have picked up.

Besides that, Claire had noticed that the sematiser would printing out lots of blank entries when dealing with questions. It was because I had my regular expressions wrong when feeding stuff to tree-tagger. I wasn't dealing with question marks or exclamation points. Simple fix:

sed -e 's/[^\.\?!] *$/ ./' -e 's/\$/ /' |\ 
 tree-tagger-french -o "-eos-tag eos -token -lemma"

Other than that, I've been trying to plug holes in sematiser's Tree-Tagger to TSNLP lexicon mapping. Had to tell it for example, that "en and "y" with category "PRO:PER" are what TSNLP calls "cl" (clitics).

Had an idea that maybe we should use the semantic macros as a way to control sematiser's semantic output. Claire doesn't think it will be too useful because basicProperty macro is used, like, all over the place... but I dunno. I think it might pay off. Only hacking will tell.

sudden burst of optimism

Suddenly, I had the impression that things weren't going so bad after. Two minor discoveries today, firstly, that the GHC profiler isn't all that hard to use after all. The trick is not to drown yourself in information. Add your cost centres by hand, using {- #SCC "the name you want to give" -} and add them a few at a time until you get a better picture of how cost is divided among the various functions of your program. One thing I'm not entirely sure about though is how things are divvied up exactly. For example, if you have

foo 25%
 bar 10%

Does that mean bar takes 10% of the entire program, or just of that call to foo? Does the 25% mean everything in foo and under or just the CAF's in foo sans anything else that is profiled? Will have to scrutinise the doc. I'm sure one of these makes more sense than the other, and that it should be blindingly obvious, but I don't see it right now.

The other minor discovery is that Makefiles really rock. Ok, not a discovery, really, but something that I'm beginning to realise more and more as time goes on. How do you go about running the profiler on real data? Simple. Just add a little bit of intelligence to the makefile for the grammar (not GenI, but TSNLP):

ifndef PROFILE
GENI:=xmgGeni
else
# performance profiling
GENI:=debugger-geni --xmgtools
EXTRA_GENI_FLAGS+=+RTS -prof -RTS
endif

Now, the user can reuse all the targets from before, and add PROFILE=1 to run the profiling version of GenI instead of the basic one, for example, instead of calling make run TESTCASE=t123, the user calls make run TESTCASE=t123 PROFILE=1 Point being that there are many more uses for Makefiles than just compiling software. A good Makefile can go a really long way.

Had an argument about testing today. I was basically supporting the platform that more tests are better, and automated tests are an important means of making exhaustive testing practical. Yannick was arguing that what was more important was testing intelligently, and that manual tests were more important because they were more rigourous and deep (or at least, I think that's what you were saying, Y). We eventually agreed that part of the debate was a confusion between functional testing and unit testing, where Y thought I was trying to sell automated functional testing as opposed to manual unit testing whereas what I was really trying to say is that all tests should be automated whenever pratical. So yes, unit tests are very important, but they need to be automated or you won't run them enough.

And worked a bit on CKY. Using manual testing ;-) with the visual debugger, I've discovered a bug in my application of adjunction (well, that was yesterday). Improved my representation of chart items so that I could more easily figure out what the heck was going on. Merged my automata in the chart. Arrgh. Not enough time.

automata and profiling

No cky work today! Implemented multiple root categories for use by polarity automata. Tweaked the gui code, moving the root category stuff into basic configuration (because of last nights' modication where now you only return stuff if its root category matches). Did I accomplish much more than this? Hmm... doesn't look good.

Remember discussing a bit with Yannick a couple of minor XMG bugs he was trying to squash -- which he did end up squashing.

Met with Claire and Carlos to talk about profiling. I was arguing that putting timing points into the code was not going to work, because of laziness, and that we shouldn't fight the laziness just so that we could time stuff. We eventually came to the conclusion that

1. we should add more counters to GenI for non-timing stuff
2. we should learn how to make better use of the cost centres and the haskell profiling tools, rather than trying to use getCPUTime
3. looking into space profiling via counters would be cool

Carlos has a nice method for counters. He created a special StateCounter monad, which I guess is a slightly transformed State monad with some setters and getters for counters. Much 'cleaner' than my approach of just dumping everything inside my state ticket. I like. We'll be looking into this tomorrow. That's when you start really having fun with Haskell, when you realise that you can make your own monads, and that they can be insanely useful.

Rest of the evening, I was working on Folli stuff with Dmitry, now that the wiki is online.

cky and simple

Alright, so I've finally got that derivation tree selector sorted out. That took way longer than neccesary, but now it's done... and it's already proved to be useful!



Just noticed that my adjunction operation was not demanding that the auxiliary tree be closed, that is, that it be completely done with adjunction. This is creating a lot of redundant items. Same reasoning as the foot node constraint: you can close off this possibility, because you know that the generator could always try creating the items in a different order.

Added a new feature upon a suggestion from Claire: due to automatic detection of polarities, the generator was implicitly filtering the results on one root category. That is, in order to make the automata work, you had to define one category, say 'S' for sentence as being the root. This category would start off with a -1 polarity so as to cancel the +1 polarity from root nodes. Problem is that if you do this, any results with that don't have the expected root category get filtered away. Claire suggests that we embrace this behaviour, and for consistency's sake, extend it to the generator when it's not using polarities! This feels like i'm deliberately breaking the generator, but it does make sense, I guess. Make sure you're always comparing the same thing. Maybe with lazy evaluation, this would also speed up the non-polarity version of GenI. It just stops at the root category check.

One thing I would like to do is extend the automaton code so that you can specify multiple root categories. It seems simple enough. Just a matter of extending the seed automaton with a disjunction on each one of the root categories.

Spent a good chunk of the day tech supporting a friend for emacs installation on windows and making gsearch work on a penn treebank tagged corpus.

Otherwise, now working on the widgety part of the user interface. Trying to make derivation tree selector. At first I got confused about my own code and made things nasty and complicated - had to return functions which would be called by other code... big big mess. But then I realised I had made a mistake, a false assumption about how my own stuff worked and re-implemented the thing in a much easier way. Don't know why I was making so little progress today. A few interruptions here and there, maybe.

more cky debugger work

I realise that I had screwed up my representation of derivation trees - or rather, I wasn't making it very useful. Took me a while to figure out what might be a good way to do it, but maybe something like this is a little more useful than what I had on Friday:


Also, Claire stumbled upon a bug that's being hiding in my polarity automaton code since my Masters. When it encountered multi-literal semantic items, my seed automaton builder was leaping way all the way to the end, dumping all the extra literals upon its null transition. Instead, it was only supposed to dump the literal at hand. Very tiny fix for a big bug.

One annoying thing, though, is that the whole thing comes crashing down if I try to visualise the automata. Don't know why exactly. Probably too much stuff in memory, probably running out. Interestingly, I get a bus error when this happens.

Other than that, Dan Flickinger came in today to talk with Jesse. Me and Claire took advantage of the opportunity to chat with him about the syntax-semantics interface for weird stuff like empty semantics and multi-literal semantics well mostly Claire doing the chatting and me trying to follow. I had all of three thoughts that I brought up afterwards

1. while reading the papers, you could actually think of what Kay 97 does, the distinguished index thing, as having the same effect as chunking the input semantics (sort of like what OpenCCG does, but maybe a little more elegant?). I'm still not sure I understand the secret sauce behind Carroll and Oepen 2005's approach, the available index thing. From what they say, it's basically a generalisation of Kay97 to cover more than one open index. But overall, it's a chunking approach, right? I mean, not literally -- OpenCCG is literal chunking -- but something which behaves as if you had chunked the input semantics
2. one dimension with which to characterise the syntax-semantics interface in your grammar design is tightness of coupling between syntax and semantics. The tighter you couple, the more precise your input semantics has to be, and the less paraphrastic power you get. That is, the more control you have over what you want to say. But tight coupling looks like the right way to go. If you wanted paraphrases, you could always have a translation step that went from one loose-coupled semantics to a set of tightly coupled ones.
3. Would subatomic semantics be useful at all? We put stuff directly into our TAG trees, but maybe it could actually be helpful to have some cases where a single predicate selects multiple lexical items that have to go together

cky debugger refactor results

debugger refactor

Refactor of the debugger code is complete. Saved me 15 lines of code, 60 if you subtract the extract comments that I wrote. Needless to say, it's not just a matter of reducing lines of code, but increasing maintainability. For example, if I wanted to implement a third algorithm for GenI (like Earley), making a graphical debugger for it is easier than before. Or if one day I decide to improve the debugger, I only have to improve it in one place. Plus I no longer feel that nagging discomfort you get when you see two pieces of code that do almost exactly the same thing, it just screams at you "factor me! factor me!" and you keep yelling back "not now! not now!" until you finally give in, and everything is ok again.

cky derivations

I had to struggle a little bit to figure out how to extract the derivation information from the CKY chart. One thing is that I gave up on producing TAG derivation trees, and focused instead on making my own stuff (which will likely end up just being more or less a derived tree). Here's the data structure for a chart operation. Each item should normally be associated with one of these, but since there are equivalence classes and item merging, we use a list

data ChartOperation = SubstOp    ChartId  ChartId 
                    | AdjOp      ChartId  ChartId
                    | NullAdjOp  ChartId
                    | KidsToParentOp [ChartId]

Extracting the derivations is a bit of a pain, but made some simpler with the help of the List monad. This is the first time I've found a use for the List monad. I think the code is clearer than the non-monadic version would be (the non-monadic version would have made liberal use of concatMap). I'm really glad I finally figured out the essential bits of how monads work. It's a useful abstraction with many applications outside of IO, (the Parsec state monad, the Maybe monad, the List monad, etc). At first, I had thought that the Maybe and List monads were just sort of useless academic examples, but no, they actually have a purpose

extractDerivations :: BuilderStatus -> ChartItem -> [ Tree (ChartId, String) ]
extractDerivations st item =
 do chartOp <- ciDerivation item
    case chartOp of 
     KidsToParentOp kids -> 
       do kidTrees <- mapM treeFor kids 
          createNode "kids" kidTrees
     SubstOp act psv ->
       do actTree <- treeFor act
          psvTree <- treeFor psv 
          createNode "subst" [actTree, psvTree]
     -- there are three more rules here that i cut out
 where 
   createNode op kids = 
     return $ Node (ciId item, op) kids
   treeFor id =
     case findId st id of
       Nothing -> geniBug "error message cut out"
       Just x  -> extractDerivations st x

Here's what the result looks like:



See, it's a pain when you've got lots of derivations. That's why I extended the CKY debugger GUI. Next week I'll work on making it possible to select from a list of derivations.

new dispatch method

While playing around with my debugger, I discovered that the generator was not setting ids on my new items. That was because dispatch filter mechanism was all wrong; if the filter doesn't catch anything, sometimes it tries to modify the item for the next filter, but the way i had it set up, this next item was always being forgotten. Here is my revised version of the filtering mechanism. It has the extra bonus of being simpler than the last one. The only counter-intuitive thing about it is that each filter returns 'Nothing' if it suceeds, or 'Just newItem' when it fails:

dispatchNew :: ChartItem -> BState () 
dispatchNew item = 
 do let tryFilter Nothing _        = return Nothing
        tryFilter (Just newItem) f = f newItem
    -- keep trying dispatch filters until one of them suceeds
    foldM tryFilter (Just item) [ dispatchTbFailure
                                , dispatchRedundant
                                , dispatchResults
                                , dispatchToAgenda ]
    return ()

I'm starting to wonder though, if this is something I can use State transformers for. I don't really understand state transformers yet... I dunno... I guess it doesn't really matter. It'd save me, like three lines of code. (Then again, transformers are probably useful enough to be worth learning about - combinining monads in an elegant way is a handy skill).

cky - debugger

Spent today working on the graphical debugger. Tidied up the code and start trying to factor things out so that I didn't have any redundant debugger code. Main thrust is making the whole thing more modular and easier to extend. Hope I'm not making things too complicated though. There are some refactors which are beautiful, which not only reduce the amount of code you have, but make it more readable. And there are others which reduce the amount the code, but increase the complexity, which make it harder to understand. This seems to be the latter kind.

So why am I doing all this? I realised that in order to make any sense out of my chart items, I need to be able to inspect their derivations - where they come from. But then I realised that this would clutter the graphical output, especially considering that with a packed forest, you could actually represent a whole set of derivations. What I wanted to have is a little gui selector that lets you choose which derivation of the chart item you want to visualise (or maybe the whole forest), as well as what portions of the chart item you want to show (tree, string, derivations).

I guess I don't really have to refactor the code to do this, but what I figure is that, if I can, why not? It'll make things easier to maintain in the long run. And it might clarify questions about exactly how modular we want to make GenI.

cky result recognition

Started the day late (was hobby-hacking till 3 last night).

Was working on gtester a little bit, trying to finesse the latex output. Well, I guess that was mostly what I was doing. 8 patches. Had to fight a little bit with Python to print a stupid summary out. Not Python's fault. I was still thinking in Haskell, trying to reduce (fold) a list that I could have been manipulating with a for loop. Don't get it though. My fold should have worked.

Oh yeah, I recall helping Claire and Yannick to set up a new branch of the TSNLP semantics repository. Sort of illustrates what I was saying about darcs yesterday -- yes, sometimes it hurts because things go wrong, yes sometimes it hurts because there is no notion of subrepository, but despite the pain, darcs also pays off in very big ways.

Easy branching is an example. Being able to rename all our repositories on the fly is another. Being able to flip back and forth between repositories is a third (Yannick and Seb will push to a repository they share among themselves, but occasionally they will also pull patches from Claire). In the old days people would have either had to edit all their CVS/ directories (which sucks the minute you have subdirectories), or just delete everything and start over. Now, people just pull from a different location. (Although yes, I will note here that Subversion branching is pretty easy also. Not as elegant, but definitely better than CVS, goes the reputation). That's really all I'm saying. Darcs is painful, but overall it is less painful than what we've had to live with in the past and I really hope that it will become even less painful down the years.

(BTW, got a response from David Roundy himself on our bug tracker entry! Ooh là là.)

Spent the rest of the day, rest of the evening hacking on CKY. Implementing results detection was not hard at all. Don't know why I was being such a putz by putting it off :

dispatchResults item = 
 do st <- get
    let synComplete = ciInit item && ciRoot item 
        semComplete = tsemVector st == ciSemantics item 
        -- join the two automata together - no more holes!
        itemJoined  = item { ciAut_befHole = joinAutomata bef aft
                           , ciAut_aftHole = emptySentenceAut }
         where bef = ciAut_befHole item
               aft = ciAut_aftHole item
        --
    if (synComplete && semComplete ) 
       then addToResults itemJoined >> return True
       else return False

I've also found some simplifications to the automaton code. Still works the same way, but feels a little better, a little less muddy. Now using integers to represent the automaton states, and using an increment operation instead of renaming the states. Computationally the same, I guess. One thing I did to make things a little nicer is to expand my data structure so that the user can define the final state either via a list of states, or via a function. Before, the user was forced to define it via a function, and that makes things a bit ugly in some cases.

Right, so how's it all going after all? Well, now the generate outputs results for "Vincent runs". For my other regression tests like "le méchant chat noir chasse la souris". Zilch. Lots of debugging output, but no cats chasing mice. Lots of work to be done. Not to mention that I'm still not merging my equivalence classes correctly.

Oh yeah, and a completely random note. Claire asked me if my CKY work was documented anywhere. I said I was planning to massage my code into literate haskell (I still believe in literate programming, though I've got lots to learn on how to do it effectively). I should have mentioned this blog, though. :-)

eval trouble

Didn't get much of a chance to work on CKY today. Mostly fixing some bugs in the evaluation stuff now that Claire has a chance to take a look, makefile hacking kind of deal.

gui

Spent some time hacking on the graphical code after Claire mentioned she prefered the aesthetics of Yannick's ViewTAG module. ;-). But the way I figure is that when people complain about aesthetics, they are sometimes unknowingly (?) complaining about usability. For instance, the main modification was adding a light yellow background to the feature structures. Why? Because it makes them stand out from the white - makes them easier to see. Simple things. Other thing was to adopt XMG display convention for certain node markers (! for substitution, # for null-adjunction), and finally to fix an interface-display bug. Output's a little more readable now, eh? Basically a copy of whatever XMG seems to be doing right:

weird problems

Struggling with a random bus error in GenI. Sigh. Not predictable, doesn't always happen on the same example. Not the slightest clue what I can do about this. Usually this kind of thing is indicative of a bug, but on a very very low level, pointers and stuff, things I'm normally not manipulating directly in Haskell. Annoys the heck out me. Errors always look something like this, except sometimes you get a a different error code, like 33792 and it always happens in a different location
Error executing '("/Volumes/Data/Users/kow/synch/phd/gtester/bin/geni" "--xmgtools" "--nogui" -m "tsnlp/grammar/valuation-sem.rec" -l "tsnlp/lexicon/lemmas.glex" -s "/Volumes/Data/Users/kow/synch/phd/gtester/scratch-tsnlp.N5L0mp/tests/batch-1/t70/semantics") > /Volumes/Data/Users/kow/synch/phd/gtester/scratch-tsnlp.N5L0mp/tests/batch-1/t70/responses': 35328

darcs trouble

Some darcs trouble on the TSNLP-semantics repository, which is pretty disturbing because it's on the push depot! Filed a bug report. No comments from the #darcs channel. Could be a weird case of the Unison thing. Maybe Claire managed to push something inconsistent onto the repository. A good methodology when things go wrong is to immediately cp -R the corrupted repository so that you and the #darcs people can do forensics on it. Took me two hours to investigate what went wrong and to make everything work again. Good thing there is stuff like darcs repair and darcs check.

I know, I know. This is the fourth time on this blog that I've mentioned having problems with darcs. Sigh. Darcs is really great stuff. Its simplicity and flexibility (atomic commits, cherry picking, decentralisation, trivial branching, undo) have really freed me as a developer. I'm always working on two or three things at a time -- for example, hacking on CKY and fixing GenI bugs for TSNLP evaluation, whilst trying to add colours to graphviz -- and using a patch model allows me to do this without worrying about things going horribly wrong. Darcs makes life for the busy hacker simpler and safer... when it's working, at least. When it's not working... oh boy! But this is the way things go with new software.

Well, it's like I said. I know I'm taking a risk, and occasionally, I lose one or two hours because things go wrong. But so far, the gain in productivity, the gain in overall safety (because my repositories are easy to duplicate) has so far outweighed the losses. I can still count the number of times things went wrong on both hands. And besides, I have shot myself in the foot enough times with CVS before, so it's not like things don't go wrong the old way either. So I take a deep breath. And thank the fact that the thing is decentralised and so much easier to backup. And continue using darcs until either the losses start to catch up to the immense gain, or until something better comes along.

cky automata

Fixed my bugs on the CKY automata business. Realised that I needed to make sure that only the item on hand was being used in the kidsToParents rule and not any of its doppelgangers. I implemented this by recognising the left and right sisters seperately in the routing map:

allMatches = leftMatches ++ ([item] : rightMatches)

Another problem was that my automaton code was not making any bridges between the stuff it was joining together. So that took a little bit of hacking. I'm growing increasingly unhappy about the way I'm doing this automata business... there must be a smarter, more elegant way to code this up. Look at this crap:

joinAutomata :: SentenceAut -> SentenceAut -> SentenceAut
joinAutomata rawAut1 rawAut2 | states rawAut1 == states emptySentenceAut = rawAut2
joinAutomata rawAut1 rawAut2 | states rawAut2 == states emptySentenceAut = rawAut1
joinAutomata rawAut1 rawAut2 =
 let aut1 = renameStates 'L' rawAut1
     aut2 = renameStates 'R' rawAut2 
     -- replace all transitions to aut1's final st by 
     -- transitions to aut2's start state
     t1 = transitions aut1
     t2 = transitions aut2
     maybeBridge s = if (isFinalSt aut1) s then startSt aut2 else s
     newT1 = Map.map (Map.map $ map maybeBridge) t1
     newStates1 = map (\\ (finalSt aut1)) $ states aut1 
     --
 in  aut1 { states      = [ concat $ newStates1 ++ states aut2 ]
          , transitions = Map.union newT1 t2 
          , isFinalSt   = isFinalSt aut2 }

renameStates :: Char -> SentenceAut -> SentenceAut
renameStates prefix aut =
 let -- prefix a state
     addP_s = (prefix :) 
     -- prefix a single transition
     addP_t (k,e) = (addP_s k, Map.map (map addP_s) e) 
 in aut { startSt     = addP_s (startSt aut)
        , states      = map (map addP_s) $ states aut 
        , transitions = Map.fromList $ map addP_t $ 
                        Map.toList   $ transitions aut 
        , isFinalSt   = isFinalSt aut . tail }

Beurk, as the French would say. Oh well. At least it works. One thing I could improve, of course, is to replace my automaton record with a typeclass. This way I can restrict any bizarro hacks like representing the list of states as a list of lists (for building polarity automaton) to the modules that actually use them, and not force the resulting ugliness on the rest of my code. But drop in the bucket. There must be more I can do to make my code suck less.

Or maybe I should just stop bitching. "Vincent runs", after all, so why am I complaining?

automata output in the works

Spent the early afternoon getting graphviz display code working for sentence automata. Pretty painless. So now I'm at last breaking ground on the automaton output code. Hopefully, by next week, we might be seeing some output in GenI CKY edition. Well, maybe that's optimistic. After all, I first thought the whole CKY thing would only take me 2 or 3 weeks, tops. Hah! Here I am, 1000 lines of poorly commented, messy, unit-testless Haskell code later and still nowhere close.

no features

I'm simplifiying the problem a bit, not going to worry about morphology whatsoever (that is, not going to worry about propagating feature structures in the automata labels) because managing the variable replacements is a pain in the butt and seems like it's going to be very expensive. Something to be thought about. À priori, I guess it ain't going to be that hard to implement, something like make an instance of the Replacable typeclass for automata. But oof. Just seems so expensive.

automata woes

My code for combining automata is pretty ugly. I use Strings to identify my states, so when I want to join two automata together, I have to rename everything. Silly eric.

joinAutomata :: SentenceAut -> SentenceAut -> SentenceAut
joinAutomata rawAut1 rawAut2 =
 let aut1 = renameStates 'L' rawAut1
     aut2 = renameStates 'R' rawAut2 
 in aut1 { states      = [ concat $ states aut1 ++ states aut2 ]
         , transitions = Map.union (transitions aut1) (transitions aut2)
         , isFinalSt   = isFinalSt rawAut2 . tail }

renameStates :: Char -> SentenceAut -> SentenceAut
renameStates prefix aut =
 let -- prefix a state
     addP_s = (prefix :) 
     -- prefix a single transition
     addP_t (k,e) = (addP_s k, Map.map (map addP_s) e) 
 in aut { states      = map (map addP_s) $ states aut 
        , transitions = Map.fromList $ map addP_t $ 
                        Map.toList   $ transitions aut }     

You'll note that joinAutomata is incomplete! It will merge the two automata together without making a bridge between them. Anyway, right now, what's bothering me most is that my kidsToParent rule does not seem to be joining my automata together. It doesn't even find which automata it needs to be joining. WTF?

graphviz note

Sigh. I've searched the graphviz mailing lists, and there is no way to make rankdir apply to subgraphs. So, for example, I can't have my trees displayed vertically and my automata horizontally. That sucks. Maybe I should include a toggle in my interface to only display the trees, or only display the automata, or maybe something to change the direction. Why not, eh? Especially, now I've made the paremeterisation thing fancy and configurable... Guess maybe there's a user interface and factorisation issue. Would need to extend graphvizGui so that it accepts an arbitrary button bar so that you can pass in the bit of user interface you want.

more graphvizShow

Meh. Still working on my graphvizShow stuff and it's starting to bore me. Lots of refactoring today. Get a feeling I'm being stupid, not entirely sure I know why I'm doing thing certain ways. Questioning a lot of the utility of my refactors. Seem to be creating lots of pointless abstraction, trying to hide away the graphviz syntax...

gvNode name label params =  
  " " ++ name ++ " " ++ (gvLabelAndParams label params) ++ "\n"

gvEdge from to label params = 
  " " ++ from ++ " -> " ++ to ++ (gvLabelAndParams label params) ++ "\n"

gvLabelAndParams l p = 
  gvParams $ if null l then p else ("label", l) : p

gvParams [] = ""
gvParams p  = "[ " ++ (concat $ intersperse ", " $ map showPair p) ++ " ]"
  where showPair (a,v) = a ++ "=\"" ++ v ++ "\""

Note that this is without the haddock annotation. You should note that the code from yesterday does not compile, but who cares, right?

Refactor mostly motivated by me giving up on having general inferable code for drawing any kind of automata. Same old worry, seems like the developer (me) would want to do this in very different ways depending on what automaton he has. So I decided to factor as much as I could so that the redundant code would be minimally painful. Gmmr. My graphviz output isn't even working. Graphs aren't being displayed quite right. Hate this mental dullness. Head a block of wood. Edit: gotcha. Simple boolean inversion... fixed the bug at least.

Note for tomorrow: this example shows how subgraphs work in graphviz.

Other than that, I did help a friend recover a pdf document from some mail server barfing. So learned a little bit how mime attachements work, how uuencode and uudecode work. Mostly in an empirical fashion, messing around with some files, hacking the output and seeing what happens. Seems kinda silly when you're using an empirical method to learn how something made by another human being, something lasting for I don't how long and very well documented.

graphvizShow

I'm currently refining my GraphvizShow typeclass so that you can use combine subgraphs together into one .dot file. What I'm really aiming for is implementing the automaton bit of Bertrand's CKY algorithm: i.e. get to point where I can spit some output out! But debugging automata sucks if you don't have a nice graphical representation. Now here's the situation: I've got code which takes a TAG tree, and spits out a dot graph. I've also got code that takes a polarity automaton and spits out a dot graph. Here are two problems.

1. As far as I know, there is no clean way in the graphviz format to combine the two graphs together
2. I would like to generalise the polarity automaton code to display any arbitrary automaton in graphviz.

So to attack these problems, I'm augmenting the typeclass with two new functions (graphvizShowAsSubgraph and graphvizLabel) which basically print out the meat of your object, but none of the stuff around it (like "digraph {}", etc)

class GraphvizShow flag b where
  graphvizShow            :: flag -> b -> String
  -- flag -> prefix -> item -> gv output
  graphvizShowAsSubgraph  :: flag -> String -> b -> String 
  graphvizLabel           :: flag -> b -> String

Not being very productive. Been mostly spending my time cleaning up and refactoring my preexisting Graphviz code. Trying to seperate bits out from each other. For example, inside my graphvizShow for TagElem, I used to have a subfunction which walked a tree, printing out the current node, and recursing to the subtrees. Now what I do is this: I have a seperate instance for graphvizShowing a single node. To be precise, the tuple Node and its highlight colour.

instance GraphvizShow (Bool) (GNode, Maybe String)

I then factor out some of the code so that it displays any arbitrary tree, not just TAG trees:

gvShowTree :: (GraphvizShow f n) => f String f (Tree n) -> String
gvShowTree f prefix (Node node l) =
   let showNode = graphvizShowAsSubgraph f prefix n ++ " " ++ prefix
       showKid index kid = 
         graphvizShowAsSubgraph f kidname kid ++ " " 
         ++ prefix ++ " -> " ++ kidname ++ "\n"
         where kidname = label ++ "x" ++ (show index)
   in showNode node ++ (concat $ zipWith showKid [0..] l)

The only problem now is that I've got a Tree GNode to show, but my code only knows how to show Tree (GNode, Maybe String). So what do i do? mapTree

graphvizShowAsSubgraph :: Bool -> String -> TagElem -> String
graphvizShowAsSubgraph sf prefix te =
  gvShowTree sf (prefix ++ "DerivedTree0") $ mapTree info $ ttree te
   where 
   info    n = (n, mcolour n)
   mcolour n = if gnname n `elem` thighlight te 
               then Just "red" else Nothing

One thing that's kind of bugging me though is a possible deficiency in the Haskell type system (or me not knowing how to make best use of it). At first, I was tempted to make gvShowTree as generic instance for GraphvizShow, something like this:

instance (GraphvizShow f n) => GraphvizShow f (Tree n)

This is possible and pretty... but the wisdom of such an instance is somewhat questionable. What if somebody has a tree of Foo, where Foo is an instance of GraphvizShow, but does not want to use the generic instance. He'd be stuck. Does anybody have ideas? For example, say you liked dynamically typed languages. How would you solve the generic re-usable code problem? Any programmers (Haskellers, anyone) reading this blog? Anyone suggest a solution?

What I would really want is some kind of type subsumption where you say, do this type inference only if a more specific type does not already exist. So, for example, if you define an instance like instance GraphvizShow f (Tree Foo) this specific instance overrides the more general instance above. But I suppose an idea like that opens up a whole can of worms.

Maybe it's time to learn about how to make things Derivable. Or maybe there is something I could do with combinators? We've got parser combinators, pickler combinators, so why not Graphviz combinators? Oh well, in any case, what I've got now is good enough for now.

cky: top/bot unification

Got an implementation of top and bottom unification. I didn't feel particularly comfortable about putting it in the non-adjunction rule like Bertrand suggests, nor did I want to make an inference rule out of it. So I coded it as part of the dispatch process.

dispatchNew itemRaw = 
 do case tbUnify itemRaw of
     Nothing   -> addToTrash itemRaw ts_tbUnificationFailure 
     Just item ->
      do let filts = [ removeRedundant, removeResults, dispatchToAgenda ]
             tryFilter True f = return True
             tryFilter _    f = f item
         -- keep trying dispatch filters until one of them suceeds
         foldM tryFilter False filts
         return ()

The dispatch process is implemented as a list of filters that are to be tried in order. I suspect that my code for this is more complicated than it needs to be. Basically the idea is try removeRedundant, then removeResults, then dispatchAgenda, but stop as soon as one of them succeeds. But this is besides the point.

What I added to today is the following process: Before applying the dispatch filters, we first attempt top and bottom unification. If that fails, well, we've got nothing to dispatch. Otherwise, we proceed to the dispatch phases proper. I was tempted to implement this as a dispatch filter itself, but I realised that we needed to keep around the modified chart item in case tb unification succeeds. This wouldn't work with my filters because they only return True/False to indicate sucess/failure. I suppose I could extend the notion of dispatch filter to also modify crap, but that doesn't seem too healthy.

Anyway, here is how top and bottom unification is implemented:

-- the idea is to return Nothing if tbUnification fails
tbUnify :: ChartItem -> Maybe ChartItem
-- things for which tb unification is not relevant
tbUnify item | ciFoot item = return item
tbUnify item | (not.gaconstr.ciNode) item = return item
-- ok, here, we should do tb unification
tbUnify item = 
 do let node = ciNode item
    (newTop, sub1) <- unifyFeat (gup node) (gdown node) 
    -- it's not enough if t/b unification succeeds by itself
    -- we also have to check that these unifications propagate alright
    let origVars = ciOrigVariables item
        treeVars = ciVariables item
        nodeVars = replace sub1 origVars
    (newVars, sub2) <- unify treeVars nodeVars
    return $ item 
      { ciNode = node { gup = newTop, gdown = [] }
      , ciVariables = newVars }

Nothing to it. I'm reusing the notion of collected variables from yesterday. In case top and bottom unification suceeds, we want to know about new values that the variables get so that they can be propagated up in the kidsToParents rule. What I mean is this - we're doing tb unification incrementally, one node at a time, as we produce the node. Now, as a result of top and bottom unification, some variables might get new assignments. For instance, you could conceivably have a node that looks like this:

top:[foo:?X]
bot:[foo:bar]

When that ?X gets assigned bar, we're going to want to remember that fact for the future, when that node interacts with other stuff.

Other than that, not much going on. Fixed the kidsToParents rule to account for unary rules. Think I'm going home now. Very short day, but I've implemented my feature du jour, so, whatever. Oh yeah, before I go, here's the rest of my CKY todo list:

1. equivalence classes (that's the whole freakin' point of this exercise!)
2. Bertrand's automata -- so that we can have output
3. modification of the Graphviz typeclasses so that we can use them to generate subgraphs which can then be combined with bigger graphs (uh maybe)
4. a gui for the 'Generate' button so that you don't have to run the debugger all the time
5. Discussion with Bertrand and probably Carlos to see if my variable collection idea is fundamentally broken or not
6. regression testing suite for all the phenomena
7. performance comparisons with the simple builder

cky: kids to parents unification

Got a new piece of CKY implemented today. My kidsToParents rule now has unification! The basic idea is that you have a rule which says that if you have all the kid nodes, then you should be able to get the parent node as well, as long as everything works out from a unification point of view. Now this problem is sort of a pain in the ass - you're not exactly unifying the kids together nor the kids with the parents. All you want to do is sort of propagate the variable substitutions accumulated by each kid and make sure that they do not clash. This was bothering me all afternoon. How do go about doing this? Don't tell me if you perform propagation on the whole tree each time? Don't tell me you have unify all these instances of the same fricking tree with each other over and over again? So I came up with the following solution. It's probably not new technology, inspired a bit from the stuff I saw in John Carroll's papers and the OpenCCG stuff.

What you do is this: you start out by collecting the list of open variables in each tree. One single pass. Anytime you perform unification on a chart item, you perform propagation on the open variables list. When you want to run the kidsToParents rule, all you have to do is unify the list from each one of the kids (and the parent) and make sure they don't conflict. Here it is in Haskell, using a Maybe monad:

let combine kids = do
          let unifyOnly (x, _) y = unify x y
          newVars <- foldM unifyOnly (ciVariables item,[]) $ 
                     map ciVariables kids  
          let newSubsts = concatMap ciSubsts (item:kids)
              newItem   = item 
               { ciNode      = replace newSubsts p 
               , ciSubsts    = newSubsts
               , ciAdjPoint  = mergePoints kids 
               , ciVariables = fst newVars }
          return $ foldr combineVectors newItem kids

I don't have the slightest clue if it's correct. It just... erm... feels right.

Today, I learned a lesson on the usefulness of obsessive refactoring. Remember that collect typeclass from mid December? Surprise, surprise, here's a brand new use for it that I hadn't expected. So when you want to perform that initial sweep, all you have to do is something like this:

map GVar $ Set.toList $ collect te Set.empty

There is nothing more satisfying than not knowing that you don't have to implement something because you had done it already, but in some totally unrelated context. The same goes for unification. At some point in the summer (?) I had seperated out variable unification into a standalone operation, that is just unify a list variables. Feature structure unification is then just a function which wraps some normalisation code around this unification. This turned out to be useful also for the unifications we perform upon lexical selection, and now, it is doubly useful for kidsToParents propagation. But maybe that was just luck. Anyway... man if only everyday was like this. A feature a day :-)

(Oh and, I am more and more happy about my decision to implement the GUI earlier rather than later. What a nightmare debugging would have been without it)

cky graphical debugger

So it looks like after a little debugging, the adjunction code is working. I can't really tell. Ought to write some tests at some point, but we're still at the stage where we can't produce any output, just a trace of events, so it's kinda hard to write anything beyond simple unit tests. Although *sigh*... I ought to be writing unit tests and QuickChecks to keep myself sane, but here I am not following my own advice. Unit testing, QuickCheck and automated functional regression tests are your friends!

Recently had a priority shift. Realised that it's not very comfortable to debug the thing using the trace of events thing. So I started putting together the gui for CKY. Sort of a test of my fancy new flexible architecture. And the verdict?



Big relief! Only took an afternoon of hacking instead of the ages I was fearing. I guess it's not that much of an achievement. Basically some copy and paste. One thing I can say, though, is that Haskell's typeclass mechanism has been a huge help here in reducing the amount of crap you need to copy. Using typeclasses, you can say stuff like

graphvizGui :: (GraphvizShow f d) => (Window a) -> [d] -> IO ()

A bit simplified. But the story goes something like this: given a list of objects d (where d is an instance of the GraphvizShow class), the graphviz gui displays these objects. See? I don't need to write a graphvizGui for every kind of object I define: automata, tag trees, chart items. Just reuse the generic code and say thank-you to the powerful type system. Yay!

(I wonder why it's all purple, my screenshot) Or actually hmmm... I wonder. I'm claiming that all this code reuse comes from type classes, but wonder exactly how true this claim is. Am i just spouting bullshit? Showing proof of lack of imagination? Hitting every imaginary nail with my typeclass hammer?

working on boring stuff

Meh, just tweaking the behaviour of the evaluation scripts today. Got gtester to produce somewhat nicer latex output (tables that don't overrun the page) and to not be pointlessly verbose.

Cobbled together a mechanism for grammar cutting on an entire test suite as opposed to just a test case. It's a pretty stupid solution - to concatenate all the test cases together, sort the predicates and uniq them so that GenI doesn't do needless lexical selection and run the whole process as usual. Tis a hack. Maybe a cleaner solution would be to build a subset of the geni code that does grammar cutting; it'd have a bit of lexical selection, wouldn't try to do any subsumption checking or propagation of values, but I don't think I care enough to go for that. So my mechanism consists of a few shell commands in the makefile plus a bit of inline perl.

Stole a Makefile silencer mechanism from Sébastien. Not exactly the same approach, but many ideas in common

ECHO_STATUS:=@echo "[TSNLP Makefile]"
ifndef VERBOSE
SILENTLY:=@
endif

The idea being that I can have a huge ugly block of Makefile and it would only print a small summary of what it was doing, unless VERBOSE was set, in which case, it'd just tell you everything:

 $(ECHO_STATUS) grammar-cutting for entire suite $(SUITE)
 $(SILENTLY) rm -rf $(TMP_DIR)
 $(SILENTLY) mkdir -p $(TMP_DIR)/cases
 $(SILENTLY) geniExtractCases $(GENISUITE_DIR)/$(SUITE).semsuite $(TMP_DIR)/cases
 $(SILENTLY) perl -e 'while(<>) { s/semantics:\[//; s/\]//; s/\) */\)\n/g; printf }' `find $(TMP_DIR)/cases -name 'semantics'` >> $(TMP_DIR)/sembits
 $(SILENTLY) echo "semantics:[" > $(TMP_DIR)/megasem
 $(SILENTLY) sort $(TMP_DIR)/sembits | uniq >> $(TMP_DIR)/megasem
 $(SILENTLY) echo "]" >> $(TMP_DIR)/megasem
 $(SILENTLY) $(GENI) --nogui -m $(GRAMMAR_DIR)/$(GRAMMAR).rec -l $(LEXICON_DIR)/$(FULL_LEXICON).glex -s $(TMP_DIR)/megasem --selectcmd=runXMGfilter 
 $(SILENTLY) cd $(GRAMMAR_DIR); mv $(FILTERED_GRAMMAR_TMP).mg $(FILTERED_GRAMMAR_FOR_SUITE).mg

And, oh, I attended a meeting for all of the PhD students in the lab. One tidbit I learned -- the official answer anyway -- is that in France, the law says that all theses have to be done in French (except for the co-tutelle ones, which are governed by what you sign). But the way my lab applies this law, trying to follow the spirit and more or less the letter of the law, is to require a 30 page self-contained mini-thesis. It has to be able to stand on its own, these thirty pages. But after said 30 pages, you could have a technical annex in English, which would contain the bulk of your thesis. Guess it wouldn't be so bad. Write my thesis in English, write a complete thing and then write a summary in French with cf references to the original thesis?

slowly making progress

Got both a passive and an active adjunction rule working now. Err... coded up anyway. They don't seem to be firing, for some reason. Also got my semantics into bit vector representation. Should have done it long ago, but never really got around to it.

me so stupid

Doh, I don't know how I managed to confuse myself into think that there was a rule missing in Bertrand's set. Went to talk to him again about the CKY, and once again it's crystal clear, like it was when I first set off to implement it. We don't need prediction, silly, it's just bottom up derivation, and all you need to do is check when you've worked your way up to the root of an auxiliary tree if the top of its root, and the bottom of its foot unify with the node in question. Nothing simpler. Sort got my adjunction rule set. Couldn't really test it out because I didn't have the comparison criteria in place, so the entire chart was always being selected and we were inifinte looping. So it's moving forward again. Slowly.

eric continues to read

Ok, so let me get this straight, this whole terminator thing, right? No big deal. You got a node A(βa...whole... bunch...of...new...crap) and a terminator for that is what you get when you eventually pop all of a...whole...bunch...of...new...crap off the stack (potentially pushing some new stuff in between, but then popping it off too) and potentially replacing it with something-else. Uh, here's a diagram, basically a cross between figures 2 and 3 on the article (page 596) but sans the greek letters and with colours:


I'm in the middle of reading about the general principles of his CKY algorithm (the whole head, middle, tail thing). Next, I will skip the CCG stuff because that fits outside of my direct reading goals, and proceed immediately to see how he uses this for TAG. In all likelihood, I don't really need this. I mean, to implement my CKY, I just have to think about propagating my insertion point up the spine, finger in ze nose. But this is useful for culture, I suppose. Plus my encardrante said something really reassuring when I mentioned that this paper was hurting me bad: yeah, you need to know this. Yay me! I found something useful to read all by myself.

Bonne année!

Happy New Year!

My thésard resolution for 2006 is to be more autonomous. As Djamé would say, "c'est ta these", it's your thesis, and it is you who should be setting the agenda. Supervisor should be that more or less to tell you if you are on the right track and to offer useful suggestions but in no way should you be relying on her to lay said track out in front of you. I'm not exactly sure what that means concretely.

One thing is finding things to read like a big boy all by myself, making a mental map of who the relevant people in your field are and checking up on them (if only more researchers had scientific blogs :-) ), backtracking your way through the bibliography to build up my general culture. I'm not sure what the process is. Simple question should be running through my head, maybe, what is the gap? What do I know that I don't know? My friend Ike had a great diagram:


There are basically two kinds of reading. One is what I call "directed reading" where you're seeking to transfer knowledge from "what you don't know" to "what you know". The other is called "undirected reading" which is very important for transfering knowledge from "what you don't know that you don't know" to simply "what you don't know" (or if you're a good reader, into "what you know" as well). For some reason, I'm much more worried about doing more of the first kind, more directed reading. Maybe because I feel more of an immediate need. Must finish PhD in 1 and a half years. Quick! Learn more, faster!

But I've sort of known about the reading problem for a long while. The theme for 2006 is autonomy. Learning how to operate in the academic real world without scientific mommy at your side (though she'll just be an email away). What more could I be doing to set the agenda? What are the questions I need to be asking myself? What does it mean to start behaving more like a researcher? Shrug. Maybe if I just keep telling myself "set the agenda, eric", I'll eventually figure it out.