So the quarter finally ended, and I can get back to having a social life over the holidays!

The compiler that I wrote was, in my personal opinion, a pathetic failure. Though we were able to generate some x86_64 code that actually ran (given a bootstrapping program), it would crash on certain valid inputs. We were also unable to handle arrays properly; our calling convention was a nightmare (I now heartily recommend going with proven standards, rather than trying to come up with one yourself); and our register allocator was basically non-existent (it just spilled everything, assigning all ssa values to their own slot, and never re-using slots). On the positive side, it was able to do factorial, and towers of hanoi, so we nailed recursion!

The TA’ing gig was wonderful. I had great fun teaching the kids concepts, tricks, ways of thinking. It was my first time, so I occasionally gave away answers in my eagerness to explain, but overall I think I did a reasonable job. Some of the kids regularly came to my office hours, and thanked me for helping them pass the class (which felt really wonderful, I made a difference!) I ended up loving the TA work so much that I even let it take time from some of my other obligations (research, and my own classwork).

Given my experience, there’s one big thing that I’d change in the current system: I’d make discussion sections mandatory, and limit their size to about 10. This would make discussion an actual discussion, rather than just another lecture. I think the discussion sections should encourage the design aspects of the homework/projects. That is, we all gather round the table, and whiteboard a design. One of the things that I noticed in grading the programming assignments was that our students are sometimes really creative in their solutions (and not always in a good way). I think that we probably do a poor job of teaching design, because there isn’t really a quantitative scale that can be used to measure how good a design is. So, they need to practice for an hour each week, offer each other design options, constructively criticize by identifying holes in each other’s attempts (with guidance from the TA), until a satisfactory solution is converged upon. I don’t think our current system quite has the resources to do this though.

I still don’t get too much of a break though: I’d like to re-do the compiler, this time with a better design; I need to catch up on some neglected research; and I want to play around with Google’s new language Go.

The Libertarian think tank CATO recently published a small, trite piece that attempts to establish The Case against Literary (and Software) Patents. Being a Libertarian, I actually agree with the position; I just don’t think that this article fully explored the issue. Here, I seek to provide some links to more fundamental content.

It begins with the hypothetical existence of a ‘Literature patent’. I consider such an idea to be terrible at face value, and the article actually dismisses it as much. It would be ridiculous to expect every author to carefully comb over their work making sure that it doesn’t infringe on any registered plots or (worse!) plot devices (good buy holodeck!) Acquiring knowledge of registered patents would be prohibitive for a beginning author, they’d have to rely on publishers/editors. This significantly raises the cost of creating an innovative work. Not to mention the human effort the government must spend to maintain consistency in it’s patent database, and the legal costs and liabilities for the inevitable infringement.

The article then proceeds to demonstrate what happens in patentable areas. Immediately, there is a land grab on the ‘low hanging fruit’. During this process, established market leaders tend to benefit, because the have the resources (both funds and people) to make a large number of claims and file the required paperwork (economics of scale apply to paper shuffling too). Typically only a relatively few companies will be successful in this endeavor. The initial grab might also appear to be an ‘economic stimulus’, as it will show a remarkably steep and sudden interest in the field, resulting from the underlying similarity of the tragedy of the commons. After the market settles, a few incumbents then use their patent portfolios to threaten up-start competition. As the article points out, in the world of software patents, so much of the field is so obvious, that agents without an explicit interest in software will find themselves infringing as a normal course of their business but will be without their own patent portfolio and unable to make a bargaining counter-threat.

Another economic phenomenon that happens as a result of the patent system’s existence is economic stalemate. This actually happened with the sewing machine, as recorded by Adam Mossoff in A Stitch in Time: The Rise and Fall of the Sewing Machine Patent Thicket, which was blogged about at the Volokh Conspiracy. He recounts how the marketing and distribution of the sewing machine was actually encumbered by the patent system, because the machine required the combination of several innovations, and no single agent held all patents on the functionality. History also demonstrates the practice of ‘patent trolling’, whereby a company, which doesn’t actually produce anything, seeks to profit by legal threats of infringement and licensing agreements on its patent portfolio. The resulting stalemate was finally resolved through the explicit creation of a patent-holding company, whose sole function was to share the patents and resulting profits of all involved manufacturing firms.

