A Deeper Look At Metafunctions

In this Artima article, David Abrahams and Aleksey Gurtovoy take a deeper look at metafunctions, and introduce the Boost metaprogramming library.

The article is an extract from the authors' forthcoming C++ Template Metaprogramming.

The authors' example application of C++ metafunctions is compile-time dimensional analysis. Higher order metafunctions, partial metafunction application and lazy evaluation are also discussed.

Wouldn't an Amazon sponsored link to the book be a good idea here?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

It's interesting that C++ tem

It's interesting that C++ templates can be parameterised by values as well as types. I don't think you can do that in Haskell.

You can, of course, create types that represent integers, and use classes with fundeps to represent operations. But it's a bit of a hack:

data Zero;
data Succ a;

class Add a b ab | a b -> ab, ab a -> b;
instance Add Zero a a;
instance (Add a b ab) => Add (Succ a) b (Succ ab);
etc.

Anyone at Microsoft reading this? Ralf Lämmel is giving a talk on doing this sort of thing in Haskell today at 3:30pm at MSR.

Templates = Lame Dependent Types

Isn't it somewhat silly to embed a limited language with bizarre syntax into existing languages for the purpose of executing code at compile time? Dependent types and compile-time partial evaluation provide a much more general and flexible means for doing this sort of thing.

Silliness

It is a bit silly. It was an accident, however.

Accident, er, Types

Jim Apple: It is a bit silly. It was an accident, however.

It was an accident that it's Turing-complete, not that it's a limited language with bizarre syntax for doing compile-time programming. I'm with Tim: now that the concept's been proven, in much the same fashion that Java made garbage collection (and really awful garbage collection at that!) acceptable to the masses, it's time for the next language that takes these lessons, among others, and does them right.

Roughly my feeling

I think, "cool that you can do this", but also, "C++ templates suck as a way of doing this" (I thought that all the way through Alexandrescu, which was a lot funnier the second time after I'd learned a bit of Scheme).

So, what's a better way - or rather, of the various better ways that no doubt exist, what's a likely candidate for inclusion in the language-for-the-masses of tomorrow?

Not Going All The Way Into It Again, But...

The Tragic vs. the Comic View

Dominic Fox: I think, "cool that you can do this", but also, "C++ templates suck as a way of doing this" (I thought that all the way through Alexandrescu, which was a lot funnier the second time after I'd learned a bit of Scheme).

It transitions from comedy to tragedy once you know a lot of Scheme. It's the difference between "Godspell" and "Jesus Christ, Superstar," which I think should only be seen back-to-back. :-)

Time to move on

it's time for the next language that takes these lessons, among others, and does them right.

Agreed.

Something like Lisp?

Ha, ha. Seriously though, whenever I thing about that, I think about something that's "turtles all the way down," like ECC or Fw, so we can abstract over our abstractions.

Next?

Jim Apple: Agreed.

Something like Lisp?

Ha, ha. Seriously though, whenever I thing about that, I think about something that's "turtles all the way down," like ECC or Fw, so we can abstract over our abstractions.

Lisp got many things significantly right. Even McCarthy has expressed his surprise that the whole parenthesis-as-syntax-and-list-representation turned out to be a feature rather than a bug, and this excellent start arrived at some kind of local maximum with Scheme's hygenic macros. Most popular languages would do well to study Scheme's results when they contemplate syntactic extension.

It becomes very interesting, though, to think about what some of the alternatives are. For example, see <http://scala.epfl.ch/intro/targettyping.html>, which offers an example of how Scala can create new syntax using just libraries, thanks to its support of automatic type-dependent closure generation and operators being usable in either infix or postfix contexts. My current favorite day-to-day language, O'Caml, has the camlp4 preprocessor, which can be extended with custom expanders. You end up working with actual ASTs rather than strings, which is nice.

But to your point about "turtles all the way down" and working with full-on ECC or Fω, systems that allow that kind of blend of specification/implementation do exist. I'm very keenly interested in MetaPRL, but other very nice-sounding candidates include Maude and OBJ3. As far as choices of formalisms are concerned, I'm especially intrigued by the Open Calculus of Constructions, which I stumbled across while researching explicit substitution calculi and finding CINNI.

As I'm very much on a type theory/formal methods/blending-specification-and-implementation kick myself, I'm most interested in sharing any learning materials/processes/experiences/results with others of similar interests. In fact, I'd be delighted to form some kind of distributed LtU workshop that touches on these subjects, if any others are interested.

Finally, let's not forget that Tim Sweeney has publically discussed, on this forum, a new language that he's designing that sounds very much like it will have some features that many of us would like. I don't know how much more Tim wants to say about it, however.

It becomes very interesting,

It becomes very interesting, though, to think about what some of the alternatives are. For example, see , which offers an example of how Scala can create new syntax using just libraries, thanks to its support of automatic type-dependent closure generation and operators being usable in either infix or postfix contexts

I'm stupid, sorry if I don't get this at first time:
There is a difference beetween scala's system and blocks as seen in smalltalk or ruby ?

Ruby even offers statement modifiers, just like scala. , and actually some control structures such as repeat_until are just a block + a postfix while.

No Uniqueness Claim

gab: I'm stupid, sorry if I don't get this at first time: There is a difference beetween scala's system and blocks as seen in smalltalk or ruby ? Ruby even offers statement modifiers, just like scala. , and actually some control structures such as repeat_until are just a block + a postfix while.

I don't believe you're stupid! I think you're imputing a uniqueness claim for Scala that I didn't make. Having said that, I haven't seen a Smalltalk implementation that has features for defining new syntax around blocks, but this is hardly surprising, as Smalltalk's notion of "syntax" is, at least to a first approximation, just naming messages and things that accept messages, and being a dynamic language, it can get away with closures not being "type-dependent," with everything that that implies in terms of the safety of applying the closure. Ruby is similar in some sense, but because its syntax is more clearly Algol-derived, it did have to worry about allowing infix/postfix operators. We still see the difference, though, in the Ruby construct being "repeat_until" instead of "repeat ... until." That is, Scala does, in fact, offer a level of syntactic flexibility that's lacking in languages that don't offer the combination of features that make this possible in Scala, and more to the point, it does so by means other than a macro or "metaprogramming" system.

ok

Oh, sorry, now I see what you mean.
Btw, ruby does allow repeat.. while, cause it allows if/unless/while/rescue as postifx statements:

 >> def repeat
 >>  yield
 >> end
 => nil
 >> i=10
 => 10
 >> repeat do
 ?>  print i
 >>  i+=1
 >> end while i 

Anyway it is quite limited related to scala.. You can't define you own postfix statement modifiers :/

Arrows == self-specializing by value?

Do the self-optimizing parsing arrows of Swierstra and Duponcheel fit into this somewhere?

I don't know much about C++ templates, but I know parsing arrows can be optimized by 'values accepted.'

Is that related?