The Artima Developer Community
Sponsored Link

Weblogs Forum
Metaprogramming on Steroids: Overloaded Type Operators

15 replies on 2 pages. Most recent reply: Sep 29, 2005 2:25 AM by Howard Lovatt

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 15 replies on 2 pages [ 1 2 | » ]
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Metaprogramming on Steroids: Overloaded Type Operators (View in Weblogs)
Posted: Sep 24, 2005 12:25 PM
Reply to this message Reply
Summary
Every once in a while I come up with a good idea for Heron, and then inevitably Vesa Karvonen tells me that it existed in ML since the dawn of time. Maybe this time will be different?
Advertisement
Writing type operators is as natural as breathing for physicists and engineers.
newton = kilogram * (meters / seconds**2);
So it seems to me to be perfectly reasonable to allow programmers to overload operators for types as well.

Another application is when emulating Backus-Naur Form (BNF) as I do in the YARD library. YARD is a C++ metaprogramming parsing engine I use in both HeronFront and HeronScript. YARD constructs a R-D parser at compile time by using metaprogramming techniques. In YARD emulation of a BNF grammar such as :

A ::== B* C
B ::== C | D
would look like:
struct A : 
  bnf_and<
    bnf_star<B>,
    C
  >
{ };

struct B :
  bnf_or<
    C,
    D
  >
{ };
As you can see this is not very pretty but in C++ it is probably as good as I can do, while still constructing the parser at compile-time. In Heron if I enable operator overloading for types, then I could emulate the BNF grammar as below:
alias A : *B & C; 
alias B : C | D;
which is quite a bit more natural.

This is actually only scratching the surface of possibilities of operator overloading on types. Eventually constant values like 42, 'q', "hello", 3.14 will all be valid types along with code blocks { ... }. I'll leave it to you to dream up the possibilities that this implies for now (hint: this makes macros obsolete).


Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 25, 2005 1:47 AM
Reply to this message Reply
> inevitably Vesa Karvonen tells me that it existed in ML since the dawn of time

Let's see, I wouldn't like to disappoint. ;-)

> Writing type operators is as natural as breathing for physicists and
> engineers.
>
> newton = kilogram * (meters / seconds**2);
>
> So it seems to me to be perfectly reasonable to allow programmers to
> overload operators for types as well.

Sorry, the above description is not clear enough for me to understand exactly what you are after here. (A formal semantics would be nice.)

However, ML doesn't support (user-defined) overloading of any kind and it only provides fairly simple type abbreviations. You might want to look at Haskell.

On the other hand...

> I could emulate the BNF grammar as below:
>
> alias A : *B & C;
> alias B : C | D;
>
> which is quite a bit more natural.

Are you familiar with parsing combinators? Try http://www.google.com/search?q=parsing+combinators .

