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.
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.
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:
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.
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:
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.
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, 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.
Copyright Michael J. O'Donnell <michael_odonnell@acm.org>. Licensed for free use.
![[CS Dept., U Chicago]](http://www.cs.uchicago.edu/i/header_background.jpg)
