List of (unsolved) complexity problems arising from PL

Question

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).

Answer 1

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.}

^{2. R. Bird, G. Jones, O. De Moor, More haste, less speed: lazy versus eager evaluation.}

^{3. Stack Overflow, Efficiency of purely functional programming.}

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