// Typed memoization in Generic C# // This program requires .Net version 2.0 // Peter Sestoft (sestoft@itu.dk) * 2001-12-04 // Compile this file with // csc /addmodule:GCollections.netmodule Memoization.cs using GCollections; using System; public interface Method { R call(A a); } // Functional-style memoization // ---------------------------- // A Method is a function of type A -> R. // A ProtoMethod is a function transformer (uncurried), // of type (A -> R) * A -> R. // A Memoize is a memoizer for recursive functions of type A -> R, in // fact, a fixed-point combinator, of type: ((A -> R) * A -> R) -> A -> R // // This uses delegates because that will permit mutually // recursive memoized methods, and memoization of static as well // as non-static methods. public delegate R ProtoMethod(Method method, A a); class Memoize : Method { private HashMap table; private ProtoMethod protomethod; public Memoize(ProtoMethod protomethod) { this.protomethod = protomethod; table = new HashMap(); } public R call(A a) { if (table.Contains(a)) return table[a]; else return table[a] = protomethod(this, a); } } // Object-oriented memoization // --------------------------- // Looks simpler, but does not permit mutually recursive memoized // methods (I think). abstract class OOMemoize : Method { private HashMap table = new HashMap(); public R call(A a) { if (table.Contains(a)) return table[a]; else return table[a] = protomethod(a); } public abstract R protomethod(A a); // To be implemented by subclass } // The Fibonacci function class OFib : OOMemoize { public override double protomethod(int n) { if (n <= 1) return 1.0; else return call(n-1) + call(n-2); } } // Memoizing and calling the Fibonacci function class TestMemo { // The Fibonacci function as a transformer static double Fib(Method fib, int n) { if (n <= 1) return 1.0; else return fib.call(n-1) + fib.call(n-2); } // The memoized Fibonacci function static Method ffib = new Memoize(new ProtoMethod(Fib)); static Method ofib = new OFib(); static void Main(string[] args) { if (args.Length != 1) Console.WriteLine("Usage: Memoization \n"); else { int max = int.Parse(args[0]); for (int i=0; i<= max; i++) Console.WriteLine(i + " " + ffib.call(i)); for (int i=0; i<= max; i++) Console.WriteLine(i + " " + ofib.call(i)); } } }