[theory] What is a type?

[Jonathan Marler]

On Sunday, 10 October 2010 at 12:28:32 UTC, Justin Johansson 
wrote:
> Specifically I have a problem in trying to implement
> a functional language translator in D.  My target language
> has a rather non-conventional type system, in which,
> superficially at least, types can be described as being
> Cartesian in nature. That is,
> types in this system have two orthogonal dimensions:
> (1) classical data-type (e.g. boolean, number, string,
> object) and
> (2) Kleene cardinality (occurrences) with respect to (1).
>
> The axial origin of this Cartesian type-system correlates well
> with the concept of the "top" type (AKA "Unit" in Scala)
> and as the rather adhoc "void" type in many Algol-derived
> languages such as C/C++/Java/D.
>
> So along axis 1 we might broadly describe the classical
> data types as item, boolean, number, string, object where
> item is effectively either a superclass or variant of the
> other mentioned types.
>
> Along axis 2 we describe Kleene occurrences of 1 as may be
> passed contractually to a receiving function.  These
> occurrences may be enumerated six-fold as:
> zeroOrMore
> zeroOrOne
> oneOrMore
> exactlyZero
> exactlyOne
> none
>
> Readers may see that, for example, zeroOrOne is a special
> case (perhaps a subclass?) of zeroOrMore.  exactlyOne is
> a special case of both zeroOrOne and oneOrMore (sounds like
> multiple inheritance?).  OTOH, exactlyZero is a special
> case of zeroOrOne, which, in turn, is a special case of
> zeroOrmore.
>
> none is a special case of all of the above and reflects
> the cardinality facet of the return type of a function
> that never returns (say as by throwing an exception).
>
> To make this type system even more enigmatic lets add a
> third dimension, taking the 2-D Cartesian type system
> model to a 3-D Spatial model, by imagining a further
> degree of freedom with respect to laziness of evaluation
> (AKA closure of arguments).
>
> Now having hopefully described that a type is something
> that might well have multiple orthogonal aspects to its
> identity, how would one go about implementing a dynamic
> language with such a complex type system in D?
>
> I realize that this is a complex topic and that it might
> require better articulation than so far I have given.
>
> Nevertheless, thanks for all replies,
> Justin Johansson

I'm getting "nostalgia" from all the math terminology :)  Here 
are some of my thoughts:

You've taken one property, cardinality, and put that on one axis 
and then declared all other properties in your system should be 
orthogonal to cardinality.  But then you said that "string" was 
on the other axis, which itself is of type zeroOrMore(char), 
violating your own system.

You also need to take into account that cardinality is 
multi-dimensional. i.e. you could have zeroOrMore(char) or 
zeroOrMore(zeroOrMore(char)).

That being said, I don't think this model really get much closer 
to answering the original question, "what is a type?".

A while back I watched a cppcon talk from Dan Saks who defined 
what a data type was in C++:

https://www.youtube.com/watch?v=D7Sd8A6_fYU#t=58m59s

Note that the whole video also contains alot of good information. 
It explores the social aspects being a programmer and is 
definitely worth watching.

In his video he declares a data type as a "bundle of compile-time 
properties for an object", namely

1. size/alignment
2. set of values
3. set of permitted operations

This model is a very good breakdown of what a type is in C++.  
D's a bit more complex.  When you say "type" in D, there's alot 
more things you could be talking about so you either need to 
expand your definition of what a type is, or restrict the 
entities you consider to be types.  But these 3 properties are a 
good start :)

A bit off topic.  I find it frustrating that types always need to 
have these 3 properties.  Most of the time a programmer doesn't 
care about size/alignment, they just want the set of values and 
operations.  D can allow a programmer to do this using templates, 
but that "throws the baby out with the bath water".  You almost 
always require subset of properties.  Because template don't 
define any of the properties, you end up with cryptic template 
error messages.  D's tried to make the problem better by using 
conditional templates and C++ is trying to solve this with 
"Concepts". I've explored these ideas for a long time and am 
still currently developing my own methods for solving these 
problems. My latest idea is that you can create different "type 
interfaces".  At a minimum, I've defined a type to be a "pure 
function" that takes any value and maps it to a boolean 
indicating whether or not that value is a member of that type.  
That's the "minimum interface", but you could also have a type 
that declares other properties, such as, a set of "values", or 
size/alignment.  However, it's important to allow a developer to 
work with types that don't necessarily define all these 
properties for every time.  Anyway, I'm mostly just sharing some 
of my thoughts.  I have alot to say on this subject but I don't 
want to go too far off into the weeds.