state of the thesis 2006-12-31

A monthly report and a yearly report all rolled into one. Written on 2007-01-02 and backdated accordingly.

December 2006 can be characterised by three activities: meeting with C, learning how other surface realisers and NLG systems work (particularly how the SFG camp approach things), and hacking on scripts. The hacking was fun, the reading was useful an the meeting with C was both. That being said, December was also a very lazy month. I think I spent half of my lab time either not there, not doing anything, or whining about my laziness afterwards. May future months be quieter and more productive.

2006 in review

code

2006 was chock full of code: I wrote Perl scripts, Python programs, a Makefile of Doom and Haskell everything.

The Perl scripts (sematiser) were for semi-automated generation of test suites from sentences. This was probably a colossal waste of time, considering that (1) we now have a perfectly good parser (2) the results were crap and wasted a lot of precious C-time cleaning shit up. That being said, it helped us to understand a little bit better what happens when you try to build a large-ish test suite for symbolic methods; and it helped us to get a clearer picture of the utility of TSNLP as a generation resource (eh... not so hot).

The Python program (gtester) was for batch-processing of GenI, being able to run different variants of GenI on the same input and compile the results into a PDF. Debugging gtester was a royal pain in the ass. I should either have thought to build unit tests or switched to a statically/fancilly typed language, hence my conclusion that Haskell is a geeeeeereat script language (except for that readFile thing).

The Makefile of Devastation was so that C could do the whole hack-the-test-suite (or the grammar), recompile via XMG, run via GenI/gtester loop without recompiling everything. Bugs crept in, usually because I got my dependencies wrong, but I get the feeling you can't really blame make for that. I mean, either you get things being run unnecessarily, and that's basically the same as not using Make, or you get things NOT being run when they really should [that's bad]. But then if you want to avoid running things, you need a dependency tracker of SOME sort, so why not use Make? Anyway, after much usage, the Makefile of Destruction seems to solid enough for daily C usage

The Haskell program was me attempting to implement the CKY algorithm for GenI and doing a craptastic job at it. I spent a lot of time coding, but most of this time was generalising GenI so that i could support multiple algorithms. 2006 was when I introduced Replaceable, Collectable, and dispatch filters. Even if it later turns out that we don't use different algorithms in GenI, it should at least make the code a lot cleaner. But please don't look at my CKY code. It sucks. There were also a bunch of Haskell scripts, itty bitty support utilities, largely for the Makefile of Demolition.

words

I did some reading in 2006, though not enough. I learned about efficient TAG parsing techniques, surface realisation search strategies, and chart parsing.

I wrote one paper (the Haskell workshop one) and added a supporting paragraph or two to a couple of others and built posters. I travelled to Sydney for ACL (mainly INLG and TAG+8), gave three posters [one of them not mine] again doing a crapful job. I also went to Portland to give a Haskell workshop talk. It seemed to be pretty well received, so I guess I should be happy or something.

In October, I started writing up my thesis, namely the state of the art. I only got up to 15 pages, or around 12 kilowords. C is pretty reassuring about that, saying that this is because it's the hardest part. I hope 12 kw for over a month is a reasonable amount of time.

ideas...

Did I have any ideas? I think I had a total of three: the latter two being the fruit of my most recent discussion with C. Only one of them is useful, and then, it was really just a technical thing. You could also count the use of typeclasses and combinators as ideas, but that's just engineering, nothing to do with NLG.

lab saturday

One, I deserve it, with all the slacking off from this week. Not too bad; 15:00 to midnight, like back in the old days before I discovered the greater joys of early rising. Two, it's a good sign in that work is sufficiently fun to merit coming in on Saturday. Hacking up scripts and Semconst. Have installed all my new scripts chez C, so now she should be able to get a summary of the paraphrase results.

Have renamed the overgens field to outputs, and accordingly repurposed it.

makefile hackery entre autres

Let's see here. Started the day with a little Haskell hacking, trying to debug my extract suite program (the opposite of the script I was working on a couple days ago). Every time I try to fix something, I also spend a bit of time cleaning it up, refactoring it, applying some of my newfound Haskell. The problem with the script was that (1) my string-only parsec wasn't taking into account the new overgen field, and so it failed somewhat early in the file. It failed silently because I wasn't explictly looking for eof (2) I was trying to zipWith on two lists of finite length, but I wasn't just assuming the same length, without thinking to hunt for mismatches. Hmm: I wish the type-checker could look for this kind of thing. One solution for that kind of situation might be to use a variant of zipWith that enforces equal length on those lines. Well, I don't care that much. But it's not so nice to see bugs just sort of slip through like that without blowing up.

Here's the refactored eof thingy:

tillEof :: Parser a -> Parser a
tillEof p =
  do r <- p
     eof
     return s

Other main activity has been to attempt to integrate SemConst and GenI into a parse-gen loop. (The holy trinity: parser, grammar, generator). Some differences in philosophy to overcome. One issue is that we would like to share a compiled grammar between the two systems, whereas right now we have two completely different approaches to producing compiled grammars. Shouldn't be too big a deal. I'll just need to adapt what I'm doing to use the grammar that SemConst produces.

Another issue is that I want to compile the grammar once and only once even though I'm in batch processing mode. It seems the solution so far is to do a little Oz-hacking, and add both a "--noparse" and "--nobuild" switch. One let's us build the grammar without doing anything with it; the other lets us run the parser on an already-built grammar. I can then fiddle with the Makefile intelligence so that it knows not to recompile the grammar unless necessary. This is something it already does for GenI anyway.

meh

Meeting with C today. Had a couple of ideas, feels like a first in my career, actually having ideas. One of which is that you can deal with adjunction in the polarity stuff by thinking of adj nodes as 0 and aux trees as 1. Instead of using sum to cancel your polarities, you use product. Amusingly enough, you have the same result: you want to have zero at the end. This seems to account both for adjunction being optional and for the possibility of adjoining more than once to the same node (well, not literally, but you know what I mean).

Other than that, having been working on the little test suite combiner thing. Had one issue with lazy evaluation today, but that was rapidly resolved by using Simon Marlow's strict readFile'. Otherwise, I was getting "too many open files". Hmm... so that's one place where maybe a naive programmer would not want to use Haskell as a scripting language (instead of something more traditional, like Perl or Python). But then again, as Phillipa on #haskell points out, all you do is give the naive programmer a library - you say, oh "don't use readFile for that; use readFile' instead".

a cheesy alphanumeric sort

Problem: you've got x1, x2, x10, x100 and they are being sorted as x1, x10, x100, x2. Possible solution, sortBy (comparing toAlphaNum) below?

data AlphaNum = A String | N Int deriving (Eq, Ord)

toAlphaNum :: String -> [AlphaNum]
toAlphaNum = map readOne . groupBy (equating isNumber)
 where
   readOne s
     | all isNumber s = N (read s)
     | otherwise      = A s

equating :: (a -> Bool) -> (a -> a -> Bool)
equating f a b = f a == f b

widdle coder eric

Look, at least I got in before noon, ok? Hey, even a whole half hour. Had a good chat with C on the phone today, paper stuff.

Worked on the wikibook, and got distracted by #haskell for a while (the problem with being alone in an office is that since you no longer have any external distractions, you make up new internal ones to replace them; for example, i never use IRC at work anymore... but being alone, eh... you just sort of let yourself go).

Got serious somewhere near the end of the afternoon, started coding up a little utility to merge the contents of geniExtract. The goal is to get the test suite, scattered through out a directory as a bunch of subdirs, and the responses back into one file. C can then edit the file to take out all the overgeneration and run some other script (which I will have to write) to get the whole thing graphable. I might be over-engineering this. I could do the job with some fancy grep and sed tricks, but I am actually parsing stuff. EH? Well, look, the idea is that you can use the same technique to augment your test suite. For example, if you find valid paraphrases for something, you stick them in. Or if you find things which are clearly overgeneration, then you tell GenI so that it can raise a red flag if one of these things get produced. Besides, the code's all there anyway. All I have to do is add a couple more instances to my typeclasses and tack on a couple lines of Parsec. I hope I'm not just being stupid. Is this another one of those "why don't you just use grep" moments?

Anyway, was playing ourd with permutation parsers for a bit. I've got a situation where I want to be able to parse any arbitrary number of foos and bars:

foo
bar
foo
foo
foo
bar
bar

Unless I'm skimming the functional pearl wrong, permutation parsers don't let me do this directly. I'd have to do some tricks with concat or whatever (they would let me parse foo foo foo foo bar bar or bar bar bar foo foo foo; but I don't think I can jumble things up). Slightly dissapointed, but I guess my other solution is something I can live with:

parseEither :: Parser a -> Parser b -> Parser (Either a b)
parseEither p1 p2 = Left `fmap` p1 <|> Right `fmap` p2

lazy lazy eric

Had a long unhealthy weekend and made it to work just before the canteen closed. Then spent the whole afternoon procrastinating. And now doing actual work at night, just like in the old days. Sigh. This blog is so full of repetition. Today I woke up. Today, I didn't wake up. Nya nya nya, blah blah blah. Thesis up, thesis down. 2007, we get back to business.

tagml script rewrite

Today, I rewrote my splitTagml script. Motivated by trying to run GenI on some data, realising the grammar was broken, pulling in some grammar fixes, recompiling, and waiting... and waiting. No, no, eric, this is stupid. Your computer shouldn't be crazy just because you're trying to cut up some little file into littler pieces. You aren't trying to build a parse tree or anything, so stop being an idiot.

The script was this horrible, complicated thing trying to play with string positions. The script treated the input file (one 67 XML) as a giant string, zipped around cutting substrings out of it and then writing thoes substrings into individual files. The point was to split the giant XML file into a bunch of smaller ones, based on some superstition that me processing a lot of little XML files is cheaper than one huge one. The only reason to have this superstition is if you think you have a memory leak in your code (laziness has its drawbacks for the naive programmer). But the problem was that my filecutter was itself eating memory.

