2010/05/06

Import options: part two

In the previous article I introduced 0.9.1's import options. Now I describe how it is implemented currently.

How names are searched for in modules

Modules have two kinds of relations. Importing is the way to use one module from another module; importing-imported relationship forms a directed graph, possibly contains cycles. Inheriting is the way to extend existing module(s) to add something; like augumenting existing modules with new bindings, or making a single facade of a bunch of modules. Inheritance is handled the same way as the class inheritance, and forms a directed acyclic graph.

Importing is formed by import, and it is not transitive. If module X imports module Y which imports module Z, X only sees Y's exported bindings but not Z's. Inheritance is formed by extend, and it is transitive. (ref:import, ref:extend).

Module inheritance is less used than imports (except that all modules inherits gauche module by default), but it comes handy time to time. And implementing import options is one of the times inheritance comes handy unexpectedly.

Suppose you set up modules as follows:

(define-module P (extend Q R))
(define-module S (extend T U))
(define-module V (extend W X))

(define-module A
  (import V S P)
  (extend B C))

The following figure shows how a name used in module A is searched for . Red numbers are the order of the search. (It doesn't show the default inherited modules like gauche, scheme etc.)

Note that this search occurs at most twice per global name; once in compile time to see if the name has a syntactic binding, and another in the first time the code is run. Once the name is resolved, the result is cached and never be searched again.

Thus, although the modules are open, once the name is resolved you cannot insert shadowing binding into the module between the current one and the one the name is resolved in. This is a trade-off between speed and flexibility; if you want the new shadowing binding to be reflected, you can always reload the current module.

Supporting 'prefix'

A 'prefix' slot is added to a module. When a name is searched into the prefixed module, the prefix is stripped from the name first---if the name doesn't have the prefix, we can stop serching of that particular path on the imported module.

A prefix is attached by the importing module, so we cannot modify the imported module itself (Another module may import the same module with different prefix or without prefix at all). The 'prefix' import option creates an anonymous module that inherits the imported moudle, and import the created module instead. The created module behaves the same as the original imported module, except that it strips the prefix.

Supporting 'except'

except is also done with module inheritance, and another new feature, a negative binding. It is a special binding that answers "no, the name doesn't have a binding along this path" when a name is looked for in it.

So, the except option creates an anonymous module inheriting the imported module, and inserts the negative bindings of the names listed in the option. When one of the names are searched for, the search is gave up at this anonymous module. For other exported names, the search is continued to the ancestor modules and eventually gets a hit.

An except and a prefix can be combined to one anonymous modules. The difference of which one comes first can be reflected to the names inserted into the anonymous module: If prefix comes first, we insert the negative bindings with the name the prefix is stripped, since the search process strips the prefix before looking into this module. If except comes first, we insert the negative bindings with the name as they are.

Supporting 'only'

For the only option, we create an anonymous module that do not inherit anything, and inserts the bindings with the listed names from the imported module.

What we actually do is taking a gloc object which is a value of the module hash table keyed by a name, and registering the name and the gloc object as a new binding in the anonymous module. So the two bindings share the same gloc object. It allows the importing module to see whenever the original binding is modified by set!.

In effect, we create aliases to exising global bindings, although in only case the aliased name is the same, only visibility differs.

Supporting 'rename'

rename was the trickiest. Not only making a new names visible, but also it must make sure that importing modules won't see the original names before renaming. The interaction with prefix is also nasty, for we may want to see the renamed symbol with or without prefix, depending on which option comes first.

We create an anonymous module, inheriting the imported module. Then creates an alias binding in the same way as only, but using the renamed name instead of the original name. Next, we insert negative bindings to the original names, except the original names that are used as renamed names as well.

For example, when we have this crazy setting:

(import (M :rename ((kar kdr) (kdr kar) (kons snok))))

We insert the following bindings to the anonymous module:

• an alias binding of kdr (which shares the gloc with the name kar in the module M)
• an alias binding kar (which shares the gloc with the name kdr in the module M)
• an alias binding 'snok (which shares the gloc with the name kons in the module M)
• a negative binding of kons

Since it inherits the imported module M, searching all other names falls into M.

If prefix is added after the rename option, after-rename names also get prefix, so we can just add prefix to the anonymous module.

If prefix is added before the rename option, however, we have to make the after-rename names without prefix. So we need two anonymous modules, the first one for prefixing, and the second one with the renaming setup, inheriting the first one.

Tags: 0.9.1, import, module