[e-lang] [Caja] Functional auditor for Cajita

David-Sarah Hopwood david-sarah at jacaranda.org
Thu Dec 10 16:46:35 PST 2009

David-Sarah Hopwood wrote:
> David-Sarah Hopwood wrote:
>> It would be possible to make the argument and result checks optional
>> depending on the function annotation: say, /*@pure*/ includes them but
>> /*@functional*/ doesn't. (The environment checks would be the same,
>> and both /*@pure*/ and /*@functional*/ would mark instances as
>> copacetic.)
>> In that case, /*@pure*/ would imply unconditional determinism
>> (referential transparency), whereas /*@functional*/ would only imply
>> determinism for calls for which all arguments are copacetic.
> In fact I'm wrong here, as shown by this example:
>   /*@pure*/ function f() { return cajita.deepFreeze({}); }
>   const a = f();
>   const b = f();
>   /*@pure*/ function g(x) { return x === a; }
>   g(a); // true
>   g(b); // false
> Since a and b are observably different, either f or g must not
> be referentially transparent.
> A Cajita that only exposed an egal operator, as defined in
>   Henry Baker,
>   "Equal Rights for Functional Objects, or The More Things Change,
>    The More They Are the Same"
>   <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=>
> would solve this problem. (It might be difficult to tame away all
> indirect access to ===, though.)

A more lenient option is to prohibit access to === and !== only to
copacetic functions. So, the above code would be invalid because
g is annotated as @pure, therefore required to be copacetic.
This would transitively deny access to === and !== as long as no
tamed objects are incorrectly marked as being copacetic.
(The fact that some code has access to === and !== precludes the
optimizations I referred to in my previous post, but those optimizations
would not be available in an ECMAScript implementation anyway.)

@pure and @functional functions would still be able to use egal,
if its implementation were "deemed" copacetic (exempted from the
restriction on === and !==).

