First order Haskell without Data
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-Effi... * 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
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
Hi
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?
I should have clarified, in my mind I was thinking "allowing only non-recursive constants, namely Int's".
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.
True, I guess that is the most minimal we can do then.
* 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 ;)
I like that paper as it shows a really trivial encoding of case and constructors into the Church encoding - i.e. how you'd transform Haskell to it easily with examples. Thanks Neil
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
Is this a pure language? If so you have to lose asymptotic performance in some cases, In "More haste, less speed: lazy versus eager evaluation" by Richard Bird, Geraint Jones and Oege De Moor there's an example of a function that can be implemented in linear time in a lazy language but requires O(n log n) time in a strict pure language. It doesn't matter if you just want to reason about results, and on the other hand for an intermediate language I suppose you might prefer to add state and explicitly manipulate the thunking. Brandon
Hi,
Just a comment or two on the implications of converting higher-order
functions to data.
The paper you reference about this uses the method of
defunctionalization. This is a whole program transformation and might
therefore not be suitable in a compiler such as GHC or YHC. On the
other hand, it is more or less exactly what JHC uses
If you want to support separate compilation you should go for more
conventional closure conversion. This is in essence what every
compiler which compiles a higher order language does. But if you want
to have a typed language which can express this transformation you
will be needing quite a sophisticated type system.
http://www.cs.cmu.edu/~rwh/papers/closures/popl96.pdf
Just my 2 öre.
Josef
On 4/19/07, 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-Effi...
* 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (4)
-
Brandon Michael Moore -
Josef Svenningsson -
Neil Mitchell -
Stefan O'Rear