Wednesday, August 26, 2015

Algebra.NET: A Simple Algebra eDSL for .NET

Algebra.NET is a simple library designed to facilitate easy expression and manipulation of algebraic functions. For instance, here's a simple function:

Function<Func<double, double>> a = Algebra.Function(x => 2 * x + 1);

We can compile such a function to efficient IL:

Func<double, double> func = a.Compile("times2plus1");

Or we can apply some algebraic identities to rewrite it:

Identity associative = Algebra.Identity(x => x + 1 == 1 + x);
Identity mulEqAdd = Algebra.Identity(x => 2 * x == x + x);
Console.WriteLine(a);
Console.WriteLine(a.Rewrite(1, associative, mulEqAdd));

// Prints:
// ((2 * x) + 1)
// (1 + (x + x))

Rewrites can sometimes loop forever (consider "x + y == y + x"), so the Rewrite method takes a number indicating the maximum number of iterations to perform all the rewrites.

All the usual arithmetic operations are available, including an extension method for exponentiation:

var f = Algebra.Function(x => x.Pow(3));
Console.WriteLine(x);

// Prints:
// (x ^ (3))

Design

As of this writing, Algebra.NET is a functional example of a simple term rewriting system. Term rewriting is usually pretty awkward to express in an object-oriented language, and I banged my head against the keyboard to figure out a nice way to do it, until I hit on just doing unification (of course!).

So I reused the term language and added an equality operator to generate an identity that conceptually maps one term to another. I then perform unification on the left hand side, and generate a set of substitutions to transform the matching term into the right hand side of the identity.

It was ultimately quite simple, consisting of 3 methods on Term:

Term Rewrite(Identity e, Term[] bindings)
bool TryUnify(Term e, Term[] bindings)
Term Subsitute(Term[] bindings)

Rewrite tries to recursively unify the Identity's left hand side with the current term using TryUnify. On success, the 'bindings' array will have been populated by TryUnify with the substitutions to perform, so it substitutes the bindings into the identity's right hand side to generate the new term.

There are only 3 term types: constants, variables and binary operations. Negation is handled as a binary operation "0 - x" for simplicity. The unification methods on each of the term types are only a few lines of code each, but are quite powerful!

So if you want to understand expression compilation to CIL, unification, or term rewriting, this is pretty much as simple as it gets.

Algebra.NET doesn't perform any term simplification at this point, only term rewriting. Some rewrites may of course be simplifications, but a term like "0 - 3" will not be simplified to "-3".

Future Work

As mentioned, Algebra.NET doesn't perform simplification, so that's a big one. I started developing this to work on symbolic and automatic differentiation for numerical optimization problems. I'm aware of other .NET libraries for this, but I didn't like how clumsy it was to write algebraic expressions, nor did they have nice and extensible facilities for rewriting expressions. So I created this in my spare time and intended to continue fleshing it out as needed.

Monday, August 10, 2015

Sasa v0.17.0 Released

A few new features in this release, and a few bugfixes and enhancements in MIME parsing. As before, the online docs are available on my site, the full release including experimental assemblies on Sourceforge, and the production assemblies on Nuget. The changelog:

 * sasametal can now replace columns and FK associations with enums that are
   provided separately
 * sasametal can now output an interface file, which generates an interface
   describing the database entities
 * many MIME fixes thanks to a few bug reports on Sasa discussion list
 * added System.Data, which provides useful extensions to ADO.NET and
   IQueryable, like a simple interface for batched SQL queries
 * MIME parser now accepts an optional parsing parameter that controls various
   parsing options, like how strict e-mail address formatting accepted,
   and whether HTML views should be parsed into MailMessage.Body
 * added enum as a primitive to Sasa.Dynamics IReducer and IBuilder
 * fixed Sasa.Enums.IsSequential check

Sasa.Dynamics probably isn't used much, but in my experiments I found it increasingly important to handle enums as a primitive, so type reduction and construction (IReduce and IBuild respectively) now includes it as such.

I created sasametal to ease the pain of maintaining several legacy systems that depend upon Microsoft's Linq2Sql. It first renames some associations to make them more meaningful, since Linq2Sql does a bad job of this in some cases. This made some integrations with ORMs like EntityFramework and NHibernate a little easier, but there still remained some painful points.

One of these pains was handling enums, ie. an entity set whose members are effectively fixed. Sasametal now takes enums into account via a command-line option, /enum:[file path], that accepts a file listing table-to-enum rewrites, one per line. For instance, if an entity Foo had a StatusId column with an FooStatus enum for the status, we could call sasametal like so:

C:\somepath> sasametal ...[other option]... /code:FooDb.cs /enum:enums.txt

and the enums.txt contains merely:

dbo.FooStatuses=Namespace.Statuses.FooStatus

You should provide the full table name including schema that sqlmetal would generate, and provide the fully qualified name of the enum you want to substitute. Sasametal will then eliminate the FooStatus entity and any FK associations linked to that entity, then it will update the type of any properties for that foreign key to use the enum type. The entities generated by sasametal are thus somewhat more efficient, and I've found it easier to use Linq2Sql as-is for quick projects against legacy systems.

When combined with sasametal's other new feature, generating interfaces describing the entities, it also eases the transition to more sophisticated ORMs that already handle enums.