PLACE
spec
solutions
Cilk

RPN Calculator in Cilk

Cilk is only different from C in its support for concurrency. The reason to write a program in Cilk is that we want it basically in C, but concurrent. In the case of the RPN calculator, one thing that can be parallelized is the evaluation of subexpressions. For example, in the expression  5 1 + 2 / 7 2 + *  the subexpressions  5 1 + 2 /  and  7 2 +  can be evaluated concurrently in order to arrive at  3 9 *. The subexpressions can be further parallelized, down to single numbers.

In order to make use of concurrency, we have to find, for any given operator, which parts of the expression yield the values of that operator's arguments – the span of the operator. We saw how to do this in the general discussion of the problem. The program shown below ‘compiles’ an expression from an input string by successively extracting tokens from it and determining each token's type (number or operator), value (for numbers), and span. This is done in the procedure compile, which builds a sequence of tokens and returns their number or -1, the latter signifying a syntax error.

The first loop in compile reads an input line into the buffer pb. The second one then cuts tokens from the line and parses and stores each one as said. A sequence expr is thus being built up of the ‘compiled’ tokens. For each element of expr its oper field is 0 for a number, and one of '+', '-', '*', and '/' for an operation.

Both pb and expr are dynamic arrays, their sizes being augmented as needed by calls to realloc.

Once compile creates the sequence expr, it remains for eval to work backwards on it in order to evaluate the expression. The integer parameter of eval is the index within expr from where the evaluation for the current call of eval starts.

Note that for all indices n within expr the subexpression whose evaluation starts at n comprises the elements of expr in the index range [expr[n].span,n]. If expr[n] is a number, then expr[n].span = n holds and therefore that range contains a single element: the number itself.

eval looks like a recursive procedure, because it contains calls to itself, but it isn't really recursive. Instead, the two calls to eval are separate threads, executed concurrently to each other and to the thread that spawns them, and joined (synced) again with that thread after they produce the results of the subexpressions. The initial call to eval in main is also spawned as a separate thread and synced back to the main one as it finishes.

On the other hand, were the cilk, spawn, and sync words not present in the program, eval would be a sequential recursive procedure, and the whole program would still be a correct implementation of the calculator – in plain C. Note that the computation and use of span values, and therefore also the eval's parameter, would then be superfluous as the recursive evaluation in eval could simply traverse expr backwards in a strictly sequential manner – no need to know in advance any points within expr (cf. C and C++, among others).

In this implementation, we spawn threads only after we have an input line completely read and transformed into the sequence expr. This is not the only way to go. We could have made the program more eagerly concurrent by spawning a thread as soon as in the course of reading we reach an operator token. So we would have been able to do some partial evaluation of the expression while concurrently parsing the rest of it.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cilk.h>

struct {int oper,span; double val;} * expr;
char *pb;
int isz,ssz;

#define OI(i) (expr[i-1].span)

int compile(int c) {
  int n,s,k,i;
  double x;
  char *p,*q,*qq, op[] = "+-*/";
  for (
    p = pb, n = s = k = 0
  ; c!=EOF && c!='\n'
  ; *p++ = c, ++n, c=getchar()
  ) {
    if (c==' ' || c=='\t') s = 0;
    else if (s==0) {s = 1; ++k;}
    if (n+1==isz) {
      pb = realloc(pb,isz*=2);
      p = pb+n;
    }
  }
  *p = 0;
  if (ssz<k) expr = realloc(expr,(ssz=k)*sizeof(*expr));
  for (i=n=0,p=pb; i<k; p=NULL,++i) {
    q = strtok(p," \t");
    if (q[1]==0 && NULL!=(qq=strchr(op,*q))) {
      if (n<2) return -1;
      expr[i].oper = op[qq-op];
      expr[i].span = OI(OI(i));
      --n;
    } else if (x=strtod(q,&qq),*qq==0) {
      expr[i].val = x;
      expr[i].oper = 0;
      expr[i].span = i;
      ++n;
    } else return -1;
  }
  if (n>1) return -1;
  return k;
}

cilk double eval(int n) {
  double x,y;
  if (expr[n].oper==0) return expr[n].val;
  y = spawn eval(n-1);
  x = spawn eval(OI(n)-1);
  sync;
  switch (expr[n].oper) {
    case '+': return x+y;
    case '-': return x-y;
    case '*': return x*y;
    case '/': return x/y;
  }
}

cilk int main() {
  int c,k;
  double x;
  pb = malloc(isz=2);
  expr = malloc((ssz=1)*sizeof(*expr));
  while ((c=getchar())!=EOF) {
    k = compile(c);
    if (k>0) {
      x = spawn eval(k-1); sync;
      printf("%f\n",x);
    } else if (k<0) printf("error\n");
  }
  return 0;
}

boykobbatgmaildotcom