[Haskell-cafe] First order Haskell without Data

[Neil Mitchell]

Hi,

I've been wondering what is essential to Haskell and what isn't. Not
from a point of view of what could be removed from the language, but
what could be removed from a Core language.

Given the features of higher-order, laziness and data types:

Laziness can be converted to higher-order functions

Data types can be converted to higher-order functions

Higher-order functions can be converted to Data


So as far as I can see it we have left:
{data-types only}
{higher-order functions only}

But we don't have laziness only, so my question is if it is possible
to represent all of Haskell in a first-order language without data
types, but with laziness. If its possible to do so in a strict
first-order language without data types, then I'd also be interested.

Are any of these known results?

Thanks

Neil

References:

* data types -> higher order is in "Efficient Interpretation by
Transforming Data Types and Patterns to Functions"
http://www.cs.nott.ac.uk/~nhn/TFP2006/Papers/03-JansenKoopmanPlasmeijer-EfficientInterpretation.pdf

* laziness -> functions, functions -> data is in "Definitional
Interpreters for Higher-Order Programming Languages"
http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf