Waterken^TM Web

Calculus

2003-03-22

This specification defines an application interface model, the web-calculus, that is independent of the application programming model. The model enables reasoning about the functionality and security of an application interface.

Abstract

A Waterken^TM Web is a directed graph. Every node in the graph is a document Node. Each node may be associated with a closure. Applications interact by traversing the graph and/or sending invocations to a target closure.

Overview

Design goals

Capability-based security

A Waterken^TM Web is a directed graph. Every edge in the graph is a capability that both designates and authorizes access to a target node. Accessing a target node is only possible by traversing an edge that terminates at the node. Starting from a source node, only edges emanating from that node are traversable. This security primitive underlies capability-based security. Access control is achieved by constructing a graph that simultaneously defines and enforces the access policy.

Meta-model

Many different application programming models exist, each with its own unique constructs. Describing these constructs in terms of a more primitive model enables application interoperation, without requiring prior understanding of foreign constructs. A Waterken^TM Web is a meta-model for describing how an application can interact with a foreign programming construct.

Partial understanding

Many useful applications can operate on a graph using only partial understanding of the node schemas in the graph. Popular examples include spiders that search a graph for a node of a particular schema. In order to function, a partial-understanding application needs to discover and follow the outbound edges of a node of unknown schema.

Interface refactoring

Many existing security models operate in terms of statically defined authority bundles. In an ACL model, an access control list controls access to a statically defined object. In an object capability model, a capability controls access to a statically defined facet. Anticipating all of the needed authority divisions in an application at design time is not feasible. Changes in application requirements, or usage scenarios, will require new authority divisions.

Adapting an application with static authority divisions to a new usage requires the creation of protection proxies. This solution engenders difficult performance and deployment issues. Requiring the hosting of a long-lived protection proxy, in order to delegate a portion of a held authority, creates implementation pressure that works against the practice of the principle of least privilege. This implementation pressure can be eliminated if the messaging model allows a client to refactor held authority. The client can then directly delegate portions of a held authority.

Description

The Waterken^TM Web calculus is an interface model; it defines how computation is requested, not executed.

A Waterken^TM Web calculus wrapper

Structure

A Waterken^TM Web is a directed graph. The target node of an edge may be reassigned any number of times. The source node of an edge is forever fixed.

Every node is a document Node. The Branches of a node are the edges of the graph. Each node may have an associated closure. The convention is to name an edge with a verb if the referred to node has an associated closure; otherwise, the edge is named with a noun.

This graph structure enables the Waterken^TM Doc Schema to be reused for defining the structure of a Waterken^TM Web, in addition to its role of defining the structure of a document. In this view, a document is simply a snapshot of an acyclic subgraph of a Waterken^TM Web.

A closure is an object with encapsulated state and a single anonymous method. The method has a fixed input parameter list and a single output parameter. [defun] Each argument in a closure invocation is a node. Invocation of a closure may cause new nodes to be created, and/or existing edges to be reassigned.

Fig. 1: A web representation

Operation

An operation is sent along a path to a target. The path begins at a source node and follows zero or more edges to the target. If a path ends with a /, the target is a node; otherwise, the target is an edge.

When following the path from a source node to a target, the operation dispatcher checks the current Node for a Branch whose Name matches the next segment in the path. If a matching Branch is found, the operation dispatcher proceeds along the Branch with the remaining portion of the path. If no matching Branch is found, the operation dispatcher checks the current Node for a super Branch. If a super Branch exists, the operation dispatcher proceeds along the super Branch with the current path. If no super Branch exists, the operation dispatcher returns a <http://waterken.com/doc/pointer/Broken> node. If a Node has multiple super Branches, they are checked in a pre-order traversal until a matching Branch is found. A super Branch is not itself directly addressable. A path containing a super segment is invalid.

A small, fixed set of operations is defined.

The GET operation creates a snapshot of the target node. In the snapshot node, all outbound edges are fixed to their target node and cannot be reassigned. The snapshot node has no closure. [HTTP GET]

For example, sending the GET operation to the graph depicted in Fig. 1 returns a snapshot node that links to the current target nodes of the spawn, withdraw, brand and balance edges.

The purpose of the GET operation is to provide the graph introspection required to support partial-understanding applications, such as spiders.

The POST operation invokes the closure of the target node. The POST operation carries the list of arguments for the invocation. The return from the invocation is the operation return. If the invocation produces an exception, the return is a <http://waterken.com/adt/promise/Smashed> node containing the thrown exception. [HTTP POST]

For example, sending the POST operation to the graph depicted in Fig. 1, with the path 'withdraw/', invokes the <http://waterken.com/iou/Account-withdraw> closure. This invocation returns a new <http://waterken.com/iou/Hold> node that contains credit withdrawn from the source <http://waterken.com/iou/Account>.

The purpose of the POST operation is to support graph mutation. POST can only be applied to a node with a closure.

The EXPECT operation checks the schema of the target node. The EXPECT operation carries an expected schema URI. If the target node is compatible with the identified schema, the target node is returned; otherwise, a <http://waterken.com/doc/pointer/Broken> node is returned. A target node is compatible with a given schema if the target node is of that schema, or if the target node has a super branch whose child node is compatible with that schema. [ARE-YOU]

