[E-Lang] The Granovetter Diagram in Russian, and more...

Jonathan S. Shapiro shap@cs.jhu.edu
Tue, 27 Feb 2001 15:12:45 -0500


Well, bother. Second try.


Here is a translation provided by one of my students [Anya Kanevsky],
who is a Russian native. She speaks computerese too. :-)
Sorry about the word wrap.

	shap


here ya go... 
it's a rough translation, and some of the choices i made
i'm not positive about... if you want i can take another
hour to run through it and fix the bugs i can find &
such...
-a



__________________________________________________
Do You Yahoo!?
Get email at your own domain with Yahoo! Mail. 
http://personal.mail.yahoo.com/




On the Concrete Strenght of Abstractions

author: Maksim Otstavnov
date of publication: 06.20.2000


Structural programming is very simple: instead of analyzing the
correctenss of
the program "in terms of execution," in procedural (?) terms ("going
through
the code or block diagram and inductively convincing yourself of its
"correctness"), we analyze the program's structure (by combining control
statements, operators and control structures through a rather sparse set
of
rules, we can deduce the correctness of the resulting program).

Despite the wide-spread myth, the theoritical selflessness of Dyjkstra
and the
methodological efforst of Gris(?) did not go to waste, and today formal
structural analysis of algorithms has a rather wide field of
application.
First, in creation of embedded systems (and understandably so: an
embedded
system, as opposed to a box with yet another @#!, is actually a part of
the
product, and the consequesces of it's application are the civil
responsibility
of the producer.  Here an as-is licesnse is no excuse). 

Secondly, in critical sites of manless systems of military purpose, for
example
in the kernel of built - in specialized operating systems (and here too
it is
understandable: a "frozen" or "failed" operating system in a flying
rocket will
inevitalby result in a known outcome. at least for the developer.)

Structural analysis aslo finds tool support (from common-application
languages,
a more or less widely known one is the rigidly objet-oriented Eiffel,
which
supports direct declaration of control statements (?), in particular
loop
invariants).

Structural analysis is what has been created and developed for coputer
science,
but does not yet exist for cryptology. In contrast with an "algorithm",
a
"protocol" as an object of analysis and construction can only be
discussed in
procedural terms: Anya said A, Boris thought B, Vera sent a message to
Anya in
secret from Boris... 

In a certain sense, computer science is a reduced area of cryptology -
numeration (?) of algorithms fulfilled by trusted calculation
participants. The
latter becomes, by the way, very much a supposition in a world where
third-party software is widely used, and in which network calculations
(in
client-server or agent-agency (?) architechrue) are becoming more the
rule than
the exception. 

A lot is missing that is necessary in order to generalize the results
obtained
in computer science to the field of cryptology.  Formalities for
denoting that
which is known and that wich is not to a given party participating in
the
calcuations. Formalities for direct assignment of theoretical-complexity
(?)
parameters of primitives (?). Simply an acceptable set of notations for
recording the protocols themselves. 

And yet, all this will have to be created.  It is possible to build one
protocol ad hoc. Maybe two, maybe three. But to set up a "production
flow"
(that will realize document digital trading [1] or implement en masse
"smart-contracts" [2], for example) will be impossible without a serious
theoretical base. 


Any effort in this direction is interesting. The most advanced attempt
to
create a notation for recording crypto-protocols known to me is the E
language
project. 

What is it like?

It would be rather presumptuous to attempt to give a language
description in
two pages (and a weekly computer digest is not intended for such
excersises),
however in two pages in is possible in interest and intrigue. 

Fig. 1 presents a rather convoluted "geneology" of E.  Most of the
languages
that are widely used today are procedural [1], deriving from ideas of
Alan
Turing.  An exception to that is LISP [2], which is funtional, that is
based on
the <greek>l-</greek>-enumeration of Alonzo Church.  A "functional"
programmer
thinks in terms of recursion and making values concrete, whereas the
"procedural" thinks in terms of iteration and assignment of values (and,
by the
way, for the two "structural" does not mean the exact same thing). 
However, no
one so far has cancelled the Turing-Church equivalence thesis.  The
thesis
asserts that an algorithm computed on a Turing machine can be written as
a
<greek>l</greek>-definition and visa versa. 

E, apparently vies for a greater <greek>l</greek>-faithfullness than
LISP,
judging by bright green Joule-Actors line rising directly to
l-enumeration. 

Actors is an experimental expansion of l-enumeration, created at MIT and
Stanford in the early nineties for experiments with the "actor" model of
collective calculations.  Actors are self-sufficient participants of the
calculations, cooperating through an asynchronous messaging, where the
amount
and the topology of cooperation between the actors within the system can
change
dynamically [3,4]. 