I made the following modifications

1. Simplified my code. Instead of doing crazy things with string indices and zip, I introduced a little helper function for splitting a line into chunks. The function is below.
2. Used appendFile for output instead of trying concatenate largish strings in memory
3. Used String instead of ByteString: the point was to go back to lazy strings (I could have used ByteString.Lazy.Char8 too, although that might make the function below a little hard to implement) - I'm not sure if this really makes a difference. My guess was that reading that whole thing into one big chunk of memory maybe isn't so good. The thinking was that
   if you do it lazily, the computer will be able to notice that earlier bits of the string are not used for anything, and garbage collect. I have no idea what I'm talking about. Just one of these gut thingies which may be wildly and absurdly wrong. Voodoo informatics. Maybe the only reason this helped is because it simplified my code, and simplifying the code helped me write a better program

Anyway, no more paging, and my code is easier to maintain. Of course, the right solution is NOT to write a filecutter, but to (A) actually test your hypothesis [I think I did run time on this once] (B) fix the memory leak in the XML program.

splitUp

Now, I'm a little embarassed about the function. I tend to feel that if I were a real Haskeller, I would be able to express something like this very elegantly, in three obvious lines, and no explicit recursion or crazy reversing. If I were a real Haskeller, you would look at my code and understand it instantly. Alas, I am not. Here is what I got. I'm sure an undergrad in an intro programming course could do better. I hope so, anyway:

-- | Split up a String at every occurrence of a substring
--   For example:
--     splitUp "-X" "-Xa-Xb-Xc-X" = ["-Xa","-Xb","-Xc","-X"]
--     splitUp "-X"   "a-Xb-Xc-X" =   ["a","-Xb","-Xc","-X"]
--     splitUp "-X"   "a-Xb-Xc"   =   ["a","-Xb","-Xc"]
--   You can treat this as a drop-in replacement for 'words' or 'lines'
splitUp :: String -> String -> [String]
splitUp d s = helper [] s
 where
  helper acc s
    | d `isPrefixOf` s = addAcc acc $ helper reverseD (drop lengthD s)
    | otherwise = case s of
                  []     -> addAcc acc []
                  (x:xs) -> helper (x:acc) xs
  addAcc acc = if null acc then id else (reverse acc :)
  lengthD = length d
  reverseD = reverse d

morphology

I remember now how I had gotten it into my head that you need some fancy 3rd party tool for morphology (or learn how to do that two-level transducer stuff yourself and/or port the Zen toolkit to Haskell): looking things up in tables does not account for the fact that morphology [depending on your language, i guess] is highly regular. For the most part, you shouldn't NEED to look shit up in a table, because there is some rule for that. And encoding those rules... well you might as well go with something fancy, not just a simple table lookup, but maybe something with automata in it. That being said, the lexicon that we're using for these tests is small enough anyway that you don't need to care about regularites. Just look everything up and go.

meeting today

Met up with Claire today.

Read up on the RealPro stuff, which gave me a taste of MTT.

Didn't do much else. Chatted with friends. Went to bed late last night (sigh), so only made it here in the afternoon. I really have to start shifting back into Morning-Eric; maybe early 2007.

Happy holidays and all that.

the realpro stuff

Seems like this realisation component is deeper down the chain than we are. The deep synt structures you provide have basically specified most of the syntax for you. Constraints on input must then be done structurally, although there's quite a bit of control that you do with features. Not much else for me to say. The pipeline is ([deep] dependency tree with lex items -> [surface] dependency tree with lex items; including function words -> string -> formatted string).

elhadad1997fcl continued

more notes on elhadad1997fcl

so what does a lexical chooser do?

The first question is what a lexical chooser should take as input. Given the notes from before, the obvious no-duh answer would be "well, the output of the content planner"... which would be "structures from the application domain selected during content planning, possibly augmented with discourse relations". You also want stuff about discourse and speaker intent, but that can all come from the planner.

Ok, so what does it output. Again the no-duh answer, "the input to the syntactic realiser" (golf clap), and this would be something more like... oops. They don't say explictly. I guess it means "go pick up a SURGE [or your favourite syntactic realiser] manual". Point is that the lexical chooser picks one paraphrase based on the input, and feeds that to your realiser.

I feel a bit uncertain about this, but I'll suppose that this does not neccesarily preclude minor syntactic variations. The lexical chooser would choose between

• The 6 AI assignments require programming
• AI has 6 assignments which involve programming

Since choice basically is "realise this relation with the verb 'require', and that one with the noun 'assignments'"; but not really any of the closed-class words (the function words), and no word on how they're supposed to be combined. It would be syntactic realiser which would then select between

• The 6 AI assignements require programming
• Programming is required by the 6 AI assignements

I think the SURGE manual says this anyway. Naturally, this decision can be made with the help of input passed through from the lexical chooser.

Anyhoo...

The 3rd piece of the puzzle is how we get from input to output. Really, what does a lexical chooser do? There are two tasks to perform, associated with decisions to make

• phrase planning (syntagmatic decisions) - from conceptual net to tree of thematic roles
• lexicalisation proper - (paradigmatic decisions) for each piece of the thematic role tree, choosing among the alternate lexicalisations for that role. The tricky part to this is that you can't make these choices independently of each other; one choice engender constraints on other choices, constraints back-propagate, all that nasty business.

The paper describes this as a two phase process, each with floating constraints. I wonder if there are cases where phase 2 constraints can force you backtrack up to phase 1 and start over, though... or if I'm just not understanding this right.

phrase planning

Skimming over this. Sorry, not what we're working on right now. Would be nice for general culture though.

merged realisations

I'm not worrying too much about merged realisations either. Again, good for general culture, but for the moment, not my problem. Something I can imagine is shunted off to "some other system" in the sky (like, this system).

cross-ranking realisations

This might be more interesting. The question is how do you map thematic structure onto syntactic structure, especially when some things can be mapped on different ranks. Same thing can be expressed as a verb, adjective, conjunction, etc [the word "but" can mean so much...]. This was a bit tricky for me to read because I didn't really know what an argumentative evaluation was, just treat it as some constraint you have to meet.

I was quite confused by the notion of expressing constraints in a unification-based formalism. I can understand that you get unification failures from two different ground values, but how do you express something like "this feature must be expressed"? From reading, I get the impression that it's because FUF has special mechanisms, noted by two keywords. One keyword is GIVEN, which basically means "this feature is expressed". If you look at Figure 16 on page 221, you can see two values for {process ao}: GIVEN and some other feature structure. So, that keyword is not a value per se, it's just some extra annotation you add into the feature. Another such keyword, by the way, is ANY, which tells FUF that you want to postpone unification on that feature until the very end. I guess not understanding that there were these extra mechanisms that tripped me up.

The feeling I get is this: you've got a constraint that you're trying to apply somewhere whilst doing your lexicalisation. Lexicalisation is top-down breadth first: for the current node, pick a word/category, instantiate, now flesh out your thematic kids. If I understand correctly, you also have these constraints that you're trying to express SOMEWHERE (they're cross rank), and in order to do that, you need to make provisions for the current constraints not to be realised at this level, but somewhere down the road. Why this sucks is that you could be happily doing your lexicalisation search, drilling all the way down to bottom, procrastinating like hell on one constraint or the other, until you realise at the very end... whoops. Can't meet that constraint. One of my previous lexicalisations was bad because it ultimately does not allow me to fulfill all my constraints.

So, backtracking is a problem.

One thing I'm shaky on is this distinction they seem to make between deterministic decisions and non-deterministic ones. How can you just "map to the first slot found in the constituent tree that can account for it?" Aren't just inherently searching anyway?

Anway, backtracking is a problem; got a big search problem on your hands. To reduce backtracking, they introduce a mechanism which smells a bit like a cut (only the opposite; it's not 'stop backtracking beyond this point' but 'leap up to this point'). The idea is the grammar writer can annonate alternations as being able to affect one constraint or another. Whenever we hit the problem that oops, that constraint wasn't realised, we aren't going to dick around backtracking all around our search tree. We look at the missing constraint, and then we jump up to the choice point that our grammar writer said was important. Something like that, right? Cut but inside-out.

where this all fits in

I guess that was a false alarm. Hard to articulate my worry really; just a sudden feeling of panic, a feeling that I suddenly didn't know how all the pieces fit together. My dividing of the world into surface realisation (what I'm doing), and everything else (what other modules are doing before they talk to me) felt supremely inadequate, or somehow that once all the important lexical choice decisions were made; eh... all this polarity business, not so interesting. It's mostly a matter of trying to see where all the pieces fit in, what my job is, so to speak.

elhadad1999scp

Flipping back to the syntactic realiser, just trying to figure out how it uses its input. Looked through the tables in the appendix and tried to mentally extract some value out of them. Table 1 and 2 maps you from process to list o participants. Table 3 goes from mood to (dunno) realisation stuff. Three kinds of input you can provide:

• ideational - via process, participants or lex-roles (if no lex-roles, the system looks up participants on the basis of process?)
• interpersonal - via the mood feature
• textual - via the focus feature

Is that the idea? If you want to run throug these systems, you specify values for these features? And then the rest happens by magic... uh... unification, I mean?

elhadad1997fcl

Slowly making my way through a re-read of elhadad1997fcl, mostly so our discussion tomorrow can be semi-productive, and also because I want to have a good idea how GenI's lexical selection process differs from other systems and/or what kind of input I can expect us to have.

Am getting increasing self-conscious about our inability to handle recursive feature structures with reentrancy. I guess you could say we've got reentrancy, but no recursion, but then that doesn't get very hard. Problem is that it makes it a bit tricky to just pop from one system to another. I wish somebody would write an FS library for Haskell. Maybe me, one day, when I decide I have the time to (1) learn how to do it (2) code the sucker up (3) test it (purrrfect for QuickCheck). It would be a nice library, useful for anybody who wants to do NLP.

