NStatic Status

It’s been about a month since I last posted, and people are wondering about status of NStatic. I have been setting myself quite a few deadlines in the past for releasing a beta. It’s getting there, but there are some of the issues I encountered.

July has been one of my least productive months as I was distracted by important personal matters, the Shareware Industry conference, and the weeklong impact of the heat wave on my residence with no air-conditioning. The month may also prove to be the most expensive. The first week of August is also likely to be fruitless as I am attending the Lang.Net symposium at Microsoft as well as my cousin’s wedding in Aug 5. Right now, I am planning to impose more discipline.

With a new product based on smarts, it’s hard to predict how well the product will perform in actual usage. I have had to partially rewrite my algorithms at least two times, because the find rate and performance wasn’t there. I noticed that I needed to gather much more information and to address a number of performance issues. I am hoping with this final revision that a full scan of very large program will proceed in a short time — and not hours or days. Most of the changes I made, being improvements to my AI routines, fortunately have general applicability to future programs that I write.

My product is basically an interpreter that that executes each line of code symbolically, branches out into multiple states at each unknown condition and merges regularly to avoid an exponential explosion of code paths explored. This approach allows me to handle a lot of phenomenon easily such as delegates, closures, iterators, gotos, and reflection. It also makes it rather trivial to support features in dynamic languages like Perl such as late-binding, dynamic scoping, and non-local gotos. Potentially large states are efficiently stored in persistent hashtables. Persistent data structures really makes it easy to achieve efficiently the equivalent of time travel and multiple universes in programming.

I recently discovered several tools, ESC/Java, for instance, in addition to Spec#, that perform similar levels of analysis although with a different approach. One of the developers from ESC/Java appears to have left HP to work for Microsoft, possibly in the Spec# group. Both of these programs transform the entire program into an abstract predicate representation which is then analyzed by a theorem prover. I deliberately avoid learning too much about these programs until after I have developing my algorithms, because the static analysis arena is a patent minefield. Quick research indicates that both of these tools are guarded by patents. I did remove a feature in my rules language in response to a Parasoft patent I discovered; this was disconcerting to me as I came up with the same idea in the late nineties before the patent was approved.

There is one thing that I noticed is that all of these tools handle looping constructs poorly, tending to either ignore all variables changed with a loop or abort a method scan in the presence of a loop. I came up with a fairly simple algorithm based on recurrence relations for handling loops in an exact manner.

I going to spend this coming month focused on delivery. This is the current interface (using the black theme); they’ll be a number of additional UI changes.

In a previous post, I mentioned the use of Direct-UI. As my build is currently destabilized, I am using an picture from April that I mailed to Judah. This was an early implementation with a lot of display bugs, but it does illustrate a few concepts such as arrows showing the flow of execution, the dimming of untraversed code, and the highlighting of various conditions.

 

Comments

[damien]

Do you have any links to information on persistent (functional-style) hashtables?

I thought hashtables are an ADT that isnt well-handled by functional programming.

[Wes]

I currently use a treap to represent associative maps, which give log n behavior.

Persistent hashtables which O(1) are possible through various strategies such as using a chained-hashtable which maintains version info in each chain node, or basing the hashtable on a vlist, an array-like data structure which gives constant access times on average, especially good if hashtables are primarily growing.

A few points:
1) persistent != immutable; they are orthogonal concepts. I recently pointed to a paper by Professor Sleator on the topic of making any data structure persistent.
2) you can get better performance by actually mutating the private data of the hashtable while maintaining the outward appearance of immutability.

[Haacked]

Wow! The UI has taken some huge steps forward. Nice work.

[Judah]

I was wondering if everything was OK for you; you mentioned some personal troubles and then you stopped posting for so long. Good to see you back, I hope everything has settled.

I see the UI has changed a lot. Using a black Office 12 look...nice.

Looking forward to that beta. I know how difficult it is to get something ready to finally roll out the door.

p.s. thanks for the blog plug.