X-Powered-By: PHP/4.4.4-8 Content-type: text/html MJ O'Donnell, Scholar, Discussion topics [CS Dept., U Chicago]

Michael J. O'Donnell (Mike)

The Scholar

Discussion topics

Here is a list of things that I might usefully discuss during my visit to Politécnica through 11 July (or in other venues). They are roughly ordered from best prepared through half baked to raw dough (or maybe even wheat in the field). I have a long-standing inability to resist talking about anything that anyone asks about, so ask at your own risk.

Prepared talks

Well, mostly prepared. Assuming that I can find the slides. Assuming that they are online, and not in a pile of transparencies somewhere.

Design decisions in the Internet
I investigated the decisions that led to the current Internet, and tried to determine why they succeeded, where they were essential, where suboptimal, where irrelevant. This was a whole course at the Suzhou Graduate Institute, but it breaks up nicely into 1-hour topics on different design decisions. You may scan the course slides to see the topics.

Minimalist Public Key Infrastructure
Many proposals for public key infrastructure try to solve real authentication problems, by associating keys with supposedly reliable identities, using chains or webs of trust. This seems to violate a key principle of infrastructure design: don't solve high-level problems, just provide tools. I propose to apply ideas from specialized areas of security to provide a minimalist PKI, providing an identity relation, but no identities as objects. Trust may be constructed in many different ways, at varying costs, depending on its importance in a particular application. Pages 187-215 of the slides with notes for the Internet course treat this topic (slides numbered 131-150: the notes increase the numbers in some viewers, but not in others).

Formal Systems as Generators of Certainty
This is a philosophical discussion. I analyze the concept of formal systems, following Haskell Curry and Saunders Mac Lane, as a tool engineered by mathematicians for a purpose (notice that I refer to formal methods themselves as a tool, not particular formal systems). I find behavioral, rather than metaphysical, reasons for their value, and qualify the very strong but not absolute certainty that they yield. I compare the explicit appeal to formal systems by Hilbert to the method of Descarte, which is arguably an early attempt to characterize formal systems and apply them very ambitiously. Hilbert's program may be seen as the restriction of Descarte's program from all of knowledge down to just mathematical knowledge. You may review slides and a brief article. I think that this article could be published in a humanities journal, if someone would join me as coauthor to search out the previous research and citations.

Multilevel Garbage Collection
My former Ph.D. student, Guanshan Tong, wrote a dissertation investigating the good performance of Generational Garbage Collection. Although GGC was justified based on an age heuristic---that heaps usually have many short-lived objects and a few long-lived objects---we found that different heaps satisfying this heuristic may support good GGC performance or not, depending on the precise shape of the age distribution. We simplified GGC into Levelled Garbage Collection, which ignores the age heuristic. For immediate promotion strategies, LGC is essentially the same as GGC. For strategies other than immediate promotion, it often performs better by tuning the space guaranteed to be available for quick allocation, rather than the ages of the objects diminishing that space. I have slides somewhere, but haven't found them yet. You can look at the JFLP article.

Papers in search of a coauthor

These are ideas that I am highly confident will work out completely, but I can't concentrate long enough to work out the details, and/or to write the article. Some of them have drafts even. I really need collaborators in order to be productive.

Time-Frequency Analysis for Sound
The standard and rather obvious approach to time-frequency analysis is to impose a fixed grid on the time-frequency plane, and use one of the points in a windowed Fourier transform to calculate a value for each grid point. This tyranny of the grid leads to results that are substantially smeared both in time and in frequency compared to our intuitive and/or perceptual appreciation of a sound. This is often justified as an unavoidable consequence of an "uncertainty principle" for time-frequency analysis, which has the same mathematical form as the Heisenberg uncertainty principle in physics.

I will explain why this justification is harmful nonsense. Heisenberg's uncertainty principle in physics is evidently a law of quantum physics. The "uncertainty principle" for time-frequency analysis is an artifact of the linear character of the Fourier transform. Worse, while many people study the engineering of T-F analysis as a problem of accuracy, the real problem is that the solution is underconstrained, and we lack a good criterion to choose from the infinitely many solutions.

In fact, there are already analysis methods, mostly called "reassignment," that beat the uncertainty principle. It starts with a windowed Fourier transform. But, instead of using each point in the FT as a value for an associated grid point, it takes each FT as a characterization of the signal weighted toward a certain grid point, and looks for salient features in that region.

Reassignment has been justified from several sensible but incomplete points of view. I have a general idea for dividing it into:
  1. Windowed FT to produce a filtered signal strongly weighted toward a particular time-frequency region;
  2. Polynomial (or in principle other) estimation to infer a good description of the signal in that region.
I have a sketch of the mathematics, and I even think I foresee how it has to work, but I can't concentrate long enough to get it right. All the manipulations are in principle just elementary FT, but it turns out the the particular FTs involved are not in any of the standard tables, and I have only found one reference treating them. This could be half of a dissertation for the right student.

Nonmonotonic reasoning with monotonic inference
I agree with the widely held notion that practical reasoning behavior is nonmonotonic (additional knowledge may cause us to abandon a previous conclusion). But I think that the introduction of nonmonotonic inference relations is a serious tactical error in the attempt to model practical reasoning. Ten years ago I wrote a short article arguing, based on the performance requirements for automated reasoning, that some sort of metatheoretic assertions, rather than nonmonotonic inference relations, are required. I think that this article only needs a search for previous literature, and a bibliography, in order to be a good publication. I will welcome a coauthor who can finish it up.

Search in partially confluent systems
My favorite activity in programming languages is to look for nice tight correspondences between logical semantics and powerful execution models. I believe that it's best to alternate matching execution to semantics & and vice versa, rather than always working in the same direction.

In my own dissertation, I studied reduction in confluent systems as an execution model nicely adapted to equational logic. But the problem of enforcing confluence limited the application of the idea, and especially hampered modular programming constructs. I also saw the value of nondeterministic programming, pretty much on the motivation given by Dijkstra, but also to introduce search into the execution model. So, I asked myself what sort of semantic interpretation would support such an execution model, and how to avoid totally undisciplined search. Finally, I was disappointed in the mismatch between the symmetry of equality and the asymmetry of reduction, which is tamed somewhat by confluence, but gets nasty without confluence. At other times I looked for symmetric execution models, but here I looked for asymmetric sematics.

If we take each term to represent a set of values, with each function symbol pulling up from a function of values to a function of sets, we have the basis for a subset logic, where the subset relation satisfies the congruence property of equality (due to the restriction on the functions), but not symmetry. It seems most natural to take reduction as going from a set to a subset, rather than to a superset. For marketing purposes, we need a better name than "subset logic programming," but it captures the technical basis.

In order to have a nice nondeterministic execution model that finds an arbitrary normal form, instead of the rather too expensive one that finds all normal forms, we need some sort of lazy (breadth-firwst) search of the reduction graph from an input. An undisciplined search will probably be useless in most cases. Given an arbitrary, usually not confluent, system of subset reduction rules, we may detect a number of confluent subsystems. It's OK if they overlap. The confluent subsystems may be used to limit the points in the reduction graph from which we need to search. I'm pretty sure that in practice, the reduction will be huge.

Nondeterministic programming typically entails a desire to occasionally commit to a particular path, and prune the search. I have seen some horribly ad hoc proposals on these lines. Subset logic programming suggests a semantically grounded form of commitment. It is commitment to a particular head structure in the normal form, rather than to a particular computation path.

I wrote some about this idea in my chapter in Dov Gabbay's Handbook of Logic in AI and Logic Programming, and I even think I had a sketch of the data structures, but I don't remember how far I got. Certainly not to the point of a separate journal article.

Directed congruence closure as radical memoization
There are a number of proposals for memoizing functions to avoid recomputation, and some study of the interaction with laziness. But all of the proposals that I have seen have some amount of ad hocery, and are highly sensitive to syntactic presentation of a program. Congruence closure is a theorem proving idea that provides a more radical, and more robust, sort of memoization, based on memoizing inferences rather than function values.

Congruence closure was originally designed to draw all possible equational conclusions from a finite set of ground equations. The original method is entirely symmetric. But it does not allow schematic equations with variables, and probably doesn't contribute directly to program execution.

My first Ph.D. student, Paul Chew, worked out a tradeoff in his dissertation. He showed that congruence closure may be applied to schematic equations, if they can be treated as nonoverlapping ("regular" in the French terminology) reduction rules. His directed congruence closure accomplishes memoization of inferences in the sense that no ground instance of an equation is ever derived more than once. But it suffers from deriving many unnecessary equations, due to an eager approach to the closure steps.

