Higher Logics

Programming with floating point is always fun. Here's a nice little screen capture summarizing the insanity that sometimes arises: .NET keeps 9 digits of precision internally, but typically only displays 7 digits of precision, so I had a hell of a time figuring out why a value from what's effectively a no-op was exceeding the 0.33F threshold I was looking for. Losing equational reasoning is always fun, but this is even more bizarre than usual. Yay floating point!

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

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen...

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

In playing around with Razor Pages, I was irritated again that Microsoft couldn't just standardize a set of interfaces for their methods so that they wouldn't need so much magic. So I just quickly hacked up RazorInterfaces , available also on nuget.org . It's probably most useful to people just learning Razor Pages, since it requires you to correctly implement the common HTTP methods you'll need to get things running: public class CustomerPage : PageModel , IPageGet , IPagePostAsync<Customer> { public IActionResult OnGet() { return Page(); } public async Task<IActionResult> OnPostAsync(Customer customer) { await DataLayer.Update(customer); return Page(); } } There are interfaces for all of the standard HTTP methods: GET, POST, PUT, DELETE, HEAD, OPTIONS. The interface names conform to the following format: IPage[HTTP method] and IPage[HTTP method]Async for the async variant, and there a...

After a long hiatus, I'm slowly starting back on blogging and some personal projects. To get me back in the swing of things, here's a short post on running ASP.NET core on Google Cloud, since this seems poorly documented online. The default project created by the Google Cloud tools includes Microsoft.AspNetCore.All which is a huge dependency. If you want something more minimal: uninstall-package Microsoft.AspNetCore.All install-package Microsoft.AspNetCore install-package Microsoft.AspNetCore.Mvc.Core install-package Microsoft.AspNetCore.Mvc This creates a runnable project using the standard Google Cloud Web API project template, although it still isn't ideal as it includes the Razor pages dependencies.

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

I've had numerous posts here describing instances where C# has come so close to getting it right, and yet misses the mark by an inch. The original C# enums have a simple semantics: enum SomeEnum { First, // compiler implicitly assigns 0 Second, // compiler implicitly assigns 1 Third, // compiler implicitly assigns 2 Fourth, // compiler implicitly assigns 3 } This worked nicely as a concise expression of a need for a set of distinct of values, but without caring what they are. C# later introduced the [Flags] attribute, which signals to the compiler that a particular enum isn't actually a set of disjoint values, but a set of bit flags. However, the compiler doesn't actually change its behaviour given this change of semantics. For instance, the following enum is completely unchanged, despite the semantically meaningful change to a set of bitwise flags: [Flags] enum SomeEnum { First, // compiler implicitly assigns 0 Second, // compiler implicitly assign...

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