Smart Software

Energy Redux

In my Performance Enhancers post, I remarked about an energy formula called RedLine. My observation after using it for a few months is that the drink seems to be effective for weight loss in addition to building energy. RedLine was a bit hard on my heart, so I sipped about a fifth of a bottle a day rather than the recommended half of the bottle, and switched my primary drink backed to Rockstar.

A few weeks ago, I tried a new energy drink, FRS healthy energy. I was actually impressed by its effectiveness with few calories and no caffeine. Unlike the other two products, my energy feels eerily natural. I was actually skeptical after the first day of use, because I expected to feel some kind of artificial kick but instead experienced a sustained (possibly heightened) "normalcy" in my energy level, the kind of energy one feels early in the day. Only after several drinks in one sitting, after which I was unable to sleep for a whole night yet was energetic as ever, did I come to the conclusion that the product was real.

This may be something that I could use on regular basis without worrying about the future risk of heart disease.

Blog Update

While I haven't written in a while, I will be posting additional entries more frequently in the near future.

There's been a number of posts that I started writing on various issues of the day over the past six months, but a confluence of different factors have caused me to postpone or not publish my entries.

This post serves to reacclimate myself to the blogging habit.

Lang.NET Presentation

I presented at both the Lang.NET Symposium and Seattle Code Camp, but it didn't proceed as I originally planned.

For several months, I have been changing the back end of my software to scale better and retain sufficient control of the performance of my product under all circumstances. I do have some hard-coded limits, but these limits and time constraints don't really work well the way my software is written. They are better for catching events that should never happen. The changes were extensive as I used functions pervasively to compress the size of my expressions and maintain the invariant that expression size stay proportional to program size. Manipulating arbitrary functions, particularly recursive functions, in a general and efficient way is really difficult.

I was using these two events as a forcing function for releasing my software. Unfortunately, I didn't make my deadline. I lost about several days of productivity due to a random apartment incident. I skipped a day and half of the conference to prepare in a valiant attempt to demo the most recent build of my software. Instead, I used an old release of my software from six months back, and messed up my demo since I forgot that I could only execute expression in the immediate window from within the context of an error.

My presentation relied heavily on slides rather than a live demo, which was not my plan. People want live code. Presentation slides also leave the audience confuse about the nature of the product as Ted Neward wrote in his Lang.NET review.

For people reading my blog, there wasn't too much extra information above and beyond what I have talked about in the past, since I could not assume that people were aware of my product. Some new points include the liveness of the environment, closed forms and some manipulations with functions.

I am wary about giving too much information, since I have leaked so much already for a considerable period of time without actually releasing the product.

I prepared the slide a month in advance, hoping that I would make changes over the course of the month, but ended up spending a full day polishing the presentation before my Code Camp talk.

Some reactions:

• Four Microsoft researchers quizzed me.
• A number of people that I have met read my blog... Most of the Microsoftees appeared to be familiar with me.
• A few people asked how they could apply for the beta. Others were hoping for a Java version. Miguel comment to me that it was a great presentation. I was surprise of my healthy applause, because I hadn't been paying attention and have never given any applause. The applause level was similar to Miguel's presentation later on, so I couldn't actually tell if the applause was enthusiastic or ordinary.
• Some questions on technical aspects:
  • did I utilize an available prover software like Z3? I wrote the software myself.
  • has my prover been benchmarked? No, and it's doesn't deal with the types of formulas use in the benchmarks.
  • how do I handle complicated cases like overflow. My overflow checking is very limited, since, in the past, I wasn't interested in cluttering my assumptions, but adding such support is trivial and now also less problematic.
  • how do I deal with invoking function variables (ie, delegates). I represent them exactly, but, for the sake of analysis, I ignore the potential effect on state if the function is unknown.

Postmortem:

• Create setup files regularly. Though I update component libraries frequently, I relied too much on .NET's XCopy support. Despite having copy DLLs to output folder, I was not able to get the build that I want working.
• Save interesting snapshot pictures of the product while in development. I reused a lot of images from my blog.
• Always try to have a working build. Include notes about the status of the software. I took a random setup build without remembering what state it was in.
• Conversations and event draw energy away from me. I usually enjoy my energy juices and bars before development, but I should actually remember to do even more so before presentations.
• Get well-rested before a presentation. This is unusually difficult for me, because I work during nights and sleep during the day.

There is still a geek dinner coming up in the next week that I may take advantage of to give a live demonstration.

Playing Chess with God

Although the title is appropriate, I wasn't actually planning on writing a post about the legendary chess grandmaster, Bobby Fischer, who died in the past few days, but I will take a few moments to pay my respects.

