I have a question for those among you that are more knowledgeable about Haskell
or other functional programming languages, or related mathematics or set theory
and such.
I recall reading that at least in certain math/logic papers that a programming
language type system can be defined logically in terms of pure sets, making it
essentially self-defined without needing to rely on external definitions of for
example what a number is. In such a type system, every value is a generic set
of 0..N elements, and the value of every element is also such a generic set,
which can recurse arbitrarily such that all leaves are the empty set. In such a
system, you could for example represent the number zero by {}, the number 1 by
{{}}, 2 by {{{}}} or something else, etc. I'm not saying that such a type
system would be practical to implement in a manner resembling this, but more
that it is simply a logical basis for defining a closed system at the most
fundamental level.
I am wanting to try designing a low-level conceptual type system like this and
was wondering what precedents existed, ideally in implemented programming
languages, but otherwise in set logic papers, for how one might do this. For
example, what set values one might use to represent integers, or booleans, or
arrays, or other data types that users would actually work in terms of. Also,
what fundamental/etc set operators one would have in terms of which all other
operators are defined.
Does Haskell at least conceptually work in terms like I described? I seem to
recall reading that how it logically thinks about string values is towards that
direction.
Or to be more clear, what I *actually* am looking to design is a system with a
single concrete base type that can represent all possible values, and that all
other types are declared as subsets.
In Perl 6 syntax I'm looking to have some single base type Foo where all other
types including eg Integers and Arrays etc are definable like this:
subset Integer of Foo where ...;
subset Array of Foo where ...;
...
I thought that the generic set was probably the best candidate for Foo. But
there might be something better.
Any pointers to precedents on what to use for Foo and how are greatly
appreciated.
-- Darren Duncan
