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