To slightly exaggerate, but not much, implementing something roughly equivalent to the Spirit C++ Parser Framework is nowadays an undergraduate programming exercise in FP. (I'm exaggerating, because FP is not always taught to undergraduates.)

> this makes macros obsolete

Well, your description is not complete enough to know for sure, but one of the things that you can do with macros, but not with combinators, is to implement new binding forms. Without macros you are likely to be limited to only use the existing binding forms (like lambda, let, and define in Scheme). Another technique that can be done with macros (or builtin staging annotations) is to perform (guaranteed) compile-time computations.

...

Unfortunately, I'm too busy today to write a longer reply, because I'm going to ICFP (http://www.cs.ioc.ee/tfp-icfp-gpce05/) and I have a lot to do before the ship leaves in the evening.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 25, 2005 7:35 AM
Reply to this message Reply
> > Writing type operators is as natural as breathing for
> physicists and
> > engineers.
> >
> > newton = kilogram * (meters / seconds**2);
> >
> Sorry, the above description is not clear enough for me to
> understand exactly what you are after here. (A formal
> semantics would be nice.)

I don't have know formal semantics. But here is what I am after in C++ using the MPL concepts:

struct kilogram;
struct meters;
struct seconds;
 
typedef star<kilogram, slash<meters, square<seconds>::apply>::apply>::apply newton;
Notice that star, slash and square are metafunctions.

> However, ML doesn't support (user-defined)
> overloading of any kind and it only provides fairly
> simple type abbreviations. You might want to look at
> Haskell.

Okay thanks.

> > I could emulate the BNF grammar as below:
> >
> > alias A : *B & C;
> > alias B : C | D;
> >
> > which is quite a bit more natural.
>
> Are you familiar with parsing combinators? Try
> http://www.google.com/search?q=parsing+combinators .

I wasn't, thanks for pointing that out.

> Well, your description is not complete enough to know for
> sure, but one of the things that you can do with macros,
> but not with combinators, is to implement new binding
> forms. Without macros you are likely to be limited to only
> use the existing binding forms (like lambda,
> let, and define in Scheme).
> Another technique that can be done with macros (or builtin
> staging annotations) is to perform (guaranteed)
> compile-time computations.

I plan on allowing guaranteed compile-time computations in Heron through the type-system manipulation, like the Boost MPL.

> Unfortunately, I'm too busy today to write a longer reply,
> because I'm going to ICFP
> (http://www.cs.ioc.ee/tfp-icfp-gpce05/) and I have a lot
> to do before the ship leaves in the evening.

Have fun!

indranil banerjee

Posts: 38
Nickname: indranil
Registered: Nov, 2004

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 25, 2005 1:12 PM
Reply to this message Reply
You might be very intereseted in the example Dimensional Analysis functions in Abrahams & Gurtovoy's C++ Template Metaprogramming book


http://boost-consulting.com/mplbook/metafunctions.html

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 25, 2005 9:55 PM
Reply to this message Reply
The language Mathematica does what you want, but it works differently, its method might give you some ideas.

1. It lays math out fully typeset or in a computer like form, I will stick to the computer form to keep the post readable!

2. Space is overloaded to mean * which in turn is overloaded to mean Times

3. Therefore when you write 1 kg it means Times[1,kg] (Mathematica uses square brackets for functions) where 1 is a number and kg is a constant from the set of constants in the package units and Times is an overloaded function that accepts a number and a unit

4. When you write force = 1 kg 2 m/(s^2) it means force = Times[Times[1,kg],Times[2,Divide[m,Power[s,2]]]] and the result is Times[2,N] or 2 N in infix form, i.e. the result is a function that it cannot reduce further

The trick here is that Mathematica has a reducer that tries to algebraically simplify expressions, I think that something a bit more advanced than simply evaluating the expression is needed. The problem is that when you evaluate the above example you get Times[2,Times[m,Times[kg,Power[s,-2]]]] or something equivalent like Times[2,Times[m,Divide[kg,Power[s,2]]]] (note change in sign of Power) and the simplifier needs to recognize a whole host of equivalent expressions and convert them to N. This is not trivial! For example consider Times[2,Times[Power[m,2],Divide[kg,Power[s,2]]]] which sould give Times[N,m] or N m (torque) in infix form.

The Mathematica system is an interesting way of handelling the problem, hope it gives you some ideas.

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 26, 2005 7:02 AM
Reply to this message Reply
> I don't have know formal semantics. But here is what I am
> after in C++ using the MPL concepts:
>
>
> struct kilogram;
> struct meters;
> struct seconds;
> 
> typedef star<kilogram, slash<meters,
> square<seconds>::apply>::apply>::apply newton;
> 
Notice that star, slash
> and square are metafunctions.

Ok... so, just to see if I understand what you mean: you want something like functions (like overloaded operators) that can operate on types (rather than values)? I.e. that types are given first-class status as values in their own right.

I still have a problem seeing how this would work. I see your example above, and the BNF example, but could you show a more complete example of (example syntax) of how the overloaded operators might be declared, implemented, and used? As it is now, it's hard to tell what kind of type computations (if any) are performed.

Regards,

Terje

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 26, 2005 9:36 AM
Reply to this message Reply
> > I don't have know formal semantics. But here is what I
> am
> > after in C++ using the MPL concepts:
> >
> >
> > struct kilogram;
> > struct meters;
> > struct seconds;
> > 
> > typedef star<kilogram, slash<meters,
> > square<seconds>::apply>::apply>::apply newton;
> > 
Notice that star,
> slash
> > and square are metafunctions.
>
> Ok... so, just to see if I understand what you mean: you
> want something like functions (like overloaded operators)
> that can operate on types (rather than values)? I.e. that
> types are given first-class status as values in their own
> right.

More or less. I want to be able to map operators to meta-functions. A meta-function is a type transformations from one type to another, ala Boost MPL.

> I still have a problem seeing how this would work. I see
> your example above, and the BNF example, but could you
> show a more complete example of (example syntax) of how
> the overloaded operators might be declared, implemented,
> and used? As it is now, it's hard to tell what kind of
> type computations (if any) are performed.

Here are some snippets from the Heron parser, which might help illustrate how it uses types:

if (!Parse<SourceFile>(in)) { ... }
...
struct SourceFile :
  bnf_and<
    WS,
    bnf_star<
      bnf_or<
        bnf_and<
          bnf_opt<External>,
          Keyword<'m','o','d','u','l','e'>,
          StoreFinao<Module>
        >,
        bnf_and<
          Keyword<'p','a','c','k','a','g','e'>,
          StoreFinao<Package>
        >
      >
    >
  >  
{ };
...
  // bnf_star matches the rule as many times as possible. 
  // bnf_star always returns true unless at the end of a file
  // note; that unlike Perl regular expression, partial backtracking is not performed   
  template<typename Rule_T>
  struct bnf_star 
  {
    template<typename Parser_T>
    static bool Match() {
      if (Parser_T::AtEnd()) { return false; } 
      while (Rule_T::template Match<Parser_T>()) { }
      return true;
    }
  };
...


Does this help clarify somewhat? The goal is to find a simpler syntax for the grammar.

Now as far as units go, check out http://boost-consulting.com/mplbook/metafunctions.html as per Indranil's suggestion. This pretty much makes the case for me for simpler syntax for type manipulation.

As far as how the type operator overload declarations might go: I am thinking that cm * m maps to _meta_star<cm, m>::type.

Does this make sense?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 26, 2005 9:42 AM
Reply to this message Reply
> The language Mathematica does what you want, but it works
> differently, its method might give you some ideas.

Thanks for sharing the Mathematica approach. It would be a dream of mine if Heron could give it some competition, but unforuntately I currently know very little about Mathematica.

> 3. Therefore when you write 1 kg it means Times[1,kg]
> (Mathematica uses square brackets for functions) where 1
> is a number and kg is a constant from the set of constants
> in the package units and Times is an overloaded function
> that accepts a number and a unit

So what does Mathematica do when you write a poorly typed expression like:

[java
x = 1 kg 2 m/(s^2)
y = 1 kg 2 m/(s) // intential error
z = x + y // how does this fail, if at all?
[/java]

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 26, 2005 2:02 PM
Reply to this message Reply
> Now as far as units go, check out
> http://boost-consulting.com/mplbook/metafunctions.html as
> per Indranil's suggestion. This pretty much makes the case
> for me for simpler syntax for type manipulation.
>
> As far as how the type operator overload declarations
> might go: I am thinking that cm * m maps to
> _meta_star<cm, m>::type.

Ah, get you now. :) I've been thinking of this, too (no, I'm not saying it exists in ML ;) ): compile-time infix operators.

Presently, in C++, we have run-time prefix and infix operators (and postincrement as the "odd" postfix one), such as:

++i; // Prefix
i+j; // Infix
i++; // Postfix

Also, we have prefix compile-time expressions/metafunctions, such as:

mpl::add<a,b>::type // "a" and "b" are types or typedefs (typedefs being our "compile-time variables")

However, as you highlight, we have neither:

1) Operator overloading on types/compile-time expressions, and therefore neither do we have
2) Infix operations on types

