2010/05/03

Import options: part one

A bit of background

Gauche's module system is based on STk's. What I liked about STk's module system was its simplicity and flexibility.

It's simple since all the forms don't have lots of options. Compare it with CL's defpackage---I always have to look up the manual whenever I write a new defpackage form.

It's flexible because modules are open---I can add definitions to existing modules later, or even alter the definition afterwards. Altering the definitions comes handy when you have to patch existing library, but you don't have permission to change the installed libraries, or don't want to risk affecting other programs by changing shared libraries. In your program you can just put some code like the following:

(with-module target-module
  (define (foo  ...)
    ...fixed definition..))

This (I think it is called monkey patching) isn't recommended in the final code to be shipped, but sometimes you have to step outside of "the Right Things" to fix the holes in emergency.

However, the system lacks some handy features like prefixing imported symbols. The limit gets in the programmer's way more often as we have more libraries, and the possibility to import from two modules that exports the same name grows.

I've been aware with this issue for long time, but procrastinating to implement it, for I want to avoid neither a complex beast that everybody have to look up manuals constantly, nor a half-baked solution that covers simple cases but falls short and nees to be reworked in practical situations. As R6RS was finalized, and it offered a module system with various options, that became my reference point in terms of implementing features.

In 0.9.1 the feature will be finally available. For a taster, the following code says load srfi-1 but only import iota and fold from it, prefixing them with srfi-1:.

(use srfi-1 :only (iota fold) :prefix srfi-1:)

(srfi-1:fold + 0 (srfi-1:iota 100 1)) => 5050

Challenge of open module

I eventually want to provide R6RS-compatible layer, so putting enough functionarity to support R6RS library form is one of the goals. However, R6RS specification poses some challenges to open module system like ours.

R6RS has a concept of import-set which is a set of names to import, and defines only, except, prefix and rename as operations on the sets; that is, each option takes a set of names, and returns a modified set of names. It is easy to explain, and straightforward to implement if you know all the names you are dealing with.

The if is the problem in our open modules, since we don't know the complete set of names when we process import forms. For example, except cannot be just a set-difference operation; if a new exported binding is added that is not listed in the except list later, that binding should become visible in the importing module.

I regret that I didn't discuss more on this during R6RS review process. Being simple to explain is a virtue, but the way of R6RS covers too broad space than necessary; for example, you can nest arbitrary number of prefix and rename forms. Suppose library lib exports names w, x, y, and z. If you import the library like the following, can you figure out what names you use to access to the original names?

(import (rename (prefix (rename (prefix (lib) n:)
                                (n:x y) (n:y x))
                        m:)
                (m:n:z z) (m:x y)))

If I understand R6RS correctly, it'll be like this:

It's hard to imagine when this kind of setting up is useful, but even if you really need this kind of multiple layering, I imagine it is doable by writing an intermediate module to remapping names. Probably nobody would want to write nested prefix/renames. But R6RS compatible implementations need to support them.

In the R6RS world, modules are closed, and the set of names is fixed when you process imports. So that's not a defect of R6RS per-se, but I like the designs more that encourages alternative views of the worlds, instead of putting hurdles to them.

Anyway, when we process import forms, we don't know yet the entire set of the names to import. We don't want to recalculate the set whenever a new exported binding is added to a module, or whenever we search for the imported module with those options.

So I employed a few tricks.

• For prefixing, we ran operation in reverse. That is, when we search into an imported module with prefix, we strip the prefix from the searching symbol first and look for the stripped symbol in the module.
• For only and inserted bindings by rename, the import form creates an anonymous intermediate module to which necessary names are injected. This is one-time cost at processing import and doesn't cost at symbol lookup.
• For except and hidden binding by rename, we also use an intermedidate module that has a special shadow binding that prevents name searching further into the module's ancestors. This is also one-time cost at processing import and doesn't cost at symbol lookup.

The implementation is a bit more compilcated than I like, but it doesn't seem to have too much impact in performance. Espcecially, if you don't use prefix, overhead is negligible.

New import and use form

The import form is extended as follows:

<import-form> : (import <import-spec> ...)

<import-spec> : <module-name>
              | (<module-name> <import-option> ...)

<import-option> : :only (<symbol> ...)
                | :except (<symbol> ...)
                | :rename ((<symbol> <symbol>) ...)
                | :prefix <symbol>

<module-name> : <symbol>

use form is also extended to accept import options. You don't need extra parentheses, for use takes only one modules (note that import can take multiple modules, that's why we needed parens).

<use-form> : (use <module-name> <import-option> ...)

The option modifies imported symbols as the way it appears, so the order matters. The following two import forms are equivalent, both make iota available in the current module under the name srfi-1:iota.

   (use srfi-1 :only (iota) :prefix srfi-1:)

   (use srif-1 :prefix srfi-1: :only (srfi-1:iota))

In the latter form, symbols in :only option must be prefixed since they are already prefixed in the previous :prefix option.

I think it is a good idea to put :only and :except option always before :prefix, for less confusion.

On the other hand, you may need both orders of :rename and :prefix, depending on what you want. If you put :prefix clause after :rename, the renamed identifier gets prefix as well:

   (use srfi-1 :rename ((iota i)) :prefix srfi-1:)
   
   srfi-1:i => #<iota>
   srfi-1:fold => #<fold>

If you put :prefix first, you can import renamed symbols without prefix:

   (use srfi-1 :prefix srfi-1: :rename ((srfi-1:iota i)))
   
   i => #<iota>
   srfi-1:fold => #<fold>

The contrived complex imports above can be written in our syntax as follows, though I don't recommend it.

(use lib
     :prefix n:
     :rename ((n:x y) (n:y x))
     :prefix m:
     :rename ((m:n:z z) (m:x y)))

In the next entry, I'd like to explain how this is implemented in Gauche. Stay tuned.

Tags: 0.9.1, import, use, r6rs