A subsequent student, David Sherman who is now on the faculty at Bordeaux, showed how to make DCC lazy, but at the cost of some deterioration of the memoizing guarantee. The method is very efficient, and uses data structures like those in linear unification. But there have been insufficient implementation experiments, and no exploration of the practical impact of the tradeoff between laziness and memoization.

There's an interaction between the DCC topic and the search in nonconfluent systems, but I don't remember it at the moment.

Incremental reduction with history
I have yet another unsubstantiated thesis: the essence of good incremental evaluation (after small change to the input) is good memoing. So, I think that the congruence closure ideas above can be applied usefully to incremental evaluation.

Take a term as input, and reduce it to normal form using some sort of adaptation of congruence closure to memoize the steps. Now, think of a local change to the input term, not as an actual replacement, but as introduction of another sort of edge in the term graph, leading from an old version of a subterm to a new version. Allow sharing between old and new, so only the truly retyped segement need be added.

I think that the essence of incremental evaluation is appropriate migration of edit edges toward the root of the term graph. Sam Rebelsky and I started sketching this out, and we might be able to find or remember some old materials. But the article, perhaps even dissertation, is yet to be written.

Embedding functional programming in procedural programming
I believe in the value, but not the exclusive moral necessity, of functional/logic/assertional programming. When something should happen, I think it's best to say "let it happen," which is procedural. Rather than seeking assertional hegemony, I would like to find semantically clean combinations of assertional and procedural programming.

When the designers of assertional programming languages feel the need for some procedural power, in all cases that I know of they just introduce procedures masquerading as assertions. I think this makes a horrible mess of the assertional foundation, since an assertionally valid change in execution strategy can destroy the behavior of a program.

I think we may have been doing this backwards. Instead of embedding procedural stuff in assertional languages, let us embed assertional languages in procedural ones. The trick is to find the right procedural interface to the workings of an assertional language, without sacrificing useful expressive power. The form of a cleanly structured interpreter for the assertional language can give us a good clue.

I worked out the basic idea of embedding lazy functional programming into C procedures with my Ph.D. student, Sam Rebelsky, now on the faculty at Grinnell College in Iowa. But he took the general techniques, and made them into a dissertation on lazy functional I/O (yet another interesting topic to exploit), so that one lazy functional program could be pipelined with another, with no loss of computational power. I think that this idea is ripe for extension to other assertional languages, and for real solid implementation in C/Java/... libraries.

Dissertation projects

More ideas that need serious working out, but I'm confident that they are good starting points for projects that could lead to dissertations or other publications.

Gestural Control of Fluent Speech
This is a project that I am unable to work on now, but I have a large emotional investment. My late colleague from Linguistics, Karen Landahl, suffered a rare disease that led to surgical removal of her tongue. For about two years, she survived and remained active in the university. She carried a small computer that synthesized speech for whatever she typed in. It was her best method for communicating, but terribly awkward.

I realized that we have approached speech synthesis backwards, at least regarding its use to support conversation by people with damaged vocal tracts. By starting with text, we have already lost the battle, because the time required to type a reply already destroys the rhythm of a conversation, so no amount of processing to add inflection, prosody, etc. can fix things.

Instead of text->sound, I propose a low-level control of sound with hand gestures. The gestures would control pitch, volume, and perhaps other elements of prosody and inflection, along with phonetic elements of speech. I have made some quick calculations, and I'm convinced that hand gestures have enough degrees of freedom, and enough speed, to do so. Sign language is part of the evidence for feasibiity, but it is not a useful starting point, because the conversational syntax of sign languages is very different from that of audible speech.

I can provide some lectures on the basics of phonetic modelling (not the fine points). The right way to approach the project is to set up a fairly general mechanism for controlling sound generators and filters by gestures (with a glove, RF elements on the fingers, ...?) and play with it for a long time. Since there is a nice theory of formants to support the production of vowels, one might start with that. But it will be important to include nonphonetic qualities, including inflection and prosody, very early in the experiments.

My strongest constraint regarding this project is that a resulting product should be called the "Karen," in honor of my late colleague.

Garbage Collection --> Rummage Sale?
The ideas on memoizing and incremental computation above suggest a world in which there are few or no provably useless nodes in a heap memory, and only a few irreplacable ones (most nodes may be recalculated at a time cost). Instead of collecting garbage, perhaps storage management should look heuristically for less valuable nodes to reclaim. I like to call this "Rummage Sale." This sort of semantically driven storage management at first looks very specialized, but as memory hierarchy and network make more and more memory contents into cache values, refreshable at a cost, it might give some insights into more general techniques.

