Monday, November 18, 2013

First-Class Slots for .NET

Yesterday, I posted about the new extension of IRef<T> to arbitrary reference semantics for the CLR, including referencing inner fields, properties, and array slots. First-class references make it simple to operate on specific mutable data without caring about the underlying type of that data.

I just pushed another abstraction that handles a related, but different case: first-class slots.

ISlot<T>

An object "slot" is a value that designates a mutable location of a specific class of values, not a mutable location of a specific instance like first-class references. Where first-class references hide the underlying object type, slots expose the object type and allow you to mutate the slots of multiple objects at once, as long as they are subtypes of the slot's object type. Here's the declaration of ISlot<T>:

public interface ISlot<TObj, T>
{
    T Get(TObj obj);
    T Set(TObj obj, T value);
}

As you can see, the object we're manipulating is passed in while operating on it, so an ISlot is actually a direct descriptor that can access members of any instance of a subtype of TObj. If you're wondering when you would ever need this, rest assured that there are applications that need to write algorithms of this type. For instance, consider an object-relational mapper (ORM), which uses reflection to extract the members that need to be get/set on object flush/load from a database. Essentially, the ORM is reflecting over all slots of an object being flushed or loaded from a database, but it does so in a manner that isn't very reusable, and the object hydration code is coupled tightly to the database access code as a result.

Reifying slots as a distinct, first-class abstraction makes them independently testable, and the reflection code and database access code is now very loosely coupled. An ORM is but one example of an application that makes use of generic object slots.

Similar to first-class references, the Slot class exposes some static constructors for creating slots:

public abstract class Slot
{
  public static Member<TObj, T> Create<TObj, T>(Func<TObj, T> get, Action<TObj, T> set);
  public static Array<T> Create<T>(int index);
  public static Member<TObj, T> Create<TObj, T>(MemberInfo member)
  public static Member<TObj, T> Create<TObj, T>(Expression<Func<TObj, T>> member)

  public sealed class Array<T> : Slot, ISlot<T[], T> { ... }
  public sealed class Member<TObj, T> : Slot, ISlot<TObj, T> { ... }
}

These operations are exactly what you saw in the last article, where you can create slots from object members and array indices.

It might seem at first that slots are strict generalizations of first-class references, but this is deceptive. It's true that any algorithm you'd could write using references could be rewritten to use slots, but the number of type parameters and value parameters could increase non-linearly to the point where it's unwieldy and could easily obfuscate the underlying algorithm.

Limitations

There is one limitation at the moment. Specifically, value types need to be passed by reference during update in order for assignment to be visible to callers of ISlot.Set, but this isn't currently possible given the interface. As a result, there's currently a type constraint on TObj to restrict it to reference types.

A simple solution would simply be to return TObj from ISlot.Set, so the calling context can simply overwrite its own local value with the one modified by the slot. Another possibility is to make the TObj parameter to ISlot.Set a by-ref parameter. I'm considering these and a few other options, and Sasa's v0.12.0 release will probably contain the final solution.

3 comments:

Mauricio Scheffer said...

I've used a similar abstraction which I called "mutable lenses". Initially I tried to use real immutable lenses, but the boilerplate required to define lenses in C# is astounding. So I went for a mutable variant, but that of course requires a mutable object, and it lacks the composability of immutable lenses. Still a useful abstraction.
I also experimented briefly with an ORM prototype based on this, but I quickly ran into the problem of having to pack all the lenses for a class together (e.g. in a list), something that's seemingly impossible to do in C# as it would require an heterogeneous list. You could pack it as existentials, but then you'd lose type information. You could pack it in an untyped list, but that's of course not type-safe. How did you solve this?

Sandro Magi said...

"So I went for a mutable variant, but that of course requires a mutable object, and it lacks the composability of immutable lenses. Still a useful abstraction."

I think it depends on how you exploit mutability. If you haven't already, read up on immediate mode UIs. They build a UI representation from a model in a continuous, imperative loop.

You could adapt this to the lens concept by simply constructing an immediate mode counterpart of your lens algorithm. Lenses are algebraic representations of updateable views, and immediate mode is a coalgebraic representation.

Coalgebraic representations are much more natural in OO languages like C#, and thus they compose well, but it takes awhile to start thinking coalgebraically because algebras are so ingrained.

"You could pack it as existentials, but then you'd lose type information."

I think any solution for .NET will have to hide some type information in some way, simply because C# types aren't expressive enough. As to how to do this, you can hide the types behind a well defined interface. ORM hydrate is essentially:

Func<Source, T>

ORM flush is essentially:

Action<T, Sink>

Then a Foo:

class Foo
{
public int Bar{get; set;}
public string Something;
}

has hydrate/flush ops:

static Func<Source, Foo> Hydrator()
{
return source =>
{
var x = new Foo();
x.Bar = source.Int32();
x.Something = source.String();
return x;
};
}

static Action<Foo, Sink> Flusher()
{
return (x, sink) =>
{
sink.Int32(x.Bar);
sink.String(x.Something);
};
}

You can make a combinator library to build up the hydrate/flush functions incrementally too (there are functional pearls covering this), because delegates can be combined on .NET:

static Action<T, Sink> FlushInt32<T>(Func<T, int> getter)
{
return (x, sink) => sink.Int32(getter(x));
}

static Action<T, Sink> FlushString<T>(Func<T, string> getter)
{
return (x, sink) => sink.String(getter(x));
}

static Action<Foo, Source> Flusher()
{
return Func.Combine(FlushIn32(x => x.Bar), FlushString(x => x.Something));
}

But really all the above is doing is performing a coalgebraic transform on an object graph into some serialized form. We can make this a fully generic transform, and in fact, I already did which is my type-safe generic reflection abstractions under Sasa.Dynamics.

Start with a low-level reflection interfaces, one for folding over an object:

interface IFold
{
void Field<T>(T value, FieldInfo info);
void Property<T>(T value, PropertyInfo info);
}

And one for unfolding:

interface IUnfold
{
T Field<T>(FieldInfo info);
T Property<T>(PropertyInfo info);
}

Then you need to perform a type case on the basic primitive types:

interface IReduce
{
void Bool(bool x);
void Int32(int x);
void Type(Type x);
...
Object<>(T x);
}
interface IBuild
{
bool Bool();
int Int32();
Type Type();
...
T Object<T>();
}

Then you can write a single piece of code that can fold any object graph into a serialized format, and perform the corresponding unfold from the serialized format back into an object graph.

Foo, from above, would serialize like so:

typeof(Foo)
+-Property(Foo.Bar)
+--typeof(Int32);
+--Int32(Foo.Bar);
+-Field(Foo.Something);
+--typeof(String);
+--String(Foo.Something);

(+- is stack depth)

You can see that all the relevant type information is present, so you can unfold the structure safely as well. Obviously you also need to handle recursive structures and other special cases like arrays and Nullable structs, but it's totally doable.

I recently realized that Sasa.Dynamics is essentially scrap-your-boilerplate generics as found in Haskell. They take the same approach using polytypic folds/unfolds as the foundation of reflection.

Mauricio Scheffer said...

Thanks for the detailed answer! You just gave me a lot to think about here :)