So we can see that for areas where copyright is already established practice, the introduction of an extension of the patent system results in litigation and paperwork and encourages the preservation of an established regime of a few powerful companies working in loose collusion, both of which tend to outweigh any potential benefits to development and innovation

Now, I’d like to go out on a limb here, and reject the very concept of ‘Intellectual Property’. Richard Stallman has spoken out against its use, and continuously advertises the fact that it’s deceptive and misleading. At the root of the issue is that ideas and physical matter behave differently. That is, copying != stealing. The reasoning behind this position is fairly simple, when an idea is copied that does not deprive the original possessor from the idea. When you tell me about your theory of X, you don’t suddenly forget after telling me. In contrast, if you give me an apple, now you no longer have that apple. Ideas are part of a different realm of existence.

Finally, I’d like to point out the slippery slope, what happens if we go too far with this property idea: we might lose The Right to Read, or watch How creativity is being strangled by the law.

I hope that through these references, you can see where, how, and why I’ve developed my position on the patent issue; I’m firmly on the side of maximum freedom (and that includes the opening up of all media: open-music, open-software, open-hardware, open-design, open-architecture, open-video, open-government, open-literature, etc…)

I didn’t know it at the time I posted my idea on secure computing, but others have been working on the idea for quite some time. It turns out that Craig Gentry recently published Fully homomorphic encryption using ideal lattices. For those, like myself, who are not well versed in the crypto terminology, Scott Aaronson provides a nice summary.

First, in what might or might not turn out to be the biggest cryptographic breakthrough in decades, Craig Gentry has proposed a fully homomorphic encryption scheme based on ideal lattices: that is, a scheme that lets you perform arbitrary computations on encrypted data without decrypting it. Currently, Gentry’s scheme is not known to be breakable even by quantum computers—despite a 2002 result of van Dam, Hallgren, and Ip, which said that if a fully homomorphic encryption scheme existed, then it could be broken by a quantum computer. (The catch? Van Dam et al.’s result applied to deterministic encryption schemes; Gentry’s is probabilistic.)

So this essentially fulfills my idea, that in order to take advantage of cloud services, it’s imperative that you be able to store and compute in an encrypted domain. Otherwise, your service provider might spy on you.

Yesterday, I had an interesting thought. My advisor once made the cultural observation that many people in Computer Science invent their own language and then immediately write a self-hosting compiler. I agree that a compiler is quite a feat of engineering and serves as a nice test case to demonstrate that the language you’ve invented is powerful enough that it can handle real-world complexity. Unfortunately, this test fails in a few important ways.

First, It doesn’t actually show as much as you think it might. There is a very strong filter on failed languages. By using this test the author runs the risk of re-designing the language, specifically to insert constructs that help them build the compiler. Now, this isn’t necessarily a bad thing, except that compiler writing is now a fairly mature field. There are standard abstractions (esp. in the lexing and parsing) that a new language will probably not experiment with. So, the author will usually just build these existing and well-understood abstractions into the new language. Rather than encouraging language experimentation we get more of the same, but with different syntax.

Second, Not all useful languages even have their own compiler. I’m specifically thinking of the domain specific languages (DSL). Nobody would write an awk interpreter in awk; or a mail engine using sendmail (even if it is Turing Complete). These are languages designed to do a specific task, many of them are quite essential to their respective fields, but none of them are self-hosting. Nor should we expect them to be.

My argument here is that the cultural practice of writing a self-hosting compiler is a big distraction. New languages should be for experimenting with new linguistic constructs. We should be looking toward the DSLs, and incorporating their innovations into our more main-stream languages. Right now, we seem to be optimizing our languages for compiler construction.

I’d rather see our languages evolve in a different direction. I’m really eager to witness the birth of an AI. For this to happen though, we need languages for expressing patterns of thought, not patterns of bits. We need the ability to cohesively and flexibly assemble the stuff of thought. I’m thinking Society of Mind stuff here. We need languages that allow for statistical fuzziness, sloppy associativity, and the ability to construct metaphor.

