Итак, решил я писать компилятор/интерпретатор функционального языка. По началу сделал в виде вычисляющего дерева Черча, где каждая команда-нейрон представляла из себя отдельный объект, к которому прицеплены параметры. При вызове функции get() выполнялось обращение к необходимым входным данным. Я даже соорудил некое подобие strchr, и оно даже работало.
Однако, оглядев сей велосипед, я понял, что у него по крайней мере 2 недостатка: все функции — встраиваемые и невозможны бесконечные вычисления як сервер в хаскеле/эрланге:
Поэтому, мне пришлось сворачивать лавочку и делать стековую виртуальную машину. Причем, не просто машину, а Форт-машину: там есть возможность пофиксить второй косяк — на Форте имеется доступ к стеку вызова :) и можно просто подменять параметры, вместо реккурсивного перевызова функции server.
Однако, все еще оставались функции следущего вида, которые не могли быть подвергнуты такой оптимизации:
здесь: f(xs) — частично специфицированная функция, возвращает функцию, которая производит конверсию типа «следущее состояние» к типу «результат», а если короче и непонятнее, то
k(xs) — функция, возвращающая следущее состояние вычисляемых даннных, например
EOSEQ — символ конца последовательности
INIT — первое приближение результата
"." — оператор композиции; в моем случае —
(чорт, я не хочу это словами расписывать… хныыы)
Рассмотрим пример такой функции:
здесь
Порядок выполнения (сначала в общем виде):
На примере:
Такие функции следовало преобразовать, и сделать это так, что компилятор мог повторить; посему мной была разработана метода, где функция g замещалась парой g и g1:
=>
Здесь ACC — это аккумулятор, который хранит результат.
Порядок вычисления для такой функции:
Первое, что бросается в глаза — этосиреневые слоники то, что INIT перекочевал в начало выражения. Пока f(xs) простая, может и прокатить… но не следует на это рассчитывать.
Рассмотрим преобразование на примерах:
=>
Вроде должно работать — просуммирует список и, дойдя до конца, завершит.
Теперь пример потоньше.
Здесь:
=>
Проблема в том, что дойдя до первого элемента исходная функция остановится, а результирующая попрет дальше — ей плевать хотелось на значение '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: Сразу писать аккумуляторные реккурсивные функции.
Если честно, я за второй вариант, ибо он развивает мозг — приходится (в отсутствие четкого описания действий) думать, как же реализовать алгоритм.
Рад буду услышать комментарии и предложения, а пока отправляюсь пить из синеньких бутылочек.
Однако, оглядев сей велосипед, я понял, что у него по крайней мере 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))
Первое, что бросается в глаза — это
Рассмотрим преобразование на примерах:
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: Сразу писать аккумуляторные реккурсивные функции.
Если честно, я за второй вариант, ибо он развивает мозг — приходится (в отсутствие четкого описания действий) думать, как же реализовать алгоритм.
Рад буду услышать комментарии и предложения, а пока отправляюсь пить из синеньких бутылочек.