Source Code

Scott Hanselman's post on Weekly Source Code 2 reminded me of my desire to post some of my source code. I'll probably do just that, but, with me and my short-term memory loss, I often forget to follow up until after a few years go by.

A couple of my classes come to mind:

• Rational number class. This is an implementation of a general-purpose 16-byte data type that can precisely represent rational numbers (up to a certain precision), long (both signed and unsigned), and doubles. The code is written in IL to take advantage of extended-precision floating point. More info...
• Fast, persistent hash-tables and array. This is one of my two sets of persistent collection classes. Similar to persistent arrays used by the COQ theorem prover for fast, functional union-find data structures, these data types are as fast as their imperative cousins and are ideal for backtracking. Unfortunately, my implementation is not thread-safe. My second set of persistent data structures is fully "functional" and thread-safe, but is more connected to my code-base.

If I haven't posted any source code by the end of September, give me a ring.

---

I have been meaning to post some regular expression matching implementations from my post in December: one using closures and another less efficient implementation using iterators. Both are functional, but imperative implementations can be compact too. I won't get around to doing it until after I ship NStatic, though.

Several years ago, I wrote a fast pattern-matcher and a slower unification engine (bidirectional pattern-matching) for expressions. Both algorithms provided a superset of regular-expression capabilities including wildcards and disjunctions.  (For unification, one regular expression pattern might be matched against another pattern.) They also handled other phenomena such as associativity and commutativity. By going completely functional, I was able to merge both algorithms into one, fast algorithm and dramatically reduce the total number of lines down to about 500.

I had written a regular expression engine for a college class based on NDFAs, the code for which was substantial. I also know that Microsoft's Rotor implementation includes a large number of files, so I was surprised by the compactness and directness of my functional pattern matcher implementation.

Since then, I have been (re-)writing most of my code in the functional style with the same consistent results. Programming in a functional manner entails heavy use of closures (anonymous methods), which is only really practical in C# 2.0+, and greatly eliminates the need for temporary or accidental classes.

Comments

[NoiseEHC]

I have been thinking for a long time to ask for some source code but never dared since probably you have much more important things to do.
What I am interested in is that you had an article about turning an imperative GUI to a functional one. You mentioned several transformations you did to your code. I would like to see some before/after code snippets to see what are the most difficult problems, how to solve them in an optimal way, and how to solve them in a fast way.
In fact I would appreciate some more Practical Functional Programming articles (part 1 to part 24 :) but probably just dumping your code would take less time...
Thanks!

[dru]

I am looking forward to see your functional code in .Net!

-d

[Simon Johnson]

In a way, I wish NStatic was open source. Perhaps not GPL but some sort Microsoft-esc shared source license.

I strongly suspect that I could learn a great deal from looking at the source code of a developer such as you. I get the impression that a lot of people who are reading about NStatic are thinking the same thing.

A question for you, I presume you have run NStatic on your NStatic source code? Has the process of building NStatic pointed out problems in your programing style that were not obvious before hand? If so, could you share what these are?

The reason I am so interested in NStatic is because it might show me how to think more "tightly". Has this been your experience of the product as you've developed it?

Simon.

[damien morton]

Also looking forward to seeing some of your code.

[Wes]

Certainly, if I wasn't able to sell my software for legal reasons or such, I would open source it.

I'll progressively share more of my code over time, and if possibly license some of my AI libraries if I remain commercial.

[Wes]

Is my code tight?

I think so,

- few redundancies
- extensive reuse
- small code base
- very few classes
- lots of closures
- heavy reliance on functional programming
- heavy reliance on code as data and declarative programming

[Patrick Smacchia]

What do you mean by?
- very few classes

that you use structure or that most of your state are enclosed in closures?

I also use a lot of closures by the mean of C#2 anonymous methods but once I'll migrate my code to C#3 most of them will suit better with lambda expression.

Closures and a more functional way of programming eliminate the need for creating new objects.

A lot of objects are truly unnecessary and serve as accidental helper functions. Think of Steve Yegge's Noun-Verb post in http://steve-yegge.blogspot.com/2006/03/execution-in-kingdom-of-nouns.html.

These accidental classes are identified by compound names with verb-like suffixes like Facilitator, Factor, Procurer, etc...

Some classes in my code become the hidden compiler-generated display classes for captured locals in closures.

Other classes were necessitated by the presence of state and side-effects. These disappear as well.

[Greg]

Interesting. I've also written a persitent ArrayList / HashTable implementation in C#. Performance was the biggest hurdle. Two issues were overcome - serialization / deserialization and file seek speed.

What challenges did you face / overcome in implementing it?

I am using a different meaning of persistence here: Multi-versioned data structure rathers than serialization.