Re: [Caja] Functional auditor for Cajita

[David-Sarah Hopwood]

David-Sarah Hopwood wrote:
> David-Sarah Hopwood wrote:
>> [Cross-posted to e-lang from google-caja-discuss. I suggest continuing on
>> e-lang, since there's not much that is Caja-specific here.]
> [...]
>> It's unclear whether we should call a function "purely functional"
>> if it is possible for it to be called with impure arguments (or use
>> captured values that are impure). If it can, and we require it to
>> have no side effects and be deterministic in that case, then almost
>> no useful functions are pure.
>>
>> To dodge this issue, let's provisionally call a function *instance*
>> "copacetic" [*] if:
>>  - that instance has only captured copacetic values, and
>>  - it has no side effects and is deterministic whenever it is
>>    only called with copacetic argument values, and
>>  - it uses no side-effecting or nondeterministic primitives.

I meant external side effects here.

> I should also have specified that
>  - primitive immutable values are copacetic,
>  - frozen objects that directly refer only to copacetic values
>    are copacetic,
>  - no values are copacetic unless they can be inferred to be so by
>    the rules above.
> 
> I think this corresponds to the Functional auditor in E (see
> <http://www.erights.org/elang/kernel/auditors/>). Is that correct?

To answer my own question, no -- mainly because there is an error in
my proposal.

The definitions of the relevant E auditors on that page are:

  Functional:
    Check that the object passes the DeepFrozen auditor and that the
    return value for each method is guarded by DeepFrozen.

  DeepFrozen:
    Check that all names accessed in the object expression are method
    arguments or declared final with def, and guarded by the DeepFrozen
    guard or by the guard for a primitive immutable type (such as int or
    char).

The first difference is the check that the return value for each
method of a Functional object is guarded by DeepFrozen. This should
correspond to a check that the return value of a copacetic function is
copacetic, which I forgot. Otherwise, a function like this:

  function() { return {}; }

would be audited as copacetic and run without throwing an exception,
which is wrong because each instance of {} is mutable.

So the (unoptimized) rewrite for

  const z = ...;
  var f = /*...@functional*/ function(x, y) { return x+y+z; };

should have been:

  const z = ...;
  var f = (___.checkCopacetic(z), ___.copaceticFunc(function(x, y) {
    ___.checkCopacetic(x); ___.checkCopacetic(y);
    return ___.checkCopacetic(x+y+z);
  }));

Notice the additional check on x+y+z.

(As it happens, the ECMAScript addition operator always returns either a
string or a number, which are primitive immutable values, therefore the
check can be optimized out in this case.)


The other difference between Functional and my proposal is that
copacetic is defined just in terms of itself; there are not two auditors
with one defined in terms of the other. In this respect, copacetic is
more conservative, and possibly less surprising -- but Functional is
not incorrect in being more lenient.

Consider the following example (in ECMAScript syntax since I'll just get
confused switching between ECMAScript and E):

  var f = /*...@functional*/ function() {
    return cajita.deepFreeze(function() { return {}; });
  };
  var obj = f(); obj.p = "surprise";

If this followed equivalent auditor definitions to E, it would pass the
audit checks, even though 'var obj = f(); obj.p = "surprise";' causes
an *internal* side-effect (that is, a side effect to an object that does
not escape).

Note that if we wrap this with another function g:

  var g = /*...@functional*/ function() {
    var f = /*...@functional*/ function() {
      return cajita.deepFreeze(function() { return {}; });
    };
    var obj = f(); obj.p = "surprise";
    return cajita.deepFreeze(obj);
  }

the object returned by g (with p:"surprise") is deep-frozen by the
time it is returned, so f and g arguably *are* functional, even
though the object f returns is *not* functional.


The auditors page also defines

  Deterministic:
    Check that each name accessed in the object expression is either:
      declared final with def and guarded by the DeepFrozen auditor; or
      visible only to this object expression and declared guarded by
      Deterministic.

but this is not included in Figure 3 showing the implications between
audited properties. I'm not yet clear on how Functional relates to
Deterministic.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

signature.asc
Description: OpenPGP digital signature