The linguistic tools that we find useful for building compilers are not necessarily the same tools that will help us build a mind.

When I visited Washington D.C. for ASPLOS/VEE, I was working on my paper about cascade failure, and had distributed systems on my mind. Some of the papers at the joint conference were about garbage collection. One of the more interestring had an approach called leak pruning, for solving logical leaks. After awhile, I had an interesting idea that merged a bit of these two fields.

You see, distributed systems and garbage collection are both about graph problems. In the case of distributed systems, it’s usually about minimizing traffic along the edges, or performing some kind of global computation by communication with neighbors. In garbage collection, we’re concerned about reference cycles and reachability. But what if you ask: Is it possible for an object (node in graph) to decide, for itself, when it has been disconnected from a root node? In answering this question I came up with a very simple approach. I’ve been sitting on it for awhile, but, just yesterday, the paper was typed up in a hurry and submitted to the Fun Ideas and Thoughts session of PLDI.

The primary idea is this: If root nodes are tagged with a high value, and heap nodes are tagged with a low value, and each object acts as a node performing a distributed computation, then the average value of any subgraph that becomes disconnected from the roots will continuously decay. When it falls below a threshold value, that whole cluster can safely be collected.

There are some implementation details though. It’s going to be easiest to process these updates in an event queue in a separate garbage collection thread, rather than as a real distributed computation. When updating a single node, if we add to the queue all the points-to nodes, then the queue will rapidly grow without bound. But, we actually don’t care too much about how quickly the average worthiness is computed, so we can easily get away with adding only those nodes that are not already present in the queue.

The second problem is that references are directional. So, if we rely only the queue to hold references to objects, then it is possible for a set of nodes to become stranded (referenced neither by the queue, nor by the program) For example, the deleted branch of a subtree. We’d initially process the root of the branch, and proceed down to the leaves, but since it has no cycles we will loose all references to it, because the processed nodes will not be re-entered into the queue. (the program asked for it to be deleted, and the garbage collector does not maintain a list of all allocation sites) But this problem only happens for acyclic structures, so it can be solved by reference counting. When we go to update a node, it is safe to collect it if its reference count is zero, regardless of its worthiness value.

The third problem is that the average worthiness value of the program-reachable cluster of nodes will go down with the number of objects held by the program. This might limit the program size, but I think that the natural range of an unsigned double should be enough to solve this problem. Root nodes can have the value MAX_DOUBLE, and even if the program holds 10^6 objects, the average is still very high.

A fourth problem is the decay rate of unreachable clusters. This will be a function of both the computed worthiness at the time of disconnect, and the number of nodes in the cluster. I will probably have to adjust the formula given in my paper so that it has a faster decay rate. Unfortunately, this and the third problem above are in conflict with each other. Having high valued root nodes allows programs with more objects, but also extends the decay time.

I don’t claim this approach to be efficient, but I do claim that it’s simple to implement, and should scale nicely. Also, it might be useful for process collection in a distributed system. I’ll know if the idea was too crazy when review committee results are released on May 29.

Last week, I landed on another PhD worthy research project.

Given a very large corpus of sentences, such as a digitized version of the Library of Congress, or a less noisy version of the Internet, how can you automatically generate a Thesaurus?

At first I thought the problem should be fairly easy, but the more I thought about it the more difficult and daunting the task became. For example, as a first approach, we might assume that textual substitution would be a good proxy for identifying synonymous terms. That is if a couple terms really are synonymous, then they ought to be substitutable for each other in a sentence. With a large enough set of sentences, we should be able to identify such situations, and thereby bootstrap the building of the thesaurus. But there’s a small problem, provided by my good friend EvB:

The sky is blue.
The ocean is blue.

But sky is not the same as ocean. Sure they are similar. A poet could compose a nice metaphor of fish swimming through their sky above the bottom feeders. But this metaphorical relationship isn’t one that would necessarily make it into a human compile thesaurus. So, textual substitution can easily lead us astray.

