[Haskell-cafe] First order Haskell without Data

[Josef Svenningsson]

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 <ndmitchell at gmail.com> 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.
>
> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>