Higher Logics

In my last  two posts  on automatic differentiation (AD), I described some basic primitives that implement the standard approach to forward mode AD using dual numbers, and then a dual representation of dual numbers that can compute in reverse mode. I'm calling these "co-dual " numbers, as they are the categorical dual of dual numbers. It didn't click at the time that this reverse mode representation seems to be novel. If it's not, please let me know! I haven't seen any equivalent of dual numbers capable of computing in reverse mode. When reverse mode AD is needed, most introductions to AD go straight to building a graph/DAG representation of the computation in order to improve the sharing properties and run the computation backwards, but that isn't strictly necessary. I aim to show that there's a middle ground between dual numbers and the graph approach, even if it's only suitable for pedagogical purposes. Review: Dual Numbers Dual numbers augment...

Continuing from my last post on implementing forward-mode automatic differentiation (AD) using C# operator overloading , this is just a quick follow-up showing how easy reverse mode is to achieve, and why it's important. Why Reverse Mode Automatic Differentiation? As explained in the last post, the vector representation of forward-mode AD can compute the derivatives of all parameter simultaneously, but it does so with considerable space cost: each operation creates a vector computing the derivative of each parameter. So N parameters with M operations would allocation O(N*M) space. It turns out, this is unnecessary! Reverse mode AD allocates only O(N+M) space to compute the derivatives of N parameters across M operations. In general, forward mode AD is best suited to differentiating functions of type: R → R N That is, functions of 1 parameter that compute multiple outputs. Reverse mode AD is suited to the dual scenario: R N → R That is, functions of many parameters t...

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu...

More adventures in C, I revisited my exception handler implementation libex . I realized there's an even simpler version that's more efficient if we give up the requirement that exceptions can be propagated to callers: #define TRY #define THROW(E) goto E #define CATCH(E) goto FINALLY_H; E: #define FINALLY FINALLY_H: This implementation requires only a single exception handling block per function, which is probably good idea as a general rule. Usage looks like: static void foo(size_t sz) { char* x; TRY { x = (char*)malloc(sz); if (x == NULL) THROW(ENoMem); // do something with x } CATCH(ENoMem) { // handle out of memory } FINALLY { if (x != NULL) free(x); } } Unlike libex, this version is actually compatible with break and continue, although using them runs the risk of skipping the FINALLY handler. An almost equally simple version of exception handlers which ensures that break/continue cannot skip the FINALLY block wraps everything in a loop:...

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre...

I've finally updated Sasa to target .NET standard 1.3, removed a lot of superfluous abstractions, and rewrote some of the existing API to target third-party packages that are better supported. This may be the last stable release of Sasa, since I'm shifting. Fortunately, the remaining Sasa features are very stable so there's not much need to evolve them further. You can find the full API documentation for v1.0.0 here , and obviously you can find Sasa itself via nuget . Here's the current breakdown of features: Sasa Assembly The core Sasa assembly contains extensions on standard .NET types, and a few new and useful abstractions that are typical for most programs: Sasa.FilePath: structured file system path handling, including jail, ensuring combined paths don't escape a root path. Sasa.Func: extensions to create delegates on methods and for operators with no restrictions, unlike the standard .NET delegate APIs. For instance, open instance delegates to virtual m...

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.Po...

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 .IsSequenti...

Just a bugfix release, mainly for the MIME parsing. Changelog: * added support for 8bit transfer encoding, even if not supported by .NET <4.5 * support content types whose prologue is empty * added support for arbitrarily nested multipart messages * added alternative to Enum.HasFlag that invokes Sasa's faster enum code As usual, online docs are available , or the a CHM file is available on Sourceforge .

Mainly a bugfix release, with only a few new features. As always, the docs are available here online , or as a compiled CHM file on sourceforge . Here's the changelog: * a few bugfixes to MIME parsing for header and word decoding (Thanks Evan!) * added combined SubstringSplit function for more space efficient parsing * explicitly parse e-mail addresses for more flexible address separators * NonNull now throws an exception if encapsulated value is null, which is used in the case when the instance is invalidly constructed (Thanks Mauricio!) * build now checks for the presence of the signing key and ignores it if it's not present * a more efficient Enum.HasFlag using codegen * added a new ImmutableAttribute which Sasa's runtime analyses respects * FilePath's encapsulated string now exposed as a property Thanks to Evan/iaiken for a number of bug reports, and to Mauricio for feedback on the NonNull<T> pattern.