Continuing with EvB’s particularly good example we can also identify another problem. Suppose that we incorporate a bit of natural language understanding, enough to pull out parts of speech. Then, the system would easily identify the equation of sky with blue, or ocean with blue. But neither of these statements is true either. Usually people take the example to mean not that sky and blue are the same thing, but that the sky belongs to the set of objects that have a property called color, the value of which is blue. So this understanding depends on what the definition of ‘is’ is (obviously not a simple affair). We also would like to avoid drawing a relationship between any of the pronouns and the rest of the language.

Next lets look at how people tend to write. Any good library is gonna be full of metaphor, simile, pun, allusion, word play, sound play, and other such highly nuanced expression. All of these things will trump any reasonably simple attempt at drawing a link between synonymous words. Political propaganda and polemic, will probably be particularly bad at equating terms that should probably be kept logically distinct. Furthermore, at least when I write, I’m reminded of other things during the process, things that are associated, but not necessarily synonymous. These remindings are an important part of the essay writing process, but will certainly throw noise into the digital library.

But if it’s so hard to make a mechanical system for identifying synonyms, then how do humans do it? Here I have a hypothesis: that similar words stimulate similar patterns in the brain. Thus when a human tries to think up synonyms it’s really the same as playing word association with a filter. First, the word stimulates the brain, bring up certain associations. These associations will be based on ‘brain distance’, a measure of the similarity of brain activity for certain words and thoughts. But some associations will be radically different from the synonyms that we’re looking for. For example, antonyms and non-sequiturs often come up in word association games. So a filter is applied to weed these out, and what’s left is passed through a dictionary/meaning check. Anything passing this process will be reported as a synonymous term.

So, in order to really generate a thesaurus, we do need AI (or at least an underlying cognitive model). When I first thought of the thesaurus problem, I was hoping that it was paired down enough, small and simple enough that it would be doable without all this complexity. We might have to reduce the problem further, make it looser. Say, build an association dictionary, rather than a thesaurus. An association dictionary might be possible, because it forgoes the understanding of meaning and similarity, it doesn’t have to question or measure why two words should be associated, only record that they are used similarly.

So, if you can automate the building of a thesaurus, you should get a PhD in Linguistics.

For some reason I was thinking about the cascade failure problem that I mentioned before my Holiday Hiatus. I discovered that this problem has gone largely unsolved when attending ACSAC ‘08, and it’s been in the back of my mind (and on my whiteboard) since then. I’ve looked online a bit to see wether any researchers are attacking the problem, and it seems that very few are. Most of the work is also around containment of the failure rather than prevention. Most of the solutions resemble burning swaths of trees to save the forest from a fire; this disgustingly requires global knowledge of the network. Also, the systems today seem to me to be built rather naively: nodes very simply reroute traffic based on failure, without taking into account the possibility that in so doing they might overtraffic their neighbors, and thus trigger a cascade. There also seems to be a lack of information in textbooks about running networks near capacity (this is desired for efficient utilization of the network, but can drastically increase the probability of cascade).

So, I want to introduce a few constraints and assumptions before I state my rough solution. Assuming the network can be viewed as a graph with nodes and edges, where some goods (power, packets, traffic) is flowing along edges from one node to another, I’d prefer a solution that used local knowledge (node capacity, and possible neighbor capacities) instead of global knowledge. So I’ll assume that each node can keep track of how much stuff is flowing through it, and what the traffic patterns actually are; that is: how much stuff goes from edge 1 to edge 2.

In computer networks it is also possible for a node to track the possible re-routings that certain packets can take and still arrive at their destination. (I don’t know wether this is true of power delivery in the electric grid, but I’m going to assume that something analogous still holds.) Each node will be responsible for measuring traffic capacity: That is for each stream of traffic, it will keep track of what other edges could have had that traffic routed onto them. Each node will also observe a capacity constraint: It will discourage traffic that cannot be re-routed if the primary edge for that traffic suddenly fails. In this way we can keep a reserve capacity in case of edge failure.

