web-calculus

Calculus

2005-04-07

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

The web-calculus is defined over a directed graph. Each node in the graph is a document Node. Each edge in the graph 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

The web-calculus operates on a directed graph. Each edge in the graph is a capability that both designates and authorizes access to its target. 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. The web-calculus 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 nodes in the graph. Popular examples include spiders that search a graph for a node that meets specified criteria. 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 web-calculus is an interface model; it defines how computation is requested, not executed.

Fig. 1: A web-calculus wrapper

Structure

A web is a directed graph composed of immutable document Nodes linked by possibly mutable edges. A Branch labels an outbound edge of a node.

This graph structure enables reuse of document schemas for defining the structure of a web. In this view, a document is simply an acyclic subgraph of a web.

Each edge may have an associated closure. 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 is either a node or an edge. Invocation of a closure may grow the web, and/or reassign existing edges.

Fig. 2: A web diagram

The target node of an edge with an associated closure is compatible with the <http://web-calculus.org/ref/Declaration> schema. A node is compatible with a schema if it is of the schema, or if it has a 'super' Branch whose target node is compatible with the schema.

Operation

A web-calculus operation operates on an edge. A small, fixed set of operations is defined.

The GET operation gets the current target node of an edge. [HTTP GET]

For example, applying the GET operation to the 'value' edge depicted in Fig. 2 returns a <http://web-calculus.org/string/String> specifying the current redirect target.

The purpose of the GET operation is to provide the graph introspection required to support partial-understanding applications and interface refactoring. The GET operation is idempotent.

The POST operation invokes an edge's closure. 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 error, the return is a <http://web-calculus.org/ref/Smashed> specifying the error. [HTTP POST]

For example, applying the POST operation to the 'assign' edge depicted in Fig. 2, modifies the redirect target.

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

Implementation

This section shows how various programming model constructs are represented in the web-calculus.

Hypertext

A hypertext model is a web with no closures. A hypertext model only supports the GET operation.

HTML is an example of a hypertext model.

Representational State Transfer (REST)

The web-calculus is a REST model. An edge is a REST resource. A node is a REST representation.

The web-calculus 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 internal structure of a representation (Structure)
• a mechanism for defining the structure of a web of resources (schema)
• a generic interface for distributed computation (Operation)

HTTP is an example of a REST model.

Remote Procedure Call (RPC)

An RPC model is a single-rooted, one level deep web. Each edge of the root node has a closure that implements a procedure. The edge name is the procedure name. 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 edge 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 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 web focused on a class-oriented programming environment. Each class is a single rooted tree. Each attribute, association, or operation is an edge. The edge is named with the name of the attribute, association or operation. Only an operation edge has a closure.

The above UML class diagram depicts node schemas used in the web depicted in Fig. 2.

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.

Copyright 2003-2005 Waterken Inc. All rights reserved.