This release features a few new conveniences, a few bugfixes and a vector that's faster than any other I've managed to find for .NET. Here's the changelog since the last v0.14.0 release: * more elaborate benchmarking and testing procedures * added a minor optimization to purely functional queues that caches the reversed enqueue list * FingerTree was switched to use arrays as opposed to a Node type * optimized FingerTree enumerator * FingerTree array nodes are now reused whenever possible * Sasa.Collections no longer depends on Sasa.Binary * MIME message's body encoding is now defaulted to ASCII if none specified * added convenient ExceptNull to filter sequences of optional values * NonNull<T> no longer requires T to be a class type, which inhibited its use in some scenarios * fixed null error when Weak<T> improperly constructed * added variance annotations on some base interfaces * added a super fast Vector<T> to Sasa.Collections *...

The µKanren paper is a nice introduction to a lightweight logic programming language which is a simplification of the miniKanren family of languages. The existing µKanren implementation in C# was a translation from Scheme, and thus is verbose, untyped with lots of casts, and non-idiomatic. I also found most of the other Kanren implementations unnecessarily obscure, heavily relying on native idioms that aren't clear to newcomers. uKanren.NET provides a clear presentation of the core principles of µKanren using only IEnumerable<T> and lambdas, showing that µKanren's search is fundamentally just a set of combinators for transforming sequences of states. The values of the sequence are sets of bound variables that satisfy a set of equations. For instance, given the following expression: Kanren.Exists(x => x == 5 | x == 6) You can read it off as saying there exists an integer value to which we can bind variable x, such that x equals either 5 or 6 [1]. Solving this eq...

NHibernate is a pretty useful tool, but occasionally it's not entirely documented in a way that makes it's flexibility evident. Composite keys are a particularly difficult area in this regard, as evidenced by the numerous articles on the topic. Most of the existing articles cover this simply enough, but there is one uncommon corner case I have yet to see explained anywhere: a composite primary key one of whose key properties is an association with a composite key. This is probably pretty uncommon and there are ways around it, hence the lack of examples, but as a testament to NHibernate's flexibility, it's possible! Here's the example in code listing only the primary keys: public class MotorType { public Horsepower Horsepower { get; protected set; } public VoltageType VoltageType { get; protected set; } } public class Motor { public MotorType MotorType { get; protected set; } public Efficiency Efficiency { get; protected set; } } The tables look like this...

.NET's delegates are a powerful and convenient abstraction available since .NET 1.1. They encapsulate a method pointer and the object the method belongs to in a single callable "function object". Multicast delegates are an extension of plain delegates, in that they encompass multiple single delegates. Invoking a multicast delegate invokes every encapsulated delegate, in the order they were added. Multicast delegates are key to event handling patterns that were a core part of the CLR nearly since its inception. If you're curious about virtual machines or CLR internals, you've perhaps wondered how multicast delegates actually work. These are the key properties of multicast delegates: They encapsulate a list of delegates of the same delegate type. Adding a delegate returns a new multicast delegate containing the new addition at the end of the list (the original is unchanged). Removing a delegate returns a new multicast delegate without the specified delegate (...

A quick release, fixing one bug and adding some performance improvements and some new collection types. Here's the changelog: * added a faster and more compact hash array mapped trie under Sasa.Collections.Trie to replace Sasa.Collections.Tree * added Sasa.Collections.FingerTree * added purity attributes throughout Sasa (for .NET 4) * expanded various test suites and documentation * added a persistent vector, Sasa.Collections.Vector * factored out Atomics.BeginRead/BeginWrite read/write protocol so it can be used in more flexible scenarios * Sasa.Dynamics.Type .MaybeMutable is now computed eagerly * added an efficient, mutable union-find data structure * fixed: Uris.UriDecode now handles the incorrect but common UTF16 encoding * moved Sasa.LockSet under Sasa.Concurrency.LockSet The Sasa.Collections.Tree type is no longer available, and is replaced by the faster and more appropriately named Sasa.Collections.Trie. The original tree was actually a trie, and I didn't ...

