Pull to refresh

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

Reading time 3 min
Views 808
Итак, решил я писать компилятор/интерпретатор функционального языка. По началу сделал в виде вычисляющего дерева Черча, где каждая команда-нейрон представляла из себя отдельный объект, к которому прицеплены параметры. При вызове функции 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: Сразу писать аккумуляторные реккурсивные функции.

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

Рад буду услышать комментарии и предложения, а пока отправляюсь пить из синеньких бутылочек.
Tags:
Hubs:
-9
Comments 7
Comments Comments 7

Articles