Skip to main content

Embedded Stack Language for .NET - Redux

Awhile ago, I had posted about an embedding of a stack language in C#. The type signatures of the functions and the stack object encoded the consumption and production of stack values, so if your program compiled, it ran correctly.

Unfortunately, the prior structure had a safety problem when generating code which I noted, but didn't have time to address.

The new structure provided below does not have the safety problem, and any functions that compile are guaranteed to execute correctly. I have also altered the style to emphasize the row variable representing the "rest of the record" which the operation knows nothing about. The row variable is denoted by "_".

This is still a fairly limited embedding, but I have added a few convenience functions, and may yet add more. Here is a sample program:
var d = new DynamicMethod("test", typeof(void), null);
var s =
1.Load() // load constant: { int }
.Int(2) // load constant: { int, int }
.Add() // add: { int, int } -> { int }
.Do(Console.WriteLine) // output top: { int } -> { }
.String("Test out") // load string: { } -> { string }
.Do(Console.WriteLine); // output top: { string } -> { }
s.Compile(d.GetILGenerator());// only compile empty stacks: { }
d.Invoke(null, null);

Thankfully, C# can infer the types used so we can avoid any superfluous type annotations. The code generation functions are a little more involved however:
/// <summary>
/// Abstracts the stack structure used to hold locals, etc.
/// </summary>
/// <typeparam name="_">The rest of the stack.</typeparam>
/// <typeparam name="T">The top of the stack.</typeparam>
public sealed class Stack<_, T>
{
/// <summary>
/// Defer the code generation by enclosing the opcodes
/// in a closure.
/// </summary>
internal Action<ILGenerator> gen;
public Stack(Action<ILGenerator> gen)
{
this.gen = gen;
}
}

/// <summary>
/// An empty value aka void.
/// </summary>
public struct Unit
{
}

/// <summary>
/// Statically typed stack operations.
/// </summary>
public static class Stack
{
/// <summary>
/// Load an int on a new stack.
/// </summary>
public static Stack<Unit, int> Load(this int value)
{
return new Stack<Unit, int>(il =>
il.Emit(OpCodes.Ldc_I4, value));
}

/// <summary>
/// Load a string on a new stack.
/// </summary>
public static Stack<Unit, string> Load(this string value)
{
return new Stack<Unit, string>(il =>
il.Emit(OpCodes.Ldstr, value));
}

/// <summary>
/// Load a string on an existing stack.
/// </summary>
public static Stack<Stack<_, T>, string> String<_, T>(
this Stack<_, T> stack, string value)
{
return new Stack<Stack<_, T>, string>(il =>
{
stack.gen(il);
il.Emit(OpCodes.Ldstr, value);
});
}

/// <summary>
/// Duplicate the top of the stack.
/// </summary>
public static Stack<Stack<_, T>, T> Dup<_, T>(
this Stack<_, T> stack)
{
return new Stack<Stack<_, T>, T>(il =>
il.Emit(OpCodes.Dup));
}

/// <summary>
/// Apply a function to the top of the stack, replacing
/// the top element with the return value of the function.
/// </summary>
public static Stack<_, R> Apply<_, T, R>(
this Stack<_, T> stack, Func<T, R> target)
{
return new Stack<_, R>(il =>
{
stack.gen(il);
il.EmitCall(OpCodes.Call, target.Method, null);
});
}

/// <summary>
/// Apply an action to the top of the stack consuming
/// the top value.
/// </summary>
public static Stack<_, Unit> Do<_, T>(
this Stack<_, T> stack,
Action<T> target)
{
return new Stack<_, Unit>(il =>
{
stack.gen(il);
il.EmitCall(OpCodes.Call, target.Method, null);
});
}

/// <summary>
/// Load the value at the given array's index on to the stack.
/// </summary>
public static Stack<_, T> LoadArrayIndex<_, T>(
this Stack<_, Stack<T[], int>> stack)
{
return new Stack<_, T>(il =>
il.Emit(OpCodes.Ldelem, typeof(T)));
}

/// <summary>
/// Check that the top element is of type U.
/// </summary>
public static Stack<_, U> IsInstance<_, T, U>(
this Stack<_, T> stack)
where T : class
{
return new Stack<_, U>(il =>
{
stack.gen(il);
il.Emit(OpCodes.Isinst, typeof(U));
});
}

/// <summary>
/// Load an int onto an existing stack.
/// </summary>
public static Stack<Stack<_, T>, int> Int<_, T>(
this Stack<_, T> stack, int i)
{
return new Stack<Stack<_, T>, int>(il =>
{
stack.gen(il);
il.Emit(OpCodes.Ldc_I4, i);
});
}

/// <summary>
/// Add the two elements at the top of the stack.
/// WARNING: T must overloead the addition operator.
/// </summary>
public static Stack<_, T> Add<_, T>(
this Stack<Stack<_, T>, T> stack)
{
return new Stack<_, T>(il =>
{
stack.gen(il);
il.Emit(OpCodes.Add);
});
}

/// <summary>
/// Return from a function.
/// </summary>
public static void Return<_, T>(this Stack<_, T> stack,
ILGenerator il)
{
stack.gen(il);
il.Emit(OpCodes.Ret);
}

/// <summary>
/// Compile the code so long as the top of the stack
/// has type Unit.
/// </summary>
public static void Compile<_>(this Stack<_, Unit> stack,
ILGenerator il)
{
stack.Return(il);
}
}

Comments

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

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

Building a Query DSL in C#

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

Easy Automatic Differentiation in C#

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