[GSOC] regular expressions beta is here

[bearophile]

Don:

> bearophile wrote:
>> 2) I have found many situations where I am able to solve a problem with both a
>> simple and slow brute force solver, and a complex and fast algorithm to solve
>> a problem. The little program maybe is too much slow for normal usage, but
>> it's just few lines long (especially if I use lot of std.algorithm stuff)
>> but it's much less likely to contain bugs.
>
> Sorry, but personally I don't believe that this is useful outside of toy
> examples.

This code of mine is a real-world example. This is a struct method with comments removed, the postcondition contains both fast loose tests and a tight slow O(n^2) version that thanks to std.algorithm is just 2 lines long (unfortunately because of DMD bug 6417 it's a bit longer than 2 lines). It's asymptotically slower than the fast algorithm, so I've put it into a debug{}.


void foo(in int[] p, int[] q) nothrow
in {
  assert(p.length == vectorLen);
  assert(q.length == vectorLen);
  assert(equal(p.dup.sort(), iota(1, vectorLen+1)));
} out {
  foreach (i, qi; q)
    assert(qi >= 0 && qi < (vectorLen - i));
  debug foreach (j; 1 .. (q.length + 1))
    assert(q[j-1] == count!((int k){ return p[k] > j; })(iota(countUntil(cast()p, j) + 1)));
} body {
  op[0] = &items[0];
  foreach (i, pi; p) {
    items[i] = Item(pi, 0);
    op[i + 1] = &items[i + 1];
  }

  foreach_reverse (k; 0 .. (lim + 1)) {
    xs[0 .. ((vectorLen >> (k + 1)) + 1)] = 0;
    foreach (j; 0 .. vectorLen) {
      int r = (op[j].space >> k) % 2;
      int s = op[j].space >> (k + 1);
      if (r)
        xs[s]++;
      else
        op[j].digit += xs[s];
    }
  }

  foreach (i; 0 .. vectorLen)
    q[op[i].space - 1] = op[i].digit;
}


This postcondition has caught a simple mistake I've put in the fast algorithm. Probably there are ways to catch the same bug with unittests too.

The ugly empty cast() inside the postcondition is another workaround, because countUntil doesn't work with a const p.

If you write those two postcondition lines in Python3 it becomes less noisy:

assert q == [sum(p[k] > j for k in range(p.index(j) + 1)) for j in range(1, len(q)+1)]

Instead of:

foreach (j; 1 .. q.length+1)
    assert(q[j-1] == count!((int k){ return p[k] > j; })(iota(countUntil(cast()p, j) + 1)));


Here using assert(equal(q, map!...)) becomes too much puzzle-code. It's already too much nested.

If you program in functional-style it's hard to write lines of 70 chars. In Haskell too lines of code are often long.

Bye,
bearophile