I was a long admirer of him, and, over the years, I identified with him ever more over the years. Here was this young natural talent who defeated several highly trained Soviet chessplayers to end Soviet domination of the chess world title. He was also very individualistic, provocative and controversial, breaking taboos and openly defying the government, by traveling to Serbia despite sanctions. In the same vein now, I do fancy myself competing against other companies and speaking freely.

Back to my intended post, I found this interesting post called "Play Chess with God" by an interesting new blogger, Russ Cox. This and his other post, SuperOptimizer, deals with computer solutions to traditional human problems mainly through brute force techniques.

Starting in the late 1970s, Ken Thompson proved by example that computers could completely analyze chess endgames, which involve only a small number of pieces. Thompson's key insight was that when there are only a few pieces on the board, there might be very many possible move sequences, but there are relatively few distinct board positions.

Given six pieces in the board, it became a simple lookup with Ken's endgame database to determine the best next move to make. Russ quotes former championship chess player Tim Krabbe describing his experiences using said database:

Playing over these moves is an eerie experience. They are not human; a grandmaster does not understand them any better than someone who has learned chess yesterday. The knights jump, the kings orbit, the sun goes down, and every move is the truth. It's like being revealed the Meaning of Life, but it's in Estonian.

While my software relies more on intelligent rules rather than brute-force techniques, the feelings and experience that I have experienced are more or less the same. My initial thought sometimes on seeing a strange result calculated by my NStatic tool is denial with the full belief that I am witnessing a software bug, only to discover after careful analysis and to my surprise that the computer's solution is in fact correct.

I don't claim this experience to be unique. This should be familiar to anyone who has ever played chess against the computer or used a declarative programming language with unpredictable control flow.

Performance Enhancers

Marion Jones, former Olympian gold medal, may be serving time for lying about using performance-enhancing drugs.

I myself have a confession to make. I use performance enhancers to gain that extra unnatural edge over other developers. I am currently using RedLine, a potent energy enhancing formula, which I ordered from Amazon a month ago, but GNC also stocks the product. I was looking for something a bit more powerful than RockStar, my previous energy drink of choice.

RedLine delivers spectacularly, almost as good as the Ephedra I consumed before it was banned three years ago. It works by inducing the body to shiver. Plus, it doesn't have any calories like RockStar. (The diet version did nothing for me, but RockStar Zero Carb might be more effective than RockStar Diet Drink.)

I have seen many reviews on the Internet by users, about half of which have had extreme reactions (uncontrollable shaking, stomach cramps, elevated heart rate, seizures) from using it and questioning why the product isn't banned by the FDA. It's been called "crack in a bottle." Still, there are others who don't feel affected by it. The product includes multiple warnings, and you are only supposed to drink half a bottle. I am not making a recommendation, because you could possibly die, but I will stick with it.

Principle of Most Power

Turing Completeness

Yesterday was Donald Knuth's seventieth birthday. I used to own the three volumes of his Art of Computer Programming, and have even quoted the book once in my blog regarding corountines. Although the content was valuable, I could not tolerate the use of the MIX assembly language with which Knuth used to implement his algorithms.

Donald Knuth also invented TeX, a markup language for typesetting. As proof of its greatness, Mark Chu-Carroll notes TeX remains dominant 30 years after Knuth wrote the original version. It also happens to be Turing complete. There are other widely used languages, which are Turing-complete, such as PostScript for generating graphical images. The template facility in C++ is Turing-complete by accident, and is used for metaprogramming and performing all sorts of optimizations that used to be done by the compiler.

Principle of Least Power

I encountered a few years ago, Tim Berners-Lee "Principles of Design," which lists a number of design principles for the web architecture.  One of the principles listed in the "Principle of Least Power," which states that we should use a low power language that is easy to implement and use.

In choosing computer languages, there are classes of program which range from the plainly descriptive (...HTML) though logical languages of limited power ...which include limited propositional logic, though declarative languages which verge on the Turing Complete (PDF) through those which are in fact Turing Complete though one is led not to use them that way (XSLT, SQL) to those which are unashamedly procedural (Java, C).

The choice of language is a common design choice. The low power end of the scale is typically simpler to design, implement and use, but the high power end of the scale has all the attraction of being an open-ended hook into which anything can be placed: a door to uses bounded only by the imagination of the programmer.