The actor model of calculaiton, as such, has found development in the
Joule
language, developed at Agorics, Inc.  In adition to the actor model,
Joule
"picked up" the idea of sequential implementation of the mandate
architecture
in the KeyKOS OS (better known in Russia by it's x86 clone with the
wonderful
name of EROS)(3). Unlike Actors, Joule is oriented towards practical
application while retaining strict verifiablity of the security model
[5]. 

Joule, in its turn, became the model for E[6].  E combines the
formalities of:

-object oriented programmint (abstraction and composition)

-security models (most of all mandate) of modern operating systems
(directing
the processes' powers) (?)

-financial cryptography (description of cooperative rights-transfer
protocols
between mutually suspicious parties).

Granovetter Diagrams

It is interesting that the developers take the base metaphor from a
completely
different field: in the early seventies, and american sociologist, Mark
Granovetter, offered to research the dynamics of the topology of
interpersonal
relations using a simple model, now referred to as the Granovetter
diagram.
Fig. 2 is a Granovetter diagram that registers a simple fact: Anya
intoduces
Boria to Vera. 

Mark Miller and his colleagues see the possibility of six
interpretations of
this formality. (formalism)

-as a stem in object calculations;

-as a mandate transfer (delegation of powers) in the OS security model;

-as a cryptographic protocol, wich realizes the distribution of powers;

-as an open key infrastructure element, in which the certificates act as
messages authorizing the participants. 

-as the rules of a game with mass participation

-and finally, as an element for building a financial instrument to
bearer. 

Is the last interpretation unevident?  But the authors insert another
schematic
(fig. 3), a special way of representing the simple assignment operator. 
By
"pacakging" the variable into a separate object and allowing access to
it
through object-functions ("installer" and "receiver" of a value), the
represent
a collection of these objects as a composite with facets - objects which
can be
referred to from an external context.  

This composite, as any object, represents a combination of state (value
of
internal variables) and behavior (code).  However, its behavior does not
only
depend on the content of the message received by the composite, but also
from
which "facet"(which of the individual objects that make it up) the
message was
directed to.  We now have a new dimension of freedom, a new degree of
flexibility!

After that, it turns out that the full protocol of call of an elementary
tool
to bearer can be depicted in a simple and gratifying way (fig4).  And
after
that, the fact, which moved me to writing this article in the first
place,
comes out. 
It turns out that generation of a "press" in E can be done in 26 lines
of code!
For comparison, consider that a reas mint out of any packet of
circulation/call(?) support of "digital currency" is several thousand
lines of
code in C++.

A real mint, of course, is somewhat more complex than Miller's
educational
example[6].  However, several weeks of experimentation with E show that
quite
practical protocols (circulation/call(?) of/to options, for example) can
be
coded in tens of lines, hundreds at most. 

Documentation, descriptions of E, code samples in E, and the source
executable
code of the programming environment (distributed under conditions of the
Mozilla license) can be found at www.erights.org. 

literature
[1] Ian Grigg. Digital trading//computerra #12, 3/30/98

[2] Nick Sabo.  Intelligent contracts. (fourth cost revolution) //
computerra
#38(266) 9/29/98

[3] G. Agha, I. A. Mason, S. Smith, and C. L. Talcott. Towards a theory
of
Actor Computation. In Concur '92, volume 630 of Lecture Notes in
Computer
Science, pages 565-579. Springer-Verlag, 1992.

[4] G. Agha, I. A. Mason, S. Smith, and C. L. Talcott. A Foundation for
Actor
Computation. Journal of Functional Programming, 1993.

[5] The Joule Manual. Agorics Tech Report ADd003.4P
(www.agorics.com/joule.html).

[6] Mark S. Miller, Chip Morningstar, Bill Frantz. Capability-based
Financial
Instruments // Financial Cryptography '00. Springer-Verlag, preparing
for
press. 


--------------------------------------
(1) line from <greek>l</greek>-enumeration to Algol-60 looks a strech:
with
some basis, only one construction of the latter can be called
unprocedural -
conditional assignment which goes very well within the context of
procedural
programming. 

(2) LISP is certainly a <greek>l</greek> language in it's origination
but using
the code corpus of LISP in order to get vivid samples of functional
programming
is a bad idea - LISP allows procedural style, and programmers have for
many
years been impudently using this minute weakness of LISP's developers. 
For
pedagogical purposes, in order to learn functional programming, ML for
example
is a good recommendation with its hard type checking.  

(3) see www.cis.upenn.edu/%7EKeyKOS.