Home » forums » LtU Forum

expressivity of "idiomatic C++"

The April issue of C/C++ Users Journal has an article called A New Solution To an Old Problem by Andrew Koenig and Barbara E. Moo. In it, they revisit the Hamming numbers problem from Dijkstra's A Discipline of Programming.

They examine four different solutions:

  1. A naive O(n^2) solution.
  2. Dijkstra's efficient but somewhat convoluted O(n) solution (re)implemented in C++.
  3. An elegant O(n) solution in Haskell.
  4. Their own new O(n*log(n)) solution in "idiomatic C++".

The Haskell solution is the following

scale n (x:xs) = (n * x) : (scale n xs)
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) =
   if x == y then
      x : (merge xs ys)
   else if x < y then
      x : (merge xs (y:ys))
   else
      y : (merge (x:xs) ys)

seq = 1 : (merge (scale 2 seq)
                 (merge (scale 3 seq) (scale 5 seq)))

Their "idiomatic C++" solution uses ordered sets:

set<int> seq;
seq.insert(1);
set<int>::const_iterator it = seq.begin();

int val = *it;
seq.insert(val * 2);
seq.insert(val * 3);
seq.insert(val * 5);
it++;

In conclusion, they have this to say (emphasis mine),

We have looked at four solutions to a simple problem. The first was straightforward but slow. The second was much faster but fairly tricky. The third, in a functional language, was again straightforward -- but requires a totally different way of thinking about programming. Indeed, advocates of this way of thinking use the program's straightforwardness to argue that this way of thinking is superior.

With the fourth solution, we believe that the argument is far from obvious.

I may be reading too much into this quote, but it sounds to me like Koenig and Moo consider it a bad thing to require a "totally different way of thinking about programming".

P.S. While googling for Hamming numbers, I came across this related paper: Expressivity of Functional-Logic Languages and Their Implementation by Juan José Moreno Navarro.

By el-vadimo at 2005-03-29 15:22 | LtU Forum | previous forum topic | next forum topic | other blogs | 82855 reads

Comment viewing options

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

I have to agree

That operator overloading was one of the smartest things Bjarne added to C++. Yes, yes, it's "just" syntactic sugar, but we are used to seeing and reading symbols, especially when they are a powerful shorthand for important concepts. Imagine if we taught schoolchildren to do math like so: 
       four
  add  four
equals eight

It's pretty much exactly equivalent to the usual notation, except that it's much harder for us to read, not at least partly because it's so verbose. I'm sure part of what makes Haskell so appealing to some programmers is how concise it is. And it achieves much of that syntactic parsimony through the heavy use of symbols. A more verbose Ada-like dialect of Haskell where all the symbols are replaced by word tokens would probably cause FP programmers to recoil in horror.

I would argue that choosing to *not* include operator overloading was one of the biggest failures of Java's design, and is why it would be utter folly to even attempt to implement half the libraries that exist for C++, including Spirit++, Blitz++, Boost.Iterator, etc. Sometimes I look upon libraries like Boost.Lambda with a combination of admiration and loathing, but you have to admit that for a 20 year old statically typed imperative PL, C++ does all right for itself.

By David B. Held at Tue, 2005-09-27 14:38 | login or register to post comments

Hmmm...

A more verbose Ada-like dialect of Haskell where all the symbols are replaced by word tokens would probably cause FP programmers to recoil in horror.

You mean like Scheme...? ;)

By Matt Hellige at Tue, 2005-09-27 17:39 | login or register to post comments

Beauty is in the eye of the beholder

