Lambda the Ultimate

Posted this on Channel9 (http://channel9.msdn.com/ShowPost.aspx?PostID=386812), but didn't get much feedback, so I thought I'd repost here.

Basically, I've been looking at a type-safe approach for the expression problem in C#, taking advantage of the lambda expression runtime compilation command Expression.Compile() in C#'s Language Integrated Query (LINQ). The biggest drawback to the solution is that the compiled lambda functions take about 2x longer to execute on primitive expressions compared to non-generic solutions. I haven't yet found an EvalStream implementation that can avoid this overhead of lambda evaluation. I'm pretty new to functional programming, but I'd love to hear anyone's thoughts on the approach I'm trying here (see LinFu author Philip Laureano's comments (thanks Philip!): http://plaureano.blogspot.com/2008/02/linfudynamicobject-and-dynamic-object.html#c4431642200009960939)

using System;
using System.Linq.Expressions;

namespace TPLTest
{
public class TestGADT
{
public static void Main()
{
Number n1 = 5;
Number n2 = 4;
Console.WriteLine(n1 + n2);

Array array1 = new Array(1000).InitializeTo(10);
Array array2 = new Array(1000).InitializeTo(20);
Array array3 = array1 + array2;
Console.WriteLine(array3[0]);

Console.Read();
}
}

public struct Number where T : struct
{
private T numValue;
public static Number operator +(Number a, Number b) { return GADT.AddFunc(a.numValue, b.numValue); }
public static Number operator -(Number a, Number b) { return GADT.SubtractFunc(a.numValue, b.numValue); }
public static Number operator *(Number a, Number b) { return GADT.MultiplyFunc(a.numValue, b.numValue); }
public static Number operator /(Number a, Number b) { return GADT.DivideFunc(a.numValue, b.numValue); }

public static implicit operator Number(T myValue) { return new Number() { numValue = myValue }; }
public static implicit operator T(Number myNumber) { return myNumber.numValue; }
public override string ToString() { return numValue.ToString(); }
public T ToValue() { return numValue; }
}

public class Array where T : struct
{
internal T[] arrayInstance;

public Array() { }
public Array(int size) { arrayInstance = new T[size]; }
public Array(T[] existingArrayInstance) { arrayInstance = existingArrayInstance; }
public T this[int index] { get { return arrayInstance[index]; } set { arrayInstance[index] = value; } }
public int Length { get { return arrayInstance.Length; } }

public static implicit operator T[](Array myArray) { return myArray.arrayInstance; }
public static implicit operator Array(T[] myArrayInstance) { return new Array() { arrayInstance = myArrayInstance }; }

public static Array operator +(Array a, Array b) { return GADT.AddFunc.EvalStream(a, b); }
public static Array operator -(Array a, Array b) { return GADT.SubtractFunc.EvalStream(a, b); }
public static Array operator *(Array a, Array b) { return GADT.MultiplyFunc.EvalStream(a, b); }
public static Array operator /(Array a, Array b) { return GADT.DivideFunc.EvalStream(a, b); }

public T[] ToArray() { return arrayInstance; }
}

public static class ArrayExtensions
{
public static Array EvalStream(this Func myFunc, Array a, Array b) where T : struct
{
Array output = new Array { arrayInstance = new T[a.arrayInstance.Length] };
for (int i = 0; i output.arrayInstance[i] = myFunc(a.arrayInstance[i], b.arrayInstance[i]);
return output;
}
public static Array InitializeTo(this Array myArray, T value) where T : struct
{
for (int i = 0; i myArray[i] = value;
return myArray;
}
}

public static class GADT
{
public static Func AddFunc = typeof(GADTHelper).GetFunc("Add");
public static Func SubtractFunc = typeof(GADTHelper).GetFunc("Subtract");
public static Func MultiplyFunc = typeof(GADTHelper).GetFunc("Multiply");
public static Func DivideFunc = typeof(GADTHelper).GetFunc("Divide");

internal static class GADTHelper
{
public static double Add(double a, double b) { return a + b; }
public static float Add(float a, float b) { return a + b; }
public static int Add(int a, int b) { return a + b; }
public static long Add(long a, long b) { return a + b; }

public static double Subtract(double a, double b) { return a - b; }
public static float Subtract(float a, float b) { return a - b; }
public static int Subtract(int a, int b) { return a - b; }
public static long Subtract(long a, long b) { return a - b; }

public static double Multiply(double a, double b) { return a * b; }
public static float Multiply(float a, float b) { return a * b; }
public static int Multiply(int a, int b) { return a * b; }
public static long Multiply(long a, long b) { return a * b; }

public static double Divide(double a, double b) { return a / b; }
public static float Divide(float a, float b) { return a / b; }
public static int Divide(int a, int b) { return a / b; }
public static long Divide(long a, long b) { return a / b; }
}
}

public static class DynamicExtensions
{
public static Func GetFunc(this Type t, string method)
{
Expression body = Expression.Call(t.GetMethod(method));
Expression e = Expression.Lambda(body);
return e.Compile();
}
public static Func GetFunc(this Type t, string method)
{
Type[] types = new Type[] { typeof(T) };
var pArray = types.GetParameterExpressionArray();
Expression body = Expression.Call(t.GetMethod(method, types), pArray);
Expression e = Expression.Lambda(body, pArray);
return e.Compile();
}
public static Func GetFunc(this Type t, string method)
{
Type[] types = new Type[] { typeof(T1), typeof(T2) };
var pArray = types.GetParameterExpressionArray();
Expression body = Expression.Call(t.GetMethod(method, types), pArray);
Expression e = Expression.Lambda(body, pArray);
return e.Compile();
}
public static Func GetFunc(this Type t, string method)
{
Type[] types = new Type[] { typeof(T1), typeof(T2), typeof(T3) };
var pArray = types.GetParameterExpressionArray();
Expression body = Expression.Call(t.GetMethod(method, types), pArray);
Expression e = Expression.Lambda(body, pArray);
return e.Compile();
}
public static Func GetFunc(this Type t, string method)
{
Type[] types = new Type[] { typeof(T1), typeof(T2), typeof(T3), typeof(T4) };
var pArray = types.GetParameterExpressionArray();
Expression body = Expression.Call(t.GetMethod(method, types), pArray);
Expression e = Expression.Lambda(body, pArray);
return e.Compile();
}
private static ParameterExpression[] GetParameterExpressionArray(this Type[] types)
{
ParameterExpression[] pArray = new ParameterExpression[types.Length];
for (int i = 0; i pArray[i] = Expression.Parameter(types[i], "p" + i);
return pArray;
}
}
}

Uniqueness Typing Simplified, by Edsko de Vries, Rinus Plasmeijer, and David M. Abrahamson.

We present a uniqueness type system that is simpler than both Clean’s uniqueness system and a system we proposed previously. The new type system is straightforward to implement and add to existing compilers, and can easily be extended with advanced features such as higher rank types and impredicativity. We describe our implementation in Morrow, an experimental functional language with both these features. Finally, we prove soundness of the core type system with respect to the call-by-need lambda calculus.

Uniqueness typing is related to linear typing, and their differences have been discussed here before. Linear types have many applications. This paper describes the difference between linear and unique types:

In linear logic, variables of a non-linear type can be coerced to a linear type (dereliction). Harrington phrases it well: in linear logic, "linear" means "will not be duplicated" whereas in uniqueness typing, "unique" means "has not been duplicated".

In contrast to other papers on substructural typing, such as Fluet's thesis Monadic and Substructural Type Systems for Region-Based Memory Management, this paper classifies uniqueness attributes by a kind system. This possibility was mentioned in Fluet's thesis as well, Section 4.2, footnote 8, though the technique used here seems somewhat different.

Uniqueness typing is generally used to tame side-effects in purely functional languages. Uniqueness types have also been contrasted with monads on LTU, which are also used to tame effects, among other things. One point not discussed in that thread, is how straightforward it is to compile each approach into efficient code. It seems clear that uniqueness types have a straightforward, efficient compilation, but it's not clear to me how efficient monads can be, and how much work is required to make them efficient. This may make uniqueness or substructural types more suitable for just-in-time compilers than monads.