[Chicken-hackers] functors

[Felix]

Hello!


For quite a while I thought about how to implement "functors",
i.e. modules that take modules as parameters. After several failed
attempts with macros that expand into modules I now tried a different
approach by directly integrating this into the core system. Tests pass
and things appear to work fine, but I'm unsure whether the approach is
sound or whether it s considered useful. This also adds a few
generalizations to the module system, and I present the concepts here
in case someone has suggestions or criticisms.


Interfaces:

It is possible to define /interfaces/ (named groups of exports),
for example:

(define-interface ARITHMETIC 
  (+ - * /))

(module foo (this that (interface: ARITHMETIC) the-other)
  ...)

The "export list" of a module may optionally be an interface name
so

(module bar ((interface: ARITHMETIC)) ...)

could also be written as

(module bar ARITHMETIC ...)

[This implies an interface may not be named "*"]

The syntax is a bit ugly, but I couldn't think of a better way, which
doesn't introduce ambiguity into the syntax. For symmetry, there is
now also "(syntax: SYNTAXIDENTIFIER [IMPLICITEXPORT ...])", equivalent
to "(SYNTAXIDENTIFIER [IMPLICITEXPORT ...])". This is not enforced in
the moment, but may be useful for documentation purposes.


Functors:

A /functor/ is a module that takes other modules as parameters,
binding the argument modules to temporary identifiers inside the body:

(functor (linear-search-functor (S FINITE-SET)) (search)
  (import scheme S)
  ...)

Inside "linear-search-functor", "S" refers to some module that
satisfies the interface "SEQUENCE", that is, which exports at least
the identifiers defined in the interface. The general syntax is:

(functor (FUNCTORNAME (ARGUMENT1 EXPORTLIST1) ...) FUNCTOREXPORTS BODY ...)

One uses a functor by /instantiating/ it:

(module my-search = (linear-search-functor some-key-value-store))
(import my-search)
(search ...)

This will expand into a module definition containing the body of the
functor "linear-search-functor", and with imports of "S" redirected to
the module "some-key-value-store". This could be simply done by syntax
that expands into a module, but functor-instantiation will check that
the argument modules satisfy the required exports. Also, the functor
itself will be put into a module, so an import-library can be
generated and installed for it.

I'm not sure if simply substituting the functor body in the
instantiation is a problem - exccessive use may result in code bloat,
which means functors should be restricted to the part that is truly
specialized to the argument modules. Standard ML compilers IMHO
generate only a single functor body, but it is very difficult to find
much information about functor implementation, apart from a lot of
type-theoretic mumbo jumbo. Scheme48 apparently has higher-order
modules, but only hints at them in the manual. Another difference is
that an import may refer to a procedure in one instantiation and to
syntax in another one. Restricting this looks like a loss of
expressivity to me, so full functor-body substitution seems to be the
only option. On the other hand, this allows the body to compile to
heavily specialized code if the imports refer to syntax, low-level
intrinsics or those core library procedures that the compiler is able
to optimize well (or for which type-information is available in the
forthcoming type-driven "specialization" optimization which is
currently in the works). I have seen heavily optimized libraries once
or twice, which basically where just a macro parameterized with
primitive operations that expands into a set of procedure
definitions. I remember a really badass red-black tree implementation
by Marc Feeley, but can't recall where I found it. It was written in
this style and would be a perfect use case for a functor.

Anyway, that's it.


cheers,
felix