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@viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
