Some primitive types for a hypothetical simple programming language: Bit, Unit, Bottom (e.g. Haskell's EmptyDataDecls), 2-Tuples (Pairs), Either, Additional library unit types (tags).
Heavily inspired by Haskell.
Nested pairs can provide arbitrary fixed length tuples. Nested pairs of Bit can encode arbitrary fixed-width bitwise data, for example, Byte = (Bit, (Bit, (Bit, (Bit, (Bit, (Bit, (Bit, (Bit, Unit)))))))).
Unary representation of natural numbers is possible with Either: Upto2 = Either Unit (Either Unit (Either Unit Bottom)). Values are Left Unit = 0, Right (Left Unit) = 1, Right (Right (Left Unit)) = 2. (This is a realistic use-case of the Bottom type. This construction of unary would be uglier without it.)
Bit could be further deconstructed into Either Unit Unit. Or Either Bottom Bottom? The latter appears usable if you have lazy evaluation, albeit awkward.
The additional library unit types, nullary data constructors, are tags to be paired with payloads built out of primitive types. They travel with the data and are intended to be used for type checking, perhaps at run-time. For example, a function that processes a character would expect a Tuple of a UnicodeChar tag and a payload built out of tuples of Bit. Some standard library unit types (tags): Arbitrary precision integers, Boolean (distinct from Bit, to allow better type checking), Byte, UnicodeChar, List, Rationals, various IEEE-754 floating point.
Some functions in the standard library: Primitive functions for input and output, of bytes and characters. Implementations of arbitrary precision arithmetic, rationals, IEEE-754 floating point. The conditional function ("if"). We won't go further into functions because this post is about types.
Lots of syntactic sugar: Literal integers, literal Strings. Fancy feature: let the user override the syntactic sugar (e.g. Haskell's OverloadedStrings). Literal strings can become Lists of UnicodeChar or Byte or something user-defined.
More syntactic sugar: Flattened tuples (e.g., (Bit, Bit, Bit) is a type synonym for (Bit, (Bit, (Bit, Unit)))), List (built the usual way out of Either and terminated by Unit), Algebraic data types, Fixed length arrays encoded as nested Pairs of the same type, for example Byte defined above. Array indices are easiest done in unary as described above, but you don't get constant-time access. Something fancier involving trees built out of Pairs would get logarithmic time.
Fancy feature: polymorphic types (already needed for Pair, Either, List).
More types: Function, Environment (i.e. symbol table), (together with which one can call eval). For metaprogramming and reflection: Type, Expression, Declaration. Error or exception types, and associated control flow constructs.
Original idea was a simple programming language with just the tuple (Integer, String) as the built-in type: integers with associated data. What else is needed, or would be nice? (Turns out, a lot.)
EmoticonEmoticon