www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Consider generalizing Bounded

reply Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
It may sound ridiculous but this is what came to me in a dream last night: why
exactly does 
Bounded have to express an interval? Forget intervals for a minute:

struct Bounded(alias Pred, T);

where Pred is a unary callable returning bool (same as in e.g. filter()).

This opens a host of possibilities:
1. sin(x) - make sure x is in e.g. (-PI/2 + 2*k*PI, +PI/2 + 2*k*PI)
2. constrain a matrix to be non-singular
3. a date variable only assignable to working days
4. don't let a missle fly off the level's bounding box in an FPP shooter
5. work exclusively with non-null references
6. ...

With all the power coming from the abstraction, it may still be worth exposing
Bounded(min, 
max, T), a wrapper over the general form to honor a common usecase. I expect
candidates 
for other wrappers to arise as bounds are laid.

Also, 'Confined' is a name that advertises the more general functionality
better and is free of 
the 2-knots-on-a-ribbon mental payload.

What you think: dream or nightmare?

-- 
Tomek
Oct 12 2010
next sibling parent reply Jason House <jason.james.house gmail.com> writes:
Tomek Sowiński Wrote:


 It may sound ridiculous but this is what came to me in a dream last night: why
exactly does 
 Bounded have to express an interval? Forget intervals for a minute:
 
 struct Bounded(alias Pred, T);
 
 where Pred is a unary callable returning bool (same as in e.g. filter()).


...

That reminds me of class invariants.
Oct 12 2010
parent Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Jason House napisał:


 Tomek Sowiński Wrote:
 

 It may sound ridiculous but this is what came to me in a dream last
 night: why exactly does Bounded have to express an interval? Forget
 intervals for a minute:
 
 struct Bounded(alias Pred, T);
 
 where Pred is a unary callable returning bool (same as in e.g. filter()).


 ...
 
 That reminds me of class invariants.


Yeah, only imposed from outside, not inside.

-- 
Tomek
Oct 12 2010
prev sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
2010/10/13 Tomek Sowi=C5=84ski <just ask.me>:

 It may sound ridiculous but this is what came to me in a dream last night=


: why exactly does

 Bounded have to express an interval? Forget intervals for a minute:

 struct Bounded(alias Pred, T);

 where Pred is a unary callable returning bool (same as in e.g. filter()).


We had a discussion 1-2 months ago on wrapping types to add
annotations. This came from Sorted!(predicate, range) which is another
example of your idea.
So I think the idea is interesting and could be generalized even
further: it's encoding external information like a contract or an
invariant in a type. Basically, creating a new, richer type from a
base type.

Ideally, we would have a generic wrapper Annotate!(Type,
someMoreInfo...), where someMoreInfo can be anything you need to
describe the new information: numbers, predicates, etc. But this comes
with a bunch of problems.

For Sorted, the (unsolved) problem was to be able to compare two
types, to see if they have 'the same' annotation.
Consider:

bool foo(int i) { return i>0;}

How can the compiler (or library writer) know whether or not
Sorted!(Range, foo) and Sorted!(Range, "a<0") are indeed the same ?

Going back to Annotate now, the difficulty is in standardizing
annotations and in combining them.
Annotate!(Annotate!(T[], hasPositiveElements), isSorted) should be the
same than
Annotate!(Annotate!(T[], isSorted), hasPositiveElements)

I found no elegant way to deal with it. One solution is to wrap each
annotation (say, in a type called Property), append them in a tuple
after the original type and sort them (maybe by name) to have an
annotation list that can be searched and compared at CT.
Like this:

Annotate!(T[], Property!(isSorted, "a<b"), Property!("a<0"))

I also remember having problems with the checking being done at
runtime, while the type is a CT entity only. Maybe I couldn't create
an enum validating or invalidating the properties, I don't rem

As jason said, this is a bit like contracts, but as you said, they are
exposed in the type. Which means they are accessible
throughcompile-time introsepction, can be changed also, extracted,
reused, etc.



 5. work exclusively with non-null references


Except, what about a non initialized object? Can you be certain that

NonNull!(someClass) c;

is not null?
Oct 13 2010
parent Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Philippe Sigaud napisał:


 2010/10/13 Tomek Sowiński <just ask.me>:

 It may sound ridiculous but this is what came to me in a dream last
 night: why exactly does Bounded have to express an interval? Forget
 intervals for a minute:

 struct Bounded(alias Pred, T);

 where Pred is a unary callable returning bool (same as in e.g. filter()).


 
 We had a discussion 1-2 months ago on wrapping types to add
 annotations. This came from Sorted!(predicate, range) which is another
 example of your idea.
 So I think the idea is interesting and could be generalized even
 further: it's encoding external information like a contract or an
 invariant in a type. Basically, creating a new, richer type from a
 base type.
 
 Ideally, we would have a generic wrapper Annotate!(Type,
 someMoreInfo...), where someMoreInfo can be anything you need to
 describe the new information: numbers, predicates, etc.


Numbers? Mind explaining?

This is interesting, nevertheless.


 But this comes
 with a bunch of problems.
 
 For Sorted, the (unsolved) problem was to be able to compare two
 types, to see if they have 'the same' annotation.
 Consider:
 
 bool foo(int i) { return i>0;}
 
 How can the compiler (or library writer) know whether or not
 Sorted!(Range, foo) and Sorted!(Range, "a<0") are indeed the same ?


It won't, and to me it's acceptable. Although time ago someone proposed
foo.body to 
retrieve ubyte[] with the binary code. So there's hope for slight improvement.

(typo? you meant "a>0"?)


 Going back to Annotate now, the difficulty is in standardizing
 annotations and in combining them.
 Annotate!(Annotate!(T[], hasPositiveElements), isSorted) should be the
 same than
 Annotate!(Annotate!(T[], isSorted), hasPositiveElements)

 I found no elegant way to deal with it. One solution is to wrap each
 annotation (say, in a type called Property), append them in a tuple
 after the original type and sort them (maybe by name) to have an
 annotation list that can be searched and compared at CT.
 Like this:
 
 Annotate!(T[], Property!(isSorted, "a<b"), Property!("a<0"))


It's tempting, but we may be trespassing on the language design territory here.
Better wait 
for user-defined annotations in D-to-be?


 I also remember having problems with the checking being done at
 runtime, while the type is a CT entity only. Maybe I couldn't create
 an enum validating or invalidating the properties, I don't rem


..ember. ;)


 As jason said, this is a bit like contracts, but as you said, they are
 exposed in the type.


BTW, his invariant metaphor gave me an idea to replace the bool predicate with
a void-
returning function to enable different actions on failure:

void check(T t) {
  assert(t.foo);
  enforce(t.foo);
  if (!t.foo) Log.warn("Bad foo");
  if (!t.foo) t.invalid = true;
  ...
}

Confined!(check, T) t;

Even if you stick only to asserts, it's an improvement.


 Which means they are accessible
 throughcompile-time introsepction, can be changed also, extracted,
 reused, etc.


Again, that's what user-defined annotations should be.

If we opt out of the predicate manipulation arms race, 'Confined' seems
tractible. 
Implement it, gain feedback from users, improve. Then, with that hindsight, try
to 
generalize further.


 5. work exclusively with non-null references


 
 Except, what about a non initialized object? Can you be certain that
 
 NonNull!(someClass) c;
 
 is not null?


Not sure if I understand... In D refs are initialized to null automatically so
the above 
wrapped class ref is null. I know "= void" leaves a trash pointer which "a !is
null" won't trip 
on. But void init means you want to play dirty so no surprize.

-- 
Tomek
Oct 13 2010