Реализация функции Аккермана

ackermann.erl

%%  @file ackermann.erl Реализация функции Аккермана.
%%  Результатом работы генератора должна
%%  быть пара {очередное_число, генератор_следующего_числа}.
%%
%%  Для ускорения счета используется классическая рекурсивная мемоизация.
%%  Она Реализована через оператор неподвижной точки (Y-комбинатор).
%%  Крайне эффективна для рекурсивных функций.
%%
%%  Для функции Аккермана разница c мемоизацией и без
%%  становится заметна уже на M = 3, N = 10.
%% 
%%  Сделано на основе:
%%      https://gist.github.com/w495/2875252
%%  Отличия:
%%      Заменена целевая функция.
%%      Ets заменен на словарь процесса.
%%      Переменованы некоторые функции.
%%      Переопределено отношение порядка (next/1).
%%
%%  generator/0 --- Функция, которая реазована по заданию
%%  generator/1 --- Основная рабочая функция generator/0
%%

-module(ackermann).

-export([
    ackermanndir/1, % Функция Аккермана без мемоизации.
    generator/0,    % Искомая функция по заданию.
    generator/1,    % Основная рабочая функция generator/0
    test/0          % Функция для тестирования.
]).

%%
%% @doc
%%     Тестовая функция для проверки
%%
test()->
    Start = fun generator/0,
    lists:foldl(
        fun(I,{Function, {M, N}}) ->
            {A,Function1} = Function(),
            io:format("~2.w: A(~p, ~p) = ~p;~n", [I, M, N, A]),
            {Function1, next({M, N})}
        end,
        {Start, {0, 0}},
        lists:seq(1, 21)
    ).

%%
%% @doc
%%     Возвращает пару {очередное_число, генератор_следующего_числа}.
%%     Генератор чисел Фибоначчи.
%%     Искомая функция по заданию.
%%
generator()->
    generator({0, 0}).

%%
%% @doc
%%     Возвращает пару {очередное_число, генератор_следующего_числа}.
%%     На вход подается порядковый номер числа.
%%     Основная рабочая часть функции generator/0
%%
generator({M, N}) ->
    Rfun = rmemoize(fun ackermannimpl/1),
    {
        Rfun({M, N}),
        fun()->
            generator(next({M, N}))
        end
    }.

%%
%% @doc
%%     Возвращает результат функции Аккермана для заданных М и N.
%%     Функция Аккермана без мемоизации.
%%
ackermanndir({0, N}) ->
    N + 1;
ackermanndir({M, 0}) when M > 0 ->
    ackermanndir({M-1, 1});
ackermanndir({M, N}) when M > 0, N > 0 ->
    ackermanndir({M - 1, (ackermanndir({M, N - 1}))}).

%%
%% @doc
%%     Возвращает следующую пару числе Аккермана (М, N).
%%     На матрице натуральных чисел не очевидно,
%%     какое число является следующим.
%%     Потому просто будем обходить матрицу
%%     по перпендикулярным диагоналям.
%%
next({0, N}) ->
    {N + 1, 0};

next({M, N}) ->
    {M - 1, N + 1}.

%%
%% @doc
%%     Возвращает функцию Аккермана по определению.
%%
ackermannimpl(Self) ->
    fun
        ({0, N}) ->
            N + 1;
        ({M, 0}) when M > 0 ->
            ((Self)({M-1, 1}));
        ({M, N}) when M > 0, N > 0 ->
            ((Self)({M - 1, ((Self)({M, N - 1}))}))
    end. 

%% ------------------------------------------------------------------------
%% Ниже описана.
%%
%% Классическая рекурсивная мемоизация
%% Реализована через оператор неподвижной точки.
%% Крайне эффективна для рекурсивных функций.
%%
%% Можно реализовать и простую мемоизацию для данного примера.
%% Будем запоминать только последний вариант чисел Аккермана,
%% но в общем случае для чисел Аккермана она не будет такой быстрой.
%%
%% ------------------------------------------------------------------------

%%
%% @doc
%%     Оператор неподвижной точки
%%     Следует из определения рекурсии в λ-исчислении.
%%
ry(Function) when erlang:is_function(Function, 1) ->
    Function(
        fun(X) ->
            (ry(Function))(X)
        end
    ).

%%
%% @doc
%%     Вычисляет рекурсивную функцию.
%%     Запоминает промежуточные результаты.
%%     И при необходимости достает их из памяти.
%%
rmemoize(Tab, Function) when erlang:is_function(Function, 1) ->
    fun (B) ->
        Bfunction = Function(B),
        fun (Args) ->
            Hash = funhash(Bfunction, Args),
            case storage_get(Tab, Hash) of
                undefined ->
                    Result = Bfunction(Args),
                    storage_put(Tab, Hash, Result),
                    Result;
                Result ->
                    Result
            end
        end
    end.

%% @doc
%%     Вычисляет рекурсивную функцию.
%%     Удаляет промежуточные результаты.
%%     Запоминает последний результат.
%%
%%     ВАЖНО:
%%         Function = fun( fun(Arg) ) -> fun(Arg)
%%     Или в стиле Ocaml:
%%         (fun (fun -> Arg ) -> (fun -> Arg)
%%
rmemoize(Function) when erlang:is_function(Function, 1) ->
    fun (Args) ->
        Anstab = storage_new(memo_rmemoize_ans),
        Tmptab = storage_new(memo_rmemoize_tmp),
        Hash = funhash(Function, Args),
        case storage_get(Anstab, Hash) of
            undefined ->
                Mfunction = rmemoize(Tmptab, Function),
                Yfunction = ry(Mfunction),
                Ans = Yfunction(Args),
                storage_delete(Tmptab),
                storage_put(Anstab, Hash, Ans),
                Ans;
            Result ->
                Result
        end
    end.

%%
%% @doc
%%     Создает новое хранилище.
%%     В идеале должен быть ets.
%%     А еще лучше, какая-нибудь чистая структура (dict).
%%     Но некоторые, считают,
%%     что тут хорошо использовать словарь процесса.
%%
storage_new(_name) ->
    ok.

%%
%% @doc
%%     Берет значение по ключу Key в хранилище Tab
%%     В идеале должен быть ets.
%%     А еще лучше, какая-нибудь чистая структура (dict).
%%     Но некоторые, считают,
%%     что тут хорошо использовать словарь процесса.
%%
storage_get(_tab, Key) ->
    get(Key).

%%
%% @doc
%%     Кладет значение по ключу Key в хранилище Tab
%%     В идеале должен быть ets.
%%     А еще лучше, какая-нибудь чистая структура (dict).
%%     Но некоторые, считают,
%%     что тут хорошо использовать словарь процесса.
%%
storage_put(_tab, Key, Value) ->
    put(Key, Value).

%%
%% @doc
%%     Удаляет хранилище.
%%     В идеале должен быть ets (для временного хранения).
%%     А еще лучше, какая-нибудь чистая структура (dict).
%%     Но некоторые, считают,
%%     что тут хорошо использовать словарь процесса.
%%
storage_delete(_tab) ->
    ok.

%%
%% @doc
%%     Вычисляет хеш для функции и аргументов.
%%     В данной задаче не имеет смысла
%%     в качетсве кеша брать что-то иное,
%%     кроме аргументов.ы
%%
funhash(_fun, Args) ->
    % {module, Module}    = erlang:fun_info(Fun, module),
    % {name, Name}        = erlang:fun_info(Fun, name),
    % {arity, Arity}      = erlang:fun_info(Fun, arity),
    % {Module, Name, Arity, Args}.
    Args.