I've played some with an idea about this, where you - as a rather big "hack", could indeed do compile-time infix computation (even including lambda (!)). This was also inspired by Alexey Gurtovoy's "round lambda" idea that he posted sometime on the Boost list, as well as some "wacky" ideas I got from discussions with Paul Mensonides (one of the authors of the Boost.Preprocessor library - the other being Vesa Karvonen).

The following is the complete, working code (requiring Boost, of course):

--- Start ---

#include <iostream>
#include <boost/bind/placeholders.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/multiplies.hpp>
#include <boost/mpl/lambda.hpp>
#include <boost/mpl/apply.hpp>
#include <boost/mpl/int.hpp>

using namespace boost;

template<int N>
struct size
{
char array[N];
};

size<1> operator+(arg<1>, arg<2>); // _1 + _2
size<2> operator*(size<1>, arg<1>); // (_1 + _2) * _1

template<int>
struct expr;

template<>
struct expr<1> : mpl::lambda<mpl::plus<mpl::_1, mpl::_2> >::type {};

template<>
struct expr<2> : mpl::lambda<mpl::multiplies<mpl::plus<mpl::_1, mpl::_2>,
mpl::_1> >::type {};

// Use:

int main()
{
typedef expr<sizeof(_1 + _2)> exprA;
typedef expr<sizeof((_1 + _2) * _1)> exprB;

std::cout << mpl::apply<exprA, mpl::int_<1>, mpl::int_<2> >::type::value
<< '\n'; // 1 + 2 = 3
std::cout << mpl::apply<exprB, mpl::int_<10>, mpl::int_<20> >::type::value
<< '\n'; // (10 + 20) * 10 = 300
}

--- End ---

The infix operations I talk about are the definitions of "exprA" and "exprB". "_1" and "_2" are "placeholders", for the actual values that get substituted later (in the calls to mpl::apply).

In other words, it computes the result of the lambda expression "_1 + _2", etc. at compile-time (!). The result is a type, with a nested "value" member, so it does in effect allow you to do infix type computations. The "_1" and "_2" are values (instantiations of types) needed to drive the overload resolution, and you get the resulting type via a sizeof-to-type mapping (with typeof or type inferencing, you might do even more clever stuff).

It's mostly for fun, :) and hardly usable in its present form, as you need to manually encode any expression in the prefix form (see the expr<1> and expr<2> specialisations).

> Does this make sense?

Indeed. :)

Regards,

Terje

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: Boost Metaprogramming Posted: Sep 26, 2005 7:16 PM
Reply to this message Reply
I mean this will all sorts of respect, but IIRC the tutorial given in Boost MPL's book does all sorts of handwaving and "and then a miracle occurs." I know why it does this, but that "why" is a good argument for desiging things into the language.

I'm referring mainly to section 3.1.4's statement

"However, if we try to write:

quantity<float,force> f = m * a;

we'll run into a little problem. Although the result of m * a does indeed represent a force with exponents of mass, length, and time 1, 1, and -2 respectively, the type returned by transform isn't a specialization of vector_c. Instead, transform works generically on the elements of its inputs and builds a new sequence with the appropriate elements: a type with many of the same sequence properties as mpl::vector_c<int,1,1,-2,0,0,0,0>, but with a different C++ type altogether. If you want to see the type's full name, you can try to compile the example yourself and look at the error message, but the exact details aren't important. The point is that force names a different type, so the assignment above will fail.

... We can correct that problem using another MPL algorithm, equal, which tests that two sequences have the same elements."

My point isn't that the solution is bad, but that the C++ type system (that I've tried to defend in another thread) doesn't permit what is needed without mystic library support.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 26, 2005 7:45 PM
Reply to this message Reply
> So what does Mathematica do when you write a poorly typed
> expression like:
>
> x = 1 kg 2 m/(s^2)
> y = 1 kg 2 m/(s) // intential error
> z = x + y // how does this fail, if at all?

It doesn't evaluate the expression other than substituting for x and y, therefore z = 1 kg 2 m/(s^2) + 1 kg 2 m/(s) which will presumable either fail at some point or be obvious in the output (Mathematica is dynamically typed so almost nothing is an error when declared!).

The functions Mathematica provides other than the simplification of units are: Convert[ <value with units>, <new units> ], SI[ <value with units> ], MKS[ <value with units> ], and CGS[ <value with units> ]. It has a list of a few hundred units and standard SI prefixes that it understands.

Also take a look at: http://jscience.org/ which has units for Java and also mentions that Java standardization efforts for units.

Steve Donovan

Posts: 24
Nickname: stevedonov
Registered: May, 2005

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 27, 2005 8:09 AM
Reply to this message Reply
> alias A : *B & C;
> alias B : C | D;

Excuse me for being a little stupid here, but why can't B,C and D be objects of some type that overloads these operators? Why do we need to overload type operators in this case?

steve d.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 27, 2005 9:08 AM
Reply to this message Reply
/* Excuse me for being a little stupid here, but why can't B,C and D be objects of some type that overloads these operators? Why do we need to overload type operators in this case?
*/

I believe that is the Stroustrup Approved Way. But doing that leads to a lot of typing, and programmers are expensive typists.

Here's the point, going back to the MPL tutorial -- in physics I have several equations that lead to a velocity (m/s). For instance, I can start with an acceleration (m/s^2) and multiply by a time (s) to get velocity (as the seconds "cancel"). Or I can start with a distance and divide by time. Or I can start with a force in Joules (a.k.a. meters * kg), divide by a mass (kg) and then divide by a time (s). These combinations increase too quickly for even the fastest typist. There has got to be a better way.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 27, 2005 9:26 AM
Reply to this message Reply
> > alias A : *B & C;
> > alias B : C | D;
>
> Excuse me for being a little stupid here, but why can't
> B,C and D be objects of some type that overloads
> these operators? Why do we need to overload type
> operators in this case?

In the case of representing grammar productions in a recursive descent parser, it is perfectly reasonable to use objects instead of types. This is part of what the Boost Spirit library does, but Spirit still generates new types from the expressions. What ends up happening in this approach, and it appears inevitable, is that with Spirit there are a lot of "ifs, ands and buts" concerning the definition of parsing rules. It would be great if things were as simple as promised in the documentation but writing Spirit grammars is very hard, and the machinery is opaque (deduced templates instead of express). This is not because of Spirit, but rather due to the difficulties inherent in using expression templates. In YARD I chose to go a simpler route, make all of the grammar production rules explicit types.

Maybe the bet approach is to blend the two and support both expression templates, and explicit types as grammar production rules? This is actually very feasable and I haven't considered until just now.

Sean Conner

Posts: 19
Nickname: spc476
Registered: Aug, 2005

Re: Metaprogramming on Steroids: Overloaded Type Operators Posted: Sep 29, 2005 12:59 AM
Reply to this message Reply
What I think you're going for a type of type progression. Or something like that. Anyway ... Let's say you have:

type length;


So, length + length yields a length but length * length yields not a length but type area. And length + area should not be allowed.

Going a bit further here:


type length;
length cm;
length in;


cm and in both are types of length, but an inch does not equal a centimeter, so some form of conversion is required (at some point). For instance:


type length;
length cm;
length in;

cm x = 1in;


x in this case, should equal 2.54 (which is the number of centimeters in an inch). What to do about something like:

area a = 3cm * 6in;

Do you convert centimeters to inches? Or inches to centimeters? It's not an easy answer. In this case it doesn't really matter since both are of similar scale, but when you do something silly like:

area a = 3cm * 2lightyears;

The 3cm kind of gets lost in the noise (let's see ... 0.03m * 2x10^11m (approximately)).

You might want to look at the code for the Unix program units which handles quite a bit of this. For example:


(spc)linus:~>units
503 units, 41 prefixes

You have: 5 femtolightfortnight
You want: feet
* 5.9486377
/ 0.16810571
You have:

Flat View: This topic has 15 replies on 2 pages [ 1  2 | » ]
Topic: Post-TDD Previous Topic   Next Topic Topic: Representing Units of Measure


Sponsored Links



Google
  Web Artima.com   

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