Functional programming :: recursive functions

So, I decided to write a functional language compiler / interpreter. At first, he made Church in the form of a computational tree, where each neuron team was a separate object, to which parameters were attached. When the get () function was called, the necessary input was accessed. I even built some kind of strchr, and it even worked.

However, looking around this bike, I realized that it has at least 2 drawbacks: all functions are built-in and endless computing is impossible like a server in a Haskell / Erlang: Therefore, I had to collapse the bench and make a stacked virtual machine. Moreover, it’s not just a car, but a Fort car: there you can fix a second jamb - Fort has access to the call stack :) and you can just change the parameters instead of recursively re-calling the server function.

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



However, there were still functions of the following form that could not be subjected to such optimization: here: f (xs) is a partially specified function, returns a function that converts the "next state" type to the "result" type, and if it is shorter and incomprehensible , then k (xs) is a function that returns the next state of the calculated data, for example, or EOSEQ is the character of the end of the sequence INIT is the first approximation of the result "." - composition operator; in my case - (damn it, I don’t want to put it in words ... hell) Let's consider an example of such a function: here The order of execution (first in general form): For example:

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



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

(head | tail -> tail)(x -> 1 + x)





(.) :: (('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

Such functions should have been converted, and made so that the compiler could repeat; therefore, I developed a method where the function g was replaced by a pair of g and g1: => Here ACC is the battery that stores the result. The calculation procedure for such a function: The first thing that catches your eye is the lilac elephants that INIT migrated to the beginning of the expression. While f (xs) is simple, it can take a ride ... but you should not count on it. Let's look at the conversion using examples: => It should work — it sums up the list and, upon reaching the end, completes. Now the example is thinner. Here: =>

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





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

The problem is that upon reaching the first element the original function will stop, and the resulting one will trample on - she didn’t care about the value of 'flag' from the top of the stack.

There was an idea to introduce an additional parameter - a computability accumulator. But then, first check another 1 example:

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

attach ("Drow,", "!", ["World"] | ["Wall"] | ["green devil"]) = ["Drow, Peace!"] | [“Dorough, the Wall!”] | [“Dorough, green devil!”].

=>

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 (“Hello,”, “!”, [“World”] | [“Wall”] | [“green devil”]) = [“Dorow, green devil ! ”] [“ Dow, the Wall! ”] [“ Dow, the World! ”].

As you can see, this is not the magic at all, the value that the original function returned.

This is where my mana ends, so I sum up.

Option 1: Complicate the formalized metaprocessing transformation.

Option 2: Immediately write battery recursive functions.

To be honest, I am for the second option, because it develops the brain - you have to (in the absence of a clear description of the actions) think how to implement the algorithm.

I will be glad to hear comments and suggestions, but for now I’m going to drink from blue little bottles.