Computer Science in the 1960s to 80s spent a lot of effort making languages which were as powerful as possible. Nowadays we have to appreciate the reasons for picking not the most powerful solution but the least powerful. The reason for this is that the less powerful the language, the more you can do with the data stored in that language. If you write it in a simple declarative from, anyone can write a program to analyze it in many ways. The Semantic Web is an attempt, largely, to map large quantities of existing data onto a common language so that the data can be analyzed in ways never dreamed of by its creators. If, for example, a web page with weather data has RDF describing that data, a user can retrieve it as a table, perhaps average it, plot it, deduce things from it in combination with other information. At the other end of the scale is the weather information portrayed by the cunning Java applet. While this might allow a very cool user interface, it cannot be analyzed at all. The search engine finding the page will have no idea of what the data is or what it is about. This the only way to find out what a Java applet means is to set it running in front of a person.

The principle makes sense for the Web in which a new device or a new application with unforeseeable constraints may need to interact with or browse the Internet. However, I do not think that we should automatically apply this principle to other domains, yet I have seen this particular design principle crop up again in a few blog posts since then. There are widely used "standard" languages like PostScript, mentioned earlier, that are Turing-complete. When I look at XAML, I see a language crying for Turing power, because I see a lot of half-measures like resources, triggers, property expressions, templates, etc.

Another View -- Principle of Most Power

In "Software Factories and the modeling problem," Steve Maine posits that a triangular tradeoff between efficiency, generality, and precision exists for any modeling language, for which I don't think is necessarily true. I think that his examples of languages favoring generality but sacrificing efficiency involve procedural languages like C# and Cw, which are more complicated that purely functional languages.

My own work over the years have focused on designing a language that is Turing-complete in some respects and provides many of the advantages of functional and logical languages. My concern was that some of these declarative languages used in academia were not practical or fast enough for building applications.

The primary language is C#, but programs in the secondary language are constructed and executed at runtime. Being functional, the language consists of immutable symbolic expressions, which are much easier to analyze that procedural programs. The language also incorporates various forms of logical reasoning. The language is used for representing all types of data and knowledge including documents, mathematical expressions and natural language.

My other concern was non-termination. Execution of the language is through partial simplification, always terminating in a reasonable amount of time, enabling its use within an interactive application. I satisfy myself with a notion of Turing-expressiveness in which the partially simplified expression is extensionally equivalent to its fully simplified value.

Many Different Languages

Usually, advocates of the "Principle of Least Power" also believe that, in the future, people will be using all sorts of languages, because no one language can serve every purpose.

I do not agree with the idea of a need for a dozen different languages. I guess I would prefer just one. With all the new LINQ features, I am seriously considering moving all my scripts from various dynamic languages to C# 3.0 with Dot Net Script or Code Runner.Net.

One of the original goals of C++ was to end the use of many specialized languages by supporting the creation of libraries for custom data types through templates, operator overloading, and object orientation. One problem with operator overloading in the "C"-based languages was operator "overloading," because there were very few standard operators offered in the language.

Emerging trends include metaprogramming and integrated support for DSLs within the languages, allowing these DSLs to use the symbols and rich computational capabilities of the host language.

I think the various advantages and disadvantages of dynamic and static languages (and other language classifications) are based on existing implementations, and they should disappear over time.

This is not to say there won't be many languages in the future. We now have a common language runtime and a dynamic language runtime that raises the base level of new languages with automatic support for garbage collection and reflection. Microsoft is also working on the Phoenix project that promises to a common compiler infrastructure to enable many different languages to benefit from advances in parsing, compiler, and optimization technologies at the same time.

Human-like Reasoning

My goal in my static analysis work is not to solve general problems like the Four Color Theorem, but rather to simulate closely the human reasoning process to solve problems that are generated, comprehendible, and solvable by normal people. Practical and deep, rather than complete.

Humans write programs to be understood by other humans. Human understanding comes about instantaneously or with relatively little effort compared to the work performed by many analysis tools. We typically don't unroll loops and recursion, but instead "get" the meaning of programs by recognizing a few standard patterns. We look at a program and instantly see a sorting operation taking place, for instance. Programs typically consist of these recurring patterns. In many programs, the only complex data structures used are a standard few like arrays, hashtables, linked lists and stacks. My approach to reasoning adheres closely to the way humans think, even when more efficient computational approaches exist, so as to align my software with human performance; the one exception is when non-human-like approach is strictly better in every way, yet yields identical results.

Stephen Wolfram, inventor of Mathematica, wrote a post Mathematics, Mathematica and Uncertainty touching on some of these themes. Even with the more advanced symbolic capabilities of Mathematica--virtually infinite compared to more than my own software package, Wolfram encountered limits trying to use his own system to verify itself.

Sometimes we use the symbolic capabilities of Mathematica to analyze the raw code of Mathematica. But pretty quickly we tend to run right up against undecidability: there's a theoretical limit to what we can automatically verify.

Yet, I think that our approaches deviate somewhat in that Mathematica isn't geared to testing programs. Also, the Mathematica code base is not typical. Being a program for doing mathematics, it naturally consists of advanced mathematics, difficult for mortals to understand and involving non-linear arithmetic, which is theoretically undecidable.

The code was pretty clean. But it was mathematically very sophisticated. And only a very small number of experts (quite a few of whom had actually worked on the code for us) could understand it.

Another point that Wolfram makes is that, contrary to my approach, Mathematica typically avoids imitating humans but instead uses complicated, non-human-friendly procedures extending hundreds of pages in length, roughly the size of the entire analysis portion of my code base.

Think of almost any mathematical operation. Multiplying numbers. Factoring polynomials. Doing integrals. There are traditional human algorithms for doing these things.

And if the code of Mathematica just used those algorithms, it'd probably be quite easy to read. But it'd also be really slow, and fragile.

And in fact one of the things that's happened in Mathematica over the past decade or so is that almost all its internal algorithms have become very broad "polyalgorithms"---with lots of separate algorithms automatically being selected when they're needed. And routinely making use of algorithms from very different parts of the system.

So even if there's some algorithm for doing something that's written out as a page of pseudocode in a paper or a book, the chances are that the real production algorithm in Mathematica is hundreds of pages long---and makes use of perhaps hundreds of other sophisticated algorithms in other parts of the system.

But such algorithms were not constructed to be understandable---and much like things we see in physics or biology, we can see that they work efficiently, but they're really difficult for us humans to understand.

And in general, the way Mathematica works inside just isn't very "human friendly"... Like when Mathematica does an integral. It doesn't use all those little tricks people learn in calculus classes. It uses very systematic and powerful methods that involve elaborate higher mathematics.

Computation as the Ultimate Metaphor

Rodney Brook, an AI professor at MIT and author of Flesh and Machine, wrote this response "Computation as the Ultimate Metaphor" to a question posed by the Edge Foundation, "What have you changed your mind about during the 2007?"

The Edge Foundation is a site that I have long subscribed to by email. [No RSS feed is available]. The Edge promotes discussion by the "third culture," which, according to its words, consists

of those scientists and other thinkers in the empirical world, who through their work and expository writing, are taking the place of the traditional intellectual in rendering visible the deeper meanings of our lives, redefining who and what we are.

Rodney recently questioned his belief in computation as the ultimate metaphor. Computer scientists, he writes, are ultimately biased towards their discipline when they attempt to explain human behavior in terms of computers, just as molecular biologists see their "their level of mechanistic explanation as being ultimately adequate for high level mechanistic descriptions such as physiology and neuroscience to build on as a foundation."

Those of us who are computer scientists by training, and I'm afraid many collaterally damaged scientists of other stripes, tend to use computation as the mechanistic level of explanation for how living systems behave and "think".  I originally gleefully embraced the computational metaphor.

Such a pattern, he argues, in fact recurs regularly at different stages in the history of technological advancements.

If we look back over recent centuries we will see the brain described as a hydrodynamic machine, clockwork, and as a steam engine.  When I was a child in the 1950's I read that the human brain was a telephone switching network.  Later it became a digital computer, and then a massively parallel digital computer.  A few years ago someone put up their hand after a talk I had given at the University of Utah and asked a question I had been waiting for for a couple of years: "Isn't the human brain just like the world wide web?".  The brain always seems to be one of the most advanced technologies that we humans currently have.

I must admit that I do subscribe to the view of computation as the ultimate metaphor, at least in its applicability to the human thought process. While I admit that I may be biased as a software developer, I still retain that belief despite his arguments. It may even be true that the both the computer scientist and the molecular biologist are both right in their thinking, but that each one is exploring a different facet of human behavior that is more appropriate to each discipline.

The universe is a computer, and everything that happens in it--everything produced--is the result of a computation. Everything is a program. By the principle of universality, we can construct a functional expression for it all. My static analysis tool, for example, instantly produces a functional expression for every variable in the program. Each expression is basically a program showing how the value could be computed, but the expression can also be viewed as the value itself, possibly unsimplified.

The same applies to our thoughts and all our natural language utterances. My own work focuses on representing and manipulating natural language as little programs or functional expressions rather than using traditional forms of knowledge representation. Words are "evaluated" by applying their definitions. This has the nice benefit of a tighter relationship between syntax and semantics, better handling of ambiguity, and ease of use similar to other primitive data types. I only became aware of other research manipulating natural language in a functional way through this paper entitled "Realization of Natural Language Interfaces Using Lazy Functional Programming" mentioned in Lambda the Ultimate. "Oh, my god! they stole my idea," I thought until I discovered that functional Montague grammars were invented way back in the 1960s.