Hobbs et al (1990) proposed abduction as a general technique for integrating all levels of natural language processing (from phonetics to pragmatics) into a single logical framework. It didn't catch on, in part because computers back then were too slow to allow rapid-cycle adjustments to the system that were critical to winning benchmark contests. Today -- more than a decade later -- perhaps the proposal can be revived? Can we at least get the code and run it, just for old time's sake even?
--KenShan
A functional text editor
A text editor written in Erlang (and taking advantage of it) would be interesting. Telecom equipment (the roots of Erlang) is not the only place where computer software needs to be up and running continuously in the face of distributed failures and incremental software updates -- text editors are another such software environment. What facilities provided by functional programming languages help? What don't? Trying would be one way to find out.
(This idea is not limited to Erlang; a text editor written in Haskell and taking advantage of it would be at least as interesting.)
--KenShan
Bayesian models of trust of adversity
Let A1, ..., An be n agents that are collaborating on some task, for example the execution of a distributed cryptographic protocol, or the joint completion of a homework assignment. Each agent may be good, i.e., behaving according to the protocol, or bad, i.e., not doing so. Usually, an observer (either one external to the system or one participating as an agent) cannot directly ascertain whether each agent is good or bad. Yet it is often useful to reason about which agents are trustworthy and which are to be considered adversaries.
Can Bayesian reasoning help? Read on about the idea in [PostScript (140K)] or [Gzipped PostScript (70K)].
--KenShan
Who killed Richard Montague?
An apparent mystery. Or is it an inside joke?
http://www.kokonino.com/dd4.html:
http://www-linguistics.stanford.edu/Archives/Sesquipedalian/1994-95/msg00001.html:
Kevin Shapiro says:
I plan to ask a reference librarian at HarvardUniversity this question. I mean, this is what they're hired to find out for us, right?
Another possible source of information:
--KenShan
MnemonicCoding (see separate page)
Imperative functional contract composition
Having read [Simon Peyton Jones, Jean-Marc Eber, and Julian Seward (2000), Composing contracts: an adventure in financial engineering], I want to compose my contracts thus:
european :: Date -> Contract -> Contract
european t u = do waitUntil t
a <- chooseItem [True, False]
if a then u else zero
american :: Date -> Contract -> Contract
american t u = do a <- chooseItem [True, False]
if a then do n <- now
b <- chooseTime n u
waitUntil t; u
... but how?
Upon initial thought, it appears to be related to the concept of arrows, which in turn has to do with parsing combinators: See under "arrows" in http://www.cs.chalmers.se/~rjmh/ for more background.
A general comment on arrows vs monads, based on my hazy understanding of both: Arrows may be a generalization of monads only because Haskell monads are required to be ones over Haskell's built in Cartesian-closed category, rather than some other category. In other words, the concept of arrows may be equivalent to monads over arbitrary categories. See Exercise 1.8 (page 7) in [Nick Benton, John Hughes, and Eugenio Moggi (2000), Monads and Effects].
See also:
--KenShan
ComposingMonadsByBuildingInterpreters (see separate page)
Page layout detection
PsBind sometimes makes mistakes in detecting margins in the input document. It gets confused by things sticking out of the margin -- for example, if the input document contains some code listing that occasionally extends beyond the right margin, PsBind takes the extent of the code listing as the right margin. This can result in too much whitespace in the output.
How can we make PsBind margin detection smarter? This problem is hopefully simpler than the kind of page layout detection that OCR software needs to perform, because PostScript documents are cleaner input than scanned images.[custom term paper]
--KenShan
Folds and sharing
Section 5.4 in [Simon Peyton Jones, Jean-Marc Eber, and Julian Seward (2000), Composing contracts: an adventure in financial engineering] describes a problem that "arises, in various guises, in almost every embedded domain-specific language" (embedded, that is, in a functional programming language).
[High School Diploma] The problem is that if you have a data structure containing shared substructures (usually but not necessarily a recursive data structure):
data Tree a = Node a | Branch (Tree a) (Tree a)
myTree :: Tree ()
myTree = Branch b b where b = Node ()
then functions that perform computations by recursing into the structure would recurse into the shared substructure twice, thus performing redundant work. For example, the following is a function that computes the size of a tree, defined as its number of leaves:
size :: Tree a -> Int
size (Node _ ) = 1
size (Branch x y) = size x + size y
To evaluate size myTree to 2, the size of the shared sub-tree b = Node () is computed (to be 1) twice. With a computation as cheap as size we probably wouldn't mind, but with a more expensive computation over larger shared substrctures we would.
Recursion into recursive data structures can often be described as a fold [Meijer, Fokkinga and Paterson (1991), Functional programming with bananas, lenses, envelopes and barbed wire] [Jeuring and Meijer (1995), Merging monads and folds for functional programming]. Would the sharing problem be solved if we implement folds natively?
--KenShan
Unsupervised statistical segmentation, Ando & Lee
[Ando and Lee (2000), Mostly-unsupervised statistical segmentation of Japanese: applications to Kanji] presents an amazingly simple Japanese segmentation algorithm that performs amazingly well.
Applications to topic segmentation
Can we use a similar technique for topic segmentation [Hearst and Plaunt (1993), Subtopic structuring for full-length document access]? In Hearst and Plaunt's approach, each article is segmented independently from all others -- their TF-IDF score compares word frequency in 3-to-5-sentence block with word frequency in the same document but not word frequency in the rest of the corpus (section 2.2, "TextTiling?"). By comparison, Ando & Lee's algorithm critically uses n-gram counts from the rest of the corpus.
We propose the following hybrid approach, borrowing techniques from Ando & Lee to perform the task in Hearst & Plaunt: Let N be a set of small integers (say {3,5}). For each n in N: At each possible segmentation point k (i.e., each inter-sentence boundary), let s(1) be the n sentences preceding k, and s(2) be the n sentences following k. Let t(i) (where i = 1, 2, ... n-1) be the n-1 sequences, each n sentences long, straddling k. (See Figure 2 in Ando & Lee's paper.) For each n-sentence sequence, let f be some TF-IDF score comparing the sequence against the rest of the entire corpus. Now compute what Ando & Lee calls v(n)(k), except replace their "#" with our "f". Continue with Ando & Lee.
To evaluate our segmentation algorithm, we can simply rerun Hearst and Plaunt's information retrieval experiments to see if switching to our segmentation algorithm improves precision and recall on what they call "sum" segment retrieval.
--KenShan
Phonemic annotation of transcribed speech corpus
A phonemically annotated corpus of Mandarin Chinese text would be useful for building and evaluating the following applications:
There currently exist many corpora (for example from the [Linguistic Data Consortium]) in which human speech was recorded, then transcribed by hand. Unfortunately, there is no phonemic annotation in the transcripts. Perhaps we can use the correspondence between the speech recordings and the text transcripts to annotate automatically?
--KenShan
The extended kinship of "almost"
Can we analyze almost as an indefinite? I want to paraphrase "John is almost six feet tall" as "John is not six feet tall; he is a certain height close to six feet".
--KenShan
I hope you do not paraphrase it thus. How about "John is not six feet tall; he is of a certain height less than but close to six feet."?
--SsSs
Hrm, depending on what we mean by "six feet tall". Is there a sense of "six feet tall" that describes a seven-feet-tall person?
--KenShan
The original paraphrase is adequate; the example is made more complicated by the use of 'tall'.
There are certainly contexts in which it is possible to describe a seven-foot person as "six feet tall", and others in which the phrase "almost six feet tall" can be truthfully applied to somebody whose height is greater than six feet:
Example 1
Sports official: " In order to take part in this event, you must be six feet tall."
Seven-foot athlete: "I'm six feet tall."
Is the athlete lying?
Depending on where pragmatics fits into the picture, this can be seen as
(a) the utterance of a semantically false proposition, which conveys the (true) implied claim "I am tall enough to take part in this event", or
(b) the utterance of a semantically true proposition, in which the phrase 'six feet tall' is "pragmatically loosened", relative to the contextual setting, to have an extension that includes seven-foot tall people (but not five foot tall people!).
Example 2
Consider a different scenario, in which the specified height may be an upper bound, not a lower bound.
Casting director: "Sorry, our chorus dancers must be six feet tall, or they won't fit into the costumes. You're too tall."
Aspiring six-foot-and-four-inches-tall performer: "Aw, but I'm almost six feet tall!''
--JohannesFlieger?
A history-oriented window manager
Wheeler Ruml recently remarked to me that people want their applications (e.g., Acrobat Reader, Microsoft Word) to be browser plug-ins because the browser imposes a linear order -- the history -- that is sometimes useful for orienting the user.
But hey, an X window manager can do almost the same job! Imagine a window manager that detects from which window you launched which application. Based on this information, the window manager keeps track of a number of disjoint "sessions". Each session contains a set of windows organized in the linear order in which they were created. (Actually the situation is a bit more complex, since the same window may beget multiple windows, and there are orphans (zombies). Therefore by "linear order" we really mean "hierarchical order", but the general idea remains the same.) The window manager [maps] (that is, un-iconifies) exactly one window at a time from each session. Through keyboard/mouse/programmatic commands, the user can move from window to window within a session. When switching from window to window within a session, the geometry of the previously mapped window becomes the geometry of the newly mapped window.
(Comes to think of it, Microsoft Word 97 sometimes uses this trick to create the illusion that it can "become" a Web browser -- it simply opens Internet Explorer in front of it, with the same window dimensions, so that IE completely and precisely occludes Word.)
--KenShan
A linguist-fun mailing list
If the mathematicians can have math-fun, why can't we linguists have linguist-fun?
--KenShan
You'd probably enjoy Chris Pound's Name Generation page: http://www.ruf.rice.edu/~pound/
Please analyze these sentences
Distilling bananas and lenses
Ehud Lamm [justifiably wants] a tutorial for Meijer, Fokkinga and Paterson's [classic bananas and lenses paper]. I hope someone gets around to it before I do...
--KenShan
Scope in the real world
Mandarin Chinese: "meigeren dou keneng shi sharenfan, danshi bushi meigeren dou shi sharenfan" 'everyone might be the murderer, but not everyone is the murderer'. In the first part in the Mandarin sentence, 'everyone' (obligatorily) scopes over 'might', unlike in the English version, which follows von Fintel and Iatridou ["Epistemic Containment", to appear in Linguistic Inquiry]. (Note that von Fintel and Iatridou only make a claim about English and do not say anything about Mandarin.)
Who says "most" in English cannot scope out of a relative clause? ["It was the first opportunity I had to see most of these performers live."] Update (March 2008): Lucas Champollion pointed out to me the possibility that "to see most of these performers live" is not part of a relative clause but merely postposed after the relatively light relative clause "I had". In that case, "most" no longer scopes out of a relative clause, so this sentence is not so exciting anymore.
--KenShan
Rejoinder: combining email dialogue with weblog egotism
A weblog should be a front-end to an email folder. A public weblog should be a front-end to the archive of a public mailing list. Let's build [software] for such.
A popular weblog program must be easy to install. For example, it must automatically listen on port 25 for SMTP connections and accept incoming posts. It should also ease migration from other software by letting the owner of a new weblog suck the layout of an existing one. Let's build our weblog program as such.
Let's call this weblog program Rejoinder.
--KenShan
Common File Selection Scheme
Imagine: No more digging in man pages to find various --include and --exclude options, unprogramming your brain from tar in preparation for rsync, trying to remember whether to put that final slash, and recovering from /etc/hosts.deny.
--KenShan
Extensible unification for type systems
The Haskell type system is renowned for its programmability: the type class system, a major advance over previous approaches to ad-hoc overloading in functional programming languages, turns out to allow us to write logic programs in the type system, effectively extending its behavior with capabilities such as unit and dimension checking for physical quantities.
However, because type-class overloading is resolved after unification, the type checker often fails to "infer enough" to stem the tide of overloading ambiguity. Also, transitive (not to mention symmetric) relations such as sub typing or containment are difficult to express using type classes without running into the (quite reasonable) prohibition on overlapping instances. Functional dependencies help (by making overloading resolution happen earlier in the type inference process), but often not enough.
What if we take the following different approach to extending the type system: instead of tacking overloading resolution onto standard unification, allow the user the extend unification? Neumerkel's paper on [extensible unification] might be the right place to start.
Binding as a computational effect
I believe that the "computational effect" of Dreyer (POPL 2004) that is unresolved binding is characterized by being an effect that can equivalently be incurred when a function is created as well as when a function is invoked. In other words, it is an effect where "evaluating under lambda" makes no difference. In yet other words, it is an effect that commutes with the environment monad (aka reader monad) -- I can't think of any other such effect! This point might be easier to make in a pure language with binding effects made explicit using monads. Let's.
(Related work by: Len Schubert, Tim Fernando, Mark Steedman.)
Tridirectional typechecking is effectful typechecking
Dunfield and Pfenning (POPL 2004) type-check union types using inference rules that make reference to the context of a term. This technique seems like a type-system analogue of Filinski's "representing monads" result, specialized to the non determinism effect. Can the technique be generalized along those lines to other "type-level effects"?
Power adaptors should extend
I want my laptop power adapter to come with a power outlet on the side.
A book or course on air travel
Air travel is fascinating to many of us, and I would really like a book that puts that fascination to good use in interdisciplinary education. How planes stay in the air (physics), how airline tickets are sold (computer science -- did you know it was undecidable?), how fuel is fought for, how landing spots are assigned, how airports are architected, how passports are controlled, how local economies and residents interact, how bags are sorted, would each make a chapter.
Typesetting by reasoning under uncertainty
If we judge the quality of a typeset document as a real number between 0 and 1 (multiplicatively), then algorithms for Bayesian inference correspond to global optimization algorithms for typesetting. A programming language for modeling uncertainty, such as [IBAL], can thus be used as a document description language for automatic typesetting with global optimization. This typesetting engine should automatically choose between "therefore" and "thus", avoid hyphenation at page breaks, and so on.