User-agent: mu4e 1.4.13; emacs 27.1
From: Christopher Lemmer Webber <cwebber@dustycloud.org>
To: cap-talk@googlegroups.com
Subject: Propagators and ocaps
Date: Thu, 04 Feb 2021 13:34:27 -0500
Message-ID: <871rdv65sc.fsf@dustycloud.org>
MIME-Version: 1.0
Content-Type: text/plain

I'm continuing a bit from this conversation:

  https://groups.google.com/g/cap-talk/c/Rye8xI1TSnU/m/1g03OG5tBAAJ

I've mentioned that I've been making progress with Propagators on top of
Spritely Goblins.  I haven't published it yet, but I am thinking of
naming this implementation "Spritely Brainy", so that finally we can
know we have a brain in a vat.  (Whether the brain itself knows is
another question.)

If you are interested in propagators, here are three good resources:

 - This talk by Gerald Sussman: "We Really Don't Know How to Compute!"
   It's about several things, but especially propagators:
     https://www.youtube.com/watch?v=Rk76BurH384

 - The most current iteration of propagator design comes from Alexey
   Radul's dissertation, which makes the advancement in having
   propagators not only supporting complete values, but accruing
   *partial* non-contradictory information about a value:

     http://web.mit.edu/~axch/www/phd-thesis.pdf

 - To really see what you can do with this, Leilani Gilpin's
   dissertation "Anomaly Detection Through Explanations" seems a really
   interesting resource (which I have only skimmed so far, but plan to
   read fully):

     https://groups.csail.mit.edu/mac/users/gjs/lgilpin-PhD-EECS-Sept2020.pdf

So, why should we care about propagators?:

 - Alexey demonstrates how propagators are the generalization of several
   kinds of programming systems in his dissertation: logic programming,
   functional reactive programming, constraint solvers including type
   inference, rule-based systems, and even probabalistic programming can
   all be nicely implemented on top.  (Except that propagators sometimes
   even seem to do better than the present approaches: for instance, in
   FRP-on-propagators as Alexey describes it, cycles in the graph are no
   problem!)

 - Propagators and the cells they talk to can be both easily modeled on
   top of "classic actors", making them a good fit for current ocap
   systems.  (Here's one example: deliver your witness testimony to the
   capability that writes to this cell and then the propagtor-detective
   will account for it!)

 - The mechanism that Alexey describes in his dissertation for
   propagation can be easily modeled on top of a "vat churn", which both
   Agoric and Spritely Goblins have tooling for (ie, run local message
   sending in the network until quiescence)

 - Partial information is considered still useful.  If we can narrow a
   range of possibilities, that might be useful to know and query... it
   might give us clues about which areas we should do more searching and
   what we shouldn't bother with.

 - It's possible to see *where* in a propagator network recursion might
   occur, and even limit the amount of search space easily, helping
   mitigate some of the "uncanny valley" aspects of logic programming
   that MarkM has mentioned (I think)

 - Alexey's version of propagators allow for propagation of the
   *sources* of where corroborating information comes in, along with
   with truth maintenance systems which allowing exploring different
   worldviews.  This can be done manually by the programmer.

 - But it can also be done automatically!  Set up an "ambiguity
   operator" propagator which auto-explores the consequences of
   different worldviews, and can even make note of which combinations
   are contradictory so it doesn't re-explore those accidentally.

 - I believe the space of exploring explainable AI is worthwhile, *even
   if not possible to be perfect*, for the same reasons that it is
   worthwhile for humans to do their best to explain themselves, even if
   they are not perfect.

Since these compose well with present exploration of ocap systems, and
propagators are fairly easy to build once the core ideas are known, it
seems worthwhile for us to add them.

There is more to say.  But perhaps I should get my implementation of
Brainy out there so I can say it better.

 - Chris