I'm all for judicious use of operator overloading, but I think it a mistake to assume that the elegance of the Haskell code is due to operators. The use of operators in the Haskell code is pretty bare minimum and there's nothing particularly out of the ordinary for those that are used ([] : * = ==

So the question back is why is the Haskell code considered elegant? FWIW, the Oz code and the Alice ML code are fairly close to the Haskell code, so perhaps the answer is not the Haskell Type system. For sure, you have to have lazy functions. (IMHO, any solution that uses iteration and array pointers misses the whole point to the elegance of the recursion).

As an aside, APL has always been on the extreme in terms of usage of operators. For those that understand the symbols, APL provides a power for manipulation that is as expressive as any language. For those that don't understand the symbols, APL can look like chicken scratch. The biggest problem with APL is that you can't define new operators that act in a first class fashion.

The use of symbols in code can sometimes aide readibility. It can also sometimes make it harder to grok. Not particularly caring about C++ at this juncture in history, I find it weird that the use of such symbols as >> and

By Chris Rathman at Tue, 2005-09-27 15:11 | login or register to post comments

Syntactic brevity

The use of operators in the Haskell code is pretty bare minimum and there's nothing particularly out of the ordinary for those that are used ([] : * = ==

In that example, although Haskell uses a lot more symbols than that. But perhaps another major source of conciseness is the type inference. That takes a *lot* of identifiers out of the code that you find in manifestly typed languages.

The use of symbols in code can sometimes aide readibility. It can also sometimes make it harder to grok.

Can we say: "awk/sed"?

Not particularly caring about C++ at this juncture in history, I find it weird that the use of such symbols as >> and

Well, I've never understood this criticism of C++. If you want to concatenate stream operations, you need to have a stream operator. Was there some de facto stream operator before ? It makes perfect sense to me, since most *nix shells use > and .

By David B. Held at Tue, 2005-09-27 21:29 | login or register to post comments

Expressivity

I was way too harsh and vague in my comment about "bad code". Excuse me, I'll try not to do this in the future.

I'll try to explain my point in some more detail, if you're still listening...

I easily grant that, given any concrete task, C++ can be made as expressive as Haskell for this task, by writing a (quite large) supporting combinator library (operator overloading and expression templates to build/evaluate syntax trees).

But the "bad code" I blurted out isn't just an expressivity measure. The criterion of "good code" I have developed over the years is as follows: good code should be right, and it should be obviously right.

Of course, there are different grades of "obviously", so it's a very subjective metric. But the experience of many people shows that it's VERY hard to write "obviously right" code in C++.

For a quick mental test, look back at the code you supplied (_if, _1, _2 and stuff). Imagine debugging/maintaining just a couple hundred lines of such code, freely mixed with "normal" C++ and - for kicks - also using some other expression-template combinator library (e.g. Boost Spirit).

I can easily imagine working with tasks of similar complexity in Haskell - though I'm a Haskell newbie at best.

And no, operator overloading isn't the biggie here. It's just syntax.

For example: you alluded to my mock Java sample as "stupid", but... dont' you think that, if you're embedding a functional language within C++, you're going to need a garbage collector at some point? Yes, value types help, but they don't solve all problems. OCaml has a GC. Haskell has a GC. And even Java has a GC... so my example wasn't so stupid after all :-)

See? This semantic issue is much more important than the syntax issue (operator overloading) you pointed out.

By Vladimir Slepnev at Tue, 2005-09-27 19:27 | login or register to post comments

No GC ;>

For example: you alluded to my mock Java sample as "stupid", but... dont' you think that, if you're embedding a functional language within C++, you're going to need a garbage collector at some point? Yes, value types help, but they don't solve all problems. OCaml has a GC. Haskell has a GC. And even Java has a GC... so my example wasn't so stupid after all :-)

Well, the most important value type in C++ is the smart pointer. ;> Not only can you use vanilla strategies like reference counting, you can use a good smart pointer framework to implement a garbage-collected pointer. Of course, if you absolutely must have a "pure" garbage collector, you can just link one in to the C++ program as well. Not only does C++ come with the kitchen sink, it comes with an optional garbage disposal too! ;>

By David B. Held at Wed, 2005-09-28 17:17 | login or register to post comments

Just for the fun of it...

Here it is in Lua, with a fairly complete lazy infinite sequence implementation using promises:

By rici at Tue, 2005-09-27 02:38 | login or register to post comments

Python version

Okay, that is a challenge. :)

def scale(n, it):
    for e in it: yield n * e

