Re: [Caja] Functional auditor for Cajita

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=10.1.1.23.9999>

would solve this problem. (It might be difficult to tame away all
indirect access to ===, though.)

Unfortunately egal isn't constant-time. Ideally, an implementation
would optimize it by unifying pointers when they are found to be egal;
in that case it still wouldn't be constant-time, but repeated tests
of egality would be efficient, and redundant subgraphs could be
garbage-collected. This would be similar to hash-consing but possibly
less expensive (depending on whether pointers can be efficiently
unified). Unification can also potentially be done on garbage collection,
as suggested in Baker's paper.


[I was disturbed to see that the first Google hit for "egal operator"
is a travel agent, not even with the same spelling. What is the world
coming to -- do people have no appreciation for computer science?]

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

_______________________________________________
e-lang mailing list
[email protected]
http://www.eros-os.org/mailman/listinfo/e-lang

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.12 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iF4EAREIAAYFAkse7/IACgkQWUc8YzyzqAeUsQD9FgLL5PRihOWzw9p5fg+7RLgj
7CLzMvmhN5ancMgDYRUBAKIpB8CdaMb/GV/NqfIcdKIP2mkU1HspB7+3SHxJysZ5
=SpiN
-----END PGP SIGNATURE-----