But the reading is going slow. It doesn't help that I'm coming in to work so late (lunchtime) and leaving so early (dinnertime), but I haven't flipped into discipline mode. Sleep bi-polar. Either I'm being really good and doing 22h00/05h45; or I'm sort of straggling off to bed around 03h00 and getting in after noon. The other problem is that reading can be boring. Well, not so much that; it just requires you to Purposely Concentrate, you know flip a switch and Bing! you're concentrating. And that was never something I was good at. It's hard to resist the temptation to just wander off and go check or mail, or see how the Haskell wikibook is doing, or just do anything other than sit down and concentrate. What a pity, because in the medium term, reading is extremely rewarding, you know that great feeling you get when you actually understand something and see how it fits in with all the other stuff? Yeah, I'm not even talking about reading being good for you (faut se nourrir scientifiquement); just in terms of sheer pleasure, reading can be loads of fun... but only in the medium/long term. You have to fight yourself over the short-term i'd-rather-be-doing-something-else hump.

the notes

Lexical choice is all about associating concepts to words. Not an easy job. First of all, you're dealing with a many-to-many situation; one concept could map to several words and vice versa. Choice is also subject to constraints from many sources: syntax, semantics, the lexicon [e.g. collocations], the domain [words have different meanings in different fields], pragmatics. Having a pipeline architecture for your lexical chooser isn't a a very good idea either, because the constrains are multi-directional. Syntactic constraints could affect semantic ones, etc. Another thing which makes this job tricky is that some constraints can float - appear at different levels in linguistic structure. Note that generation algorithms only handle the easier "structural" constraints, which are consistently expressed on a given linguistic rank.

where do you do lexical choice?

