CREATE OR REPLACE PACKAGE ackermann IS
/*   File: ackermann-memo.pls

     Explicit memo-fn version of ackermann's function
  
     Without memorization:
            Ackermann(3,10) = 8189
            44698325 calls

     With memorization:
            Ackermann(3,10) = 8189
            20481 calls, 4103 cache hits
   
     (functional languages can do this transparently by currying with
      the memo() function, eg "let ackermann = memofn(ackermann);" )
*/
TYPE param2 IS TABLE OF PLS_INTEGER INDEX BY PLS_INTEGER;
TYPE memo2d IS TABLE of param2 INDEX BY PLS_INTEGER;
FUNCTION memofn(x IN PLS_INTEGER, y IN PLS_INTEGER) RETURN PLS_INTEGER;
END ackermann;


CREATE OR REPLACE PACKAGE BODY ackermann IS
  cache    memo2d;

  FUNCTION memofn(x IN PLS_INTEGER, y IN PLS_INTEGER) RETURN PLS_INTEGER
  IS
    r PLS_INTEGER;
  BEGIN

    -- previous computation already memorized?
    IF cache.EXISTS(x) AND cache(x).EXISTS(y) THEN RETURN cache(x)(y); END IF;

    IF x = 0 THEN
      r := (y+1);
    ELSIF y = 0 THEN
      r := (ackermann.memofn(x-1,1));
    ELSE
      r := (ackermann.memofn(x-1,ackermann.memofn(x,y-1)));
    END IF;

    cache(x)(y) := r; -- memorize new result

    RETURN r;
  END;
END;


set serveroutput on
BEGIN DBMS_Output.put_line('Ackermann(3, 10) = ' || ackermann.memofn(3, 10)); END;