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