state of the thesis 2006-08-31

Monthly report number three: (back posted on Friday)

I have not made very much progress on my thesis in July or August. Part of the reason is that I was travelling, but only for two weeks. The main problem was that I was being lazy and having trouble getting back into a work rhythm after a long absence from the lab.

One could argue that during my holiday at the end of June, I have learned a bit more about recent techniques used to optimise TAG parsing algorithms, so I have a somewhat clearer picture what's new in TAG land.

Otherwise, the two months have been useful because it allowed me to somewhat interact with researchers, and learn some useful programming techniques like zippers for manipulating tree-like data, and existential types for loosening some constraints of the type system where they (might) be (occasionally) needed.

I have also used the time to clean, document and maintain GenI so that it can be used by somebody in the lab besides Claire. This gave me a chance of scratch a few itches, get around to nagging jobs like "improve the regression testing system" or "clean up the configuration code". I hope not to be doing any more work like this on GenI. GenI work from now on should be of the "important" variety, neither infrastructure (that was year 2) nor cleaning up. But actually exploration of the algorithmic/optimisations stuff.

But otherwise, bupkis. No new graph, nothing to report.

zillion minor things

One of those days where you know you haven't been slacking off, yet you don't feel like you've done very much. Well, ok, the early morning 07:00 - 09:00 (overdrive eric is back?) involved a little too much chatting on the haskell channel, but otherwise, I've been busying myself improving a bunch of bits and pieces of GenI (that'll be 15 patches there...). Combination of implementing Alex's suggestions/requests (it's good; he spots some of the annoying small stuff), and getting rid of personal pet peeves.

The one major change I've made is to tighten up the Parsec code so that it uses a notion of reserved words. I'm hoping this would make it harder to introduce errors into the input files. Problem with that was that now we were too restrictive, so I had to introduce a new notion of 'loose' identifier (just for the lexicon), which acts just like an identifier, but doesn't care about reserved words:

looseIdentifier =
 do { i <- ident ; whiteSpace; return i }
 where
  ident =
   do { c <- identStart geniLanguageDef
      ; cs <- many (identLetter geniLanguageDef)
      ; return (c:cs) }  "identifier"

I've given up on the weird GUI (?) bug. Noted down a lot of behaviours for it, but don't really know what's up. I figure Alex has a workaround, and Claire doesn't see the bug, and neither do I, so off to the backburner it goes.

Tomorrow I meet with Claire. Hope I have something useful to say. Brain fried. Think about it in the morning.

Actions list for the lab has been whittled down quite a bit:

• implement optional dependencies - i think this means "make the configure script smarter"; probably renegotiate this to back-burner land...
• plan out Smart Earley
• write IAF overfilter report
• jot down notes for Claire meeting
• mail O.R re: surface realisation problem comments
• write rapport d'avancement
• prepare HW slides

random bugfixes, gui troubles

Tested the aconstr stuff on the TSNLP grammar, seems to work.

Fixed a stupid GUI bug I had introduced, and refactored the code to avoid future such bugs.

Decided I really did not like my GUI code, but that I did not have the time to rewrite it :-(

Trying to hunt down another GUI bug which makes GenI not do anything on Alex's linux box, unless you supply some totally unrelated switches (--verbose seems to be one of them). I don't recall GenI misbehaving like this before. Never did that to me on my Mac anyway. Trying to replicate on an Ubuntu laptop.

Dang... I thought today I had cleared everything out and had nothing to do but the rapport and my HW slides (eep).

testing, aconstr seems to be working

Sigh...

> import System.Random
> import System.IO.Unsafe
>
> data Product = Paper | Code | Report deriving (Enum, Bounded, Show)
> type Worker = ()
> type Eric = Bool
>
> work :: Worker -> Product
> work _ = toEnum . unsafePerformIO $ randomRIO (0, fromEnum mp)
>  where mp = maxBound :: Product
>
> anybody :: Worker
> anybody = ()
>
> eric :: Eric
> eric = head full && lazy
>  where full = [True]
>        lazy = True

*Main> work anybody
Report
*Main> work anybody
Code
*Main> work eric
    Couldn't match `Worker' against `Eric'
      Expected type: Worker
      Inferred type: Eric
    In the first argument of `work', namely `eric'
    In the definition of `whatDidEricDoToday': whatDidEricDoToday = work eric

Could not motivate myself to get into the lab this morning. And when I got there, I really did _not_ feel like working. Argh. Updated my French admin diagram, did a little emailing, not much else.

I wrote a little Haskell script to sum up the results of several HUnit runs (say you want to test different bits of software in your code using HUnit, and for some reason, you don't want them integrated in a big hunit call) It involved me doing silly things like:

hunitResult :: Parser Counts
hunitResult =
 sillyLiftM4 Counts $ map field fs
 where fs = ["Cases", "Tried", "Errors", "Failures"]

field :: String -> Parser Int
field s =
 do string s ; char ':' ; spaces
    r <- read `liftM` many digit
    spaces
    return r

sillyLiftM4 :: Monad m => (x -> x -> x -> x -> r) -> [m x] -> m r
sillyLiftM4 f [a,b,c,d] = liftM4 f a b c d
sillyLiftM4 _ _ = error "sillyLift4 needs exactly 4 elements in the list"

Hmm... maybe I should have used a regular expression library instead. In Perl, I would have written it like /Cases: *$1 *Tried: *$2Errors: *$3 *Failures: *$4/ (don't quote me on this), which is more concise and does not involve the use of 'silly' functions. Then again, it would not be as well factored as my script (which actually reuses fs for output), and once I start trying to refactor the Perl script, things would get complicated enough that you might as well do it Haskell.

Also tested the top/bottom unification stuff with a small case. Seems to work.

aconstr issues solved

Note: back-posted on Tuesday

Pulled an all nighter last night out of stupidity, nothing to do with work, just me being an idiot.

The good news is that I managed to get in to work really early, almost as early as the overdrive days. But I spent large chunks of the day falling asleep in front of the keyboard in middle of debugging some Haskell. Had introduced a major adjunction bug just by twiddling the input format parser a bit (saved by regression testing!)... turns out it was just me being stupid. Bug introduced by removing one case statement too many... and me running around in little circles for nothing. That's what you get trying to code on zero sleep. I could have not gone in to work of course, but I really wanted to reset my clock, get back to overdrive time.

The strangest bit of the day is that somewhere in the afternoon, despite the continual falling asleep in front of the keyboard, I managed to fix two or three GenI bugs in a pretty simple way. Perhaps it is the way alcohol slows your brain down, and your inhibitions, thus leading you to display really extroverted and open behaviour. Maybe the sheer fatigue was dampening my ability to think myself into a corner and opened the door to clear and elegant solutions. Fighting stupid with stupid, should that be my motto?

The problem, I think is that my on-the-fly top/bottom unification completely overlooks nodes with a null adjunction constraint. The first part of the solution is to begin all surface realisation tasks by running all initial items through the dispatch filter. Incidentally, this fixes an unrelated bug where trivial solutions were not being recognised as such. The second part of the fix is to recycle the siPending mechanism for top/bottom unification. siPending was only meant to be used during the one-phase algorithm. We build up a list of nodes on which top/bottom unification needs to be performed, and then we do it all in one go. Well, it turns out that this is useful for the two-phase algorithm as well. You just put any non-substitution null-adjunction node on to the pending list, use GenI's >--> combinator to build a dispatch filter including top/bottom unification and run your initial dispatch. Simple. (really) And here I was thinking I would need to come up with a special algorithm for this corner case or something. No, no, just more dispatching.

Anyway, tomorrow (well, today, since this is a back-post) I'm going to write some tests for the aconstr stuff and go over the patches I made. Then push everything in.

semantic index counting bug

Thanks to my new suite of regression tests, I have discovered a bug in the semantic index counting mechanism (the polarities stuff). Ok, so the basic idea is that if your input semantics does not list pronouns explicitly, you have to do semantic index counting to ferret them out from the input semantics. However, semantic index counting is fragile in that the same literal can be associated to two different counts. For example, promise(x y z) could either be "X promised Y to Z" or "X promised Y that ***he*** would Z". See? Different numbers of pronouns. What we do in this case is be very pessimistic, we assume that we're going to need to insert an extra pronoun (to provide a "he" for that last example), and then we compensate for this pessimisticness by injecting a fake literal (corresponding to the pronoun) into the semantics of the other lexical items. Basically, it's as if "X promised Y to Z" already realises the 'he' bit.

That's the basic setup. The bug comes in when really, you don't actually want any pronouns. Your input semantics has all the holes plugged. Nonethless, your two forms of "promise" retain their distinct semantic-polarity profiles, which means the mechanism is going to try to insert an extra "he" semantics into the tree for "X promised Y to Z". And that extra semantics makes GenI choke because we're trying to be fancy and represent the semantics as a bit vector, and the extra fake literal doesn't appear anywhere.

So to solve this, we cap the number of indices we insert. Only insert as most many indices as we actually need in order to plug the pronoun cap. And now all tests pass! That's nothing to be too excited about; it's just a bunch of itty bitty teensy weensy example grammars.

Also, I've tried looking into one of the aconstr bugs (there's two of them). The one I'm looking at now, is ticket21 on the bug tracker. Weird! I have no idea what would be causing this.

hooray for HUnit!

So, no more verbose mode crap to work on. Now to fix that aconstr bug I've been worrying about... eh... not quite yet. In the "eric gets around to things he's been putting off" series, I've finally gotten myself to sit down, roll up my sleeves and learn how to use HUnit... and you know what? It is EAAAAASY. The tutorial's quite helpful. The only problem is that my failures are getting treated as errors, but that apparantly is a known bug. My use of HUnit is quite simple: for every case in a GenI test suite, i generate a main case to determine if we return any results at all for that semantics, and also a supplementary case for every example sentence the user provides. In other words, if the user says that this semantics Foo should generate sentence Bar, it had better well do it.

This is a *HUGE* improvement in the day-to-day testing of GenI. I used to have a script that would run GenI on a few cases here and there, and then eyeball the results. But the problem with eyeballing is taht you tend to get lazy about things, not look too carefully. You glance at the thing, and say "eh... that looks about right". Now, I get something much more detailed, like "test case baz_quux failed, because it did not produce the sentence (I like cheese in my pants)". Not only is it more detailed, it is also more exhaustive. Every single case in the suite gets run. Very pleased with the result. At last I am taking my test suites more seriously.

Now I can whip up a test case for the aconstr bug and know when I've killed it.

enough flag talk (almost)

Ugh... so could not motivate myself to get into the lab this morning.

Anyway, after dragging myself in, I finally corrected my flag code and pushed into the repository. Also fixed an annoying bug in the test suite stuff which was making the regression tests fail. So, now (at last) I can worry about the flags.

Had a nice little mail chat with Daniel about the new flag code. He points out that now my flag handling is O(n) instead of O(1). Meh. I had thought about that in the back of my head, but I guess I'm not too worried because n is really small and this isn't really going to affect the surface realisation stuff. Main concern for me is that I'm not sure this new code is really better. I mean, ok, what's nice about it is that I have basically three less things to modify whenever I add a flag (the tuple, the default values, and the getopt -> tuple stuff). So adding flags is a bit more convenient, but as D. points out, it's slightly less type safe (as I experienced yesterday) and it costs more. Eh...

Daniel also reminded me of Haskell pattern matching. He suggests this nicer, more concise, getFlag:

getFlag f fs = do (Flag _ v) <- find (isFlag f) fs ; cast v

Hooray for pattern matching (and monads)!

Heh... took me one week to overhaul all this flag code, but at least I learned about existential types and dynamic stuff in the process. Now actually implementing the verbose mode that Alex asked for should take, like, half an hour. If I were a wiser eric, I would have implemented verbose mode first, wrote a note to myself about overhauling the configuration code for later, and then done something productive, like my rapport d'avancement de thèse, or fixing that nasty aconstr bug he ran into...

still flags?!

Sheesh. That sure was a lot of recoding. I've finally switched over all my code from the old big-tuple-of-things way of handling flags. That took quite a while... kinda disturbing, really. Also revealed a couple of assumptions and things I'm going to want to think about. For example, now I have Flags that either be unset, set to an empty argument (if the argument is a list type, e.g. String), or properly set. Seems like we need to preclude the possibility of there being an empty argument separate from the unset state. Should I create something like List1 which is always non-empty?

I don't know. As an aside, the fact that I'm using existential types and Typeable, that still bothers me. It feels like I'm making things waaaaaaaaay too fancy for my own needs, like there's a much simpler solution to this flags thing right under my nose, and I'm just being too convoluted in my thinking to see it.

Now the big dissapointment is that the code doesn't actually work. Got some weird errors merging list flags together for one. In general, I'm finding no results in my regression tests... :-/

random junk

Am now using snownews to following my trac and lab wiki RSS feeds. Very handy.

Also, here's the French admin diagram I drew yesterday in my state of mental kaputitude.



See, it's not so bad when you have it all laid out like that...

admin, trac and flags

Spent the morning and early afternoon setting up my rendezvous for the carte de séjour and getting my dossier d'inscription from UHP. Turns out I didn't need the dossier, could have just brought them my autorisation d'inscription, and they would have let me register online. I always have this notion that things are easier online, even if it's not neccesarily true.

Alex seems to be back from holiday, so he helpfully pointed out some GenI bugs, and found some problems with my trac install. Spent a good chunk of time figuring out what was wrong with the accountmanager plugin (some unicode thing which they fixed in svn), and getting that nicely set up. What's good now is that on the trac server, you can log in with a simple HTML form, no HTTP authentication.

Rest of afternoon was working on GenI, still cleaning up the flag handling. Now that I've changed the flags architecture, any piece of GenI code that is related to configuration needs to be updated. Ick. Oh well, the result does appear to be slightly cleaner and more extensible.

Towards the end of the evening, I started getting sick of work, and so starting putting together this flowchart of administrivia. Can't show it to you now, because Blogger's not responding. Maybe tomorrow.

Configuration code rewritten

We didn't have any electricity yesterday (public works), so no koweynlg there.

Spent today rewriting my configuration code to use the new existential type configuration stuff. Some things are a bit harder because of the new code. For example, you can no longer pattern match on the flags because they're all different types :-(. But overall, the resulting code is more succint, and slightly easier to update.

Note that most of the day wasn't really spent playing with existential types, but completely rearranging the Configuration module. It's always been one of the neglected parts of GenI: I'd just keep throwing stuff in without sitting down to clean up. Now torn up the whole module and put it back together. Quite self-documenting now. I'm also experimenting with using literate Haskell to build the manual: will need to write a small script that converts GenI values to tex. The script will be in Haskell so that I can manipulate the GenI values directly. The idea is somehow to convert [OptDescr Flag] into latex decriptions.

Oh, yeah, I noticed there were quite a few bugs in my code from yesterday. Here's one of them fixed:

getFlag f fs    = case find (isFlag f) fs of
                  Nothing         -> Nothing
                  Just (Flag _ v) -> cast v

back to normal?

Oh yeah, forgot to mention. Got in at 08:30 today. Looks like I'm starting to get my rhythm back... sigh... a bit late though. Basically means I'm getting-back-to-work around the same time everybody comes back from holiday. What I dissapointment. I was hoping to take advantage of the quiet time to catch up... you know... start kicking ass.

I guess I did polish off a lot of stupid administrative stuff that's been clogging up my actions lists, but that's about all I did. Could have done so much more though. For example, my rapport d'avancement de thèse could have been done by now, as well as my Haskell Workshop slides. I could even have started something new, like trying to implement SmartEarley, or writing up my IAF report. But no... Lazy eric :-(

command line parameters with existential types and Data.Typeable

I wasn't too happy with my flags solution from Monday. I was trying to write some code in it and realised how prone I was to making type errors with it. Yeesh. So we want flags, we want matching on the flag data constructors, but we also want to have the types. Here's what I came up with, playing with existential types (uh... I think?) and Data.Typeable.

The idea is that you write stuff like

> -- You might want a cpp macro to automate this, btw)
> data LogFileFlag = LogFileFlag String deriving (Typeable, Show)
> data TimeoutFlag = TimeoutFlag Int deriving (Typeable, Show)

which you can then use like this...

lf = Flag LogFileFlag "foo"
tf = Flag TimeoutFlag 3

*Main> hasFlag LogFileFlag [ tf ]
False
*Main> hasFlag LogFileFlag [ lf, tf ]
True

*Main> [lf, tf]
[Flag LogFileFlag "foo",Flag TimeoutFlag 3]
*Main> getFlag LogFileFlag [lf,tf]
Just "foo"
*Main> setFlag LogFileFlag "bar" [ lf, tf ]
[Flag LogFileFlag "bar",Flag TimeoutFlag 3]

As for the actual code, well, you might not agree with it, and I haven't actually used it in GenI yet, so I don't know if it's any good, but... here goes...

> {-# OPTIONS_GHC -fglasgow-exts #-}
> module FlagsAndSwitches where
> where Data.Typeable (Typeable, cast)
>
> data Flag = forall f x . (Show f, Show x, Typeable f, Typeable x) =>
>      Flag (x -> f) x
>  deriving Typeable
>
> instance Show Flag where
>   show (Flag f x) = "Flag " ++ show (f x)

> isFlag     :: (Typeable f, Typeable x) => (x -> f) -> Flag -> Bool
> hasFlag    :: (Typeable f, Typeable x) => (x -> f) -> [Flag] -> Bool
> deleteFlag :: (Typeable f, Typeable x) => (x -> f) -> [Flag] -> [Flag]
> setFlag    :: (Show f, Show x, Typeable f, Typeable x) => (x -> f) -> x -> [Flag] -> [Flag]
> getFlag    :: (Show f, Show x, Typeable f, Typeable x) => (x -> f) -> [Flag] -> Maybe x
>
> isFlag f1 (Flag f2 _) = typeOf f1 == typeOf f2
> hasFlag f      = any (isFlag f)
> deleteFlag f   = filter (not.(isFlag f))
> setFlag f v fs = (Flag f v) : tl where tl = deleteFlag f fs
> getFlag f fs   = find (isFlag f) >>= cast

I'm putting this in the public domain if you want it, btw. It might be total crap. I might be making things way more complicated than they need to be. We'll have to see.

dissociating flags from their values

Alex asked me for a verbose mode in the console today. Fair enough. I spent the afternoon generalising my Configuration code. Rather than using one megatuple with Maybe for the optional parameters, I'm finally switching to a list of flags à la Darcs. This will make it a lot easier to add new options... I hope. One thing I'm doing differently, though is using two different datatypes, one for the flags themselves and the other for the switches using them. So instead of code like this:

data Flag = FooFlg | BarFlg String | BazFlg String
                   | PingFlg Int   | PongFlg Int 
newFlags = (FooFlg "hello") : flags

I have code like this:

data Flag = FooFlg | BarFlg | BazFlg | PingFlg | PongFlg
data Switch = NullSwitch Flag
            | StringSwitch Flag
            | IntSwitch Flag

newFlags = (StringSwitch FooFlg "hello") : flags

The disadvantage of this code is now I can't force BarFlg to only contain String... yeeach. But it does have one advantage, in that now, it's easy to write stuff like hasFlag BarFlg and deleteFlag BarFlg (whereas before I would have to write a seperate hasFlag/deleteFlag combo for each thing). I don't know if this is the best way to do this... if this is really a good tradeoff to make though.

situation irrégulière

Oops. Today, I got yelled at by the DDTEFP, because even though I knew I needed to go get a carte de travail, I never got around to doing it (I got as far as photocopying my avenant...) and so have been working illegally for the past 9 months. Ok, that's a lesson to you foreign thésards out there: if you've got a carte de séjour Étudiant (and not Scientifique), you most likely need to get your Carte de Travail, even if nobody ever asks you for it. The other thing is that no, my statut is not one of travailleur temporaire because my contrat de travail specifically says that I have to be a student. If I were doing something after my thèse, something like an ATER, then I'd have to get a carte de travailleur temporaire. The fact that I'm salarié don't make a difference whatsoever.

Oh, didn't do any work today either. But next week. Next week will be better.

:-(

I pretty much spent the whole day procrastinating on writing that rapport d'avancement. It's useful work. It makes you think. But it is sooooooo boring. I'm pretty much trying to say the same thing I said two days ago, but in not-blog style, which is considerably harder.

nothing much

The trac-darcs duo were quite responsive last night when I mentioned the slowness of the new 0.4. One of them came up with a clever workaround, and so I spent about an hour installing the new version and testing stuff out. Seems much better now! I'm no longer afraind to click on changesets, and all the little bits of bugginess have dissapeared.

Didn't much else otherwise. Spent a good chunk of time thinking about M.Q. MMAX stuff and wrote an email with my suggestions. Nothing very precise, but maybe a couple of ideas here and there about exactly what kind of stuff the tool is capable of, and what kind of workarounds he might implement to fit his task.

Read a very nice introduction to monads. Very down-to-earth, concrete, no bullshit, but no scariness either.

Did some ICFP-related admin, like faxing them my student card, and booking some nights at a hostel.

Added my publications to the rapport d'avancement, and re-read what they want me to write. A part of me just going "uggggghhh... do I really have to?"

Not being nearly as productive as I'd like to be lately.

Sucks.

Yeah, so I figure if I can just get rid of the rapports d'avancement (both of them), maybe work on my HW slides, write my mail to O.R (I'm using people's initials because I don't want somebody to google a name and hit koweynlg), then... I will have exhausted my supply of non-thesis-related lab stuff. And I'll have to do actual work. I'm looking forward to it. I've run out of easy non-work, and the only thing I have left now is the really annoying non-work. So now, work's looking much more interesting!

sleepy eric

Blech! Insomnia last night. So not functional right now.

Upgraded our trac-darcs installation to 0.4, which is very nice because it actually works now, but not so good because it uses darcs annotate, and darcs annotate is very very slow. So now, at least we got timeline and browse source working again on trac.loria.fr, but clicking on a changeset is probably not a good idea unless (a) somebody else has clicked on it before you or (b) you're willing to wait 10 minutes or so.

I actually still have some stupid stuff I could be doing. M.Q. has an MMAX usage question that I promised to think more about. And this week, I should probably write up my rapport d'avancement so that I can kill it dead and move on to something else. I'd have to wait to show it to Claire anyway, but at the very least, having a first draft, and sort of positioning my third year semi-intelligently should be useful.

I guess the rough idea of the erician thesis is that we're working out a pretty apparatus/methodology for building surface realisation algorithms and grammars (i.e. how you figure out that something actually works, what you have to count for). That's all that's really new about these two years so far is that we've got some good "solid" tools for trying out new shit. And like a Christmas tree, the thesis is really going to hanging all sorts of ornaments to the tree. Look, now that we have this apparatus, let's see what happens when we implement IAF, let's see what happens when we implement QuickCheck, hey, let's throw in some statistical stuff for good measure, and take the polarities too. Now what happens when you mix and match. How do you tell which optimisations really helped, and how they interacted among themselves? What happens when you go from a toy grammar to the real thing?

I dunno about that. Don't seem very exciting, does it? We'll see. Could end up being a whole different thesis come 2007.

another day of straggling

Eh... got here around 14:00 again... it was semi on-purpose in that the canteen was supposed to be closed today, but I ended up neither being productive, nor doing my grocery shopping. Meh.

Got some annoying busy-work done today. Updated my webpage to include 2006 publications. Though I just realised I'll have to do it again later for my HW slides. And finally improved the GenI input format doc upon Alex's advice. He basically asked me to put down an EBNF. I used to have one actually, but got rid of it for some reason, maybe because there were a bunch of changes and I was getting sick of documenting unstable crap. Now that the dust has somewhat settled, we can write things in somewhat more formal ways.

My actions list is now bereft of annoying busy-work. Which I means I no longer have any excuse not to be productive.

Uh-oh.

stupid stuff

Polished off a bunch of stupid stuff, like updating my CV, updating kowey-generic, setting up darcs repositories, a bit of preparation for the ICFP (looking into hotels, etc). I believe that one more day of this, and I'll be all done with stupid stuff, and will have no choice but to do real work. Yep, the whole procrastinating by working thing.

Today, I actually managed to get up early, like, before 07:00. But then I couldn't motivate myself to go to work, so by the time I got here, it was lunch. After which I had a long and utterly fascinating discussion about the state of the French higher educational system. That bumped me up to 14:00 before I started my day. And then the rest of it was busy-work like above, you know, brain off, keyboard on. But I'll be back. Soon, hyper-motivated eric will return. Please?

darcs vs the dfd

One reason why I like using darcs - easy branching:

darcs get 2005/rapport-05 rapport-06
cd rapport-06
darcs mv rapport-05.tex rapport-06.tex
darcs mv rapport-05.bib rapport-06.bib
darcs replace rapport-05 rapport-05 Makefile
darcs replace 1st 2nd rapport-05.tex

And there's my 2006 rapport d'avancement set up. What's neat about this is that my INRIA rapport is a branch of DFD one, so I could have something like this:

DFD rapport 05 ---> INRIA rapport 05
     |                     |
     |                     |
     |                     |
     V                     V
DFD rapport 06 ---> INRIA rapport 06

If I play my cards right (without setting up any false dependencies), I should be able to pull patches from both DFD rapport 06 and INRIA rapport 05. If not, no big deal. I can still copy-and paste, but at least all the branching manuevers are easy.

more scripting

Alright, I haven't been a very good eric these past couple days. Yesterday, I stayed home, at first thinking I was sick, and then procrastinating on taking a shower, and eventually getting sucked into some major darcs hacking (and a bit of freeciv playing, sadly). This morning, I polished off some of that darcs stuff which had been nagging at me for a while (no freeciv this time!). So that's a day point five on an unofficial holiday.

Uh, let me rationalise my way out of this one. See, this darcs stuff had been bothering me for a while, stuff I had done wrong and stuff which was affecting other people or that they were waiting on. Now that they are done, I can sleep easier... or something. No seriously, I do feel like my head is a little bit clearer. Less of that overwhelmed omg-omg-going-to-die. So this is good right?

Except that this afternoon, I also pretty much did nothing. Let's see. Sylvain helpfully (*) sent me the full Zen document. It's it Literal O'Caml! Gérard Huet believes enough in literate programming to do it for Zen (I guess), so see, this whole literate Haskell thing isn't just being silly (I hope). I wish somebody would port this to Haskell. That somebody might just be me. Interestingly, Huet points out that zippers are geeeerrreat for TAG adjunction. This could be useful for the derived-tree construction phase of the Simple algorithm. Shave off a bit of time and memory consumption. Not the bulk of the work, but eh, every little bit counts.

* (ok, when people keep promises that you forgot they made, that's like cool and shit)

Learned a little bit more about the programming language Epigram. Hmm. 2D programming with really wild and crazy types. Are we all going to be programming in Epigram in the next 10 years? (Yeah, like we're all programming in Haskell now, right?)

Now this one is very clearly not work: Made some extensive improvements to the Understanding Darcs wikibook. Oh well, maybe somebody will find the Undoing mistakes chapter helpful. It tries to clear up all the different commands for undoing stuff, like revert, unrecord, obliterate, rollback, etc.

Finally, work... uh work... Well, I finally finished up that disk space reporting script. Now, in addition to the durep stuff, it prints out summaries like

You're using 1.2G in this directory.
That's enough space for 2.4 people.

Ok, it's not really work. It's admin. But it "had" to be done. By me. Yep. Had to be me. I swear. Honest. Sigh. One action down. Ten zillion to go.

day-o-scripting

Transition insomnia. So I let myself sleep in and mosey on in around 10:00... this is progress! It's before noon again, but we're not hitting our target yet.

While waiting for the bus, I finally figured out the Zippers paper (it's simple stuff, but I'm a slow eric), so this morning I wrote it up as the previous koweynlg post.

Spent the afternoon working out all the kinks in my automated nightly darcs dist script, which I'm pretty happy to have.

Spent the early evening improving some scripts for reporting disk space usage on the local NFS share.

projects and actions

The following is completely redundant with my paper lists, but this might give you sort of a day-in-the-life feel of things:

open projects

• memoisation idea for Simple 2005
• TSNLP evaluation for GenI 2006-01 (WF: better test suite data)
• OS X Tiger on the laptop (WF: wxhaskell on darwinports)
• automatic detection of zero-literal semantic index polarities 2005
• obtain SFG grammar for French 2005
• implemented Carroll FS QuickCheck 2006
• Shieber restrictors? 2006
• index accesibility filtering 2006
• Smart-Earley 2006-04-23
• superpacking with Bertrand 2006-05-04
• cky profiling and rewrite 2006-05-04
• rapport d'avancement de thèse 2006-07-25
• rapport d'avancement INRIA 2006-07-25
• Haskell Workshop

next actions

• write IAF problems report for Claire
• mail O.R. regarding surface realisation poster comments
• submit garkow to Hal
• update CV with latest publications
• note tips for installing GenI on Windows
• set up rapport d'avancement deux darcs
• outline rapport d'avancement
• check exact ICFP conference location
• book ICFP hotel
• adopt M's quota stuff into ezshowusage
• cleanup polarity examples - remove manual polarities? hide them under a rug?
• mv vi stuff to bottom on examples
• make macros description in GenI doc more readable
• see if html.sty is actually needed in genidoc
• try to upgrade ej example to new feature-based syntax
• make latex-beamer part of kowey-generic slides
• setup ICFP slides skeleton
• revisit SmartEarley idea - note the general ideas
• implement optional dependencies in GenI makefile?
• CODE: solution to the aconstr problem
• add a no-grouping option to gtester
• think: determine if there is a way to do M's annotation stuff in MMAX or not

There's a bunch of stupid shit mixed in there with the hard stuff. Naturally, I'm going to push all the stupid stuff out of the way and really clear the deck for the real thesis stuff. Is that procrastination-by-working? Or am I just making room in my head? Can't tell the difference.

understanding huet zippers

Gérard Huet's zippers paper very succintly presents a simple, elegant solution for a frequently occuring problem: cheaply navigating up, down, left and right in a tree. The paper is only 6 pages long, and the basic idea is already presented in the first three papers. Even still, I had a little bit of trouble understanding his approach until I sat down with a pen and translated his code into graphical notation. Then it all made sense. And yes, the solution is elegant indeed. Here are my notes. You probably need to have the paper with you in order for the notes to make sense.

different trees

Notice that Huet represents trees differently than we do in Data.Tree. Namely, whereas our structure looks like this:

data Tree a =
 Node a [Tree a]

His structure looks like this:

data Tree a =
 | Leaf a
 | Node [Tree a]

(note that I am translating from O'Caml into Haskell, and that I am calling them Leaf and Node instead of Item and Section). If you're not paying attention to this difference, then you're just going to trip yourself up. Just to be annoying and insistent about this, here is a parse tree for the expression "a*b + c*d" the way a Haskeller would write it:

Node "+" [ Node "*" [ Node "a" [], Node "b" [] ]
         , Node "*" [ Node "c" [], Node "d" [] ]
         ]

And here is how the Haskellfied Huet might write it:

Node [ Node [ Leaf "a", Leaf "*", Leaf "b" ]
     , Leaf "+"
     , Node [ Leaf "c", Leaf "*", Leaf "d" ]
     ]

Both of these make sense, I guess, but to understand the zipper idea, we're going to stick with Huet's version for now.

a visual representation

You might find the following graphical representation to be useful. It shows the "a+b * c*d" parse tree both as a tree and as a path to the second * in that expression:



Simple, isn't it? Now what Huet is saying about "like an inverted glove" actually makes sense. Note that the

Oh and by the way, a path in Haskell could probably look something like this

data Path a =
 | PathRoot
 | PathNode [Tree a] (Path a) [Tree a]

I'm not doing anything special, just dumbly translating between Caml and Haskell syntax. The three arguments to the PathNode constructor correspond to your left, parent and right, respectively. Naturally, this isn't complete without a representation of the current tree. A location is just a tuple consisting of the current tree (in this case *) and its surrounding context (the blue diagram above):

type Location a = (Tree a, Path a)

navigation

Using the diagram above, moving left and right should be pretty easy to understand (it should also be clear that it's dirt cheap). When moving down, we just pick the leftmost kid. Moving up costs a little bit more because we got to glue the left kids, current tree, and right kids together).

Another minor note is that the idea of "elder" and "junior" is pretty confusing if you're just talking about left to right stuff. When Huet says "elder" in this case, he means "on the left"; likewise, "juniority" can be read as "rightmostness"

other stuff

This is as far as I've gotten - understanding the basic idea and navigation. I haven't looked into the scarring idea yet, but I'm hoping it won't be so hard, now that I know how the basic zippers work. I'm also not yet sure it would be easy to translate this to work with Data.Tree style trees. There is a Haskell library floating around. I guess I should take a look or something if at some point I decide this is going to be useful for me. Maybe for the CKY algorithm, for climbing up elementary trees?