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;