The latest Sasa release fixes a few bugs with MIME parsing, and adds a few new concurrency features. Here is the online documentation , or a downloadable CHM file from Sourceforge is available alongside the binaries . The binaries are also available via nuget , of course. Here's the changelog: added Sasa.Concurrency.RWLock, a truly slim concurrent read/write lock switched Sasa.Dynamics.PIC to use RWLock switched Sasa.Dynamics.PIC to rely only on arrays for performance reasons Mail message parsing now doesn't use ad-hoc means to extract a body from the attachments added Sasa.Changeable<T> which encapsulates all INotifyPropertyChanged and INotifyPropertyChanging logic with no space overhead fixed an MIME HTML parsing bug fixed regex lexing added more efficient Enums class exposing static properties for various enum properties alternate views inside multipart/related no longer incorrectly dropped added well-behaved standards conforming URI encode/decode to Sasa.Uris added ...

I've previously posted about Sasa's hash-array mapped trie, but I never posted any benchmarks. I recently came across this post on Stackoverflow which provided a decent basic benchmark between .NET's default Dictionary<TKey, TValue>, the C5 collection's hash dictionary, F#'s immutable map, and .NET's new immutable collections. I slightly modified the file to remove the bench against the F# map and the new immutable collections since I'm still using VS 2010, and I added a simple warmup phase to ensure the methods have all been JIT compiled and the GC run to avoid introducing noise: static void Warmup() { var x = Tree.Make<string, object>(); var y = new C5.HashDictionary<string, object>(); var z = new Dictionary<string, object>(); z.Add("foo", "bar"); for (var i = 0; i < 100; ++i) { x = x.Add("foo" + i, "bar"); y.Add("foo" + i, "bar...

It's pretty well known that the CLR's ReaderWriterLock and ReaderWriterLockSlim have unappealing performance characteristics. Each class also encapsulates signficant state, which precludes its use in fine-grained concurrency across large collections of objects. Enter Sasa.Concurrency.RWLock in the core Sasa assembly. This is the most lightweight R/W lock I could come up with, particularly in terms of resources used. It's a struct that encapsulates a simple integer that stores the number of readers and a flag indicating whether a writer is active. The interface is similar to ReaderWriterLockSlim, although there are a few differences which are needed to keep the encapsulated state so small: public struct RWLock { // this field is the only state needed by RWLock private int flags; public void EnterReadLock(); public void ExitReadLock(); public bool TryEnterReadLock(); public void EnterWriteLock(object sync); public bool TryEnterWriteLock(object sync); ...

Stan Drapkin, of SecurityDriven.NET fame, was nice enough to provide a little feedback on the Clavis implementation . He pointed out a possible issue with parameter names not being properly URL-encoded, which this release fixes. I also applied a few minor optimizations so generating URLs should be a little faster. I've been using Clavis in production for a couple of years now, so it's fairly stable and user-friendly. The Clavis wiki and issue tracker are available here .

A few years ago, I wrote about a web security microframework for ASP.NET which provided a few primitives for secure parameter-passing and navigation. I've just released a public alpha on Nuget for anyone who's willing to try it. The previous article covered the theoretic foundation of Clavis well enough, but it has undergone a few small revisions to make it easier to use and integrate more seamlessly with ASP.NET. This post will serve as an end-user introduction to Clavis, the rationale behind the design decisions, and the benefits it provides. As a brief summary to whet your appetite, here are the advantages that the Clavis library provides for an otherwise standard ASP.NET web forms or MVC project: By default, URLs are derived from types, so the compiler ensures that every page that will be displayed actually exists. The default URL generated can be overridden via an attribute. Declarative specification of the types and number of parameters a page accepts, which the c...