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!

I typically keep this blog about computer science, but I also dabble in a bit of philosophy. I was initially struck by Bostrom's simulation argument when I first read it years ago. Over the years, I've cycled a few times between disputing what I believed were some of its assumptions, and cautious acceptance after realizing my mistake. The simulation argument in its simplest form is that one of the following must be true: simulations of humans can't be built, or simulations of humans won't be built, or we are almost certainly living in a simulation I think this argument is absolutely valid, so one of those outcomes is true. Claiming #3 is most likely is what's known as the simulation hypothesis , and has such proponents as Elon Musk. Sabine Hossenfelder recently argued against the simulation hypothesis by basically asserting that #1 above is plausible, but I actually think #2 is the most likely case. For reference, Bostrom calls future civilizations capable of r...

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

A thread on reddit pointed to Canada's consultation on what sort of legislative framework they should create to facilitate investigations in the digital world. Many of the questions are leading and borderline deceptive in their phrasing, but if we're being charitable, this is a good opportunity to inform policy makers. To that end, these are my responses: How can the Government address challenges to law enforcement and national security investigations posed by the evolving technological landscape in a manner that is consistent with Canadian values, including respect for privacy, provision of security and the protection of economic interests? Evidence-based policy suggest you first demonstrate the actual need for such respective legislative changes, and further, that the proposed changes actually solve the problems they are intended to solve. Impartial third-party studies should be required for any proposed measures. As a computer scientist with some expertise in computer...

There are plenty of tutorials online for creating tabbed panels in HTML documents, some using JavaScript, some using pure CSS tricks. Most of the approaches seem to assume that a list of some type is the appropriate element to use for a tabbed interface, but I'd argue that lists are not semantically descriptive of tabbed interfaces. They either include the main tab content along with the tab name, like so: <ul class="tabs"> <li class="tab-active"><a href="">Active</a> Active tab content goes here</li> <li><a href="">Second</a> Inactive second tab content goes here</li> <li><a href="">Third</a></li> </ul> Or the tab content has no semantic relationship with the tabs that control their display, like: <ul class="tabs"> <li class="tab-active"><a href="#first">Active</a></li> ...