<p>Pippenger's (1) from 1996 shows that (under some assumptions)  <strong>strict</strong> (CBV) functional programming languages are asympotically slower than imperative languages.  It is open whether Pippenger's result can be generalised to <strong>lazy</strong> functional languages, as was pointed out in (2).</p>

<p>Pippenger imposes two simplifying assumptions (on-line computation, and a certain atomicity of input). It is open whether 
they can be removed.  Pippenger conjectures that it can be done, but warns: <em>"[s]uch a result [...] seems far beyond the reach of currently available methods in computational complexity theory"</em>.</p>

<p>See also Campbell's answer in (3), and  Ben-Amram's notes (4).</p>

<hr>

<p><sup>
 1. N. Pippenger, <em><a href="https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Pure%20Versus%20Impure%20LISP.pdf" rel="noreferrer">Pure Versus Impure Lisp</a></em>.
</sup></p>

<p><sup>
 2. R. Bird, G. Jones, O. De Moor, <em><a href="https://www.cs.ox.ac.uk/richard.bird/online/BirdJonesDeMoor1997More.pdf" rel="noreferrer">More haste, less speed: lazy versus
    eager evaluation</a></em>.
</sup></p>

<p><sup>
 3. Stack Overflow, <em><a href="https://stackoverflow.com/questions/1990464/efficiency-of-purely-functional-programming">Efficiency of purely functional programming</a></em>.
</sup></p>

<p><sup>
 4. A. M. Ben-Amram, <em>Notes on Pippenger's Comparison of Pure and Impure LISP</em>.
</sup></p>

CC BY-SA 3.0
2018-04-11T09:37:25.143Z
2018-04-11T15:20:56.163Z
2018-04-11T15:20:56.163Z
Martin Berger
<p>What are some major, open computational complexity problems that arise from programming languages, especially program analysis and compilation? I am looking for problems on the lines of "the time complexity of Hindley-Milner type inference" or "the time complexity of 0CFA" (though both are solved problems).</p>

CC BY-SA 3.0
2018-02-26T11:17:53.277Z
Why the vote to close?  If this question is "too broad", tons of other questions on this site should be closed.
Damiano Mazza
CC BY-SA 3.0
2018-03-18T16:31:35.620Z
One I’m interested (but I am not sure if it is unsolved) is using (non-closed) Beta distance of lambda terms from a ground term as a measure of complexity.
Samuel Schlesinger
<cc.complexity-theory><pl.programming-languages><big-list><open-problem>
List of (unsolved) complexity problems arising from PL
xrq
# List of (unsolved) complexity problems arising from PL

(Asked by: username_0 on 2018-02-26)

What are some major, open computational complexity problems that arise from programming languages, especially program analysis and compilation? I am looking for problems on the lines of "the time complexity of Hindley-Milner type inference" or "the time complexity of 0CFA" (though both are solved problems).

**Tags:** cc.complexity-theory, pl.programming-languages, big-list, open-problem

> **Comments:**
> **username_1**: Why the vote to close?  If this question is "too broad", tons of other questions on this site should be closed.  
> **username_2**: One I’m interested (but I am not sure if it is unsolved) is using (non-closed) Beta distance of lambda terms from a ground term as a measure of complexity.  

---

## 1 answers

### Answer by username_3 on 2018-04-11. Score: 8 | Accepted answer

Pippenger's (1) from 1996 shows that (under some assumptions) **strict** (CBV) functional programming languages are asympotically slower than imperative languages. It is open whether Pippenger's result can be generalised to **lazy** functional languages, as was pointed out in (2).

Pippenger imposes two simplifying assumptions (on-line computation, and a certain atomicity of input). It is open whether
they can be removed. Pippenger conjectures that it can be done, but warns: *"[s]uch a result [...] seems far beyond the reach of currently available methods in computational complexity theory"*.

See also Campbell's answer in (3), and Ben-Amram's notes (4).

---

1. N. Pippenger, *[Pure Versus Impure Lisp](https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Pure%20Versus%20Impure%20LISP.pdf)*.

2. R. Bird, G. Jones, O. De Moor, *[More haste, less speed: lazy versus
eager evaluation](https://www.cs.ox.ac.uk/richard.bird/online/BirdJonesDeMoor1997More.pdf)*.

3. Stack Overflow, *[Efficiency of purely functional programming](https://stackoverflow.com/questions/1990464/efficiency-of-purely-functional-programming)*.

4. A. M. Ben-Amram, *Notes on Pippenger's Comparison of Pure and Impure LISP*.


---