def cons(x, it):
    yield x
    for e in it: yield e

def merge(xs, ys):
    x, y = xs.next(), ys.next()
    if x == y:
        for e in cons(x, merge(xs, ys)): yield e
    elif x 

This basically follows the Haskell version point for point except that it's done using generators and iterator algebra (by the way, the above merge function only works with infinite iterators since it doesn't catch StopIteration).
By Per Vognsen at Tue, 2005-09-27 13:22 | login or register to post comments

That's very pretty, but...


>>> from itertools import izip
>>> for i, e in izip(range(100000), seq()):
...   if i % 10000 == 0:
...     print i, e
... 
0 1
Traceback (most recent call last):
  File "", line 1, in ?
  File "", line 3, in seq
<snip />
  File "", line 3, in cons
  File "", line 2, in merge
RuntimeError: maximum recursion depth exceeded

To be fair to Python, a nice fast working solution is in here, from a thread previously referenced in this topic.

By rici at Tue, 2005-09-27 14:55 | login or register to post comments

Well...

The Haskell version has the same number of recursions as my Python version, up to a constant factor. None of the recursions in either version are in tail call position, so they cannot be optimized away. So as far as expressivity at the language level is concerned, I don't think the maximum recursion depth bail-out is very relevant--if you tested it on Stackless (or any other Python implementation with a priori unbounded call stack) there would be no issue aside from performance (a function call in Python is at least two heap allocations).

By the way, I wasn't trying to present my code as "the best" or whatever, I just wrote it up to see how close to the spirit of the Haskell code I could get without doing any insane stunts. I figured I might as well share it.

By Per Vognsen at Tue, 2005-09-27 15:34 | login or register to post comments

Sharing vs. reevaluation

The Haskell version has the same number of recursions as my Python version, up to a constant factor.

I'm just a casual Python user, but it seems to me that your version starts new generators for each recursive call to seq(), whereas the Haskell version shares the ham list.

None of the recursions in either version are in tail call position [..]

But the recursive calls of ham are on lazy positions and the Haskell program only needs constant stack space.

By Ronny Wichers Schreur at Tue, 2005-09-27 16:55 | login or register to post comments

Yes

You're absolutely right, that's what I get for only being a casual Haskell user (if even that). Oh well.

By Per Vognsen at Tue, 2005-09-27 16:59 | login or register to post comments

Haskell-to-Scala translation

Just for kicks, here's a Scala solution:

object hamming extends Application {
  import java.math.BigInteger

  def merge(xs: Stream[BigInteger], ys: Stream[BigInteger]): Stream[BigInteger] =
    if (xs.isEmpty) ys
    else if (ys.isEmpty) xs
    else {
      val x = xs.head
      val y = ys.head
      val cmp = x compareTo y

      if (cmp == 0) Stream.cons(x, merge(xs.tail, ys.tail))
      else if (cmp < 0) Stream.cons(x, merge(xs.tail, ys))
      else Stream.cons(y, merge(xs, ys.tail))
    }

  def seq: Stream[BigInteger] =
    Stream.cons(BigInteger.ONE,
                merge(seq map new BigInteger("2").multiply,
                      merge(seq map new BigInteger("3").multiply,
                            seq map new BigInteger("5").multiply)))

                            

  Console.println("The first 20 numbers:")
  Console.println (seq.take(20).mkString("", ", ", ""))

  Console.print("\nThe 100th number (counting from 0): ")
  Console.println(seq.drop(100).head)

  Console.println("\nThe 1000th:")
  Console.println(seq.drop(1000).head)
}

It's a real shame it doesn't work. You can compute the first 100 numbers, but you can't compute 1000. 

