digitalmars.D - Type unions in D
- Justin Johansson (17/17) Sep 15 2009 What's the best way of emulating a system of quantified type unions in D...
- Justin Johansson (3/13) Sep 15 2009 JJ
- Jeremie Pelletier (2/31) Sep 15 2009 What you want sounds a lot like a variant type. Check std.variant in pho...
- Justin Johansson (5/9) Sep 15 2009 Thanks Jeremie. It certainly does .. but the reason I haven't seen it b...
- Fawzi Mohamed (3/26) Sep 16 2009 Tango has variant (tango.core.Variant), and is D1, if that could be an
- language_fan (3/13) Sep 17 2009 Do the various variant structures presented here support recursive type
- Daniel Keep (8/22) Sep 17 2009 Tango and Phobos2's Variants are very different beasts.
- Andrei Alexandrescu (18/38) Sep 17 2009 std.variant includes three parameterized types. One is the backend
- Justin Johansson (2/7) Sep 17 2009 Now that sounds absolutely wicked. :-) JJ
- Danny Wilson (5/10) Sep 17 2009 Including some sort of object literal syntax?
- Andrei Alexandrescu (5/20) Sep 17 2009 In Phobos' Algebraic, if you mention the type This inside the allowed
- language_fan (2/11) Sep 17 2009 Roger that. Thanks Andrei for the clear answer.
- bearophile (4/5) Sep 15 2009 Having nullable values may be useful, having nonnull class references ca...
- Justin Johansson (11/15) Sep 15 2009 Thanks for asking. Here's a use case. Suppose you have a container cla...
- Jeremie Pelletier (11/38) Sep 15 2009 You don't need a variant type for such a thing. A simple template will d...
- Justin Johansson (4/5) Sep 15 2009 Well you could return -1, 99 or any arbitrary integer for that matter; j...
- Jeremie Pelletier (16/26) Sep 15 2009 The line between invention and discovery is rather thin, I myself like t...
- Edward Diener (8/13) Sep 15 2009 Your return situation is what an 'optional' template is made for. The
- Ary Borenszweig (23/38) Sep 16 2009 So after invoking max on the list you would want to know whether it
- bearophile (7/10) Sep 17 2009 Cute.
- Justin Johansson (10/16) Sep 17 2009 Perhaps I'm not as eloquent as some writers are, so perhaps I could reca...
What's the best way of emulating a system of quantified type unions in D (D1)? By type unions (sometimes called algebraic sums in the literature), I don't mean the C/C++ "union" facility. Suppose there is some class X, I'd like to have a first class type for representing the following quantified types (using RegExp notation): X? zero or one instances of an X (call this type XQ) X a single instance of X X* zero or more instances of X (call this type XS) X+ at least one X (call this type XP) To unify the whole thing, now let X, XQ, XS and XP all be derived from a common base type T. Note that Scala has the Option, Some and None classes which kind of handles (but not exactly) the XQ case. Brendan Eich, JavaScript inventor, apparently has suggested type unions for that language. Some FP languages also have type systems that support type unions. http://wiki.ecmascript.org/doku.php?id=meetings:minutes_oct_13_2005 "Type Unions Brendan thinks we should have some ability for type unions in the language. var x : Number | Null It would be good to have something like this because otherwise developers end up enforcing their invariants on their own, with the potential for buggy code." As always, thanks for all replies. Justin Johansson
Sep 15 2009
Correction:Suppose there is some class X, I'd like to have a first class type for representing the following quantified types (using RegExp notation): X? zero or one instances of an X (call this type XQ) X a single instance of X X* zero or more instances of X (call this type XS) X+ at least one X (call this type XP)To unify the whole thing, now let X, XQ, XS and XP all be derived from a common base type T.Should be:X? zero or one instances of T (call this type XQ) X a single instance of T X* zero or more instances of T (call this type XS) X+ at least one T (call this type XP)JJ
Sep 15 2009
Justin Johansson Wrote:What's the best way of emulating a system of quantified type unions in D (D1)? By type unions (sometimes called algebraic sums in the literature), I don't mean the C/C++ "union" facility. Suppose there is some class X, I'd like to have a first class type for representing the following quantified types (using RegExp notation): X? zero or one instances of an X (call this type XQ) X a single instance of X X* zero or more instances of X (call this type XS) X+ at least one X (call this type XP) To unify the whole thing, now let X, XQ, XS and XP all be derived from a common base type T. Note that Scala has the Option, Some and None classes which kind of handles (but not exactly) the XQ case. Brendan Eich, JavaScript inventor, apparently has suggested type unions for that language. Some FP languages also have type systems that support type unions. http://wiki.ecmascript.org/doku.php?id=meetings:minutes_oct_13_2005 "Type Unions Brendan thinks we should have some ability for type unions in the language. var x : Number | Null It would be good to have something like this because otherwise developers end up enforcing their invariants on their own, with the potential for buggy code." As always, thanks for all replies. Justin JohanssonWhat you want sounds a lot like a variant type. Check std.variant in phobos, it has a template to let you define custom variants through type tuples.
Sep 15 2009
Jeremie Pelletier Wrote:Justin Johansson Wrote:What's the best way of emulating a system of quantified type unions in D (D1)?What you want sounds a lot like a variant type. Check std.variant in phobos, it has a template to let you define custom variants through type tuples.Thanks Jeremie. It certainly does .. but the reason I haven't seen it before is because I'm using D1. Sure enough though I poked the D2 Phobos code and there it was. Right at the top of the file is the link to Andrei's circa 2002 article in DDJ which makes for very interesting reading. http://erdani.org/publications/cuj-04-2002.html A colleague of mine is suggesting that I really do take a closer look at D2 now but I'm not sure that I'm ready to go standing on the bleading bleading (the blood doesn't clot) edge just right yet. :-( JJ
Sep 15 2009
On 2009-09-16 02:40:02 +0200, Justin Johansson <procode adam-dott-com.au> said:Jeremie Pelletier Wrote:Tango has variant (tango.core.Variant), and is D1, if that could be an option for you.Justin Johansson Wrote:What's the best way of emulating a system of quantified type unions in D (D1)?What you want sounds a lot like a variant type. Check std.variant in phobos, it has a template to let you define custom variants through type tuples.Thanks Jeremie. It certainly does .. but the reason I haven't seen it before is because I'm using D1. Sure enough though I poked the D2 Phobos code and there it was. Right at the top of the file is the link to Andrei's circa 2002 article in DDJ which makes for very interesting reading. http://erdani.org/publications/cuj-04-2002.html A colleague of mine is suggesting that I really do take a closer look at D2 now but I'm not sure that I'm ready to go standing on the bleading bleading (the blood doesn't clot) edge just right yet. :-( JJ
Sep 16 2009
Wed, 16 Sep 2009 12:41:06 +0200, Fawzi Mohamed thusly wrote:On 2009-09-16 02:40:02 +0200, Justin Johansson <procode adam-dott-com.au> said:Do the various variant structures presented here support recursive type definitions such as lists? Is this done efficiently?A colleague of mine is suggesting that I really do take a closer look at D2 now but I'm not sure that I'm ready to go standing on the bleading bleading (the blood doesn't clot) edge just right yet. :-( JJTango has variant (tango.core.Variant), and is D1, if that could be an option for you.
Sep 17 2009
language_fan wrote:Wed, 16 Sep 2009 12:41:06 +0200, Fawzi Mohamed thusly wrote:Tango and Phobos2's Variants are very different beasts. Phobos2's Variant is a discriminated union; you give it a set of types, and that's what it can store. The general-purpose one, I believe, can store any type so long as it's no larger than the biggest primitive types (it can't store big structs or static arrays, for example). Tango's Variant is a generic boxer.On 2009-09-16 02:40:02 +0200, Justin Johansson <procode adam-dott-com.au> said:A colleague of mine is suggesting that I really do take a closer look at D2 now but I'm not sure that I'm ready to go standing on the bleading bleading (the blood doesn't clot) edge just right yet. :-( JJTango has variant (tango.core.Variant), and is D1, if that could be an option for you.Do the various variant structures presented here support recursive type definitions such as lists? Is this done efficiently?Given the above, this question doesn't apply to Tango at all.
Sep 17 2009
Daniel Keep wrote:language_fan wrote:std.variant includes three parameterized types. One is the backend VariantN, which has the maximum size as a template argument, so it can accommodate any type size as long as the maximum is known in advance. The second is Algebraic, which is useful when you want to model a holder for any of a finite and known set of types. Essentially Algebraic aliases itself to VariantN with an appropriately computed maximum size. Finally, there is the generic Variant which can hold any type in an unbounded set. Until last dmd release, Variant had the limitation that types larger than a delegate could not be stored directly. I fixed that, so now for large types Variant uses dynamic allocation and pointers under the wraps. I have big plans with Variant - I want to make it (or a related type) the variable type common in dynamic languages, with flexibility, dynamic invocation using common syntax, the works. So if you write a short script and want dynamic typing, you should be able to use Variant throughout. AndreiWed, 16 Sep 2009 12:41:06 +0200, Fawzi Mohamed thusly wrote:Tango and Phobos2's Variants are very different beasts. Phobos2's Variant is a discriminated union; you give it a set of types, and that's what it can store. The general-purpose one, I believe, can store any type so long as it's no larger than the biggest primitive types (it can't store big structs or static arrays, for example).On 2009-09-16 02:40:02 +0200, Justin Johansson <procode adam-dott-com.au> said:A colleague of mine is suggesting that I really do take a closer look at D2 now but I'm not sure that I'm ready to go standing on the bleading bleading (the blood doesn't clot) edge just right yet. :-( JJTango has variant (tango.core.Variant), and is D1, if that could be an option for you.
Sep 17 2009
Andrei Alexandrescu Wrote:I have big plans with Variant - I want to make it (or a related type) the variable type common in dynamic languages, with flexibility, dynamic invocation using common syntax, the works. So if you write a short script and want dynamic typing, you should be able to use Variant throughout.Now that sounds absolutely wicked. :-) JJ
Sep 17 2009
Op Thu, 17 Sep 2009 16:56:41 +0200 schreef Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:I have big plans with Variant - I want to make it (or a related type) the variable type common in dynamic languages, with flexibility, dynamic invocation using common syntax, the works. So if you write a short script and want dynamic typing, you should be able to use Variant throughout.Including some sort of object literal syntax? You know, like javascript var obj = {i_am:"Dynamic", ...};
Sep 17 2009
language_fan wrote:Wed, 16 Sep 2009 12:41:06 +0200, Fawzi Mohamed thusly wrote:In Phobos' Algebraic, if you mention the type This inside the allowed types list, it will expand to the Algebraic's type. The support for complex constructs involving This is at the moment incomplete. AndreiOn 2009-09-16 02:40:02 +0200, Justin Johansson <procode adam-dott-com.au> said:Do the various variant structures presented here support recursive type definitions such as lists? Is this done efficiently?A colleague of mine is suggesting that I really do take a closer look at D2 now but I'm not sure that I'm ready to go standing on the bleading bleading (the blood doesn't clot) edge just right yet. :-( JJTango has variant (tango.core.Variant), and is D1, if that could be an option for you.
Sep 17 2009
Thu, 17 Sep 2009 09:46:01 -0500, Andrei Alexandrescu wrote:language_fan wrote:Roger that. Thanks Andrei for the clear answer.Do the various variant structures presented here support recursive type definitions such as lists? Is this done efficiently?In Phobos' Algebraic, if you mention the type This inside the allowed types list, it will expand to the Algebraic's type. The support for complex constructs involving This is at the moment incomplete. Andrei
Sep 17 2009
Justin Johansson:What's the best way of emulating a system of quantified type unions in D (D1)?Having nullable values may be useful, having nonnull class references can probably be very useful, having tagged unions (I am talking as C unions here) can be useful. But can you show me some usercases/purposes for what you are asking for? I think other people too here are curious. Bye, bearophile
Sep 15 2009
bearophile Wrote:Justin Johansson:Thanks for asking. Here's a use case. Suppose you have a container class which represents a list of numbers. Let's call this class ListOfNums. Now a ListOfNums can contain zero or more numbers. Now you want a function called max that takes a ListOfNums, xs, as an argument and returns the number in the list, xs, that is greater than or equal to all other numbers in xs. So if xs contains (3, 9, 9, 2), max( xs) returns 9. Now it makes sense that xs should contain at least one number, so if xs contains just (3), max( xs) returns 3. But what if xs contains no numbers i.e. xs = (), the empty list? What should max( xs) return in the way of a meaningful result short of throwing an exception? Put another way, what is the maximum number in an empty list of numbers? If you allow the numbers in the list to be real, then I suppose you could return NaN but there is no way of expressing NaN if the numbers you are dealing with are purely integer .. and it certainly is not a good idea to make a function that is dealing purely with integers to return a real just allow the corner case to return NaN (a real). An elegant solution to this problem is to specify the max function as taking a quantified list of zero or more numbers and returning another quantified list of numbers which may contain either zero numbers or just one number: zero numbers if the argument list is empty and a single number (being the maximum number in the argument list) if the argument number list is non-empty. The important point in this solution is realizing a type system that treats a list of zero_or_one numbers, a list of zero numbers, a list of zero_or_more numbers, etc, as distinct types. Trust this makes sense. <JJ/>What's the best way of emulating a system of quantified type unions in D (D1)?Having nullable values may be useful, having nonnull class references can probably be very useful, having tagged unions (I am talking as C unions here) can be useful. But can you show me some usercases/purposes for what you are asking for? I think other people too here are curious.
Sep 15 2009
Justin Johansson Wrote:bearophile Wrote:You don't need a variant type for such a thing. A simple template will do the job. As for the max of an empty set, you can just return zero. class ListOfNums(T) if(isNumeric!T) { T max() const { T max = 0; foreach(n; _nums) if(n > max) max = n; return max; } T[] _nums; } It's been too long since I last used D1 so the above may use D2 only features.Justin Johansson:Thanks for asking. Here's a use case. Suppose you have a container class which represents a list of numbers. Let's call this class ListOfNums. Now a ListOfNums can contain zero or more numbers. Now you want a function called max that takes a ListOfNums, xs, as an argument and returns the number in the list, xs, that is greater than or equal to all other numbers in xs. So if xs contains (3, 9, 9, 2), max( xs) returns 9. Now it makes sense that xs should contain at least one number, so if xs contains just (3), max( xs) returns 3. But what if xs contains no numbers i.e. xs = (), the empty list? What should max( xs) return in the way of a meaningful result short of throwing an exception? Put another way, what is the maximum number in an empty list of numbers? If you allow the numbers in the list to be real, then I suppose you could return NaN but there is no way of expressing NaN if the numbers you are dealing with are purely integer .. and it certainly is not a good idea to make a function that is dealing purely with integers to return a real just allow the corner case to return NaN (a real). An elegant solution to this problem is to specify the max function as taking a quantified list of zero or more numbers and returning another quantified list of numbers which may contain either zero numbers or just one number: zero numbers if the argument list is empty and a single number (being the maximum number in the argument list) if the argument number list is non-empty. The important point in this solution is realizing a type system that treats a list of zero_or_one numbers, a list of zero numbers, a list of zero_or_more numbers, etc, as distinct types. Trust this makes sense. <JJ/>What's the best way of emulating a system of quantified type unions in D (D1)?Having nullable values may be useful, having nonnull class references can probably be very useful, having tagged unions (I am talking as C unions here) can be useful. But can you show me some usercases/purposes for what you are asking for? I think other people too here are curious.
Sep 15 2009
Jeremie Pelletier Wrote:As for the max of an empty set, you can just return zero.Well you could return -1, 99 or any arbitrary integer for that matter; just that it doesn't make sense to do that from a pure maths perspective. Mathematicians have spent centuries trying to make number systems consistent. The invention (or discovery**) of "i", the square-root of minus-one, was a major major break-through. In similar vein, it's nice if the type systems we use for programming follow from a consistent set of axioms. ;-) (**Is mathematics invention or discovery?) <JJ/>
Sep 15 2009
Justin Johansson Wrote:Jeremie Pelletier Wrote:The line between invention and discovery is rather thin, I myself like to think of both as two sides of a same coin. For inventions you need to first discover how to do it, and for discoveries you need to invent the system to describe it. Basically anything that draws a line between how we perceive something and how we communicate it can be thought of in terms of semantics and syntax respectively. You discover the semantics and then invent the syntax to describe it, so other people can study your syntax and hopefully get a grasp of the semantics you originally had in mind. As for your code, you could always use more template parameters to control the behavior of your list type: class ListOfNums(T, T DefaultValue = T.init, bool ThrowOnEmpty = false) if(isNumeric!T) { T max() const { static if(ThrowOnEmpty) if(!nums.length) throw new EmptyListOfNumsException(); T max = Defaultvalue; foreach(n; _nums) if(n > max) max = n; return max; } T[] _nums; }As for the max of an empty set, you can just return zero.Well you could return -1, 99 or any arbitrary integer for that matter; just that it doesn't make sense to do that from a pure maths perspective. Mathematicians have spent centuries trying to make number systems consistent. The invention (or discovery**) of "i", the square-root of minus-one, was a major major break-through. In similar vein, it's nice if the type systems we use for programming follow from a consistent set of axioms. ;-) (**Is mathematics invention or discovery?) <JJ/>
Sep 15 2009
Justin Johansson wrote:Jeremie Pelletier Wrote:Your return situation is what an 'optional' template is made for. The entire idea about 'optional' is that you should be able to always return a value for a type which is not a valid value for that type. Some other languages use a built-in value, like 'None' in Python, to solve the problem. C++ and D can use an 'optional' template to solve this problem. See optional<T> in Boost for the C++ answer. I believe Andrei is working on a similar solution for D.As for the max of an empty set, you can just return zero.Well you could return -1, 99 or any arbitrary integer for that matter; just that it doesn't make sense to do that from a pure maths perspective. Mathematicians have spent centuries trying to make number systems consistent. The invention (or discovery**) of "i", the square-root of minus-one, was a major major break-through. In similar vein, it's nice if the type systems we use for programming follow from a consistent set of axioms. ;-)
Sep 15 2009
Justin Johansson escribió:bearophile Wrote:So after invoking max on the list you would want to know whether it contains a single element or it's the empty list, right? If so, why not asking it before invoking the max function? if (xs.isEmpty) { // no max, do something } else { auto max = max(xs); // do something *else* } I've seen this code a lot of times, and it being: auto max = max(xs); if (max.isEmpty) { // no max, do something } else { // do something *else* } is exactly the same thing, unless you are planning to do something with the list that contains max. At least one of the first things I learned when studying computer science if function pre and postconditions, and max's is "list is not empty". :) What's wrong with that?Justin Johansson:Thanks for asking. Here's a use case. Suppose you have a container class which represents a list of numbers. Let's call this class ListOfNums. Now a ListOfNums can contain zero or more numbers. Now you want a function called max that takes a ListOfNums, xs, as an argument and returns the number in the list, xs, that is greater than or equal to all other numbers in xs. So if xs contains (3, 9, 9, 2), max( xs) returns 9. Now it makes sense that xs should contain at least one number, so if xs contains just (3), max( xs) returns 3. But what if xs contains no numbers i.e. xs = (), the empty list? What should max( xs) return in the way of a meaningful result short of throwing an exception? Put another way, what is the maximum number in an empty list of numbers?What's the best way of emulating a system of quantified type unions in D (D1)?Having nullable values may be useful, having nonnull class references can probably be very useful, having tagged unions (I am talking as C unions here) can be useful. But can you show me some usercases/purposes for what you are asking for? I think other people too here are curious.
Sep 16 2009
Justin Johansson:But what if xs contains no numbers i.e. xs = (), the empty list? What should max( xs) return in the way of a meaningful result short of throwing an exception?<In both Python and my dlibs it throws an exception.An elegant solution to this problem is to specify the max function as taking a quantified list of zero or more numbers and returning another quantified list of numbers which may contain either zero numbers or just one number: zero numbers if the argument list is empty and a single number (being the maximum number in the argument list) if the argument number list is non-empty.<Cute.The important point in this solution is realizing a type system that treats a list of zero_or_one numbers, a list of zero numbers, a list of zero_or_more numbers, etc, as distinct types.<I don't understand the correlation from this last part and what you have written about max(). Maybe what can be useful is to define as a type a "not empty iterable", so if max() takes as input such type it's sure to not throw an exception. In general iterables can be lazy, their items can be computed on the fly, so there's no way to know at compile time if an iterable will be empty or not. Bye, bearophile
Sep 17 2009
bearophile Wrote:Justin Johansson:Perhaps I'm not as eloquent as some writers are, so perhaps I could recast the scene as follows: What is a type system? (Rhetorical question) When speaking of types most programmers think, well, is an int or a double, is it a thing (aka object) that one could apply some taxonomy to? Classical CS101: You have a car and a bike. Now come up with the typical OO class structure that has Vehicle as a base class of Car and of Bike. Mostly when thinking about types we think about the qualitative attributes of what we are trying to model .. and we make distinction of types based upon those qualities (and class hierarchies accordingly -- well up to the point that single inheritance breaks down but that's a side issue). OTH quantitative typing (layperson speak .. I'm not a published academic) considers the quantity of things to be separate types. For example, in some problem spaces, typically pattern matching, it may be useful to consider a dozen eggs (12 off) as being a different type to baker's dozen of eggs (13 off). Taking this further, one might well consider how to unify a type system based upon both qualities and quantities. Anyway, regarding my max() example, this was just a single case taken illustrating a problem in the quantitative typing domain. Noting that a number of repondents on this thread suggested various work arounds/solutions for this particular example, me thinks the bigger picture for my particular problem was missed. I've got a good collection of links regarding type systems which I can post if people are interested further in the subject. To be honest though, some of the literature looks like you have to be Einstein to understand it. Google for "type union", "existential types", "quantified types" and similar and you'll find yourself buried up to your neck in literature in no time. Cheers Justin JohanssonThe important point in this solution is realizing a type system that treats a list of zero_or_one numbers, a list of zero numbers, a list of zero_or_more numbers, etc, as distinct types.<I don't understand the correlation from this last part and what you have written about max(). Maybe what can be useful is to define as a type a "not empty iterable", so if max() takes as input such type it's sure to not throw an exception. In general iterables can be lazy, their items can be computed on the fly, so there's no way to know at compile time if an iterable will be empty or not.
Sep 17 2009