Relevance logic for automated reasoning
Lots of applications of automated reasoning, particularly in knowledge bases or deductive databases with large, distributed weakly controlled inputs (datamining is a particularly difficult case), may go astray because of the catastrophic impact of error in classical and intuitionistic systems. A single contradiction about a minor fact enables all conclusions about everything.

Relevance logics have been proposed by philosophers who think implications should always connect their hypotheses to their conclusions in some meaningful way. These logics all avoid explosion in the presence of contradiction. They appear promising for robust, prudent inference under imperfect information. But there are many relevance logics to choose from, and little reason to believe that the one we need has already been described. Intuitively useful semantics could help us design the right useful logic for reasoning from good but not perfect information.

The most promising semantic approaches appear to me to be those that reduce the definition of relevant implication to one of relevant function. But mere strictness in a Scott domain is insufficient, and I don't know what definition of relevance is needed. Jim Lipton and I have worked out a lot of the details of this semantic approache (called "realizability") to constructive logic, and we have a plausible starting point for extending it to relevance logics.

I worked up an introductory talk on the topic, and append the abstract below. I have slides and notes, which I will try to link in eventually.

The relevance of relevance

This talk discusses work from 1976 by Stuart Shapiro and Mitchell Wand, whose potential value is growing and requires some redisemination.

Deductive DataBases, which include Relational DataBases as a relatively primitive case: DataBases of all sorts contain errors, in spite of the care taken in building them. Assertions in RDBs are so restricted (only atomic relational tuples, no negation, no disjunction) that it is impossible to represent a contradiction. But as we extend the expressive power of DB contents, and the range of sources of data (e.g., the whole Web), not only errors but contradictions become inevitable.

Classical and intuitionistic logic both explode in the presence of contradictions. Using these logics as foundations for DDBs, we could discover from one Web site that Finland will host the next Winter Olympic Games, and from another contradictory site that the games will be in Saudi Arabia. A DDB using classical or intuitionistic logic is allowed to inform us, based on this contradiction, that the Euro has crashed to $0,02.

A sensible business will not make decisions based on such inferences, in spite of their respectability in the mathematical theory of logic. I will explain why all of the currently feasible approaches to avoiding outrageous conclusions are hopeless as long-term solutions. I propose that a logic of relevant implication is the right starting point for research to create sensible, robust, and powerful DDBs.

In the Olympic example, the bad information about the venue will unavoidably lead to some bad conclusions---perhaps contradictory predictions for the luge races. But we need some clear and conceptually coherent criterion that prevents the contradiction from polluting inferences for which it is irrelevant. I will explain why relevant implication has many of the qualities desired for limiting the impact of contradiction, and why we don't yet know enough to implement it.

Generalizing Böhm Trees
Böhm trees are the most syntactically natural extensions of normal forms in the lambda calculus to infinite terms. But they are really just the most obvious example of the accumulation of cofinal characteristics of the reduction graph below a given term. A systematic study of other possibilities will be very valuable. For example, whenever we recognize a strongly connected component in the graph, such as the unary cycle below lambda x. xx, or the infinite component below lambda x. xxx, we might treat it as an extended normal form. More generally, whenever we can show that all descendants of a term A[B/x] have the form A'[B'/x], where A reduces to A' and B reduces to B', this is a structural stability that could be added incrementally to an accumulating output. And these are just the next most obvious forms; there will be more to discover. Then, there can be similar phenomena in other systems. Nondeterministic production of infinite output may be particularly interesting.

A weird approach to lazy constraint reduction
This one is suggested in my chapter in Gabbay's Handbook of Logic in AI and Logic Programming. It starts out with a simultaneous hacking of semantics and deductive systems and computational model. I think that it can lead to a very useful foundation for some unusual directions in functional/logic programming.

I would like to combine several imperfectly defined nice qualities that I see at least previewed in Prologish and Functionalish execution models: My idea is an execution model based on a language that looks like FOPC with relations only, no terms (not even constants). Please don't think of the ugliness of current presentations of relational systems as a key issue---I postulate some serious work on display before a user can stand to look at the structures.

