[e-lang] Module naming and identification

[Mark Miller]

> On Thu, Apr 16, 2009 at 10:37 AM, Lex Spoon <lex at lexspoon.org> wrote:
>> I have to ask: your first message mentions cycles specifically, but three
>> messages later you still didn't address them.   Do you have a pointer to
>> that issue?  It's highly relevant for modules.

I kept building up to it, but I never did get around to writing that
message. My only excuse is that same day I was distracted by E's
proudest moment:
<http://www.eros-os.org/pipermail/e-lang/2000-January/003199.html> ;).

I will try to write here a summary of what I had in mind as best as I
can remember.

Given any directed graph, we can factor the transitive closure of the
directed graph into a dag of fully connected cycles. In our case, the
directed graph is the graph of direct dependencies between module
editions, and the transitive closure represents direct and indirect
dependencies among module editions. Say module edition A depends on
module edition B. Let's describe this as B <= A, where <= represents a
partial order. If A and B are members of the same cycle, then A <= B
&& B <= A, so all members of a cycle are in an equivalence class,
which we'll describe (using E's notation) as A <=> B. Between distinct
cycles C1 and C2, if any node in C1 depends on any node in C2, then
all nodes in C1 depend on all nodes in C2, which we describe as C2 <
C1.

For each cycle, we deterministically sort the module editions within
that cycle. So, given a self-authenticating designator, DCi for cycle
Ci, a self authenticating designator for the jth module edition within
that cycle is a pair [DCi,j]. The remaining problem is to create a
self authenticating designator for a cycle.

We can consider each statically linked module edition to consist of a
pair [src,clist], where the src contains information corresponding to
the source. For JavaScript, it may be the source. For Java, it may be
a classfile compiled from the source. The clist is a mapping from the
src's names for its dependencies to designators for these
dependencies. If the designated dependency is a module edition in a
different cycle, the designator is the self-authenticating designator
described above. If it designates a module edition within the same
cycle as itself, then the context-dependent designator is only the
index into this cycle.

Optimizations aside, the self authenticating designator of a cycle can
now be calculated by hashing the concatenation of all the hashes of
all the [src,clist] pairs of statically linked module editions within
this cycle in sorted order. Since the range of all the clists of
module editions within the same cycle will be the same, a more compact
representation is possible.


On Thu, Apr 16, 2009 at 10:53 AM, Kris Kowal <cowbertvonmoo at gmail.com> wrote:
> I'm only following this thread shallowly, so please forgive me if this
> response does not address the actual issue.
>
> Here's a link to the draft specification for modules that the ServerJS
> group is converging on:
> https://wiki.mozilla.org/ServerJS/Modules/SecurableModules
>
> 1.3 under "Module Context" addresses the requirement to behave
> gracefully when there are cyclic dependencies among modules.  The
> verbiage here only addresses the requirement, but not how to satisfy
> it in an implementation.  The trick is to keep a memo of singleton
> module exports object.  The modules do not return these exports
> objects, or render them as the last evaluated expression.  Instead,
> the sandbox creates an empty object and stores it in the memo *before*
> applying the corresponding module factory function.  This ensures that
> a cyclic dependency will get the partially completed exports object
> instead of recurring indefinitely.  This is perhaps not as elegant as
> mutual recursion, but it makes it possible to have mutually dependent
> modules.


Hi Kris, no it isn't directly relevant. The current thread is really
about cryptographically strong static linking of resolved module
dependencies, as opposed to how module dependencies are presented by a
language API.

However, now that Tyler's ref_send library is has been proposed as a
standard way to do E-like concurrency and distribution in JavaScript,
perhaps we can use it for language-level cyclic imports in the same
way it is used in E, to whit, have a cyclic require return a promise
for a module instance that only resolves to a module instance once it
can resolve to a complete one.


-- 
Text by me above is hereby placed in the public domain

    Cheers,
    --MarkM