<p>Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend this problem, such as Stream Fusion, which allow the combination of list consuming/producing functions. Those techniques require specialised, specific algorithms and only work for a restricted set of recursive functions.</p>

<p>My question is: what determines which recursive functions can, and which recursive functions can not be fused that way? Is there a programming system with well-behaved recursion where any arbitrary function could be fused this way?</p>

CC BY-SA 3.0
2014-04-23T11:09:46.687Z
Any recursive function can be implemented alternatively as a non-recursive function. After all, hardware does not know about recursion, yet GHC manages to compile recursive functions to machine code. Concretely, you can turn any recursive function into a fancy while loop which implements the call stack of the original recursive function by hand. (Which is what GHC compiler does to convert Haskell to machine code.)

So perhaps I do not understand your question because you have a particular method in mind ("fusion"). It would help to say a few words about it in your question.
Andrej Bauer
CC BY-SA 3.0
2014-04-23T16:18:23.830Z
I don't understand what you mean. Please tell your technique to fuse functions such as `g` in `evens [] = []; evens (x:xs) = (if even x then x else []) ++ evens xs; doubles [] = []; doubles (x:xs) = x*2 + doubles xs; g a = doubles (evens a)` - what is your algorithm to find that `g [] = []; g a = (if even x then x*2 else []) ++ g xs` ?
MaiaVictor
<ds.algorithms><pl.programming-languages><computability><optimization>
Is there a programming language where any arbitrary recursive function can be fused?
MaiaVictor
# Is there a programming language where any arbitrary recursive function can be fused?

(Asked by: username_0 on 2014-04-23)

Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend this problem, such as Stream Fusion, which allow the combination of list consuming/producing functions. Those techniques require specialised, specific algorithms and only work for a restricted set of recursive functions.

My question is: what determines which recursive functions can, and which recursive functions can not be fused that way? Is there a programming system with well-behaved recursion where any arbitrary function could be fused this way?

**Tags:** ds.algorithms, pl.programming-languages, computability, optimization
> **Comments:**
> **username_1**: Any recursive function can be implemented alternatively as a non-recursive function. After all, hardware does not know about recursion, yet GHC manages to compile recursive functions to machine code. Concretely, you can turn any recursive function into a fancy while loop which implements the call stack of the original recursive function by hand. (Which is what GHC compiler does to convert Haskell to machine code.)  So perhaps I do not understand your question because you have a particular method in mind ("fusion"). It would help to say a few words about it in your question.  
> **username_0**: I don't understand what you mean. Please tell your technique to fuse functions such as `g` in `evens [] = []; evens (x:xs) = (if even x then x else []) ++ evens xs; doubles [] = []; doubles (x:xs) = x*2 + doubles xs; g a = doubles (evens a)` - what is your algorithm to find that `g [] = []; g a = (if even x then x*2 else []) ++ g xs` ?  

---

## 0 answers

