Skip to content

Instantly share code, notes, and snippets.

@eriawan
Last active May 22, 2023 19:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save eriawan/64e0988029b329460dbad32f0e3490f9 to your computer and use it in GitHub Desktop.
Save eriawan/64e0988029b329460dbad32f0e3490f9 to your computer and use it in GitHub Desktop.
A helper class to enable trampoline to handle large recursive by adapting Y Combinator
internal class Program
{
static void Main(string[] args)
{
var fac10 = Factorial(10);
Console.WriteLine("Factorial 10 = " + fac10);
var fac20 = Factorial(20);
Console.WriteLine("Factorial 20 " + fac20);
var facAddition8000 = Factorial(8000);
// code below will throw StackOverflowException
var unoptimizedFac1000 = UnOptimizedFactorial(7000);
}
static BigInteger Factorial(BigInteger number)
{
BigInteger facresult;
facresult = 0;
Func<FuncRec<BigInteger, BigInteger, BigInteger>, Func<BigInteger, BigInteger, FuncRec<BigInteger, BigInteger, BigInteger>>> facRec =
f => (x, a) => x <= 1 ? f.Break(a) : f(x - 1, a * x);
Func<BigInteger, BigInteger> fac = (BigInteger n) => facRec.Fix()(n, 1);0
facresult = fac(number);
return facresult;
}
static BigInteger UnOptimizedFactorial(BigInteger number)
{
BigInteger facresult;
facresult = number < 1 ? 1 : number + UnOptimizedFactorial(number - 1);
return facresult;
}
}
using System;
using System.Collections.Generic;
namespace NETFX.FixCombinatorTrampoline
{
public delegate ActionRec ActionRec();
public delegate ActionRec<T> ActionRec<T>(T t);
public delegate ActionRec<T1, T2> ActionRec<T1, T2>(T1 t1, T2 t2);
public delegate FuncRec<R> FuncRec<R>();
public delegate FuncRec<T, R> FuncRec<T, R>(T t);
public delegate FuncRec<T1, T2, R> FuncRec<T1, T2, R>(T1 t1, T2 t2);
/// <summary>
/// A helper class to enable trampoline to handle large recursive by adapting Y Combinator.
/// </summary>
/// <remarks>
/// <para>Inspired by Bart De Smet's blog about trampoline recursion:
/// http://community.bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly-recursion.aspx </para>
/// <para>The Bart's implementation inspired by Y Combinator, a common technique to simply Fixed function in Lambda Calculus.
/// See the Wikipedia article: https://en.wikipedia.org/wiki/Fixed-point_combinator and also other resources in Lambda Calculus, especially currying.</para>
/// </remarks>
public static class YCombinator
{
public static ActionRec Break(this ActionRec a) { return null; }
public static ActionRec<T> Break<T>(this ActionRec<T> a) { return null; }
public static ActionRec<T1, T2> Break<T1, T2>(this ActionRec<T1, T2> a) { return null; }
public static Action Fix(this Func<ActionRec, Func<ActionRec>> f)
{
return () =>
{
ActionRec a = null;
for (a = () => a; a != null; a = f(a)())
;
};
}
public static Action<T> Fix<T>(this Func<ActionRec<T>, Func<T, ActionRec<T>>> f)
{
return t =>
{
ActionRec<T> a = null;
for (a = t_ => { t = t_; return a; }; a != null; a = f(a)(t))
;
};
}
public static Action<T1, T2> Fix<T1, T2>(this Func<ActionRec<T1, T2>, Func<T1, T2, ActionRec<T1, T2>>> f)
{
return (t1, t2) =>
{
ActionRec<T1, T2> a = null;
for (a = (t1_, t2_) => { t1 = t1_; t2 = t2_; return a; }; a != null; a = f(a)(t1, t2))
;
};
}
// Would really like to store result on a property on the delegate,
// but can't derive from Delegate manually in C#... This is "brr".
private static Dictionary<Delegate, object> _brr = new Dictionary<Delegate, object>();
public static FuncRec<R> Break<R>(this FuncRec<R> a, R res) { _brr[a] = res; return a; }
public static FuncRec<T, R> Break<T, R>(this FuncRec<T, R> a, R res) { _brr[a] = res; return a; }
public static FuncRec<T1, T2, R> Break<T1, T2, R>(this FuncRec<T1, T2, R> a, R res) { _brr[a] = res; return a; }
public static Func<R> Fix<R>(this Func<FuncRec<R>, Func<FuncRec<R>>> f)
{
return () =>
{
object res_;
FuncRec<R> a = null;
for (a = () => a; !_brr.TryGetValue(a, out res_); a = f(a)())
;
var res = (R)res_;
_brr.Remove(a);
return res;
};
}
public static Func<T, R> Fix<T, R>(this Func<FuncRec<T, R>, Func<T, FuncRec<T, R>>> f)
{
return t =>
{
object res_;
FuncRec<T, R> a = null;
for (a = t_ => { t = t_; return a; }; !_brr.TryGetValue(a, out res_); a = f(a)(t))
;
var res = (R)res_;
_brr.Remove(a);
return res;
};
}
public static Func<T1, T2, R> Fix<T1, T2, R>(this Func<FuncRec<T1, T2, R>, Func<T1, T2, FuncRec<T1, T2, R>>> f)
{
return (t1, t2) =>
{
object res_;
FuncRec<T1, T2, R> a = null;
for (a = (t1_, t2_) => { t1 = t1_; t2 = t2_; return a; }; !_brr.TryGetValue(a, out res_); a = f(a)(t1, t2))
;
var res = (R)res_;
_brr.Remove(a);
return res;
};
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment