Last active
May 22, 2023 19:46
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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