I wrote my NStatic tool to perform quickly with the goal of scaling linearly with the size of the code base. Analysis of a single terminal function is done in a single pass and is basically linear with the size of a function. Performance is impacted more by the call depth of some of the functions than by the number of functions in the code base. Even with deep calls, I found ways of keeping analysis tractable through lazy and cached evaluations.
The main issues I am currently grappling with are some scalability issues that I discovered while scanning Rotor (the Shared Source Common Language Implementation). I found some interesting errors in Rotors, which I'll eventually post in my blog.
I also found some gotchas as well. My tool zipped through hundreds of functions in a split second before stalling in a function, which wasn't all that complex. Some of my transformations, while seemingly simple, exhibit exponential characteristics. This occurs when a function application duplicates an argument.
f(x) => x op x
Repeated forward use of such transformations can lead to large expressions that take long to evaluate or even print.
I found a general, elegant solution that I have been implementing. Ideally, the normal form should be at least as compact as the original form [considering the fully expanded lambda expression representation of f], preferably more so. With constant and atomic arguments, this is the case. For more complex arguments, the reverse transformation is applied: The left hand side of the transform becomes the normal form. It's counterintuitive, but there's no reason why we can't continue to simplify this normal form as the two sides of the equation have the same value.
Comments