Satisfiability & Verification

The field is getting mature: a new book 'Satisfiability & Verification' by Marc Herbstritt which I should buy.



I used to like sat research; I think I skimmed through about three thousand articles and read about ten percent of that.

A Proof I am getting Old

Saw this on local television:

MD: What is your problem?

Child: It itches.

Child shows rash to MD.

MD: That's shingles. It weal heal in a few weeks. Just a virus, don't worry.

Child now looks very confused.

Child: I am not a computer. How can I have a virus?

Clay Shirky: Gin, Television, and Social Surplus

Clay Shirky on what we can accomplish if we stop watching tv.

So how big is that surplus? So if you take Wikipedia as a kind of unit, all of Wikipedia, the whole project--every page, every edit, every talk page, every line of code, in every language that Wikipedia exists in--that represents something like the cumulation of 100 million hours of human thought. I worked this out with Martin Wattenberg at IBM; it's a back-of-the-envelope calculation, but it's the right order of magnitude, about 100 million hours of thought.



And television watching? Two hundred billion hours, in the U.S. alone, every year. Put another way, now that we have a unit, that's 2,000 Wikipedia projects a year spent watching television. Or put still another way, in the U.S., we spend 100 million hours every weekend, just watching the ads. This is a pretty big surplus.

Through Wadler's blog.

Equality Saturation

Equality Saturation: A New Approach to Optimization, Ross Tate, Michael Stepp, Zachary Tatlock, Sorin Lerner, POPL 2009.

Optimizations in a traditional compiler are applied sequentially, with each optimization destructively modifying the program to produce a transformed program that is then passed to the next optimization.

We present a new approach for structuring the optimization phase of a compiler. In our approach, optimizations take the form of equality analyses that add equality information to a common intermediate representation. The optimizer works by repeatedly applying these analyses to infer equivalences between program fragments, thus saturating the intermediate representation with equalities. Once saturated, the intermediate representation encodes multiple optimized versions of the input program.

At this point, a profitability heuristic picks the final optimized program from the various programs represented in the saturated representation. Our proposed way of structuring optimizers has a variety of benefits over previous approaches: our approach obviates the need to worry about optimization ordering, enables the use of a global optimization heuristic that selects among fully optimized programs, and can be used to perform translation validation, even on compilers other than our own.

We present our approach, formalize it, and describe our choice of intermediate representation. We also present experimental results showing that our approach is practical in terms of time and space overhead, is effective at discovering intricate optimization opportunities, and is effective at performing translation validation for a realistic optimizer.

This is a great approach to classical optimizations.

Peta

Funny, just found her photo by chance, one in six billion; should call her once.

Darn

Forgot 100 Euros at the ATM. Been booked away too. Stupidity kills.

Dark Humour

Below, some black political comments. Not necessarily true or even the opinion of the author.

Obama failed to lie and presented an honest budget. The US government will run a $1,750bn fiscal deficit this year. Equivalent to 12.3 per cent of gross domestic product, the biggest yearly deficit since the second world war.

• US deficit first year: 1.75 trillion, second year: 1.75 trillion, third year: 1.3 trillion, fourth year: 550 billion.
  
  (We need money now but they're on to US. Let's borrow while we still can and push the deficit from the last year to the first three years and pray nobody notices)
  


• The US will enforce a cap on carbon dioxide emissions.
  
  (We won't have enough money to pay for oil in the future.)
  


• The plan reserves a whopping 634 billion dollars over 10 years to finance reforms to make health coverage affordable.
  
  (Damned, we screwed up! We didn't save enough money to take care of our elderly.)
  


• Money will be pored into education.
  
  (Fuck, all our PhDs are Asian or moving there! Unless we develop some intellect of our own, we'll never run a trade surplus.)
  


• The rich will be taxed more, the poor less.
  
  (Big red flag. If it freezes in hell then the US must be in a really, really, really tight spot.)
  


• The US could funnel up to $750 billion in fresh government aid to their battered banks. Some banks may be nationalized.
  
  (Hey! The Chinese have four state owned banks which just own the economy. Why didn't we think of that?)
  


• Most US Troops will be out of Iraq by August 31, 2010.
  
  (We threw our ethnic minorities into a desert but the simple harsh bastards ignore the possibility to die.)
  


• US spending on defence will be up 4%.
  
  (If the Asians start borrowing money to other nations and want their money back, we'd better have a strong arm.)
  

Meanwhile, teethless Europe is poring money into the IMF, nationalizing, and counting their left money. They also warn the Chinese that surplus countries have the most to lose in a recession.

(Blimey, the US robbed us, our manufacturing is now placed in Asia, and the Liberians are now asking the Chinese for money! Better poor money into the IMF before they get out of our strong-hold. Why are these Chinese laughing at us?)

The biggest joke: Given circumstances, Obama is doing a good job.