[viff-devel] Small VIFF language parser

[Janus Dam Nielsen]

>>> 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.
> I am not aware of any of-the-shelf technique for this, but it would  
> be a fun problem to solve.
> Define a cost function:
> Gamma(+) = 5
> Gamma(-) = 5
> Gamma(*) = 10
> I have no clue if these costs reflect the relative cost among the  
> operators, please correct me.
>
> Given the size of an expressions that naturally appear in programs  
> I think it is reasonable efficient to compute all permutations of  
> the expression under the distributive law and then pick any one of  
> those with the lowest cost under the Gamma cost function.
>
> This is worstcase exponential, but given the size of expressions  
> programmers are inclined to write in a program, then I don't think  
> it will be a problem.
>
> We need to combine this with elimination of common subexpressions.


I have made a limited(yet) implementation of this in SMCL which can  
rewrite

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

Rewriting this to
   x = a * (y - x) + x

should be pretty straight forward. I'll look at that tomorrow.