[Haskell-cafe] First order Haskell without Data

[Stefan O'Rear]

On Thu, Apr 19, 2007 at 02:47:30AM +0100, Neil Mitchell wrote:
> 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.

A first order language without data types cannot exist - what could
the arguments of functions be, if they cannot be function types or
data types?  If you allow recursive primitive types, then data can be
trivially encoded, by the sum-of-products construction.  If you allow
non-recursive primitive types, then any function space contains only
functions with a priori bounded argument and result sets, and thus
your language is trivally Turing incomplete. 

> * 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

You could just have referenced Church encoding ;)

> * 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

Stefan