アッカーマン関数＋メモ化をいろいろな言語で

wikipediaから数式見て書いた
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%83%E3%82%AB%E3%83%BC%E3%83%9E%E3%83%B3%E9%96%A2%E6%95%B0

Scheme(Gauche)

(ack 4 2)でメモリ1Gほど使ってアロケートエラー(スタックオーバーフローかもしれないけど、わからない)

(define (ack m n)
  (cond ((= m 0) (+ n 1))
        ((= n 0) (ack (- m 1) 1))
        (else (ack (- m 1) (ack m (- n 1))))))

 (define (memoize func)
  (let ((dp (make-hash-table 'equal?)))
    (lambda args
      (if (hash-table-exists? dp args)
          (hash-table-get dp args)
          (let ((value (apply func args)))
            (hash-table-put! dp args value)
            value)))))

(define ack (memoize ack))

gosh> (ack 3 9)
4093

gosh> (ack 4 1)
65533

gosh> (ack 4 2)
GC Warning: Out of Memory!  Returning NIL!
out of memory (16).  aborting...

ack(4, 1)で一瞬でスタックオーバーフロー、ふざくんなwwwwwwwwwww
スタックのサイズを弄るためにソースに手を入れる必要があるらしい

function ack(m, n)
   if m == 0 then
      return n + 1
   elseif n == 0 then
      return ack(m - 1, 1)
   else
      return ack(m - 1, ack(m, n - 1))
   end
end

--http://stackoverflow.com/questions/129877/how-do-i-write-a-generic-memoize-function     
function varg_tostring(...)
   local s = select(1, ...)
   for n = 2, select('#', ...) do
      s = s..","..select(n,...)
   end
   return s
end

function memoize(f)
   local cache = {}
   return function (...)
             local al = varg_tostring(...)
             if cache[al] then
                return cache[al]
             else
                local y = f(...)
                cache[al] = y
            return y
             end
          end
end

> print(ack(3, 9))
4093

> print(ack(4, 1))
stdin:4: stack overflow
stack traceback:
	stdin:4: in function 'ack'
	stdin:7: in function 'f'
	stdin:8: in function 'ack'
	stdin:7: in function 'f'
	stdin:8: in function 'ack'
	stdin:7: in function 'f'
	stdin:8: in function 'ack'
	stdin:7: in function 'f'
	stdin:8: in function 'ack'
	stdin:7: in function 'f'
	...
	stdin:7: in function 'f'
	stdin:8: in function 'ack'
	stdin:7: in function 'f'
	stdin:8: in function <stdin:3>
	(tail call): ?
	stdin:8: in function <stdin:3>
	(tail call): ?
	stdin:8: in function 'ack'
	stdin:1: in main chunk
	[C]: ?

Ruby

メモ化で詰まった

? def memoize(f)
?   dp =  {}
?   lambda {|*arg| dp[arg] ||  dp[arg] = f.call(*arg)}
? end

Rubyの関数オブジェクトの実行は

func.call()

で呼ばないといけないので上の記述方法は使えない

メタプログラミング技法を使わないといけない、しかしこれもm.ack(4,1)でスタックオーバーフロー、Gaucheすごい

#http://www.geocities.jp/m_hiroi/light/abcruby11.html
class Memoize
  def initialize(name)
    @table = {}
    eval <<"DEF"
      def #{name}(*args)
        unless n = @table[args]
          n = super(*args)
          @table[args] = n
        end
        n
      end
DEF
  end
end

def ack(m, n)
  if m == 0 then
    n + 1
  elsif n == 0 then
    ack(m - 1, 1)
  else
    ack(m - 1, ack(m, n - 1))
  end
end

m = Memoize::new(:ack)

>> m.ack(3, 9)
=> 4093

?> m.ack(4,1)
SystemStackError: stack level too deep
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
... 7229 levels...
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):47:in `ack'
	from (eval):3:in `ack'
	from (irb):55

yppp’s diary

info

アッカーマン関数＋メモ化をいろいろな言語で