Thanks to Petr and Andrej for their feedback. I'm rephrasing my question and give a bit of a context:
Functional programming languages are mostly based on lambda calculus. Implementing a functional language straight forward is inefficient on today's hardware. For example:
\begin{eqnarray} f &\equiv&\ \lambda x.\lambda y.\ x+y \\ g &\equiv&\ f\ v \end{eqnarray} Those functions will have the following types: \begin{eqnarray} f &\colon& a \rightarrow b \rightarrow c \\ g &\colon& a \rightarrow b \end{eqnarray}
Now the function $g$ needs to store the variable $v$ in an runtime environment, when the variable $v$ is only accessible in a specific context. This concept is known as closure.
I'm looking for an method to eliminate all closures in a given program and avoid the allocation of environments at runtime.
- Is this even possible?
- What are the disadvantage of such an algorithm?
Thanks to Petr for mentioning the S-K basis. As I understand, the combinator graph reduction will put any function in a point-free style. However by applicate arguments partially, there is still some form of environment necessary.
Original question:
Is a purely functional programming language like Haskell still turing complete without the concept of closures?
Or the other way around: Is it possible to eliminate all closures in a Haskell program in order to use no heap space?
nat
it'll be Turing complete. $\endgroup$while
-loops, too.) $\endgroup$