$ scalac hamming.scala
$ ls -lh
total 80K
-rw-rw-r-- 1 vadim vadim 1.1K Sep  7 19:59 hamming$$anonfun$0.class
-rw-rw-r-- 1 vadim vadim 1.1K Sep  7 19:59 hamming$$anonfun$1.class
-rw-rw-r-- 1 vadim vadim 1.1K Sep  7 19:59 hamming$$anonfun$2.class
-rw-rw-r-- 1 vadim vadim 1.5K Sep  7 19:59 hamming$$anonfun$3$$anonfun$4.class
-rw-rw-r-- 1 vadim vadim 1.5K Sep  7 19:59 hamming$$anonfun$3$$anonfun$5.class
-rw-rw-r-- 1 vadim vadim 1.5K Sep  7 19:59 hamming$$anonfun$3$$anonfun$6.class
-rw-rw-r-- 1 vadim vadim 1.3K Sep  7 19:59 hamming$$anonfun$3.class
-rw-rw-r-- 1 vadim vadim  868 Sep  7 19:59 hamming.class
-rw-rw-r-- 1 vadim vadim 2.4K Sep  7 19:59 hamming$.class
-rw-rw-r-- 1 vadim vadim  992 Sep  7 17:55 hamming.scala
$ time scala hamming
The first 20 numbers:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36

The 100th number (counting from 0): 1600

The 1000th:
java.lang.OutOfMemoryError: Java heap space

real	0m11.424s
user	0m9.053s
sys	0m0.344s
By el-vadimo at Fri, 2006-09-08 00:08 | login or register to post comments

still broken under Scala 2.6...

Under Scala 2.6 / Sun JDK 1.6.0_02:

$ sudo rpm -ivh http://www.scala-lang.org/downloads/distrib/files/scala-2.6.1-1.i386.rpm

$ java -version
java version "1.6.0_02"
Java(TM) SE Runtime Environment (build 1.6.0_02-b05)
Java HotSpot(TM) 64-Bit Server VM (build 1.6.0_02-b05, mixed mode)

$ cat -n hamming.scala | head -14 | tail -3
    12        if (cmp == 0) Stream.cons(x, merge(xs.tail, ys.tail))
    13        else if (cmp < 0) Stream.cons(x, merge(xs.tail, ys))
    14        else Stream.cons(y, merge(xs, ys.tail))

$ time scalac hamming.scala

real    0m4.721s
user    0m4.296s
sys     0m0.169s

$ time scala hamming
The first 20 numbers:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36

The 100th number (counting from 0): 1600

The 1000th:
java.lang.OutOfMemoryError: Java heap space
        at scala.Stream$cons$.apply(Stream.scala:45)
        at hamming$.merge(hamming.scala:14)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$3.apply(hamming.scala:14)
        at hamming$$anonfun$merge$3.apply(hamming.scala:14)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$3.apply(hamming.scala:14)
        at hamming$$anonfun$merge$3.apply(hamming.scala:14)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)

real    0m26.626s
user    0m24.523s
sys     0m0.520s

Will try again in a couple of years.

By el-vadimo at Fri, 2007-12-28 02:08 | login or register to post comments

Scala 2.8.1

Note to self regarding comment-38966: 

$ time /var/tmp/scala-2.8.1.final/bin/scala hamming
The first 20 numbers:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36

The 100th number (counting from 0): 1600

The 1000th:
java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOfRange(Arrays.java:3137)
    at java.math.BigInteger.trustedStripLeadingZeroInts(BigInteger.java:2792)
    at java.math.BigInteger.multiply(BigInteger.java:1144)
    at hamming$$anonfun$seq$1$$anonfun$apply$1.apply(hamming.scala:19)
    at hamming$$anonfun$seq$1$$anonfun$apply$1.apply(hamming.scala:19)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)

real    0m25.552s
user    0m25.692s
sys     0m0.919s
By el-vadimo at Wed, 2010-11-10 13:42 | login or register to post comments

Relying on libraries

This is common language bigotry, and the authors cheat on their C++ "solution". They're relying on a heavyweight library class to do the difficult work, and thus hiding both the complexity and performance implications of their solution.

If you're going to compare language expressiveness and programming paradigms using examples like the Hamming problem, YOU HAVE TO ACTUALLY SOLVE THE PROBLEM, and not call some big library function to solve it for you. Otherwise you're just comparing libraries, and degenerately, an arbitrarily crappy language with a library that includes GiveMeHammingNumbers() wins.