When an edge fails, the node will re-route its current traffic in a load balanced manner along the secondary edges available for that traffic. This will temporarily violate the reserve capacity constraint, but not over-traffic other nodes. [Actually I don't think this is true, unless the node can use capacity info from its neighbors] In this way, outage of a single edge cannot trigger a cascade failure, because enough reserve capacity is always available for the traffic that was allocated to the failed edge.

Still to be addressed:
• Node failures which can cause multiple simultaneous edge failures.
• Characterize the efficiency in terms of what is kept as reserve capacity and theoretical max capacity in the naive systems
• Formalize the measurements taken by each node
• Investigate push vs pull flows (power grid is demand based, computer networks are push)
• Do nodes still need a means of capping their flow? (can the power grid drop packets?) I’d prefer not to require this.
• Specify what each node is to communicate to its neighbors
• Investigate the use of probability for multiple node failures (earthquake, software bug). Failures are not generally identically distributed or independent

So, I went to ACSAC the other week, and sketched out some crazy notes:

It seems that nobody is really working on large scale distributed systems reliability. By this I mean things like the Internet and the Power Grid. Both of these are highly distributed systems, where nodes automatically route around local failures. Unfortunately, and probably due to locality of knowledge, cascade failure is still an unsolved issue. Most of the solutions require early detection, and prevent systemic failure by removing of key nodes before things begin to cascade. This is quite similar to bulldozing trees to save the forest. It’s a sub-optimal solution. It’s also extremely difficult to automate, as it requires more global knowledge and assumes reliable control system connectivity in order to direct shutdown. It would be much better if each node behaved in such a way as to dampen the ‘cascade wave’ while still having only localized knowledge.

In some cases, rebooting becomes an issue. The graphic on wikipedia shows this quite well, when the center node reboots and becomes the only link in a high-demand chain. In the real power grid not all stations are capable of coming online without a fairly large kick-start from the grid itself. That is, some of the emergency/peak generators require power to start up. In a total network outage, you might find yourself without power for a while, even though you have a generator. Also, the power grid is run as close to maximum capacity as possible (for efficiency reasons) even though this increases the likelihood that a local failure can trigger a cascade.

Also these lines, I’ve also scrawled that it would be nice if a network protocol could give early warning of DDOS or similar attacks. Is early warning of global events possible in a distributed system with very localized knowledge at each node? given the lack of central authority, who would receive the warning? neighbor nodes? Can the protocol be specified so as to dampen over-traffic attacks? What info must a node disclose about itself in order to prevent a cascade failure (econ, info theory)?

Whitfield Diffie also spoke at the conference. He was nice enough to give explicit Creative Commons permission to record and distribute his speech, if any of us felt so inclined. He gave an off-the-cuff history of cryptography and society, with a focus on how we modify our behavior and adjust our risk-cost tradeoffs as technology changes. He also mentioned that he prefers Availability to Integrity to Confidentiality; that is, He thinks the rest of the security world has priories reversed.

Some more chicken-scratch:
Is it possible to do a BCC encryption? So that Alice post a single message a public BBS that can be read by both Bod and Charles, but each thinks they are the only recipient. Can this be done (a) transparently (b) in a way that adjusts to addition and removal of members in the group. Secure IRC, IM chat.

The best way to secure computer systems is probably to look toward biology, and create an immune system. Learning, dynamic collection of agents that monitor and repair.

We’ve reached the NP-completeness section of my Fundamental Algorithms class, and I’ve noticed something interesting about P and NP.

We have problems from a variety of different fields, for which one instance of the problem is in class P and the other is NP-Complete. I conjecture that whatever property it is that separates one class from the other, it must show up in all such fields. So the underlying fundamental reason for separating P from NP must translate from graph theory to boolean logic theory. It would be nice to gather such example divisions and then try to formulate an isomorphisms between fields. I’d think that eventually an isomorphism will be found that sheds enough light on the P vs NP problem that it can finally be cracked.

What really got me interested in this problem was noticing that Hamiltonian Cycle would be very easy to solve if we could convert it into an Euler tour by constructing an interchange graph; where all the nodes become edges and all the edges become nodes. But interchange is not a well defined operation on graphs, indeed it isn’t even possible in some cases. Example: The graph of 5 nodes and 0 edges. The interchange would have 0 nodes and 5 edges, which isn’t a graph. So, I was wildly speculating that perhaps what separates P from NP are these impossible operations. But to shed some light on the situation, I’d first want to construct a reduction of Euler tour from 2-SAT which mirrors the reduction of Hamiltonian cycle from 3-SAT.

Today I decided to send the following email. Usually, when I do such things it doesn’t make any difference. But it still never hurts to try. We’ll see what becomes of my efforts this time.

Dear PZ Myers and richarddawkins.net,

I wanted the following to go personally to Richard Dawkins, but could not find his personal email through websearching (likely with very good reason). I’m uncertain wether he has the opportunity to read every mail sent to richarddawkins.net; So I humbly ask you to forward this (at your own discretion) to the Eminent Professor of Public Understanding of Science. Oh and feel welcome to post this communication publicly, in part or in full. (Comment feedback from either or both of Pharyngula and richarddawkins.net readers would likely be rather informative)

——-
Dear Darwin’s Rottweiler,

On several occasions I’ve heard you mention that you’d like to, or were considering writing a children’s book. I think that this is an astounding idea. I share your views that the uncritical acceptance of religion, and the assumed authority it has over moral issues poisons our culture, and threatens our social progress. I currently think that the primary reason for the perniciousness of religious belief is that it is crammed into the skulls of children before they’ve developed the capacity for critical thinking or other tools of intellectual defense. Children’s books that promulgate the values of the Enlightenment could very well be the best weaponry against religion that we have at our disposal. And it doesn’t even have to appear as an attack!

I would like very much to see a series of children’s books that propagate some of the allegorical tales in science. The stories could cover Newton’s Apple, Galileo and the Tower of Pisa, Friedrich Kekule and the Benzene Ouroboros, Eratosthenes and the Round Earth, Copernicus and Geo-Centrism, Archimedes and the Bathtub, Watson and Crick and their puzzle pieces, Einstein and the light-train, Alexander Fleming and his dirty dishes. Science is replete with heroes that should be celebrated for their hard and tireless brain-work; heroes that used their mind and reason to solve real-world problems; heroes that stood up against dogmatic authority. These stories should celebrate such individual efforts, acknowledge their personal sacrifices, and encourage children to become active participants in growing our collective knowledge. (We should also celebrate supporting roles, not exclusively heroes; since, realistically, that’s where most of us are positioned.)

In my mind many of these stories would be ideal for bedtime. I think it is more important to instill in children the values of science rather than its teachings. If society were to completely lose its scientific knowledge, a social structure that encourages well-thought-out dissent, evidence-based critique, and the importance of experimental repeatability, logic, reason, precision in communication, would be vitally important to regaining that knowledge. The methods of science are more important than the results of science; and children’s stories should draw upon this phenomenon, instilling values rather than dry facts. The very notion that by reason alone we can come to know more about the world and our position in it, is, to me, much more inspiring than anything religion has to offer. And I feel it is a moral obligation to communicate this innately human desire to our children, such that they might learn our methods early and be ably equipped to build upon our work as early as possible. To demonstrate through stories that the best, prooven and reliable method for getting ahead in life, is to use your mind for understanding what you observe around you.

There are so many children’s story books that focus on tales from the bible, that it’s time we created some competition. Most of these books tend to have an overtly moral tone to them; please make every effort to avoid that. Even children can tell when they are being preached to, and they grow to resent such condescension.

I’ve also noticed a wild cry among the populace that science education is faltering in America. I have personal experience that tells me technically minded parents are quite concerned about the current state of affairs, and already make efforts outside of the curriculum to inspire their children in the ways of science and math. Help give these families some tools to teach their children what the education system ignores. I eagerly look forward to any effort you make in this direction, and I’m sure that geek parents everywhere will rejoice in the marketplace once such materials appear.

Inspire them while they’re young!

PS. Thank you (both) for speaking your opinions about issues of religion, and raising our collective consciousness about its uncritical acceptance in our society.