The Artima Developer Community
Sponsored Link

Weblogs Forum
A Problem involving the Syntax of Concepts in Heron

27 replies on 2 pages. Most recent reply: Nov 27, 2005 8:56 AM by Roberto Moriyon

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 27 replies on 2 pages [ 1 2 | » ]
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

A Problem involving the Syntax of Concepts in Heron (View in Weblogs)
Posted: Nov 5, 2005 12:16 PM
Reply to this message Reply
Summary
A concept is a description of a type, including functions signatures, preconditions, postconditions, invariants, and member types. In C++ it is an abstract idea, but in the next Heron it will exist as a construct. There is one small problem with the syntax when writing function signatures which use concepts.
Advertisement
Here are some examples of Heron concepts from the next version of the Heron standard library, which I am currently working on:
  concept Stack {
    refines  {
      Container;
    }
    signature {
      is_empty() : bool;
      push(element x);
      pop() : element;
    }
  }

  concept Container {
    types {
      Value element;
    }
    signature {
      for_each(Functor f);
    }
  }
The above code is hopefully self explanatory for most Java/C++ programmers, though I would be happy to explain anything which isn't clear.

In Heron you will be able to write a function using concepts as parameters instead of actual types as follows:

  fubar(Stack x, Stack y) {... }
The problem occurs when you want the two parameter types to be equivalent. A concept can match any type, so two completely different types can be passed to fubar as long as they model a stack concept. So what syntax should I use to express that I want the two parameter types to match? Here are some ideas:
  fubar(Stack x, y) { ... } 

  fubar(Stack x, x::self y) { ... } 

  fubar[Stack T](T x, T y) { ... } 

  fubar(Stack x, type[x] y) { ... } 
Which of these do you prefer? Any other suggestions?


Sean Conner

Posts: 19
Nickname: spc476
Registered: Aug, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 5, 2005 3:30 PM
Reply to this message Reply
Why is that a problem at all? If I want to ensure that the type parameters are of the same type, why muck around with concepts and force the types to be the same? Isn't the point of a concept (which seems to follow Java's interfaces) that I don't care what the thing is, as long as it has the appropriate signatures?

But if you do want to go down this path, why not something like:


foobar(Stack x,Stack y)
where (typeof(x) == typeof(y))
&& (x != nil)
&& (y != nil)
{ ... }


(or however you declare preconditions).

Calvin Mathew Spealman

Posts: 13
Nickname: ironfroggy
Registered: Aug, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 5, 2005 6:43 PM
Reply to this message Reply
I agree with Sean. Why would you need to ensure they are both the same type, as long as they follow the same signatures of the Stack concept? Seems like this is both a case of premature optimization and of burning bridges.

Morel Xavier

Posts: 73
Nickname: masklinn
Registered: Sep, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 5, 2005 7:29 PM
Reply to this message Reply
I concur that this awfully look like interfaces even though you seem reluctant to give them that name.

And the declaration is, in my opinion, quite horrible and over-complicated.

As far as syntax is concerned, I don't quite see the point of asking for two objects of the same type, since the interface (or concept) defines a "common ground" for every object implementing the interface or materializing the concept.

In the very rare cases (that 99% of the population won't ever see) where that would be required, Sean's suggestion is more than good enough.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 5, 2005 11:44 PM
Reply to this message Reply
> Why is that a problem at all? If I want to ensure that
> the type parameters are of the same type, why muck around
> with concepts and force the types to be the same?

I can't figure out how to answer this question other than to say: sometimes it is often useful to say "give me two arguments of the same type, and that type should behave like a stack". It happens all over the place in the STL.

> But if you do want to go down this path, why not something
> like:
>
>

> foobar(Stack x,Stack y)
> where (typeof(x) == typeof(y))
> && (x != nil)
> && (y != nil)
> { ... }
>

>
> (or however you declare preconditions).

That is a good idea, thanks for contributing it.

Zeljko Vrba

Posts: 10
Nickname: zvrba
Registered: Aug, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 6, 2005 2:59 AM
Reply to this message Reply
>
> I can't figure out how to answer this question other than
> to say: sometimes it is often useful to say "give me two
> arguments of the same type, and that type should behave
> like a stack". It happens all over the place in the STL.
>
"sometimes it is often useful" is a contradiction in itself. it doesn't sound either plausible or that you have a real use case for this. it's sound like "wow, this could be a cool feature, let's add it".

maybe you are actually trying to express the notion of "two stacks holding the items of the same type"? because this is the form in which it appears in the STL. in the STL, a concept is always bound to concrete implementation instantiated over some type (e.g. -> sequence over vector<int>).

in your case, how would you express "stack containing items of type T"?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 6, 2005 10:12 AM
Reply to this message Reply
> "sometimes it is often useful" is a contradiction in
> itself.

Yes, badly speak I do. ;-)

> it doesn't sound either plausible or that you
> have a real use case for this. it's sound like "wow, this
> could be a cool feature, let's add it".

Consider in C++ you can have:


template<typename T>
bool lt(T x, T y) {
return x < y;
}


In Heron I want to express it as:


bool lt(Comparable x, typeof[x] y) {
return x < y;
}



> maybe you are actually trying to express the notion of
> "two stacks holding the items of the same type"? because
> this is the form in which it appears in the STL.

It also occurs frequently in the form of iterator pairs. For instance,


template<typename Iter_T>
std::accumulate(Iter_T x, Iter_T y) { ... }


> in the
> STL, a concept is always bound to concrete implementation
> instantiated over some type (e.g. -> sequence over
> vector<int>).

If you mean that that a concepts bound type is always a template instantiation, that isn't true.

> in your case, how would you express "stack containing
> items of type T"?

I would have to make a parameterized stack concept, which would be a refinment of the general stack concept.


concept Stack[type T] {
refines {
Stack;
}
extends {
define element = T;
}
}

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 6, 2005 10:23 AM
Reply to this message Reply
> I agree with Sean. Why would you need to ensure they are
> both the same type, as long as they follow the same
> signatures of the Stack concept? Seems like this is both a
> case of premature optimization and of burning bridges.

Let's say you have:


class stack[type T] {
// models Stack concept
}

swap_tops(Stack x, Stack y) {
x::element x_top = x.pop();
y::element y_top = y.pop();
// the following two lines may or may not work,
// depending on whether the two stacks hold compatible type
x.push(y_top);
y.push(x_top);
}

main() {
stack[int] ints;
stack[string] strings;
swap_tops(ints, strings);
}


The error of mismatched types can be easily detected when they are used (x.push(...)) however, I want to be able to make the function signature reflect the requirements on the types used.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 6, 2005 10:46 AM
Reply to this message Reply
> I concur that this awfully look like interfaces even
> though you seem reluctant to give them that name.

They are *very* close to interfaces. The difference is here:


MyConcept c;
MyInterface i;

fu(SomeConcept x) {
c = x; // only works if the actual type of c supports assignment from the actual type of x.
}

bar(SomeInterface y) {
i = y; // always works.
}


A concept is implemented using a type-substitution mechanism just like C++ templates, while an interface has runtime typing. The concept has a huge performance benefit, because the type is known at compile-time and runtime-type checking is not needed. However an interface is much more flexible (arguably too much so).

> And the declaration is, in my opinion, quite horrible and
> over-complicated.

I am very open to suggestions on that front. I would like an attractive syntax, as long as the core ideas can be easily expressed.

> As far as syntax is concerned, I don't quite see the point
> of asking for two objects of the same type, since the
> interface (or concept) defines a "common ground" for every
> object implementing the interface or materializing the
> concept.

The common ground defined by a concept is not sufficient. The concept only covers part of the type details.

> In the very rare cases (that 99% of the population won't
> ever see) where that would be required, Sean's suggestion
> is more than good enough.

I think 99% might be an exageration, but your general statement may be correct.

I do want to support both concepts and interfaces though I fear the subtle differences may just add too much confusion. If I start sacrificing performance in terms of flexibility, then I wonder, am I not going to end up reinventing something Python-esque? So far, the design decisions have been made to provide Heron with performance competitive with C++.

Reno C.

Posts: 10
Nickname: saxml
Registered: Oct, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 6, 2005 11:34 AM
Reply to this message Reply
> Which of these do you prefer?

None of these!

Something conventional:

fubar(Stack x, Stack y) {
static_assert<type_eq<x, y>>;
...
}

Another idea: make fubar a model of a Function concept that constrains its parameters to be of the same type. Good luck ;)

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 6, 2005 11:58 AM
Reply to this message Reply
> > Which of these do you prefer?
>
> None of these!
>
> Something conventional:
>

> fubar(Stack x, Stack y) {
> static_assert<type_eq<x, y>>;
> ...
> }
>


Not a bad idea. Can you think of any ways to express it in the function signature so that someone browsing function signatures can get an idea on the type constraints.
It is my belief that a function signature should completely express all of the type constraints on the parameters.

> Another idea: make fubar a model of a Function concept
> that constrains its parameters to be of the same type.

That is a very creative idea, I wonder how would I express it?

> Good luck ;)

Thanks!

Reno C.

Posts: 10
Nickname: saxml
Registered: Oct, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 6, 2005 1:12 PM
Reply to this message Reply
> Can you think of any ways to express it in the function signature

Not in an elegant way unless the introduction of a "function concept".

> I wonder how would I express it?

Let's have fun:

// blah models the Function concept
blah(int a) { ... }

// fubar models the my_function concept
my_function fubar(Stack x, Stack y) : bool {
...
}

concept my_function {
refines {
Function;
}
returns {
bool;
}
// well, hum...
parameter<T> {
T, T; // order is important!
}
}

concept Function {
// empty
}

Other parameter examples:


// blah(int a, bool b)
parameter {
int, bool;
}

// blah(int a, a_type b, an_other c)
parameter<T, U> {
int, U, T;
}

// blah()
parameter {

}

What if we need other assertions/constraints ?

parameter<T, U> {
int, U, T;
assert {
static_assert<...>;
meta_if<...>;
// etc.
}
}

What do you think ?

Tim LS

Posts: 37
Nickname: parchandri
Registered: Jul, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 7, 2005 1:39 AM
Reply to this message Reply
I think the problem is that you don't have enough preciseness in the concept definition. So I'm wondering what your concept for it looks like.

This?

concept Comparable {
signature {
compare(Comparable x) : bool;
}
}


Which have we promised to implement...

compare(MyType x) : bool;
or
compare(Comparable x) : bool;

...?

If the former, there is no real problem - when you try to compile, it just won't work, because it can't find matching function signature.
In the latter, you still have the problem.

Tim LS

Posts: 37
Nickname: parchandri
Registered: Jul, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 7, 2005 1:47 AM
Reply to this message Reply
An idea... how about there being a special type in concept definitions: 'MyType', or 'ThisType', or something like that, which evaluates to the class being concept-checked, so that our signature can be

compare(ThisType x) : bool;

in the case where we want the restriction to the same type, and

compare(Comparable x) : bool;

in the case where we want the restriction to be to only comparable objects?

I can see one possible gap remaining, which is forcing something like (Stack<int>, Stack<int>), but it might already work out in any real-world example...

Paul de Vrieze

Posts: 9
Nickname: pauldv
Registered: Oct, 2005

Re: A Problem involving the Syntax of Concepts in Heron Posted: Nov 7, 2005 4:26 AM
Reply to this message Reply
I don't like the assert kind of solutions. Why do things at runtime when they could be done at compile-time. While asserts could be hacked for runtime, they still should be better expressed for clients of the function.

What I would like to see would be something along the lines of:

fubar[T typeinstanceof Stack](T x, T y) { ... }

where typeinstanceof means that T is a concrete type that has been derived from the template/generic Stack. If x and y are not comparible to eachother (for example) then they cannot have the same instanced type based of stack.

Flat View: This topic has 27 replies on 2 pages [ 1  2 | » ]
Topic: XSLT: The Other Programming Language in your Browser Previous Topic   Next Topic Topic: Upgrading Jini lookup to include more explict control and flexibility


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us