Use case#

Modules should enable:

  • Combining related definitions
  • Code reuse
  • Abstract data types
  • Encapsulating state

A typical problem which modules might solve is: create an implementation of a reader/writer lock, an implementation of a binary search tree, and a mutable binary search tree which combines the two.

The essential technical difference between Packages and modules is that packages enable compile-time instantiation and composition while modules enable run-time instantiation and composition.

Questions#

Questions to answer:

  • Are modules protected from external termination?
  • Do modules have a goal expression, and if so what are its semantics?
  • Can we get by with records or some more fundamental data structure instead?
  • Are modules first-class?
  • Are modules parameterized (ala ML)?
  • Do we support module inheritence? Is this inheritance first-class (i.e. mixins)?
  • Are modules related to the type system?
  • How do modules relate to concurrency? I.e. should modules provide syntactic sugar for Erlang-like single-threaded processes (actors)?

Jay's Proposal#

Module declaration

module module_name(parameters) exports {list of exported names} =
   set of defs and vals
   goal expression

Creating an instance

val b = module_name(n)

Exclusive modules#

modules exclusive xxx ...
means at most one def in a given module instance can evaluate simultaneously. This is very similar to an actor.
module xxx ... =
   def exclusive f ...
means at most one call to f can evaluate simultaneously for a given module instance.

Questions:

  • What about recursive definitions?
  • How can one definition depend on another (e.g. Semaphore.acquire may depend on Semaphore.release), like a monitor? How does a definition know when to release exclusive access?
  • When are transactions more appropriate?

Nested modules#

Modules can be nested:
module concBST() =
  module BST() = ...
  module ReaderWriter() = ...

Parameterized modules#

Modules may have parameters:
module DiningPhil(n) = ... -- run N dining philosophers

Futures#

Is a module available before its contents? For example:

module M() exports {f,v} =
  val v = Rtimer(1000)
  def f() = v
  stop

M() >m> ( m.f() | m.v )

This violates the structured dependency introduced by the pruning combinator. Normally in f <x< g we know that only f can depend on x. Modules should preserve something of this dependency structure.

Modules versus Sites#

In order to better understand modules, we should identify how they relate to the existing abstraction mechanisms (definitions and sites). Are modules merely a way to group related definitions? Are they a way to define sites in Orc? Are they something in between?

We have agreed on the following general conception of modules:

  • A module consists of a set of names, definitions for those names (called methods), and a body (goal expression).
  • A module may be invoked (as a constructor). This initiates evaluation of the goal expression and returns a module instance which provides access to methods.
  • Methods can be invoked on an instance using dot notation.

How do modules compare to sites and defs? Some basic features are uncontroversial:

defmodule constructormodule methodsite
YYYYis a value
NYNYcalls are strict
N-YYcan use . operator
YNYNmultiple returns
reduces to haltreduces to haltreduces to haltraises a halt eventhow is termination detected?
YYYsometimescan take logical time

That leaves the following features to consider:

defmodule constructormodule methodsite
N??Ycalls are protected from termination
N??-may hold unbound free variables
--?Ybacking process (goal expression) protected from termination
Y??sometimesgarbage-collected when unused

The most important question is how termination is handled, which is considered in the next section.

Termination Protection#

Our actor-style implementation of the reader/writer lock involves a process which serializes modifications to the lock. Users of this library must take care not to accidentally terminate this process. This is a leaky abstraction, since users can tell whether the implementation uses locks or a backing process to serialize mutations.

Modules could potentially solve this problem, by imposing the rule that the goal expression of a module instance is protected from forced (external) termination. In essense, this goal expression becomes a site, running independently of the main Orc program, communicating with it only via shared sites. The only way to terminate such an expression is via some kind of signal, which it is free to ignore. This is not a very satisfactory solution, since explicitly managing termination is akin to explicitly managing memory and has all the same compositionality problems.

Automatic termination#

Can we automatically detect when a goal expression can be terminated? The following conditions are sufficient:

  • the goal expression is quiescent, so it cannot advance without external input
  • the goal expression is not blocked on any futures or sites reachable from the main Orc program, so the main Orc program cannot unblock it
  • the goal expression is not blocked on any external sites (like Rtimer), so the external world cannot unblock it

The existing garbage collector implements these rules (i.e. it will collect terminatable tokens) provided:

  • the engine does not explicitly hold references to quiescent tokens (e.g. via a region)
  • the engine does hold references to all non-quiescent tokens (e.g. via the active queue)
  • quiescent tokens are held by the group cells or sites (or, in the case of an external site, a proxy thread) they are blocking on

My strong instinct is that automatic termination is an implementation detail and should be semantically equivalent to non-termination. This means that finalizers should not record that a token has died in the usual manner. However there are still some subtle and tricky issues that arise when we try to make termination explicit:

  • tracing: automatic termination will not show up in traces; is this a problem?
  • otherwise combinator: if the LHS is automatically terminated, then the RHS must be as well. Since the RHS token is kept alive only via a reference from the LHS region, that should happen naturally.
  • completion of the program: we still need to detect when the program is complete, without relying on non-deterministic GC. It's not enough to observe that the main program has terminated, since there may still be isolated expressions being kept alive by site threads (e.g. the Rtimer). Therefore we need some bookkeeping to determine when all the site threads are quiescent.

Records#

Records are a possible implementation of modules. Example:

def M() =
  val v = Rtimer(1000)
  def f() = v
  { f => f, v => v }

M() >m> ( m.f() | m.v )

In this example, the syntax { f => x } creates an immutable record object where field f has value x. If this value were assigned to y, you could read the value of the field f with the syntax y.f .

This neatly solves the dependency issue, since record construction requires a site call, so the module's record is not published until all values are available. However this does not allow you to isolate processes from termination.

Comparison to CLU#

Jay suggested that CLU demonstrates a failed approach to using records for modularity.

Based on the CLU Wikipedia page, the most significant flaw with CLU was that it did not provide namespacing for record type names and constructors. In contrast, Orc record types would be anonymous (they are related by structural rather than nominal subtyping), and record constructors would be ordinary functions which obey lexical scope.

Termination Isolation#

Consider a new keyword "site" with the following semantics: site E waits for all the free variables in E to become available, then evaluates E protected from termination, publishing only the first value published by E. The effect is to execute E as if it had been wrapped up in a site call. (Questions: is it important that we wait for free variables to become available? Is it important to publish at most one value?)

Together with records, this allows us to implement actors naturally:

def M() =
  val in = Buffer()
  def handle(message) = ...
  site (handle(in.get()) | { send => in.put })

val m = M()
-- the handler is still running
m.send("hi")

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-1) was last changed on 21-Mar-2009 17:15 by AdrianQuark