From now on, I'll rename copacetic to deep-frozen, since it is close
enough to the E concept that I don't think there will be any confusion.
(Bye bye, copacetic. We'll miss you.)
I'll also rename the @functional annotation to @deepFrozen.

I'll write out the differences between the auditing in E, Joe-E, and
my proposal for Cajita in a separate post. In the meantime, here is most
of the run-time support that could be used to implement deep-frozen
auditing in Cajita:

// Using <http://wiki.ecmascript.org/doku.php?id=strawman:weak_references>.
function makeWeakTable() { return new EphemeronTable(true); }

 * An auditDeepFrozen entry has the value:
 *   false or a sour pumpkin, if the key is known not to be deepFrozen
 *   true or a tasty pumpkin, if the key is known to be deepFrozen.
 * The objects traversed in a given checkDeepFrozen run are set
 * to a unique pumpkin object, which is used to detect loops.
 * A "tasty pumpkin" is an object with a 'tasty' field set to
 * true, indicating that its run succeeded. A "sour pumpkin" has
 * its 'tasty' field set to false. If a run fails, the entries
 * pointing to its pumpkin (which has no 'tasty' field) are left
 * in the table but are ignored, i.e. treated as equivalent to a
 * missing entry, on subsequent runs.
/*const*/ var auditDeepFrozen = makeWeakTable();

/*const*/ var tastyPumpkin = Object.freeze({ tasty: true });
/*const*/ var sourPumpkin = Object.freeze({ tasty: false });

 * A functionMarks entry has the value:
 *   'deepFrozen', if marked as @deepFrozen
 *   'pure',       if marked as @pure.
/*const*/ var functionMarks = makeWeakTable();

 * Check that obj satisfies the conditions to be deepFrozen, and throw
 * AuditError if not. Memoize any results for non-primitive objects in
 * the auditDeepFrozen table.
function checkDeepFrozen(obj) {
  if (isPrimitive(obj)) return;

  /*const*/ var pumpkin = {};
  if (isDeepFrozen(obj, pumpkin)) {
    // Mark all visited objects that participated in a loop as deepFrozen.
    pumpkin.tasty = true;
  throw new AuditError();

 * Return true if obj is definitely deepFrozen, false if it definitely
 * isn't, and pumpkin if we encountered a loop.
function isDeepFrozen(obj, pumpkin) {
  var t = auditDeepFrozen.get(obj);
  if (t) {
    /*const*/ var tasty = t.tasty;
    if (tasty !== undefined) return tasty;
    if (t === pumpkin) return t;

  test: {
    // Function instances must be marked in order to be deepFrozen.
    if (typeof obj === 'function' && !functionMarks.get(obj))
      break test;

    // Mark that we are checking obj, to avoid infinite loops.
    // Progress depends on single-threadedness; multiple threads
    // could livelock by treading on each other's pumpkins.
    auditDeepFrozen.put(obj, pumpkin);

    t = isDeepFrozen(Object.getPrototypeOf(obj), pumpkin);
    var loopy = t === pumpkin;
    if (!t || !Object.isFrozen(obj)) break test;

    /*const*/ var ownprops = Object.getOwnPropertyNames(obj);
    for (var i = 0; i < ownprops.length; i++) {
      /*const*/ var prop = ownprops[i];
      /*const*/ var desc = Object.getOwnPropertyDescriptor(obj, prop);

      if ('value' in desc) {
        t = isDeepFrozen(desc.value, pumpkin);
        loopy = loopy || t === pumpkin;
        if (!t) break test;
      } else {
        t = isDeepFrozen(desc.get, pumpkin);
        loopy = loopy || t === pumpkin;

        // It would be sufficient to check that the setter is deepFrozen,
        // but a setter that doesn't actually set anything is misleading.
        if (!t || desc.set !== null) break test;

    // If the traversal from this object did not hit a loop, then we can
    // memoize it as deepFrozen even if the overall checkDeepFrozen run
    // fails.
    if (loopy) return pumpkin;
    auditDeepFrozen.put(obj, tastyPumpkin);
    return true;

  // break test:
  auditDeepFrozen.put(obj, sourPumpkin);
  return false;

 * Check that a chain of property accesses starting from obj, and
 * using property names given by subsequent arguments, is guaranteed
 * to give a constant result. No getters are invoked during the check.
 * This can be used to relax the condition that all accesses to captured
 * variables of a deepFrozen function are deepFrozen. For instance,
 * if a @deepFrozen function uses foo only by accessing foo.bar.baz,
 * then rather than requiring foo to be deepFrozen, we can require
 * just that foo.bar.baz gives a constant result.
 * I.e. we verify that foo is statically const, and generate a call to
 * checkConstant(foo, 'bar', 'baz') for each scope in which foo
 * might be different.
function checkConstant(obj /*, ...*/) {
  var i = 1;
  test: while (true) {
    if (i >= arguments.length) return;

    /*const*/ var t = auditDeepFrozen.get(obj);
    if (t && t.tasty) return;  // optimization

    /*const*/ var prop = arguments[i];

    var desc;
    try {
      desc = Object.getOwnPropertyDescriptor(obj, prop);
    } catch (e) {
      // getOwnPropertyDescriptor *should* only throw if Type(obj) is not
      // Object. However the ES5 spec doesn't explicitly say that
      // [[GetOwnProperty]] for a host object can't throw (even though
      // that would break stuff).

      if (isPrimitive(obj)) return;
      break test;

    if (desc === undefined) {
      // If prop doesn't exist as an own-property, then the object must be
      // non-Extensible, and we continue using the object's prototype.
      // If the property doesn't exist in the prototype chain and all
      // objects in the chain are non-Extensible, then obj will eventually
      // be null, which is allowed by the primitive case above.

      if (Object.isExtensible(obj)) break test;
      obj = Object.getPrototypeOf(obj);

    // The property must be non-Configurable. If it is a data property,
    // it must also be non-Writable, and we continue checking that
    // subsequent property accesses on the value are constant. If it
    // is an accessor property, we conservatively require its getter
    // to be deepFrozen (note that the getter may be null).

    if (desc.configurable !== false) break test;
    if ('value' in desc) {
      if (desc.writable !== false) break test;
      obj = desc.value;
      i++;  // next access
    } else {

      // Since the getter is deepFrozen, there is no need to check
      // subsequent properties in the chain (which is lucky, because
      // we can't).

  // break test:
  auditDeepFrozen.put(obj, sourPumpkin);
  throw new AuditError();

function isPrimitive(obj) {
  if (obj == null) return true;  // null and undefined
  /*const*/ var t = typeof obj;
  return t === 'number' || t === 'string' || t === 'boolean';

 * This would be called by the rewritten code that instantiates an
 * annotated function.
function markFunc(mark, obj) {
  if (typeof obj !== 'function' || functionMarks.get(obj) !== undefined)
    throw new TypeError();

  functionMarks.put(obj, mark);

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
Url : http://www.eros-os.org/pipermail/e-lang/attachments/20091211/089e6a9d/attachment.bin 

More information about the e-lang mailing list