[e-lang] Looser memoization and constant-folding: will this work?

[Mark S. Miller]

This is in reply to old e-lang message
http://www.eros-os.org/pipermail/e-lang/2006-May/011208.html


Kevin Reid wrote:
> On May 6, 2006, at 12:50, Mark S. Miller wrote:
> 
>> Kevin Reid wrote:
>>>    - Is this correct?
>> I think so.
> 
> So far, testing agrees.
> 
>>>    - Is there a way to handle the DeepFrozen-returns-DeepFrozen case
>>> which does not involve two possibly-arbitrarily-expensive  
>>> evaluations?
> ...
>>        # map from msgs to good results
>>        def cache := [].asMap().diverge()
>>        # map from msgs to either null or [possible result]
>>        def dfCache := [].asMap().diverge()
> ...
>>                    if (dfCache[msg] =~ [oldResult]) {
>>                      if (df == oldResult) {
>>                        # Happened again, so memoize it for real
>>                        cache[msg] := df
> ...
> 
> Clever. Unfortunately, it won't work for constant folding since a  
> definite answer is needed the first time a particular call is seen.
> 
> I'll certainly try it for the memoizer, however.


The problem here is motivated by what we may call "on line optimized 
compiling". By "on line", I mean that the result of the constant folding 
optimization is not data, Hence "DeepFrozen" is stated above as the 
constraint, rather than the stricter "DeepPassByCopy" aka "Data". If these 
cases could be constant folded during the compilation of E-to-CL, then 
identity-bearing objects would appear literally in the resulting CL program. 
Such a CL program could not be printed or saved to a file.

As has been discussed, if we limit constant folding in the compiler to 
Data-returns-Data cases, i.e., the constant folding cases classically within 
the abilities of an offline compiler, then we could run the computation in a 
separately budgeted vat, and terminate it if it exceeds its budget. However, 
Kevin reports that many of the desirable constant folding cases for E-on-CL 
are the online cases. I suppose, since the E-to-CL compiler is part of the TCB 
and can be in bed with the E-on-CL runtime in magic ways, it could run the 
DeepFrozen-returning-DeepFrozen computation in the same vat but with a budget. 
If the computation exceeds its budget, the E-to-CL compiler could preemptively 
terminate it, in violation of the general E model. This would be safe since a 
partially completed DeepFrozen-returning-DeepFrozen computation cannot leave 
behind any reachable residual side effects.

Is this reasoning sound? Is it really safe to preemptively terminate such 
computation? If it is safe, should we make such budgeted/terminatable 
execution within a vat more generally available to E programmers? Is the 
inability to express such a thing, even though it's actually safe, a weakness 
in the current E model?

-- 
Text by me above is hereby placed in the public domain

     Cheers,
     --MarkM