By Tim Sweeney at Fri, 2006-09-08 17:16 | login or register to post comments

Parsimony

To some extent judging parsimony is in the eye of the beholder. Different dimensions of parsimony referenced in the discussion above include: runtime complexity of the algorithm, code length, whether the code uses language intrinsics vs. standard libraries vs. user-defined functions, runtime memory usage, and how close the algorithmic solution is to the way the individual wants to think about the problem. To my mind, some of the solutions others judged as very elegant are a little less so because they either require redundant information to be stored in different lists or involve a loss of information about the "progress" of each multiple generator (i.e. the 2,3,and 5 series). It seems easier to compose a solution that doesn't have these drawbacks by using an imperative style algorithm with shared state among the generators. Here is a version in C++ that doesn't use any libraries (except for I/O messaging). It would obviously look a little cleaner if it relied on a built in list construct, GC, and a more elegant looping syntax. However, it is clearly more minimalistic in terms of run time and potential memory footprint than most (perhaps all) other solutions presented. It is incomplete in the sense that it does not incorporate a BigNum library or check for overflow. As such, if the constant "1000" in the print loop is replaced with some bigger number it may overflow and generate nonsense long before it runs into other computational limitations. 

 #include < iostream >

typedef long long  BigN; // replace with best BigNum type available to you


class HammingIterator {
protected:

  // Helper Definitions: 

  // Roll our own singly linked list called HCell
  struct HCell {
    HCell(BigN v) : val(v), next(0) {}
    HCell(BigN v, HCell* n) : val(v), next(n) {}

    BigN       val;
    HCell*     next;
  };

  // for N=2,3,5, Gen<N>  will keep track of next generated and where we are
  // in working through the historical values
  template <int N>
  struct Gen {
    Gen(HCell* c) : trail(c), cand(N*trail->val) {}

    HCell* trail;
    BigN   cand;

    void goNext(BigN best) {
      if (best == cand) {
	trail=trail->next;
	cand = N*trail->val;
      }
    }
  };


  BigN min3(BigN v1, BigN v2, BigN v3) {
    return ((v1 <= v2) ? ((v1 <= v3) ? v1 : v3) : ((v2 <= v3) ? v2 : v3));
  }

  // Data Members of the iterator:

  HCell* d_list;     // all the stored list
  HCell* d_curr;   // the current value to output (end's the list)

  // State of the 3 generators, containing a trailing position and the next value
  // for this generator series
  Gen<2> d_g2;     
  Gen<3> d_g3;
  Gen<5> d_g5;

  void cleanTrail() { //remove no longer needed front of the list
    while ((d_list != d_g2.trail) && 
	   (d_list != d_g3.trail) && 
	   (d_list != d_g5.trail)) {
      HCell* next = d_list->next;
      delete d_list;
      d_list = next;
    }
  }

public:
  HammingIterator() : 
    d_list(new HCell(1)), d_curr(d_list), 
    d_g2(d_list), d_g3(d_list), d_g5(d_list) {}


  ~HammingIterator() {
    HCell* first = d_list;
    while (first) {
      HCell* next = first->next;
      delete first;
      first = next;
    }
  }

  BigN current() const { return d_curr->val; }

  void advance() {
// figure out which candidate is smallest:
    BigN best = min3(d_g2.cand,d_g3.cand,d_g5.cand);
// append smallest to the list as the new current
    d_curr->next = new HCell(best);
    d_curr = d_curr->next;
// advance state for any generator with candidate equal to best
    d_g2.goNext(best);
    d_g3.goNext(best);
    d_g5.goNext(best);
// remove front part of the list that's no longer needed
    cleanTrail();
  }

};



int main(int argc, char** argv) {

  HammingIterator hi;

  for (int i=0; i < 1000; ++i) {
    std::cout << hi.current() << std::endl;
    hi.advance();
  }
}
By Josh Stern at Wed, 2010-11-10 22:56 | login or register to post comments