Security, parallelism

[Laurent Martelli]

>>>>> "Tril" == Tril  <dem@tunes.org> writes:

    Tril> Currently we have the "procedure" as a high level
    Tril> abstraction for serial execution.  It consists of an ordered
    Tril> collection of instructions.  The "ordered" property of the
    Tril> collection means there is a relation of "sequence" between
    Tril> every two consecutive members of the collection.

    Tril> In the new system, use an unordered collection of
    Tril> instructions.  "Unordered" means no relation of sequence
    Tril> exists, therefore no dependency of one instruction on the
    Tril> previous.  Where there is no dependency, the compiler can
    Tril> assume the instructions can be scheduled in parallel.  It
    Tril> seems pretty simple to me, but all languages (?) seem to
    Tril> include an implicit dependency of serialization between
    Tril> every instruction, which is why it is so hard to program
    Tril> parallel software.

    Tril> It also would help to have meta-programming utilities which
    Tril> can take an abstract algorithm, and translate it into any
    Tril> number of threads of execution.  That would be hard, but
    Tril> possible if the language didn't imply dependencies.

I agree completly on this point. Implicit order is painfull. Ideally,
a procedure should not be represented by a list of instructions, but
by a graph of instructions, with vertices representing dependencies
between instructions (that instruction must be executed before this
one). 

C is a poor language because it has the implicit order built
in. However, Lisp does not have this problem. You just have to add a
function unordered-execute which takes a list of instructions to be
executed without any special order. I have the intuition that you have
unordered-execute and the usual order-execute, it is equivalent to
having a graph.

    >> But there's however a problem : how can you be sure that the
    >> code does not do more than what it is supposed to do?

    Tril> That sounds like a hard question.  I think the best answer
    Tril> is to not have any code at all, only the specification.  My
    Tril> answer seems very confusing.  How about this: Every program
    Tril> is broken down into pieces, right?  Each piece has a
    Tril> precondition and postcondition.  Well at some point there
    Tril> are axioms.  These are basic operations that aren't broken
    Tril> down into smaller pieces.  In fact all they consist of is a
    Tril> precondition and a postcondition.  (Usually they have a
    Tril> name, too, but see my other posts for my ideas on getting
    Tril> rid of named functions.)  Because axioms are not broken
    Tril> down, you don't have their source, and you don't know how
    Tril> they work.  You just assume they do.

    Tril> All the axioms are implemented on your computer, and you
    Tril> have already decided that they do what they say. (By trying
    Tril> it over and over, or reading the source)

Yes, ideally, pres and posts should be sufficient. The system should
be able to build the implementation from the axioms that it
has. There's however a big problem of computation time. But I do not
give up. I believe that with good heuristics, much of the work of
implementing a pre-post could be done automatically. After all, we
always repeat the same design patterns all the time. I had found on
the web the thesis of somebody who tried to compute implementations
from pairs of input and output. It don't think it is usable, but
working on pres and posts should give some results.


Laurent