[EMAIL PROTECTED] writes: Hi everybody,
> 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. Right, good point! We should do that. Maybe a smart compiler could do the necessary deductions automatically? So it would go from x = a * y + (1 - a) * x to x = a * y + x - a * x to x = a * (y - x) + x via knowledge about the distrubutive law and knowledge about the cost of addition/subtraction versus multiplication. I guess this is where the compiler guys get into the picture -- I'm Cc'in Janus, Michael and Sigurd in case they have any input on this. > 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 Yeah, ups! :-) >> 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). Outputting values (or causing any other side-effects) is a problem. But a program where the side-effects depend on a secret shared variable is not secure anyway. I guess the best thing would be to forbid side-effects in both branches and tell the programmer that on compile time. > But I'm worried that the naive approach won't give us any reasonable > efficiency except for trivial examples. Yeah, that is a concern :-( > [...]. 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 Yes, when x is an assignment-target in both branches we should collapse the two statements into one assignment. > 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) Wow, this is quickly getting complicated! :-) In the prototype I tried to do the simplest thing that could possible work, and for dealing with cases like the above I opted for simply writing out all the assignments. > 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). There must be compiler techniques that can recognize things like this, pull out the common parts, and make sure that everything is only computed once. To do that we of course rely heavily on an assumption that e*x always gives the same result -- in other words that the multiplication function is pure and causes no side-effects. So the functional language community might have some tricks we can use to optimize such expressions. > 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? I don't know, but I can tell that we need more thinking and more experimenting here... :-) I'm a bit reluctant to go ahead with the simple prototype since we already have a compiler from SMCL, even though I cannot find the source for it here (the smclc.tar.gz file lacks a smcl.jar file): http://www.brics.dk/SMCL/ Janus asked me why I hadn't just changed the backend of that one, and part of the reason is that I find no source and part of the reason is that I just wanted to play around with a small system. Depending on how much the SMCL compiler can do, it would be stupid to throw it away. But on the other hand we might be able to reimplement things quickly in Python from which we can work directly with the Python AST. I guess we need more comments from the Janus and Michael. -- Martin Geisler _______________________________________________ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
