[viff-devel] Small VIFF language parser

[T.Toft at cwi.nl]

Hi all

> We have talked on and off about making a front-end compiler for VIFF and
> today I figured that I would try making such a guy...
>
> So far it can only parse a simple language and spit out something which
> looks like equivalent Python code in which both branches of
> if-statements are run. So a program like this:
>
>   if a:
>     x = y
>     if b:
>       x = z
>     else:
>       x = w
>     fi
>   fi
>
> is transformed into this
>
>   x = (a * y + (1 - a) * x)
>   x = (a * b * z + (1 - a * b) * x)
>   x = ((1 - a * b) * w + (1 - (1 - a * b)) * x)
>
> which one could plug into a VIFF skeleton and run (not yet done).

Cool, but two serious comments:

1) Rather than

   x = (a * (y + (1 - a) * x)

you want

   x = (a * (y - x) + x)

so you shave off a superfluous mult for each assignment.

2) As far as I can see, it doesn't work. :-( There is a small bug in the
calculation of the third expression:

(1 - a * b) means !(a && b) but you want (a && (!b)) which translates to:

   a * (1-b) = a - a*b


> The idea is that the conditions in if-statements are pushed down to all
> assignments done in the then- and else-branches, nothing more.

Very basic, but the idea works (modulo the above problems).

> This is just a quick test to make people start thinking about what we
> want in such a language and to make people think about what kind of
> transformation we can do and which we cannot do.

I think that we can translate anything to a list of working expressions
(at least anything that doesn't involve outputting values). But I'm
worried that the naive approach won't give us any reasonable efficiency
except for trivial examples.

I have a few suggestions for improvements, but I'm not sure how difficult
they are to implement. Take the following as inputs for discussion...

1) When
    if b:
      x = z
    else:
      x = w
    fi

is translated into two distinct statements:

  x = (a * b * (z - x) + x)
  x = ((a*(1-b)) * (w - x) + x)

you increase the depth of the arithmetic circuit as the second expression
must wait for the new x-value. However, as only one of b and !b will be
true, the depth does not need to increase:

  a * ((b * (z - w) + w) - x) + x

(or simply: a*b*(z-x) + (a*(1-b))*(w-x) + x)


I'm not sure how easy this is to handle in general though, think of
examples such as:

  if a:
    x = c*y
    y = d*x
  else:
    y = e*x
    x = f*y
  fi

where we really want something like this:

(x, y) = (a*(c*y - f*e*x) + f*e*x,   a*(d*c*y - e*x) + e*x)


2) In the above translations a*b is computed multiple times. It would be a
lot more efficient if this was moved into a temporary variable so it could
be reduced. The same is true in hand-translation immediately above, where
e*x is computed 4 times (2 times by itself and 2 times as part of f*e*x).

Hmmm, Maybe using temporary variables partly solves the round-problem
above as well... Just execute both branches and conditionally select the
right results... What do you think?

/Tomas

> The program is attached below -- you will need to grab simplegeneric and
> PLY (Python Lex-Yacc) to use it, but both modules are easy to install:
>
>   http://pypi.python.org/pypi/simplegeneric
>   http://www.dabeaz.com/ply/
>
> You run the program by giving it the name of a file to parse and it will
> tell you the results on stdout.
>
>
> --
> Martin Geisler
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel at viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>