The article argues that lexical choice should be an independent module between content specification and syntactic realisation. Those of us working with reversible grammar generators tend to do it as sort of "by-product" of realisation. So the SFG people (although they handle their semantic constraints during content specification; e.g. their realiser input already has the semantic stuff figured out -- but wait don't we as well?). Arguments why this is not the best way to do things are

1. limited range of possible constraints -- they doubt that pragmatic constraints can be taken into account for example
2. hard or impossible to deal with floating constraints (need "global knowledge of interaction between semantic units").

There's also a paragraph after this that shows why just doing it as part of content planning is a bad idea (combinatorially expensive? need to read more carefully).

so what does a lexical chooser do?

Eh... we're supposed to go have drinks or something. Guess I'll have to pick this up tomorrow.

more reading

Wading through elhadad1999scp and now elhadad1997fcl. Again, both are quite written, but it's just a lot of material to absorb in a couple of days. Reading is hard for me, not quite as hard as writing, but you get the same trouble forcing yourself to concentrate, and not wander off to check your mail or something. Feeling kind of woozy. Got three sources of confusion here:

1. Specifying processes in terms of transitivity or "lexically" with subcat features -- how are they different really? is one finer grained than the other, for example? What are the implications?
2. Role of a lexical chooser vs. a syntactic realiser - seems like GenI is trying to do some of the lexical chooser's job, but not all of it. We seem to be what elhadad1997fcl describe as what traditional reversible-grammar based generators do; have a lexical chooser component that's part of the syntactic realiser. Our lex chooser seems pretty poor wrt to theirs; we allow for less paraphrastic power, less non-determinism; but is it ok for us to say "well, that's another module's job"? What kind of syntactic constraints is the lex chooser supposed to handle. What's the division of labour between the lex chooser and the syntactic realiser? It's all in the papers, so I probably just need to reread and digest for a bit
3. Sub(sub)grammar hiearchy vs. systems - these are supposed to be orthogonal layers of organisation. How? Certainly not redundant information?

Je suis analphabet.

mostly reading

Mostly just reading and thinking about elhadad1999scp, intro to SURGE. Nicely written. I say that because I go through the thing without going HUH? And writing something that people can do that with (without treating them like idiots or just being a vapid fool) is fricking hard. I'm going slowly though because I still haven't figured out how to tune out distractions or not just wander off and do something less boring, like check my mail.

transitive lambda

Other than that, a friend was asking me why transitive verbs get such complicated lambda terms, something we had seeen in class a while back. This is the kind of thing you learn once, go "ahah! neat!" and then forget. So, it's always fun to sort of reconstruct it. The way I like to think about is with types. Here's the low-down in Haskell notation.

john walks

walks :: E -> T
walks = \x -> _WALKS(x)

john :: (E -> T) -> T
john = \v -> v _JOHN

Now if we do functional application, everything works (uh, being sloppy with my notation here):

john $ walks :: T -- yes! (btw, result is _WALKS(_JOHN)

john loves mary with a stupid transitive verb

mary :: (E -> T) -> T
mary = \v -> v _MARY

stupid_loves :: E -> E -> T
stupid_loves = \o s -> _LOVES(s,o)

mary $ stupid_loves :: TYPE ERROR!
-- mary was expecting (E -> T), but got E -> E -> T
stupid_loves $ mary :: TYPE_ERROR!
-- stupid_loves was expecting E, but got (E -> T) -> T

If you want to get a feel for why this blows up, try something like "john loves every_woman", where

every_woman :: (E -> T) -> T
every_woman = \v -> _EXISTS(x, _AND( _WOMAN(x)
                                   , v(x))

If we magically removed type-checking, and managed to apply (every_woman $ stupid_loves) you'd get something weird and useless like

_EXISTS(x, _AND( _WOMAN(x)
               , \s -> _LOVES(s,x))

Try it the other way 'round too. Just as ugly.

john loves mary intelligently

smart_loves :: ((E -> T) -> T) -> E -> T

-- yuck... maybe...
type NP = (E -> T) -> T
smart_loves :: NP -> E -> T
smart_loves = \npd s -> npd $ \o -> _LOVES(s,o)

mary$smart_loves :: E -> T -- yay! just like an intransitive verb!
john$mary$smart_loves :: T -- double yay!

more reading

Same old warning. This is just my (mis-)reading of the article. Opinions here are neither mine nor those of the authors. Rather, they are my understanding of the authors' arguments.

mccoy1990uta

why TAG for SFG

The paper begins by motivating TAG as the structural basis for systemic grammars (uh, did my sentence make sense?). SFG is great; it gives us a semantics-oriented view of language (function over form) rather than syntax-oriented one (form over function). The problem with SFG is that not enough attention is paid to the syntactic nitty gritty.

Sentences are built by accretion: when your functionally motivate something piece of language, you thrown it out into the pool and glom it on to whatever structure you are trying to build. This works rather poorly when you get fancy sentences, for example, with discontinuities. Consider "It was Mary that John thought Bill liked", for example. Said sentence can be thought to be made of bits like "Bill liked Mary" and "John thought...". SFG does not provide a mechanism for that Mary to be extracted or for that "John thought" to be "spliced" into the sentence, so what you get is the situation:

possible - John thought it was Mary that Bill liked
impossible - It was Mary that John thought that Bill liked

There is a mention in this paper of some independence criterion, some principle of grammar design that I haven't completely absorbed yet. It goes something like: "realization of different independent functions do not influence each other". I guess the point is that you should be able to pick out the "It was Mary that Bill liked" and the "John thought" without caring about the relationship between the two components... (for example, "John thought Bill liked Mary")
The reason why TAG is a good choice is because it gives us exactly the splicing operations we need to combine language fragments together. And because we have the right tools (adjunctions), we can design our grammars the right way, the clean way, the respecting-the-independence-criterion way. It's a choice between (1) getting it wrong (2) using dirty hacks, or (3) the best option, splicing.

It's not all about the adjunction, either I guess. The whole extended domain of locality thing is pretty big, having self-contained trees that express basically everything you need to know about a structure. But then again, having that only makes sense when you got the adjunction. Or something.

how S-TAG works

You got a lexicon, tree groups (tree families?), and trees. A key quote from the paper might be

Rather than building up structure only when we have enough evidence to know that it is correct (as has previously been done), our operation can be characterized as deciding between syntactic possibilities that are consistent with what is known at the given point in the network

Argh, now too tired to post anything substantial. Basic idea seems to be (1) pick your lexical item (2) pick a tree group/family (3) pick a tree out of it.

other than that

More discussing and thinking about the selection stuff. Think hard and all that.

reading day

Let's see here: upgraded the toolbox chez Claire, observed some small bugs, more or less got things running.

Now focusing on learning about input specifications, with a bit of hand holding because I said I was scared and didn't know how to do this kind of stuff well. We're going about this in a highly controlled fashion, first focus on the TAG-based systems. So I compiled a list of TAG generators and their basic characteristics (a whole bunch of ??? because I didn't really grasp the details very well). I then zeroed in on two SFG-related systems, Mumble (mcdonald1985tgf) and the mccoy1992uta stuff. I really appreciate the hand-holding here. After two years of this, I still haven't figured out how to use the literature effectively. This is a really good chance to practice.

Here are my notes for today. Keep in mind that these are Dumb-Eric-Doesn't-Know-How-To-Read notes, so you shouldn't try to use them for any of your work. It'll probably set you back more than anything else.

mcdonald1985tgf

This is about MUMBLE, what seems to be a surface realiser. In they paper, they say that they are mainly talking about "(3) realizing the specified information and rhetorical intent as a grammatical text".

mumbling about sfg

It turns out that this stuff is not so much SFG-based, but SFG-inspired. The article claims that they use the same information as you would find in a systemic grammar, just "bundled differently". They say that in a systemic grammar, you've got five different things being encoded

• dependencies among structural features - some choices constrain others: e.g. main clauses must express tense/modality, but subordinate clauses must not
• usage criteria - uh... ok
• coordinated structural alternatives - e.g. active vs. passive
• efficient ordering of choices - no choices made unless required, no choices made before its dependencies are settled
• typology of surface structure - huh? i do like the "almost by accident" phrasing though

realisation specification

Here's an idea of what the linguistic component (i.e. mumble) should be receiving as input: a text plan, aka a "realization specification" (see Figure 1, page 97). The input has three kinds of symbols:

1. particular features of the utterance - (:event-require-certification-as-to-source)
2. content items of the specification (main-event ...whole bunch of stuff...) - big structure
3. information units from the knowledge base ().

The paper also talks about recursive planning. So, wait, I guess their realiser is actually a combination sentence planner-realiser? What MUMBLE is not doing, is "(2) planning what information content and rethorical force will best meet those goals given the conext" [uhh... text planning?], but I guess they've got a good healthy dose of sentence planning in there. Fine. Tactical generation. Or something. I just don't have a good idea how all the pieces fit together yet.

thee guts

I really don't get this part. Seems to be talking about how they map functional bits (SFG inspired, remember) into TAG trees. Whenever there are "alternate choices" to be made, such choices are grouped into "realization classes" (Figure 3, page 98).
Realisation classes map "desired characteristics" [e.g. mentioned-elsewhere(agent)] on to "choices" (raise-VERB-into-PROP). One seemingly important thing they point out is that where as SFG requires you to make the selection of linguistic features incrementally (uh... efficient ordering of choices), their system lets you do it simultaneously. No networks; just pick alternatives from each one of the classes you need to choose from.

Somewhere in the system, there is an association between each "choice" into TAG trees. I don't really get how this maps exactly, but there is some association between the choices and the actual TAG grammar. The paragraph between Figures 4 and 5 confused me. What constraint? What parentheses? Huh? It's probably just me not reading things right, though. Another I didn't understand too well was this business of attachment points. Attachment points are sub-components of the "choices". Once you make a choice, you get its attachment points, and that tells you where you can insert specific information units. Seems like choices tell you what trees to select, and attachments tell you how to put them together. Or something like that. Ugh... will need to read this again to get a better idea.

mccoy1992fag

I kinda liked this paper, although I didn't read it deeply enough to achieve grokkage. The main feature of this paper is its clarity. You don't so much go "huh?" as "ok, I think if I sat down read more slowly, I would actually get it". Paper seems to go like this:

1. generating from logical forms is nice and all, but problem is you don't know which paraphrase is the right one
2. mumble 86 goes beyond logical forms
3. here's how Mumble 86 works
4. here's how we're (systemic tag) are different
5. here's how we work

mumble according to McCoyEtAl

The input is an LSpec (Linguistic Specification), basically a set of logical forms. Mumble uses a dictionary mechanism to associate LSpec bits to elementary trees (oh, that's all? just look stuff up in a table and spit out the corresponding elementary tree?). It's just recursive descent. You pick a tree for the initial sub-piece; you traverse the tree in a set order; whenever you hit an attachment point ("a palce where new information could be added into the evolving surface structure - what, a subst or open adjunction site?"), you grab look up the corresponding bit of LSpec, grab its elementary tree (dictionary, remember?) and plug it in (adjoin, substitute). The paper has some complaints to make about Mumble:

1. no distinction between decisions made for functional vs. syntactic reasons (makes it hard to hack/maintain the system)
2. syntax driven - as opposed to... function-driven?
3. strictly left-to-right processing makes it "problematic for generating some connectives"

how these guys are different

1. this system is much more based on SFL, as in they actually use system networks
2. not syntax driven, but "follows a functional decomposition called for by the systemic grammar"
3. clean separation between syntactic and functional bits
4. no constraints on LF (mumble makes some assumptions... nothing I deeply understand yet); they can read the same stuff an SFG generator would
5. can do standard SHDGA

how it works

The system can be broken down into two phases, a descent process, which traverses the SF network and picks out the elementary tres we want, and a ascent process which combines them together (SHDGA?). I'm not sure I understand the stuff about regions though. Every region is associated with one tree. When traversing the systemic network for one region, you can sometimes spawn sub-regions. In every region, you go through the same flow (I really liked Figure 7 of this paper... it gave me a good feel of things for not very much headache):

1. traverse a functional network - this gives you a set of features
2. traverse a TAG network (using said features as input) - this gives you an elementary tree

Traversing these networks can spawn subregions (which go through the same flow), but it seems the input to these subregions comes from the parent traversal: the functional features collected, and the elementary tree selected.

I suspect the ascent process is pretty run-of-the-mill (the fact of which is actually quite exciting, imho). Two keywords I need to reread the paper for are "mapping table" and "fr-root". Was skimming, so I didn't really understand what those are for. The ascent process, that's all I got out of it.

crap code

Today rated relatively high on the fun scale. Had an interesting discussion with Claire about where we want to go in the next month, plate full, sense of direction locked into place. Mostly hacking up GenI, correcting the way we build derivation trees. The way I currently have in mind is to propagate the elementary tree name to each node so that we can track the adjunctions properly.

Just talked with Yannick about GenI output... and you know, I think he's right: GenI should be able to do morphological processing. I don't have to go as far as to do fancy things with transducers; just a simple lookup and unify should do the job. To make it even simpler, I can also pretend that ambiguity does not exist, just systematically pick the first result. This would make evaluation so much simpler, and we wouldn't have to walk around with all those annoying lemmas all the time. I guess I just had a blind spot to it, just thinking "aaack! morphology, farm it out!" So I guess I've got a new project on my end. Implement a simple morphological generator for GenI. By simple, I mean "looks it up in a table". Not going to be a high performer, just going to be good enough to help us evaluate our parsing-generation loop. So thanks, Yannick.

Hmm, what else to report...

Well, my code is crap.

After leaving the GenI code alone and coming back to it, or rather, wading through it, I get the feeling that I'm really a pretty crappy programmer. How hard is it to do something clean? To write code that you yourself can read, much less to say somebody else? Can you imagine that? I have been programming computers for 18 years now (though the first 10 years of that maybe doesn't count, all those lines of BASIC! all that self-taught mish-mash C/C++) and I still produce crap. I wonder how many more years I'll have to code before I can write something, and not come back to it 12 months later, going "yeck".

hmmm...

That's odd. I have the vague feeling that I was relatively productive today (though still not getting to work early enough), but I don't really remember what I did. Figured out how to do http authentication with a darcs repository. Started reading some SFL stuff. Gave Claire and Yannick a hand with some missing lexical entries. Fixed my KPML parser. Talked a lot with a Masters student, giving the traditional how-to-be-a-PhD-student (as if I knew what I was talking about).

sfgtools

I'm still not back in my work-rhythm -- amazing amount of laziness and inertia to overcome -- but hey at least I'm coding. Let's see, I spent today upgrading software on my machine, preparing the latest GenI release (might as well), talking to some guy from the MI who might be taking over custody of the loriawiki (yay!), getting lost in a talk about minimalist grammar, and hacking up some SFG tools. I've got a little extractor script (Haskell, Parsec) that prints out all the statements, and now I'm working on a little script to group them into trees.

Composing functions together is such a fun and fast way to program. All those little Perl scripts I used to write, half an hour here, half an hour there become something like one minute here, one minute there.

interact $ dropWhile null . map dropParens . sort . nub . lines

Voilà. It's like those Linspire guys say: "when we code in Haskell, we go home on time"

new blogger

But does it publish using my email address?

timetable

Met with Claire this morning. I'm still really bad at meetings in that I'll occasionally just sort of ramble on about something without actually thinking if it's worth hearing, or the right time to discuss whatever it is I'm going on about.

Anyway, Claire seems to think that finishing this year is doable and worth trying. Here is the timetable she proposes:

1. mid feb - chapter 5 (paraphrase selection)
2. end feb - chapter 4 (polarity filtering)
3. end mar - chapter 1 (intro, surface realisation task, positioning, we focus on reversible grammar side of things)
4. end apr - chapter 2 (TAG and surface realisation)
5. end may - chapter 3 (main issues in SF; the stuff I've been working on, i.e., search strategy, chart generation)
6. end jun - chapter 6 (evaluation)
7. end jul - chapter 7 (generator as grammar debugging tool)
8. mid aug - conclusion, introduction
9. 15 sep - version française; print out and bind some copies for the école doctoral
10. 18 sep - final version of the dissertation
11. 15 nov - defense (must be no later than 15 nov)

Note that the I-need-a-month-to-write-VF thing is me just worrying. I might be able to get help from my francophone friends, but there is a slight question of pride (oh dear) and wanting to at least try to be a big boy about it, even if it means having whatever I wrote be torn to shreds so that it actually sounds like French and not English with French words in it.

Anyway, so we're setting aside the state-of-the-art stuff for now. Come back to it in a few months when all of this has ripened in my head. Maybe if we have free time between the writing I'm supposed to do and the actual research bits I can try to move forward.

aujourd'hui

Didn't do very much today other than that. Looked into some SFL stuff, trying to learn more about realisation statements in systemic grammars. Cobbled together a GenI release just so we can update the rapport d'activité (well, it's also a good time to just say "here is the last working version"). Tidied all my project support materials, did a lot filing. Probably a wise strategic choice. I was too tired to do anything intelligent.

Hacking up my SFL browser so that I can output just the realisation statements from a bunch of systems. Maybe this will be useful.

blocked (words: 12939, pages: 17)

Trying to explain the CKY algorithm, do it nice and simple. My basic plan is something like this:

1. explain cky
2. now step back and dissect tabular parsing, break it up into a bunch of individual techniques
3. talk about generation stuff

I hope I'm not just wasting my time. Spent most of today just blocked. Worked on the easy stuff like looking up entries for the bib, putting together my CKY table and the pseudocode. Just need to plug in a couple of paragraphs or so.

marginally more productive

I'm not sure what I did today. Got here in time for lunch (yay, before noon!). Spent many hours trying to avoid work, although a good chunk of those was spent using the GTD method of procrastinate-by-doing-something-constructive (e.g. setting up a dentist appointment, doing DDTEFP crap). I worked a small visualisation of subtree sharing vs. packing within the CKY algorithm (for the longest time, I couldn't understand EdC's pseudocode, but then the stupid just washed away and i got down to work). Sent a mail to GN to confirm that the uniform architecture does subtree sharing and not packing, which took a little bit of guts on my part. Sent a mail to JB to see if he's got the French SFG or not. Stared at my thesis a little bit more, looked at the Kay chart parsing notation, made sure I understood that.

Tomorrow, I have no choice but to write.

I think one of the things that was gumming up the works was that I was really hoping to use the Kay notation once and for all to explain CKY, without actually being sure I understood the notation. Now that I have a better idea, I think I'd better stick with the table stuff.

first (half) day in the lab

Ugh. I don't really want to be here. Well, work feels better than vacation anyway, but it takes a while to get used to again. Spent today doing admin stuff, talking to Claire [mostly saying hi]. Set up an appointment for Friday to explain the difference between subtree sharing and packing. Worked out a short visual description, three pictures showing parses for Mary saw the boy with the telescope without any sharing or packing, with just sharing, with sharing and packing. Not doing crazy things with graphs or arrows, just re-writing the chart items or using pointer numbers because it's just so much more readable that way. I really don't want to be here.

sigh...

Home at my parents' place. Week 1 has been hanging out with family. Week 2 has been almost pure procrastination. Well, the first half was getting rid of non-work actions that had been piling up. But the last few days have consisted of simply resisting work. I can never work when I'm in Jax. Can't really figure out why, maybe it's just being home in general. But all I can seem to motivate myself to do is have a snack here, a nap there and a sudoku (or solitaire) game from time to time.
Partly a problem of poor definition: I haven't sat down and figured out exactly what it is I'm supposed to do. The problem there, I suppose is also that I'm fighting the very act of sitting down and thinking about what I'm supposed to do.

Let's see... on the plane, I read delaclegerie2006dtp (the esslli course), though I started getting lost when the automata started getting fancy. Also read nederhof2004tp and alonsopardo2001tat. The three texts belong to the same family of tabular parsing work (note the co-authorships and repeated themes). If I can remember the gist correctly, (actually reading the alonsopardo2001tat abstract): the idea is that there is a concrete way of separating your parsing strategy from your control strategy, this isn't the same thing as me saying they are orthogonal and just sort of hand waving my way around the details. These guys actually deliver the goods: you treat parsing as the construction of a non-deterministic automaton. Your parsing strategy can be expressed as a set of inference rules that discover the transitions in your automaton. On the other hand, your control strategy -- the tabulation bit -- consists of generic memoisation techniques for automata. Or, err... something like that. As you can see I've not understood things very well yet. My rough impression of this is that we now have something very modular on our hands. All the tabulation stuff is cleanly separated from the parsing stuff. I also get the impression that alonsopardo2001tat is worth a re-read or two. It looks scary at first with all the symbols and rules, but if you go real slow, and give yourself time to digest it, it actually makes a lot of sense (i hope! I think I'm still struggling with the tabulation itself).

So that's where I am: that's the most productive thing I've done this week, writing this blog entry. I should have realised that this was the next action: summarise your airplane reading.

Guess the question here is where do I go from here: do I invest more time and energy trying to understand this parsing as automata stuff? Shouldn't there be little gears turning in my head trying to see if there's anything to be said about the relationship between (polarity) automata as filters and automata as used for parsing? Or should I just knuckle down and get back to trying to write my tabular/chart parsing stuff? I'm just afraid of finding myself down a rabbit trail.

sub-tree etc (words: 12447, pages: 16)

Let's see:

1. Rearranged the tabular algorithm stuff - first we talk about tabular parsing, just parsing, and only then do we worry about generation.
2. Wrote the sub-tree stuff
3. Started writing about local ambigiuity packing
4. Made a sort of conclusion transitiony thing in the search strategies section
5. Switched to jqt1999 bib style (which shows the whole author name, thus making things more readable

Also goofed off a lot this afternoon. I wasted two hours playing around with the Haskell wikibook when I should have been plugging away. Oh well. I seem to have made progress anyway.

ten kilowords! (words: 10376, pages: 13)

But I'm still deeply dissatisfied with my progress. One, come on... this is slow as crap. Two, it's ten k-words only because I'm a lousy writer, verbose and rambling instead of concise and to the point. Arrrrrrrghhhh.

Halfway through the indexing stuff. Got kind of stuck, because I realised that in order to explain the uniform indexing mechanism in neumann1994ucm, I had to talk about active and passive edges. Spent a good chunk of time rewriting my subsubsection on edges.

Other things is that I have (re)renamed the chart parsing section to tabular parsing. Let's try not to change my mind again. I'm not doing this for aesthetic reasons or anything. Just trying to find the most accurate term.

Well, ten kilowords. Now what would make my progress suck less is if I managed to wrap up the chart stuff tomorrow: talk about kay1996cg's indexing mechanism, talk about subtree sharing, and finally local ambiguity packing.

So slooooooooooow.....

Oh! I forgot to mention. Yannick suggested I take a look at EdC's ESSLLI 2006 course on tabular parsing. Seems to be exactly what I was looking for. Merci, Y.

some insights, random writing (words: 9642, pages: 12)

Ok, I just punched out a pageful of what might be filler re: why chart parsing matters and what an edge is. Hmm... but I'm not sure it's very useful. It seemed to make sense at the time, but so do many bad ideas. This morning, I had a valuable ah-hah moment when I read that sub-tree sharing and packing are two different ideas (see tomita1987eac for details). Nice! This was the thing I had be suspecting all along, sort of the reason I had been confused over all this indexing and packing stuff, this business with equivalence classes. Felt like there was some missing link somewhere. And now I've pinned down one of the sources of confusion. Looking at neumann1994ucm, I get the impression that he does sub-tree sharing and not packing. Will have to send him a mail to see what he thinks. (/me feels shy).

Today, I did something slightly silly. Somehow managed to convince myself that there was this difference between tabular parsing and chart parsing, that chart parsing could just be seen as really advanced tabular parsing, where in my head, tabular parsing was just the idea that you store intermediate results instead of not backtracking; and that chart parsing was when you started layering on the clever stuff: using pointers instead of copying subtrees, and doing packing. Don't know how I got that idea. Think it was a silly conclusion I leapt to from the structure of a neumann1994ucm chapter, where the title was something like "A Tabular Algorithm" where he builds up a tabular algorithm with blocking and agenda-based control, and then only later on in the game, introduces indexing (one mechanism of which is the chart). I made a silly connection of dots, oh, chart parsing = tabular parsing + charts, and proceeded to start writing a bunch of stuff (it all seemed oh so clear) motivated by this distinction. I was going to have two sections, one for vanilla chartless thing I called tabular parsing, and another for chart parsing proper (it made sense at the time). But now I appear to have been full of crap. Somewhere found my way to an article like alonso2001tat, where you get the clear impression that, no (smack self upside the head), "tabular algorithms" is some technical term, tabulation refers to something specific that I clearly was not talking about. So I need go away and read some more and come back with a clearer understanding of what we mean by tabular.

Gah I hate that: first you get the feeling that FINALLY you see how all the pieces fit together, and you're all happy... then you (re)read some article and realise that uh... no... actually you don't. You don't understand anything.

state of the thesis 2006-10-31

Not much to report for this month. I spent the whole time reading intensively (by my standards) about search strategies and chart parsing, most of it motivated by trying to understand something solidly enough that I could write about it without this nagging self doubt in the back of my mind (wait... do I really believe that?). The month has been a long struggle to convince myself of some very basic things. I have produced a total of 10 pages (that's 11 minus bibliography), which is rather pathethic, especially considering that I'll probably have to toss in all in trash when it's been looked over by somebody else. Next month, I'll be back home... hoping desperately that I can be productive without being in an office.

agenda stuff written (words: 8772, pages: 11)

Ok, I think I have a more solid grasp of the agenda based control in shieber1988uap. Embarrasingly enough, part of my problem was that I was confusing my search tree with my syntactic tree. (Stuuuuuuupiiiiid), so of course breadth first and depth first didn't quite mean what I thought they meant. I was having trouble seeing where the non-determinism comes from because all I could see was that the order of edge availability was pretty fixed (i.e. you have to predict foo before you even have the choice to complete it). But now I see more clearly that all this just refers to syntactic ambiguity. If you FIFO, you explore the ambiguity first (breadth-first); if you LIFO, you explore the current tree first (depth-first); if you go prediction-lex-etc-rightmost, you get shift reduce (note that the shift reduce thing, the prediction rules first thing is kinda important for seeing it work).

working algorithms out by hand

Working this out has made me rediscover by old bag-of-tricks of working out algorithms from when I was still taking classes. I like this kind of stuff, algorithms for human beings. Basic point is, don't waste your time; just focus on the interesting bits.

Trick #1: Use the simplest phrases you need to illustrate the point:
Bad : The man saw the boy with the telescope
Good: Bob saw the boy with the telescope

Trick #2: Compress your phrases unless they really illustrate a point.
Bad : 0 Bob 1 saw 2 the 3 boy 4 with 5 the 6 telescope 7
Good: 0 Bob 1 saw 2 the 3 boy 4 with-the-telescope 5

Trick #3: Use first letters; choose your words so that they unambiguously correspond to a first letter (seen in neumman1994ucm)
Bad : Bob saw the boy with-the-telescope (b s t b w)
Good: John saw the boy with-the-telescope (j s t b w)

Trick #4: Pare your grammar down to the minimum possible. Refactor mercilessly?
Bad:

NP -> PN
PN -> j

Good:

NP -> j

Here's what I use for John saw the boy with-the-telescope:

S  -> NP VP
NP -> j
NP -> t b
NP -> NP w
VP -> s NP
VP -> VP w

Trick #5: Assume an oracle that can tell you if an edge is going to lead you to a dead end. If the oracle (i.e. a human being, i.e. you) tells you the edge is useless, dump it toot sweet.

Trick #6: Don't worry about order. Use order to represent things going into the chart. Use check marks to represent the order that they get removed from the agenda. No need to write things down twice, what.

unproductive afternoon

Was pretty good this morning, painstakingly working out the differences between the three variants shown in shieber1988uap. Now need to write about indexing and packing, although have some ideas still mixed up in my head. I was really hoping to make 10 kilowords by the time I headed to the states. Oh well. Guess it's not very likely.

short day, cabalised

Very short day. Was helping a friend move from 09:00 to 15:00. Spent some time chez moi lazy as hell even though I didn't actually do very much (tidy up a desk, etc). Spent about 2 or 3 hours at work, mostly goofing off - realised that while I get the rough idea of parameterising your algorithms by changing the data structure of your agenda, I don't see the concrete mapping between the structures and the algorithm behaviour. Another one of those moments where you think you understand something, and then when you sit down and you actually try to write it up... HUH?

Other than that, at home, I noticed on the tutorial How to write a Haskell program that Cabalising your software is VERY VERY easy. It took me less than ten minutes. So you have no excuse. If dumb eric can do it, so can you. Just copy the templates from the wiki, open up the cabal docs when stuck. I'll post a link to my Cabal file when I have pushed the patches in.

lazy eric (words: 8564, pages: 11)

Got in late, and sort of bummed around today. But I think I understand the agenda-based control stuff better.

progress in the morning (words: 8198, pages: 11)

Had a little bit of clarity this morning and was able to move forward a little bit on the chart parsing stuff. Managed to think myself out of a little bit of confusion about subsumption based checking and restrictors. Part of me was thinking "gee: wouldn't subsumption based checking make restrictors sort of unnecessary? Because you can block an infinite looping prediction just the same way you avoid left-recursion for context free grammars". Then I sat down and thought about it for a while, and noticed that people who talk about subsumption based checking also talk about restrictors, so that can't be it [He's a slow one, the eric], and then though about it somewhere and realised that (A) i'm an idiot (B) you still need restrictors, because with unification grammars, it's always possible to make infinite looping predictions which don't have a subsumption thingy. Take your basic subcategorisation list for example. It's sooooo simple: X does not subsume Cons foo X. End of discussion. So hey, at least we got that cleared up. I get the impression that for anybody else, this kind of thing would have been like "no duh, obvious!". In fact that's all I've been doing the whole month. Getting stuck on some stupid question that I don't even know how to formulate, and when I finally get around to putting my question into words, thinking about it really hard (sifting through papers very inefficiently, trying in vain to find a response), finding finding the answer, and then saying "golly! that should have been self-evident". Yeah, that's the issue, see? I spend a lot of time worrying about the self-evident.

Now the thing I'm cracking my head over is agenda based control. I've grown up with agenda based control, and it's very hard for me to imagine a world without it. Sure, I could talk about using the agenda to make your control more explicit and easier to parameterise, but what I have a hard time doing is wrapping my head around what exactly an agenda buys you besides this. Like, really, what's the alternative? The Prolog NLP course has been helpful for this once more, in that here I see an agenda-less parser. But the thing is that I don't want to mix up the notion of passive/active items with the agenda or no agenda. It's really a matter of dissecting everything, making sure I understand really what all the pieces of the puzzle are, and precisely what happens when you do away with them. What worries me is that all this stuff is just simple undergrad to first year Master's stuff. As D once said "it took you two days to figure out left corner parsing?"

So I'm slow. Very slow. I do eventually get things and understand them well (I hope), but it takes me next to forever.

feeling better (words: 7520, pages: 10)

Feeling slightly better about the whole thing. Not making real progress yet, but (1) I actually got enough sleep last night, which is new for the past couple of weeks [been bad and not forcing myself to bed despite tiredness] (2) I think I can finally move on to talk about chart stuff instead of just search strategies. Wrote the first paragraph of the chart stuff. Mapped out the rest of it, plopped down the ideas on paper. Didn't get much else done today. Short day, off to get my carte de séjour.

recul (words: 6722, pages: 10)

Not really getting anywhere today. Going backwards even! This morning, I commented out all the stuff I felt I haven't really written, you know, the big gob of drool falling on your keyboard thing. So that lost me about a good kiloword. Been slow going today. I have once again rearranged the bu/shdga stuff, realising how silly it was of me to want to elaborate on all this bu stuff in shdga land. Excellent strategy for confusing the reader, good job! Took me a while to understand the empty head problem well enough to write about it. Just going with vanilla shieber1990shd. Am going to need some hand-holding on the German or Dutch grammar though, cuz I want to use a smaller example that they gave, really just nothing more the mininum you need to show the verb movement stuff.

Speaking of shieber1990shd, I just realised that what I've been calling shieber1990shd is in fact shieber1989shd, a similar but ever so slightly different article. Oh it's more or less the same thing, though everybody seems to refer to the former and it has a little bit more stuff, e.g. a discussion on the empty head stuff. It was funny, yesterday I was so confused because gerdemann1995sop talks about some example in shieber1990shd, and I'm like "what? where?" Oooooohhhh, now I get it...

This is quite discouraging. I've been en rédaction since forever, which btw translates to 2006-10-03. This puts me at a rate of 420 words (or 0.6 pages) a workday. I hope the only reason I'm going so slow is because that's the price of actually trying to understand things well and not just me being stupid or something. I hope it's just a small hurdle to slog through, that the rest of it will go faster, that everything will just suddenly make sense, like that one day that everything clicks and you suddenly know how to ride a bike. Cuz otherwise, this sucks. Well no, it's kinda nice when stuff that you've been hazy on for so long starts to clear up... yeah that's not so bad... but it's the excrutiating slowness of it all, that huge chunk of "huh?" that hurts so much.

crawling out? (words: 7226, pages: 11)

Spent this morning rearranging the bottom-up stuff, moving a good chunk of the discussion to the end of the SHD stuff. It feels a little bit more solid, both sections. What I'm stuck now on is a little discussion on the drawbacks of SHD. I'm not sure I really want to be digging out examples in German, or if I completely understand the gap/filler stuff, much less to say the movement stuff. Haven't really sat down and tried hard to understand the type raised functors. Maybe now is a good time to set this aside and move on to chart generation... I guess I sorta have some sense of closure now that the bu stuff is in a semi-stable state.

Anyway. I'm going to head home early. I think one of my problems is just being tired in general, so perhaps a good dose of doing nothing every night and then going to bed early might make me more productive. Think I've been sticking around just to go the canteen because I'm too lazy to cook, which is kinda stupid. Should probably get into the habit of making huge amount of food over the weekend and then just heating it up over the week. I'd get to have my rest and my laziness too.

not very productive (words: 6174, pages: 10)

Nah... I spent most of today goofing off. Redid my "discovering a syntactic tree" diagrams so that they are clearer and quieter (and added a bottom-up tree). Tried to rearrange things so that the bottom-up stuff was clearer and had a more cohesive narrative structure. The problem with trying to jump down to the chart stuff is that I don't have much of a sense of closure on the search strategies stuff, don't feel like it's in a state where I can leave it alone. Don't be fooled by the high word count - a lot of it is just random gibberish at the end, just me jotting down some things I might like to say about the chart processing.

Not very disciplined. Blew a good chunk of time just watching TED talks online and staring out into space.

it's just not working today

Nope.

I think I want to give up on writing the td, bu, shdga stuff for now, move on to chart parsing and go backwards. Part of me wants to scrap the whole lot and just start over, whole new approach. Problem is that I'm trying to build this up chronologically, which maybe made sense 10 years ago when all of this stuff was still fresh and in context. But now, 2006 I should maybe step back and lay it out differently. Here are the basic points: (1) you want an approach that combines goal-directedness from top-down processing [i.e. get your logical form as instantiated as you can] with immediate exploitation of lexical information from bottom-up processing. I can't quite argue the goal directedness stuff because I just don't have the practical experience and can't poke at the algorithms in my head to see how they would behave in real life (2) you want a head-driven approach for generation instead of left-to-right ordering. LR sort of works for parsing because you're constrained against your input string, but in generation, you don't have an input string, so you're just going to sit around generating stuff you don't even know if you can use. A head-driven approach makes more sense because the semantic heads have their semantics already instantiated, meaning more stuff to constrain against. More variables given nice constant values. I can sort of see this intuitively, but I can't argue it convincingly either (3) you want memoisation (chart) instead of backtracking -- or maybe not, some people have complained that charts are useless for generation. I need to find these arguments and understand them, and then see how they fit in the other research.

There is so much going on in the chart stuff

• Storing of intermediate results - that's the big thing, forget indices, agendas, passive and active edges, whatever. The one big thing is that you've got your intermediate results stored somewhere and you're not recomputing them
• Indices as comparison constraints -- this is only a big deal if comparing items is expensive (which it might be, say unification). The whole point about indices is that they give you an instant answer, yes or no, I can try combining these two items together. You don't have to actually try it to find out. An NLP newbie [wait... I'm an NLP newbie...] might look at this stuff and think "oh, ok, array lookup is O(1) instead of list lookup O(n)", but that's just not all that important.
• Equivalence classes - packing. These two items can merge. The consequences of packing can be sloppy - you could use it to combine two items that really DON'T have any business going together, but that's ok, because you can always verify it during the unpacking phase (analogy: prediction over-predicts and is cleaned up after by completion)
• Subsumption based blocking -- I had written this down, but it sort of seems the same as packing
• Active vs. passive edges -- I had written this down, but it sort of seems the same as indices as comparison constraints
• Agenda based approach - the ability to adjust search strategy just by changing the way you put things into the agenda and take them out

I really do not understand this stuff as well as I should, i.e. know it cold. For example, I'm still not sure I understand the relationship between chart and search. I understand that you can layer a chart onto any search strategy and make it better, but I also get the impression that somehow this matters more for some strategies than others. Like for a top-down approach on CFG: using a chart is the difference between life (bad) and death (termination, that's good). As for GenI, we combine all items together anyway, so unless you do something clever which involves NOT allowing all comparisons (substitution before adjunction, eh?), it really doesn't seem like your search strategy matters all that much. Keep in mind, we're just pacmaning our way through the items. No crazy recursion thingies going on here (unless you have empty sem), just "destructively" combining our way down. But there must be some link. Maybe I can see it making sense if you only want one response, because then you try to order things so that you get a response early and stop (hopefully the best response). But if you care about paraphrases, it seems you're exploring stuck with exploring the whole search tree/graph anyway.

I feel like such a fraud. It's so different writing for a blog, than say, your PhD thesis. You can just randomly assert stuff because you feel like it and nobody even notices. Trying to write something serious, something that you yourself are convinced by, wow that's hard... that's where you learn that you're an idiot and you really don't just don't get it. They say that perfectionists are the worst procrasinators... yeah fine I believe in "shitty first draft" theory too. But this isn't creative writing. This isn't about getting the words to fit together right. It's about not getting the basic facts down and that's the stuff I'm mired in. I can't shitty first draft my way out of that!

Haven't fit all of the pieces together in my head yet. Only thing to do is keep reading and talking to people. Find the right stuff to read, the right questions to ask.

going home early (words: 5532, pages: 9)

Wrote a basic description of SHDGA, and some discussion regarding why we see the shieber1988uap algorithm as primarily bottom-up. It's not all very solid, but in any case, moving on past the Earley stuff and straight into SHDGA was a useful way to make a little progress. You write some head-driven stuff, think about it some more and then go back and add more stuff to the bottom-up section. This goes so slowly for me (I know, I keep bitching about this) because everytime I write a sentence I worry to myself, "does that even make sense? Do I actually understand what I'm saying? Do I believe it?". Anyway, I feel like going home early today.

Oh yeah, btw, I hacked my thloria so that it doesn't do the even-page thing. For writing drafts, at the snail's pace that I go, it's really discouraging to see your page count go up in 2 page increments.... I would much rather have "1...2...3...4...5...6....7..." than "1.......3......5......7........". Of course, counting pages is kinda stupid if in the back of your mind you're also wondering - what if I'm writing the wrong thing? I don't just mean what if I'm writing it wrong, but hey, did you really need that paragraph about Earley deduction, or about restrictors? Just what is it do you think you're doing, eric?

shdga - kowthese.tex (words: 4514, pages: 7)

Sigh... well ok, I've sort of jotted down some more stuff about the bottom-up stuff... I'm still not sure I understand all the arguments about non-determinism. My main issue is that I really don't see why prediction as used in shieber1988uap fails to constrain the derivation of items. Is it as gerdemann1995sop says, that it's just because of not quite using the right restrictors, or is there something more subtle going on here? I feel soooo stupid. I feel like a third grader, I do, in that I can see procedurally how things work - I can see dots moving around in different orders, but I don't understand them deeply enough for arguments about their behaviour to actually be meaningful to me. I don't want to just rehash what all the other papers are saying and then call that an état de l'art; I want to actually be convinced by what I'm writing. When I'm writing something, it has to be because I actually believe it, not because some guy smarter than me wrote it in the past, and it kinda sounds like it makes sense, so I'll just say what he said. But then I just get stuck because justement, the problem is that I don't understand. I sorta see it for parsing ok, top-down not exploiting lexical information, bottom-up not sufficiently goal directed (i.e. given s(np(a plant), vp(iv(died)), you might waste a lot of time trying things that involve tv(plant) (instead of n(plant)), can see how the interleaved top-down/bottom-up works in parsing, yet for some reason I can't quite make the leap. Can't quite see why shieber1988uap isn't Earley enough, can't see if it's really just a problem with left-right vs. head-first scheduling or if there really is a bottom-down vs. top-down issue going on.

Anyway, I have decided to put a todo in there and just move on and talk about shdga which I understand procedurally, but don't completely see yet. I have the feeling that maybe writing about this will really help me to come to grips with the bottom-up stuff. Yeck. Moving ever so slowly.

Approach has been all wrong. Trying to brute force, frontal assault my non-comprehension, keep staring at something until you get it, when I should really be stepping aside, off the line of attack, understand something which is easier to 'get' and is sort of related to what I'm really stuck on, and then use that as sideways scaffolding to clear up the issue at hand. I spend all this time just feeling so dumb.

eric so slow (words: 3916, pages: 7)

Talked with Bertrand about Earley behaviour - he showed me a way to look at it, rewriting CKY using Earley-style syntax. In any case, we're talking about bottom-up here (Earley says top-down, but is that because he's talking exclusively about CFG? because it's not exactly the right way to look at it). Earley is just CKY with a better prediction rule, one that makes fewer predictions (but of course, the complete set).

That helped a bit. Spent some time making a little graphic for this, don't know why, just being empty-headed:



Anyway, I guess that wasn't really what I was looking for, although it did help a lot to look at things this way. I was already comfortable with the relationship between CKY and Earley because of the time I spent implementing the stuff. I guess what I'm really looking for now is what's missing in that predictor step for the uniform architecture... is generation with the shieber1988uap stuff purely bottom-up or is that actually some goal-directedness offered by that prediction step. What does SHGDA really add besides head-first-ness? Is SHGDA really just head-corner whereas the uniform architecture is left-corner-esque or does it somehow succeed in using more "top-down" information? I think I'm just looking at this in a very stupid and rigid pigeonholey way. But slowly starting to get a clearer picture.

Sigh. I'll never finish this état de l'art. I'm also worried that I'm doing a lot of writing, which is in the end going to be "too far back" and not really worth my time.

just Prolog hacking

Uhh... oops. No, I didn't get any writing done today. But I did suggest to Claire that instead of hacking on GenI this November, I would spend my time writing up instead (still the state of the art). That sort of buys me time... which I hope I won't need. Work harder, eric! Creeeeack! Aieee!

I was sort of bad today. I had walked into Claire's office, discovered and fixed a couple of minor UI bugs, namely with the input semantic box and calling ViewTAG.

We were sort of chatting about the semconst stuff, and me being meddlesome and curious, offered to have a look. So spent the morning debugging the Prolog. Turns out it was a problem in the grammar. The np nodes had only one index (idx), instead of two (idx, label) and that was causing a unification mismatch. Now we can parse "jean rêve de paul". Unfortunately, we can't seem to parse more complicated stuff. Useful exercise. Now I know how to debug Prolog better, i.e. how to use the trace information (having multi-coloured pen is useful here, red X for failures, green for depth level, etc).

Also seems like one of the problems is knowing which version of the grammar we've got. Kinda useful being able to selectively obliterate patches. One thing which seemed to be problematic was that Claire was running on a recent generation grammar, which could explain the parse failures. Spent the early part of the afternoon trying to put together a parsing grammar by obliterating some generation specific patches and seeing what happened. We believe that somewhere out there is a working copy of the grammar for parsing. But we'll need to sit down and ferret it out.

Along the way, I noticed that with one version of the grammar, we could parse the simple sentences again but not the slightly more complicated ones. (Actually, C says she has the same result with her copy...). We're back to the point where we do get a parse forest, and semantic construction mostly fails (except for Jean rêve de Paul type sentences). But I guess it's better than nothing.

Spent the rest of my afternoon looking at some more Prolog... but no luck. Probably some weird grammar problem. Anyway, that's what I get for sticking my nose where it don't belong. But I felt sort of responsible see, what with the whole darcs stuff.

new earley diagram

Tightened it up a little bit.

earley drawings (words: 3394, pages: 7)

Oops! I just managed to blow a whole afternoon playing with Omnigraffle. I was reading pereira1983pd (Parsing as Deduction) this morning, when I suddenly found myself trying to replicate the parsing process on paper. I don't know why; I see myself as pretty comfortable with the idea of Earley parsing, but I guess I wanted to make sure I really got what it is that's supposed to make it efficient. Here's what I ended up making. I was experimenting with ways to make the diagram a more effective way to communicate what's going on. Note that I have s/hit/punched/ so that I can use first-letter abbreviations everywhere (a-s-h-p-u: Agatha's husband punched Ulrich)

The first diagram (click to enlarge):


The second diagram separates the deduction steps from the picture:


I'm not sure if I was succesful or not. Maybe the original diagram in the paper is better.

restrictors

Wrote the bit about restrictors. Didn't get much done. Spent my time trying to deeply understand Earley and goal directedness in generation. I hate how slow I am. I guess I should be glad though. At least now I think I understand restrictors.

GenI

I have this really bad programmer habit, the "yep, looks like it works". Need to be more rigourous in testing stuff out, not just try an easy case, but something non-trivial. Showed Claire the lemanchor mechanism, but turns out it wasn't completely. It was only doing the first lemanchor in the tree... mostly because I didn't think things through and make sure it worked on n > 1. Took like 2 minutes to fix, but gah! Way to waste people's time, eric.

clickity click (words: 3096, pages: 7)

Some things are starting to become clearer in my head. Read blackburn2003cs, which is a very nice introduction to computational semantics and a good refresher to the fundamentals.

flat sem and the whole lfe thing

Reading it, I realised that the whole flat semantics thing, at least what we're using, is actually extremely weak as far as logics go - we've got first order terms, i.e. constants and variables, formulas, and conjunction. No negation or disjunction. I had a few words to say about this, something along the lines of "that's ok", but I'm feeling too shy and clueless, so I'll save it for another day.

earley and shieber1998uap

This is kind of obvious, but it really things go "click". Earley scanning is just initialisation in a parsing-as-deduction framework. You do not "scan", you just initialise with all the words you've already seen. I'm starting to get a clearer picture on the notion of goal-directedness now wrt to generation algorithms. I'm still not sure I understand why we see this as bottom-up, but I think I'm close to getting it.

restrictors

After reading neumann1994ucm, I have a better grasp of the whole restrictors idea. One thing which was confusing me is that (1) we use restrictors to prevent our parsers from over-predicting (i.e. predicting things that would send us into an infinite loop (2) in a seeming contradiction, using restrictors now causes you to... over-predict... wait wasn't that the whole point, to prevent over-prediction? Now I think I understand this.

Using a restrictor, you still over-predict; you just do it in a controlled fashion. You still effectively predict all the nasty stuff that would cause an infinite loop, but not explicitly... the nasty stuff is collapsed into one of a finite number of equivalence classes. I guess, instead of equivalence classes, we could just think of it as there being one little feature structure that subsumes an infinite number (of course) of feature structures, including ones that you "want" and ones that you don't want. That's why we say it over-predicts. You need your completion step to fail those guys out.

hacking away

Most of the day spent hacking on GenI. Added a lemanchor feature and discovered a bug in the lexical selection step (merging synonyms causes two lexical items with different path equations to be treated as the same... bad eric!). Everything fixed.

not much progress (words: 2945, pages: 5)

Making slow progress. Have wrapped up the top-down stuff. Now time to explain bottom up. Attended a PhD defense. Helped a friend with some Prolog. Helped Claire prepare some demo stuff. Discovered some potential last minute features to implement or bugs to fix. Tomorrow morning, I get to write code again. It's funny. I'm actually at the point where my desire to write English is (almost) greater than my desire to write Haskell.

oh... (words: 2595, pages: 5)

[Backdating]

Ok, now after reading a bunch of BUG-related articles, I think I'm finally getting the point - yes the problem is undecidable in general, no semantic monotonicity is not a sufficient restriction on grammars to ensure termination (completeness just means IF it terminates, it gets all the relevant yes'es). Things now starting to fit together. Spent a bit of time rewriting the top down stuff. I hope this doesn't suck too much. I'm rehashing a lot of stuff that a bunch of people smarter than me have explained before... but maybe my way of explaining it will be just a little different and be useful to the "I can program a computer but I'm a worthless computer scientist and don't know anything about linguistics crowd". Boy, I am glad surface realisation for TAG and a flat semantics is only NP-complete.

c'mon eric, try to keep up

Was really tired yesterday, whole day just going "ugh". Feeling slightly better.

cl crash course - unification grammars

Alright, time to crawl out of my ignorance. I spent all this time trying to learn about semantic formalisms, then parsing algorithms... now I need to buff up on my unification grammar and computational linguistics culture. Like, I don't mean to be an HPSG or LFG expert or nothing. Just need to get enough of my shit together. This is kinda fun in a painful way, lots of "oh!"s and "ah!"s to be expected, but a lot of embarassing "ooh! I should have known that, or taken the trouble to go find out!"

So here's the result of reading Unification Grammars, the ESSLLI 2003 reader:

• subcategorisation - I've asked a million times what this was, and gotten the answer, sometimes remembering it, sometimes not. Don't get me wrong, each time I understood that it was a really easy concept, but I must have a learning disability or something because N months later, I'll go back to a paper and see "subcategorisation list" and go huh? But now that I've seen the "source code" for subcategorisation - showing one approach using atomic values and then showing a better one encoding it in lists - this time it should stick. "Subcategorisation list" should no longer make me go "huh?"
• long distance dependencies - handling via (1) slash introduction [and propagation] (2) gap filler [plugging the 'whom' in]. Learned this 5 years ago, but never saw it again, so it's nice to have a refresher. This and subcategorisation aren't very useful to me by themselves. Their real utility is for making the examples that people put in articles about generation easier to understand. When somebody says "yeah, so you can see that this won't terminate with a simple subcategorisation list thing", the example actually evokes a mental image of the appropriate grammatical machinery. No more taking people's word for things.
• reentrancy - coreference, nothing to it
• LFG arrows - I've sort of figured this out for myself, but I wanted somebody to tell me for sure (UP = mother, DOWN = me). Nothing serious, but having to think about it reduces fluency

It's not so much about concepts being easy to understand, or important, or particularly pertinent. A lot of this is a question of fluency. Being able to read stuff without having to deal with friction from stupid little details like what the arrows mean.

A lot of this I can just apply my programmer's brain to. Like the reason why you want subcategorisation lists (as opposed to the atomic value approach). It just makes for redundant code. It's just a matter of refactoring your code. Oh. Refactoring. I understanding refactoring.

bug, shdg

Head swimming after reading vannoord1989, vannoord1994 and chunks of gerdemann1994sop. I feel like I'm getting to close to wrapping my head around the state of the art, but so many things I just don't get yet and need to get. Like the semantic monotonicity thing - that's enough to make shieber1988uap terminate right? Complete means that if the answer is yes, your program says "yes" too. And it can't be complete if it don't terminate, right? Can we prove it? In other words, it is necessary for completeness, but is it sufficient? What's this problem with BUG and non-head daughters that have exactly the same semantics as the mother? Why is that a problem? I need to run through the algorithm in order to really understand this better. Is this enough to guarantee that BUG would terminate, or are we just plugging our finger in a hole only to find water spurting out somewhere else later on? Gerdemann1994sop shows where shieber1990shd would fail to terminate. Are these two places related?

Note to self - vannoord1989 shows very simply a kind of rule that shows generation is undecidable in general (essentially VP -> foo VP). Not the same problem for parsing, because in parsing, at some point you'd have to eat that foo, so if you bottom-up, you're ok. Just not clear on the restrictions we apply to grammars to make it so we come up with algorithms that terminate under those conditions.

solving two different problems

Seems like there's really two different generation problems - generation from Prolog-style logical forms and shake-and-bakey generation (two, instead of "everybody's solving a different problem"... this makes it easier; really two families of literature so far). Difference is that the second one, you can spell out from the beginning all the bits and pieces you are going to use, and then "destroy" them as you use them. No non-termination problems there. But what's the trade-off solving this problem, instead of the more general (undecidable) problem? Is this really related to the semantic formalism (seems doubtful), or is this something related to the grammar formalism (which lets you use a certain semantic formalism)? Lexicalist? All our information is in the lexicon - you don't need to look things up from the grammar, no rules like VP -> VP ADV, every bit and piece associated to a single lexical item.

oh... yeah...

So today I just learned something I should have known from the very beginning, something that should have been no-shit-Sherlock obvious: generation on unconstrained unification grammars is undedicable. Well, I guess that sort of makes sense if unification grammars are... you know... turing complete? "[D]etermining whether a given string is generated by a unification grammar is as hard as deciding whether Turing machine halts on the empty input". What I would like to see is a minimal encoding of the lambda calculus or something like that, something to just drive the point home.

Have much more reading to do if I want to talk about the search algorithm stuff better. Hope not lost of course, you just have to restrict your grammar formalism. We know that shake and bake on CFG is NP-complete; shake and bake is just surface realisation with flat semantics, right? We also know that it is NP-complete on LTAGs (no feature structures). Now just need to read a bunch of stuff and see whether arguments about termination and stuff still actually make sense. Getting there.

Otherwise, have been practically useless today. Got in late. Didn't do much. Series of distractions, but that's really no excuse.

Plodding along (words: 1633, pages 5)

Not a very productive day. Made some diagrams for the top-down and bottom-up realisation stuff. I hope using Omnigraffle isn't the wrong approach to this - I dunno, maybe I should generate these programmatically using some nice latex package. Got stuck for a while on the bottom-up stuff, kind of a sudden realisation that I didn't know what the heck I was talking about.

A stupid roadblock was that (in the Masters) I had talked about selecting all items whose semantics subsumes some part of the input semantics... but then I got to thinking "Is that actually easy?". For a while, I was stuck because I simply didn't know how one would express that in Prolog (silly way of thinking, not really even giving code). I eventually thought to ask Sébastien, and he told me about the =.. operator. So the subsumption check is really just four lines of Prolog; here's my implementation to convince myself that it really is something easy that we can just gloss over:

subsumePartOf(X,X).
subsumePartOf(X,T) :- T =.. [_|Args], subsumePartOfArgs(X,Args).

subsumePartOfArgs(X,[Y|_]) :- subsumePartOf(X,Y).
subsumePartOfArgs(X,[_|Args]) :- subsumePartOfArgs(X, Args).

Apparantly the subsumePartOf(X,X) is wrong, but it works well enough to convince me. Anyway, it's a really stupid reason to get stuck. I guess I just watned to make sure I wasn't completely talking out of my butt or something.

Anyway, today I actually managed to get in before 08:00 like back in the overdrive days. Maybe we're back in business. Wasn't very productive in the morning, though. Heck, wasn't very productive in the afternoon either. I spent about 3 or 4 hours hacking on my BibTeX citekey script, improving the family name logic so that I could handle 'von' particles, like the "van" in "van Noord" (citekey vannoord, not noord). Silly eric. Stop procrastinating.

Arrrrrgh... 2 pages, mostly diagrams. This is REALLY crappy progress, especially considering that this is stuff I have written about before! Two years later, I guess all I want is to get it right this time, really explain it well, because I [think] I understand it a lot better. But for the time being, it might actually be going in the wrong direction. Maybe I'm muddying things up even more.