Graph-reduction rules should be explained logically as Pi2 clauses of the form All x1 ... xm Exists y1 ... yn T1 and ... Tp => H1 and ... Hq. The variables x,y stand for points in the graph, the relations H,T stand for multiedges. The rule allows a subgraph of the form given by the Hs to be replaced by one given by the Ts. The universally quantified variables may be unified with one another and with other points in a large graph. The existentially quantified variables may have only the connections given in the clause.

A goal is a graph representing a conjunction of relations on variables, plus an indication of which variables are interesting.

In order to allow lazy evaluation, we must be able to throw away subgraphs that lose all connection to the interesting variables. For this purpose, we need to restrict the semantics to universes in which all constraints are inhabited. I think I know how to do this satisfactorily. Perhaps the logic of such systems should be called "Unicorn Logic," since every expressible constraint is inhabited, so the inhabitants should perhaps be viewd as concepts rather than solid things.

Unification is allowed by the universal quantification of some variables. Unfortunately, unification in relational systems is far too unconstrained. It is logically correct to add arbitrary constraints in order to express one possible solution. I think that some sort of relevant interpretation of the implication can solve this in a useful way, but I haven't got the solution.

Wild ideas

Here are some wild ideas we can talk about. But I don't have serious progress beyond the brief descriptions below.

Circuit->Packet->Signal Switching
As processing speeds get faster and faster, we can make routing decisions in communications networks for smaller and smaller informational units. This trend led from the circuit switching of the original telephone system to the packet switching of the Internet. Now processors are fast enough to perform digital modulation and demodulation of signals at the waveform level. Will we find a regime of networking using signal switching? This will be spooky for computer scientists, since switching will go below the level of bits. It will require expertise in multiple movable tunable antennas. Some proposals for open spectrum communication are perhaps tending this way already.

Economics/Procurement in Free vs. Proprietary Software
I think that a lot of discussions about free vs. proprietary software, and about the economics of software in general, get muddled because of a confusion between product and license, and a similar confusion about the boundaries of different markets.

Many (I think most) government and large private institutions obey a second source rule in procurement of essential items. They refuse to buy any item unless there are at least two independent sources for interchangeable items. In some cases, Im pretty sure that companies have helped to fund the startup costs of a competitor in order to make a product acceptable on this basis (I remember these things from somewhere, but cant find the source). If this principle were applied to the Windows OS, it would be ineligible for purchase, since nobody but Microsoft sells a compatible product. But *NIXes are arguably acceptable, since there is at least a reasonable approximation to interchangeability. In the case of *NIX, the openness of the Posix standard allowed multiple sources to flourish spontaneously, and the free nature of much of the relevant source code made the dissemination even more efficient.

Many discussions of free vs. proprietary software, particularly when people propose rules limiting certain government acquisitions to free software, focus on freedom to compete and the quality of the software. But the inherent difference between free and proprietary software is the license, not the code itself. Nobody in the world can purchase full rights to Microsoft software. I think that the discussion should focus on the licensed rights, and it should be roughly analogous to the decision whether to lease or purchase: proprietary software comes with rights somewhat like a lease, free software comes with almost all of the rights in a purchase, and some of those rights (particularly, to copy) are even more valuable than they would be for a physical object. If a government chooses to restrict certain acquisitions to carry the full rights of free software, it has not prohibited commercial companies, including Microsoft, from bidding to deliver software with those rights.

In general, Microsoft likes to present itself as competing with Apple and *NIX. But, due to very high switching cost, this competition has a very long time scale, on the order of magnitude of decades. That is more like the competition between oil economy and hydrogen economy than the competition between different automobiles. Only within the *NIX market is there competition for largely interchangeable products.

Im pretty sure that someone with good understanding of software (me or someone else), collaborating with someone who understands economics and can communicate in its language (definitely not me) can integrate these observations into a very interesting article, even a dissertation, on the economics of software.

What Mathematics Can Teach Us About Life
When I propose mathematical insights into living phenomena to my colleagues in the humanities, and even---to their special shame---to some in the biological science, a common response is that the phenomenon is too complicated to quantify accurately, and therefore requires a nonmathematical description. But I observe that the nonmathematical descriptions tend to be far more simplistic than well studied mathematical structures. I think that we may gain a lot of insight into the fuzziest of phenomena by contemplating the possibilities for structural surprise that mathematics provides. And I think that a proper understanding of mathematics and its relation to life in general alerts us to a complexity far greater than can be expressed in other forms of thinking.

Valid HTML 4.0!

Last modified: Mon Oct 5 19:20:37 CDT 2009