For example, sending the EXPECT operation to the graph depicted in Fig. 1, with the argument <http://waterken.com/iou/Account> returns the target node. Providing any other schema URI as an argument returns a <http://waterken.com/doc/pointer/Broken> node.

The purpose of the EXPECT operation is to support dynamic type checking.

The EXTRACT operation extracts an edge or node from the graph.

For example, sending the EXTRACT operation to the graph depicted in Fig. 1, with the path 'balance', returns an <http://waterken.com/script/Edge> node. Sending EXTRACT to the returned node, with the path 'target/', returns the current target node of the balance edge.

If instead, the path 'balance/' is sent in the EXTRACT operation, the current <http://waterken.com/Integer> node is returned.

The purpose of the EXTRACT operation is to enable interface refactoring by client code.

An edge may exist without being assigned to a target node. The SETTLE operation allows a client to register an observer that will be notified after the edge is assigned to a target node. The SETTLE operation carries this observer node. The observer node MUST be compatible with the <http://waterken.com/adt/promise/Resolver> schema. [__whenMoreResolved]

For example, invoking the <http://waterken.com/iou/Account-withdraw> closure returns a new <http://waterken.com/iou/Hold> node. Another node may have an edge that will eventually be assigned to the new node. A client with access to the edge could arrange to be notified of the completion of the withdrawal invocation by sending the SETTLE operation along the edge.

The purpose of the SETTLE operation is to enable asynchronous logical dependency resolution.

Implementation

This section shows how various programming model constructs are represented in the Waterken^TM Web model.

Hypertext

A hypertext model is a Waterken^TM Web in which no lambdas are defined. A hypertext model only supports the GET operation.

HTML is an example of a hypertext model.

Representational State Transfer (REST)

The Waterken^TM Web model is a REST model. Every Waterken^TM Web node is a REST resource. A node snapshot is a REST representation.

The Waterken^TM Web model is an application of REST design principles to distributed computation. This application extends REST with:

• a security model (capability-based security)
• a model for the external structure of a resource (Structure)
• a model for the internal structure of a representation (snapshot)
• a mechanism for defining the structure of a web of resources (schema)
• a navigation standard for a web of resources (dispatch)
• a generic interface for distributed computation (generic)

HTTP is an example of a REST model.

Remote Procedure Call (RPC)

An RPC model is a Waterken^TM Web in which each site has a root node that links to all other nodes on the site. Each child node has a lambda that implements the procedure. Each edge is named with the name of the procedure. An RPC model only supports the POST operation.

Typically, an RPC model only allows nodes from a fixed set of schemas as parameters. The node schemas typically correspond to the primitive types from the C programming language. This restriction of parameter node schemas promotes the design of lambdas that do fine-grained graph manipulations.

XML-RPC is an example of an RPC model.

Document Exchange Model (DEM)

A DEM model is like an RPC model where the edges are named using the schema of the input document, instead of the target procedure name. A DEM model only supports the POST operation.

Unlike an RPC model, a DEM model allows nodes of arbitrary schema as parameters. Typically, a DEM model will combine multiple parameters into a single complex parameter that is the exchanged document. Allowing more complex parameters promotes the design of lambdas that do large-grained graph manipulations.

SOAP is an example of a DEM model.

Network Object Model (NOM)

A NOM model is like an RPC model that has been divided according to encapsulated state. Each miniature RPC system is called an object. Each root node is called a vtable, and each child node a method. A NOM model only supports the POST operation.

A NOM site is a dynamically growing set of disjoint graphs. Each graph represents an object. An application can jump between graphs by receiving a link from an invoked closure. The ability to dynamically grow the set of message targets is a significant difference between the NOM and RPC models.

Like a DEM model, a NOM model allows nodes of arbitrary schema as parameters; any type of object can be sent as an argument. In the NOM model, some objects are pass-by-reference and others are pass-by-copy. When a pass-by-copy object is sent as an argument, its state is transported between sites. A standard serialization method is defined for decomposing object state into a Waterken^TM Web, and then reconstructing the object.

Java^TM RMI is an example of a NOM model.

Concurrent Constraint Programming (CCP)

From a messaging perspective, a CCP model is the same as a NOM model. Each miniature RPC system is grouped around a logic variable in the same way that a NOM object is grouped around encapsulated state. The difference between the two models is in how the programming logic of each lambda is expressed. A CCP model only supports the POST operation.

Mozart is an example of a CCP model.

Unified Modeling Language (UML)

A UML class diagram is a Waterken^TM Web focused on a class-oriented programming environment. Each class is a single rooted tree. Each attribute, association, or operation is an edge pointing to a child node. The edge is named with the name of the attribute, association or operation. Only an operation child node has a closure.

The above UML class diagram depicts node schemas used in the Waterken^TM Web depicted in Fig. 1.

Footnotes

[defun] The term "closure", as used in this specification, is similar to what is returned by the defun function in LISP. The term "lambda" refers to the program code that defines what a particular closure does.

[HTTP GET] The GET message is similar in spirit to the GET message used in HTTP.

[HTTP POST] The POST message is similar in spirit to the POST message used in HTTP.

[ARE-YOU] The EXPECT message is similar in spirit to the ARE-YOU message used in ACT 1.

[__whenMoreResolved] The SETTLE message is similar in spirit to the __whenMoreResolved message used in the E language.

Copyright 2003 Waterken Inc. All rights reserved.