Функциональное программирование :: реккурсивные функции

    Итак, решил я писать компилятор/интерпретатор функционального языка. По началу сделал в виде вычисляющего дерева Черча, где каждая команда-нейрон представляла из себя отдельный объект, к которому прицеплены параметры. При вызове функции get() выполнялось обращение к необходимым входным данным. Я даже соорудил некое подобие strchr, и оно даже работало.

    Однако, оглядев сей велосипед, я понял, что у него по крайней мере 2 недостатка: все функции — встраиваемые и невозможны бесконечные вычисления як сервер в хаскеле/эрланге:

    server state = server renew(state, iosystem)
    server EXIT = EXIT

    Поэтому, мне пришлось сворачивать лавочку и делать стековую виртуальную машину. Причем, не просто машину, а Форт-машину: там есть возможность пофиксить второй косяк — на Форте имеется доступ к стеку вызова :) и можно просто подменять параметры, вместо реккурсивного перевызова функции server.

    Однако, все еще оставались функции следущего вида, которые не могли быть подвергнуты такой оптимизации:

    g(xs) = f(xs) . g(k(xs))
    g(EOSEQ) = INIT


    здесь: f(xs) — частично специфицированная функция, возвращает функцию, которая производит конверсию типа «следущее состояние» к типу «результат», а если короче и непонятнее, то

    f :: ('state -> ('param -> 'result))

    k(xs) — функция, возвращающая следущее состояние вычисляемых даннных, например (head | tail -> tail) или (x -> 1 + x)

    EOSEQ — символ конца последовательности

    INIT — первое приближение результата

    "." — оператор композиции; в моем случае — (.) :: (('a -> 'b) -> ('b -> 'c) -> ('a -> 'c))
    (чорт, я не хочу это словами расписывать… хныыы)


    Рассмотрим пример такой функции:

    fac N -> N * fac (N-1)
    fac 0 -> 1


    здесь xs = N, f(N) = (N *), k(x) = x - 1, EOSEQ = 0, INIT = 1

    Порядок выполнения (сначала в общем виде):

    g(xs) = f(xs) . f(k(xs)) . f(k^2(xs)) . ... . f(k^N(xs)) . INIT

    На примере:

    fac N = N * (N-1) * ((N-1) - 1) * ... * (N - (N - 2)) * 1

    Такие функции следовало преобразовать, и сделать это так, что компилятор мог повторить; посему мной была разработана метода, где функция g замещалась парой g и g1:

    g(xs) = f(xs) . g(k(xs))
    g(EOSEQ) = INIT


    =>

    g(xs) = g1(xs, INIT)

    g1(xs, ACC) = g1(k(xs), f(xs) (ACC))
    g1(EOSEQ, ACC) = ACC


    Здесь ACC — это аккумулятор, который хранит результат.

    Порядок вычисления для такой функции:

    g1 = INIT . f(xs) . f(k(xs)) . ... . f(k^N(xs))

    Первое, что бросается в глаза — это сиреневые слоники то, что INIT перекочевал в начало выражения. Пока f(xs) простая, может и прокатить… но не следует на это рассчитывать.

    Рассмотрим преобразование на примерах:

    summ(head|tail) = head + summ(tail)
    summ([]) = 0


    =>

    summ(xs) = summ1(xs, 0)

    summ1(head|tail, accum) = summ1(tail, head + accum)
    summ1([], accum) = accum


    Вроде должно работать — просуммирует список и, дойдя до конца, завершит.

    Теперь пример потоньше.

    isSort (x|y|tail) = if x >= y then isSort(y|tail) else false
    isSort (x|[]) = true


    Здесь: f(x|y|tail) = (value -> if x >= y then value else false)

    =>

    isSort(list) = isSort1(list, true)

    isSort1(x|y|tail, flag) = isSort1(y|tail, if x >= y then flag else false)
    isSort1(x|[], flag) = flag
    -- тут хорошо бы:
    -- isSort1(_, false) = false


    Проблема в том, что дойдя до первого элемента исходная функция остановится, а результирующая попрет дальше — ей плевать хотелось на значение 'flag' с вершины стека.

    Появилась идея ввести дополгительный параметр — аккумулятор вычисляемости. Но это потом, сначала проверим еще 1 пример:

    attach (pstart, pfin, head | tail) = [pstart | head | pfin] | attach(pstart, pfin, tail)
    attach (pstart, pfin, []) = []

    attach («Дороу, », "!", [«Мир»] | [«Стена»] | [«зеленый чертик»]) = [«Дороу, Мир!»] | [«Дороу, Стена!»] | [«Дороу, зеленый чертик!»].

    =>

    attach (pstart, pfin, head | tail) = attach1 (pstart, pfin, head | tail, [])
    attach1 (pstart, pfin, head | tail, []) = attach1 (pstart, pfin, tail, [pstart | head | pfin] | ACC)
    attach (pstart, pfin, [], ACC) = ACC

    attach («Здравствуй, », "!", [«Мир»] | [«Стена»] | [«зеленый чертик»]) = [«Дороу, зеленый чертик!»] [«Дороу, Стена!»] [«Дороу, Мир!»].

    Как видите, это уже совсем не та магия то значение, которое возвращала исходная функция.

    На сем у меня кончается мана, поэтому подвожу итог.

    Вариант 1: Усложнять формализованную метапроцедуру преобразования.

    Вариант 2: Сразу писать аккумуляторные реккурсивные функции.

    Если честно, я за второй вариант, ибо он развивает мозг — приходится (в отсутствие четкого описания действий) думать, как же реализовать алгоритм.

    Рад буду услышать комментарии и предложения, а пока отправляюсь пить из синеньких бутылочек.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 7

      +3
      поставь кат а то заминусуют не читая
        +5
        Слово «рекурсия» пишется с одной буквой «к».
        • НЛО прилетело и опубликовало эту надпись здесь
            0
            > а пока отправляюсь пить из синеньких бутылочек.
            Ой зря :)
              0
              Ох, если хотя бы три человека со всего хабра поймут, о чем собсно статья, то… то значит она не зря была написана :)
                +1
                В последнем случае (а это map по сути) с энергичным списком вроде никак не выкрутиться: если хвостовая рекурсия, то либо последующее обращение списка, либо переписывание в CPS с разменом стека на кучу. Так что здесь рулят ленивость и stream fusion.
                Всё это похоже на переписывание примитивной рекурсии в терминах foldl. Какие из этого следствия, сейчас не соображу.
                  0
                  Цель была формализовать переделку рекурсии в foldl, или установление невозможности такого преобразования.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое