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.

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.

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:- Windowed FT to produce a filtered signal strongly weighted toward a particular time-frequency region;
- Polynomial (or in principle other) estimation to infer a good description of the signal in that region.

**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.

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:- interpret their contents as assertions in some logical language,
- interpret queries as questions in a similar language,
- derive responses as logical consequences of of the stored assertions.

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:- Very sensible declarative semantic foundations.
- Radically lazy evaluation (at the deductive level, leading to some sort of semantic completeness).
- Output language is a subset of input language (like normal forms).
- (Multi-)Graph reduction (
*real*relatively unconstrained graph reduction, not just the implementation of term reduction with graphs). - Unification.
- Nondeterministic search.

*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.

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, I´m 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 can´t 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.

I´m 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.

- In general, mathematics invites us to seek common structure behind
completely different-looking presentations.
- What happens when a constraint is removed? Using naive reasoning
(such as that usually employed by rich businessmen and powerful world
leaders) we often focus on the impact of that constraint, and try to
extrapolate our experience in a direction that is intutively
orthogonal to the constraint. Linear programming suggests that the
removal of one constraint reveals others that can change the structure
of the problem arbitrarily much.

To get a bit more concrete, when a particular burdensome task becomes much quicker, we often expect to gain much more leisure time. In many cases, we may spend more time on the quicker task, because the marginal value of an investment of time goes up. I have found that I spend more time and energy communicating with students now that it is easier to do so. - When other people's behavior is unsatisfactory, we often apply
what seems to be pressure toward the desired behavior, often with
disastrous results. A bit of attention to the instabilities that arise
in control theory might give us pause.
- Progress in social/political conflict is often viewed as though
each formal accomplishment is added to a counter, and that the level
of success is measured by the accumulation in this counter. We realize
that the opposition is busily decrementing the counter, and perceive
the conflict as a sort of race. But much progression of
social/political structure looks a lot more like a sequence of XORs
than like summing into an accumulator. The last application of
social/political power in a sequence may completely reinterpret
earlier steps. A brief contemplation of modular arithmetic with
modulus larger than 2 might warn us not to extrapolate thoughtlessly
the experience of cumulative progress over too short a time
scale.

- In general, mathematics invites us to seek common structure behind
completely different-looking presentations.

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