Functional programming :: recursive functions

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

However, looking at this bike, I realized that he had at least 2 drawbacks: all functions are embedded and infinite calculations are impossible for a yak server in Haskel / Erlang:

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

Therefore, I had to fold a shop and make a stack virtual machine. Moreover, not just a car, but a Fort machine: there is an opportunity to fix the second joint - on the Fort there is access to the call stack :) and you can simply replace the parameters, instead of recursively calling the server function.

However, the following functions still remained, which could not be subjected to such optimization:
')
g(xs) = f(xs) . g(k(xs))
g(EOSEQ) = INIT

here: f (xs) is a partially specified function that returns a function that converts the type of "next state" to the type of "result", and if shorter and more incomprehensible, then

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

k (xs) is a function that returns the next state of the calculated data, for example (head | tail -> tail) or (x -> 1 + x)

EOSEQ - end of sequence character

INIT - the first approximation of the result

"." - composition operator; in my case - (.) :: (('a -> 'b) -> ('b -> 'c) -> ('a -> 'c))
(hell, I do not want to paint it with words ... whny)

Consider an example of such a function:

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

here xs = N, f(N) = (N *), k(x) = x - 1, EOSEQ = 0, INIT = 1

The order of execution (first in general):

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

For example:

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

Such functions should be transformed, and make it so that the compiler could repeat; therefore, I developed a method where the function g was replaced by a pair g and 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

Here ACC is the battery that stores the result.

The calculation order for this function is:

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

The first thing that catches your eye is the purple elephants that INIT migrated to the beginning of the expression. While f (xs) is simple, it may take a ride ... but you should not count on it.

Consider the conversion examples:

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

=>

summ(xs) = summ1(xs, 0)

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

It seems to be working - to summarize the list and, reaching the end, complete.

Now the example is thinner.

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

Here: 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, having reached the first element, the original function will stop, and the resultant will trap further - she didn’t care about the flag value from the top of the stack.

An idea to introduce an additional parameter - accumulability accumulator. But this later, first check one more example:

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

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

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

I’m running out of mana for this, so I’ll summarize.

Option 1: Complicate a formalized metaprocedure of transformation.

Option 2: Immediately write rechargeable battery functions.

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

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