Skip to content

Instantly share code, notes, and snippets.

@Porges
Created June 17, 2014 21:16
Show Gist options
  • Save Porges/df44e6a2f281277d842f to your computer and use it in GitHub Desktop.
Save Porges/df44e6a2f281277d842f to your computer and use it in GitHub Desktop.
Encoding open recursion in C#: not recommended
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TypedTaglessFinal
{
// based upon: http://okmij.org/ftp/tagless-final/course/lecture.pdf
static class Deserializer
{
public static T Fix<T>(Func<Lazy<T>, T> f)
{
return f(new Lazy<T>(() => Fix(f)));
}
public static Repr FromTreeExt<T, Repr>(T _, Tree tree)
where T : ExpSYM<Repr>
{
return Fix<Func<T, Tree, Repr>>(FromTreeExtOpen<T, Repr>)(_, tree);
}
public static Func<T, Tree, Repr> FromTreeExtOpen<T, Repr>(Lazy<Func<T, Tree, Repr>> self)
where T : ExpSYM<Repr>
{
return (_, tree) =>
{
switch (tree.Label)
{
case "Lit":
if (tree.Children.Count() == 1 && tree.Children[0].Children.Count() == 0)
{
return _.Lit(int.Parse(tree.Children[0].Label));
}
break;
case "Neg":
if (tree.Children.Count() == 1)
{
return _.Neg(self.Value(_, tree.Children[0]));
}
break;
case "Add":
if (tree.Children.Count() == 2)
{
return _.Add(self.Value(_, tree.Children[0]), self.Value(_, tree.Children[1]));
}
break;
}
throw new InvalidDataException("Invalid tree");
};
}
public static Repr FromTreeExtMul<T, Repr>(T _, Tree tree)
where T : ExpSYM<Repr>, MulSYM<Repr>
{
return Fix<Func<T, Tree, Repr>>(FromTreeExtMulOpen<T, Repr>)(_, tree);
}
public static Func<T, Tree, Repr> FromTreeExtMulOpen<T, Repr>(Lazy<Func<T, Tree, Repr>> self)
where T : ExpSYM<Repr>, MulSYM<Repr>
{
return (_, tree) =>
{
switch (tree.Label)
{
case "Mul":
if (tree.Children.Count() == 2)
{
return _.Mul(self.Value(_, tree.Children[0]), self.Value(_, tree.Children[1]));
}
break;
}
return FromTreeExtOpen(self)(_, tree);
};
}
}
class Program
{
public static Repr TF1<T, Repr>(T _)
where T : ExpSYM<Repr>
{
return _.Add(_.Lit(8), _.Neg(_.Add(_.Lit(1), _.Lit(2))));
}
public static Repr TF1WithMul<T, Repr>(T _)
where T : ExpSYM<Repr>, MulSYM<Repr>
{
return _.Mul(_.Lit(8), _.Neg(_.Add(_.Lit(1), _.Lit(2))));
}
static void Main(string[] args)
{
Console.WriteLine(TF1<IntExpSYM, int>(new IntExpSYM()));
Console.WriteLine(TF1<StringExpSYM, string>(new StringExpSYM()));
Console.WriteLine(TF1WithMul<MulIntExpSYM, int>(new MulIntExpSYM()));
Console.WriteLine(TF1WithMul<MulStringExpSYM, string>(new MulStringExpSYM()));
var tree = new Tree("Add")
{
new Tree("Lit")
{
new Tree("2")
},
new Tree("Lit")
{
new Tree("3")
}
};
Console.WriteLine(Deserializer.FromTreeExt<IntExpSYM, int>(new IntExpSYM(), tree));
Console.WriteLine(Deserializer.FromTreeExt<StringExpSYM, string>(new StringExpSYM(), tree));
var tree2 = new Tree("Mul")
{
new Tree("Lit")
{
new Tree("2")
},
new Tree("Lit")
{
new Tree("3")
}
};
Console.WriteLine(Deserializer.FromTreeExtMul<MulIntExpSYM, int>(new MulIntExpSYM(), tree2));
Console.WriteLine(Deserializer.FromTreeExtMul<MulStringExpSYM, string>(new MulStringExpSYM(), tree2));
}
}
interface ExpSYM<Repr>
{
Repr Lit(int val);
Repr Neg(Repr repr);
Repr Add(Repr l, Repr r);
}
interface MulSYM<Repr>
{
Repr Mul(Repr l, Repr r);
}
class IntExpSYM : ExpSYM<int>
{
public int Lit(int val) { return val; }
public int Neg(int val) { return -val; }
public int Add(int l, int r) { return l + r; }
}
class MulIntExpSYM : IntExpSYM, MulSYM<int>
{
public int Mul(int l, int r) { return l * r; }
}
class StringExpSYM : ExpSYM<String>
{
public string Lit(int val) { return val.ToString(); }
public string Neg(string val) { return "(-" + val + ")"; }
public string Add(string l, string r) { return "(" + l + " + " + r + ")"; }
}
class MulStringExpSYM : StringExpSYM, MulSYM<String>
{
public string Mul(string l, string r) { return "(" + l + " * " + r + ")"; }
}
class Tree : IEnumerable<Tree>
{
public Tree(string label) { Label = label; }
public string Label { get; private set; }
public IReadOnlyList<Tree> Children { get { return (IReadOnlyList<Tree>)_children; } }
private IList<Tree> _children = new List<Tree>();
public void Add(Tree tree) { _children.Add(tree); }
public IEnumerator<Tree> GetEnumerator() { return _children.GetEnumerator(); }
IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment