Weblogs Forum - Designing the Heron Standard Library

Articles |
News |
Weblogs |
Books |
Forums

Artima Forums | Articles | Weblogs | Java Answers | News

Sponsored Link •

Weblogs Forum
Designing the Heron Standard Library

13 replies on 1 page. Most recent reply: Aug 5, 2005 11:01 PM by Christopher Diggins

Welcome Guest
Sign In

Back to Topic List

Reply to this Topic

Search Forum

Threaded View


Previous Topic		Next Topic

Flat View: This topic has 13 replies on 1 page

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Designing the Heron Standard Library (View in Weblogs)

Posted: Aug 3, 2005 7:23 AM

Summary
I am in the middle of implementing the Heron standard library, and I have found two techniques for implementing container concepts. One is more object-oriented and the other is more generic. Which should I use?

Below is an example concept from the Heron standard library. In order to understand the code you should take note that: a) the question mark represents an assertion statement, b) define is for defining a type-alias, which may be overridden

    concept Stack[T : type] {
      contract {
        is_empty() : bool;
        top() : value_type {
          before {
            ?(!is_empty());
          }
        }
        pop() {
          before {
            ?(!is_empty());
          }
        }
        push(value_type x) {
          after {
            ?(!is_empty());
          }
        }
      }
      types {
        define value_type : T;
      }
    }

The above code is pretty straightforward, but it behaves more like an interface than a concept. The following concept is more sophisticated as it doesn't require a template parameter.

    concept Stack {
      contract {
        is_empty() : bool;
        top() : value_type {
          before {
            ?(!is_empty());
          }
        }
        pop() {
          before {
            ?(!is_empty());
          }
        }
        push(value_type x) {
          after {
            ?(!is_empty());
          }
        }
      }
      requires {
        value_type : Any;
      }
    }

The second version of the Stack concept requires that a class which models (implements) the concept provides its own definition of value_type. Any is an unbounded constraint on the set of types accepted (it also could have been a concept).

My plan is to support both techniques in Heron, but I have to choose one for the standard library. I am leaning towards implementing the library using the first technique, at least for now.

Tanton Gibbs

Posts: 20
Nickname: tanton
Registered: Aug, 2005

Re: Designing the Heron Standard Library

Posted: Aug 3, 2005 8:32 AM

I would imagine that you would want the concept to be template-less. In other words the second that you show, because it is more of an interface to me. Basically, anything that has a value_type and certain functions is a "stack". To me, a template should be an implementation mechanism, not a specification mechanism; so, you might have implementations that use templates, but your specification would be template-free.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Designing the Heron Standard Library

Posted: Aug 3, 2005 9:17 AM

> I would imagine that you would want the concept to be
> template-less. In other words the second that you show,
> because it is more of an interface to me. Basically,
> anything that has a value_type and certain functions is a
> "stack". To me, a template should be an implementation
> mechanism, not a specification mechanism; so, you might
> have implementations that use templates, but your
> specification would be template-free.

Is there any specific reason that you feel that specifications shouldn't be parameterized? Do you feel that it shouldn't be allowed in the language at all, or that it just would be a better design for programmers to avoid parameterizing concepts?

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Designing the Heron Standard Library

Posted: Aug 3, 2005 1:29 PM

> Is there any specific reason that you feel that
> specifications shouldn't be parameterized? Do you feel
> that it shouldn't be allowed in the language at all, or
> that it just would be a better design for programmers to
> avoid parameterizing concepts?

This is basically discussed in chapter 8 of Advanced Topics in Types and Programming Languages (http://www.cis.upenn.edu/~bcpierce/attapl/index.html) in conjunction with the design of ML-style module systems. The case made in the book is that parameterized signatures (concepts) do not scale.

Michel Parisien

Posts: 25
Nickname: kriggs
Registered: Jul, 2005

Re: Designing the Heron Standard Library

Posted: Aug 3, 2005 9:53 PM

Tough call...

Know that whatever you decide will influence the way programmers choose to use your language. Everything up to the very way you titlecase or abbreviate will have a great impact on the coders of your language.

Looking at your examples, neither solution really makes me feel all warm inside. It is a choice of the lesser evil. This is one of those fundamental situations that they always bring up when trying to test the strength of a language: how do you handle pseudo-typelessness in a typed language.

Ok, so I gave it a bit of thought, and I decided on the first one being better. I'll be frank though, I have something against templates. They just rub me the wrong way.

I'll tell you why I went with #1 though. Solution 2 requires you to either a) always have a variable that is automatically included in all objects but rarely used or b) have people specify it manually, which they only do for an indirect purpose: using it with some concept. Templates, on the other hand, are direct. You type the template, and right away you specify the type. Bing bang boom.

If you'd like, I have my own ideas for this kind of problem, as I've tackled on it myself with Codre, but I'll keep it for some coffee shop/bar meeting.

See you there!

Tanton Gibbs

Posts: 20
Nickname: tanton
Registered: Aug, 2005

Re: Designing the Heron Standard Library

Posted: Aug 4, 2005 8:22 PM

I guess I'm not sure what benefit you receive from the specification - I have to admit that I'm not that familiar with Heron. I started monitoring Heron when I found out about the concept idea. I had a similar idea a while back and wanted to replace the C++ Template Model with a concept approach in a language I called ConceptC. When I saw Heron following a similar idea, I was intrigued. I guess that somewhat explains my confusion. I was intending concepts to be a strongly enforced method of "duck typing". Therefore, I would like to eradicate templates as much as possible and use concepts instead.

Furthermore, it seems to me that in the template concept, you have to specify the type when you instantiate the concept (e.g., at a function call site); whereas in the non-template concept you only have to specify the type once, in the class modeling the concept. Correct me, if that is not the case.

The second approach seems safer to me, if a class intends to model a concept, then it should provide the right typedefs and the user never has to do so (and therefore can't get it wrong). It is easy enough to establish a convention of using value_type, etc..., C++ already relies on such conventions in the boost meta-programming facilities.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Designing the Heron Standard Library

Posted: Aug 5, 2005 4:59 AM

If you are really interested in "concepts", I would strongly recommend reading about module systems (signatures, structures and functors) as found in Standard ML and Ocaml. They offer an informed and semantically solid contrast to the C++ idioms (to put it nicely). Most comprehensive, but still introductory, books on those languages also introduce the module systems, but many tutorials you can find on the net stop before getting to the module system.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Designing the Heron Standard Library

Posted: Aug 5, 2005 7:12 AM

> If you are really interested in "concepts", I would
> strongly recommend reading about module systems
> (signatures, structures and functors) as found in Standard
> ML and Ocaml.

It looks like an Ocaml signature is very close to a Heron concept. I found a decent online book at: http://files.metaprl.org/doc/ocaml-book.pdf which talks a bit about the Ocaml module system.

Anything more you can share about them would be appreciated, for instance what are the salient features of Ocaml signatures. I don't understand the Ocaml relationship between a class and a module, so my big question is are signatures applicable to classes. Furthermore do OCaml signatures support multiple inheritance, non-abstract functions, and parameterization.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Designing the Heron Standard Library

Posted: Aug 5, 2005 3:37 PM

> what are the salient features of Ocaml signature

Well, the thing about ML-style signatures is that they provide a simple and (in a sense) complete way to specify abstractions. What I mean by simple should be inferable after a brief examination of signatures; a signature is just a specification of types and values (and submodules, but I'll ignore them in the following). As to what I mean by complete, unlike abstract classes or interfaces in typical OO languages, an abstraction described by an ML-style signature can be multi-sorted.

I would recommend reading chapter 8 of ATTAPL. It is an informal treatment of the subject and fairly accessible.

> relationship between a class and a module

In order to understant ML-style modules, I think that it would probably be better to forget about classes (and objects) and consider the relationship between ML-modules and things like Ada packages, C++ namespaces, Java packages, separate compilation, C/C++ header and implementation files.

> do OCaml signatures support multiple inheritance,

ML-signature matching is structural rather than nominal. There is no need to "inherit" a signature from another signature in order to match it. However, include provides a (bit simplistic) way to factor out common parts of signatures.

> non-abstract functions, and

Signatures contain specifications of types and values rather than (actual) types or values.

> parameterization.

As discussed in chapter 8 of ATTAPL, ML-style signatures support fibration. In practise, this means that you can "generate" new signatures from existing signatures by adding constraints (using with in Ocaml).

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Designing the Heron Standard Library

Posted: Aug 5, 2005 4:32 PM

> Furthermore, it seems to me that in the template concept,
> you have to specify the type when you instantiate the
> concept (e.g., at a function call site);

Yes.

> whereas in the
> non-template concept you only have to specify the type
> once, in the class modeling the concept. Correct me, if
> that is not the case.

Yes.

> The second approach seems safer to me, if a class intends
> to model a concept, then it should provide the right
> typedefs and the user never has to do so (and therefore
> can't get it wrong).

Well it depends on who the user is and what they are doing. The thing about the parameterized version is that it is simpler to use in some cases, because the user doesn't have to declare their variables as so:


  void FuBar(Stack x) {
    Stack::value_type local = x.top();
  }

compared to:


  void FuBar(Stack[int] x) {
    int local = x.top(); 
  }

Tanton Gibbs

Posts: 20
Nickname: tanton
Registered: Aug, 2005

Re: Designing the Heron Standard Library

Posted: Aug 5, 2005 10:12 PM

<pre>
void FuBar(Stack x) {
Stack::value_type local = x.top();
}

compared to:
void FuBar(Stack[int] x) {
int local = x.top();
}
</pre>

Well, the first version seems to be more flexible, as it would work for any type, not just ints. However, if the user wanted to forgo flexibility, would the following not work?

<pre>
void FuBar(Stack x) {
int local = x.top();
}
</pre>
Since the user "knows" that the Stack only contains int then Stack::value_type should always be int, and if it is not, you would get a compile time error telling you so.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Designing the Heron Standard Library

Posted: Aug 5, 2005 10:31 PM

> Well, the first version seems to be more flexible, as it
> would work for any type, not just ints. However, if the
> user wanted to forgo flexibility, would the following not
> work?
>
> <pre>
> void FuBar(Stack x) {
> int local = x.top();
> }
> </pre>
> Since the user "knows" that the Stack only contains int
> then Stack::value_type should always be int, and if it is
> not, you would get a compile time error telling you so.

Yes it definitely works. The problem is that there is no compiler enforcement that the caller of FuBar passes a stack of ints. If a function only accepts a Stack of ints, then that should be ideally specified in the function signature (in a statically typed language).

Tanton Gibbs

Posts: 20
Nickname: tanton
Registered: Aug, 2005

Re: Designing the Heron Standard Library

Posted: Aug 5, 2005 10:55 PM


void FuBar(Stack x) {
 int local = x.top();
}

>The problem is that there is no compiler enforcement that
>the caller of FuBar passes a stack of ints

Really? If the client passes in a stack of floats, then won't the int local = x.top() not compile because of a type error casting from float to int? Or perhaps that conversion is done automatically?

>If a function only accepts a Stack of ints, then that
>should be ideally specified in the function signature (in
>a statically typed language)

Yes, I'll definitely agree with this. I'm not sure of how this can be fixed without resorting to parameterized types.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Designing the Heron Standard Library

Posted: Aug 5, 2005 11:01 PM


> void FuBar(Stack x) {
>  int local = x.top();
> }
>

>
> >The problem is that there is no compiler enforcement
> that
> >the caller of FuBar passes a stack of ints
>
> Really? If the client passes in a stack of floats, then
> won't the int local = x.top() not compile because of a
> type error casting from float to int? Or perhaps that
> conversion is done automatically?

In Heron a float to int cast is not automatic so yes you are correct, but the compiler error occurs inside of the function implementation rather than at the callsite. This is arguably simply my point of view, but I consider it an important programming practice.

Flat View: This topic has 13 replies on 1 page

Previous Topic

Next Topic