!!! 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.

* 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:

[{orc runnable='false'

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

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:

|def|module constructor|module method|site|
|Y|Y|Y|Y|is a value
|N|Y|N|Y|calls are strict
|N|-|Y|Y|can use . operator
|Y|N|Y|N|multiple returns
|reduces to halt|reduces to halt|reduces to halt|raises a halt event|how is termination detected?
|Y|Y|Y|sometimes|can take logical time

That leaves the following features to consider:

|def|module constructor|module method|site|
|N|?|?|Y|calls are protected from termination
|N|?|?|-|may hold unbound free variables
|-|-|?|Y|backing process (goal expression) protected from termination
|Y|?|?|sometimes|garbage-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:

[{orc runnable='false'

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|http://en.wikipedia.org/wiki/CLU_programming_language], 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:

[{orc runnable='false'

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

val m = M()
-- the handler is still running