Q: Functors?

Fare Rideau rideau@ens.fr
Sat, 9 May 1998 22:12:53 +0200 (CEST)

>: Eric W. Biederman

> Upon occasion it happens that Functors are mentioned on this list.
> Does the concept of Functors trace it's roots back to category theory?
Well, yes, though indirectly.

I took the word "functor" as is from the ML module systems.
I cannot guarantee that where the use has originated from,
but people from the ML community sure have knowledge of category theory,
since there are lots of bridges between category theory and type theory;
however, I'm sadly not a specialist, so I can't say more about it.

As for the word "functor" in ML-like module systems, the need for it
stems from modules being second-class citizens rather than first-class,
which is required for compatibility with fully static typing and binding
and separate optimizing compilation used in languages of the ML family
(Matthias Blume's higher-order module proposal for Scheme is essentially
a revamp of the ML module system). Hence, the word "functor" applies to
second-class "functions" that operate on first-class modules, to distinguish
them from first-class functions that operate on first-class objects.

If our modules are first-class citizens, maybe we don't need the name
"functor", for normal "functions" would do.

However, if we want to take advantage of the technology associated
to traditional (static) "HOT" (Higher-Order, Typed) language design,
and more generally of propagation of static type information for
specification, bug-tracking, and optimization, I feel that the problem
of second-class vs first-class is not that it imposes an unnecessary
distinction, but that the distinction it imposes is not expressive enough
to deal with the kind of dynamic and reflective computations we want
to be able to carry on. That is, the kind of dynamism we want
is not one that forbids constitution of static information,
but one that allows constitution of static information according
to patterns that are not statically wired into the programming language,
which is perhaps the opposite.

Not only should we be able to distinguish between a program's runtime
and its compile-time, but we must be able to distinguish between the
runtime and compile time of just every piece of code in the dynamic
reflective system, which includes the meta-programming system, and
hence module-management. I think there should not be a unique
one-size-fits-all "base level" semantics for all programs in the language,
but that every piece of code should explicitly declare the semantics
in which it is to be interpreted (that is, what syntax/grammar, type system,
execution model, etc, it relies on, with what subsets and extensions);
meta-programs could then manipulate them with a finer grain.

Particular Meta-programs would draw bridges between different semantics,
so that you could interface programs written in different styles;
some of them would manage language "extensions" and dialects with additional
"implicit semantics", and ensure that those extensions are consistent:
errors or at least warnings would be issued when a programmer tries
to mix programs that rely on extensions that haven't been shown
to be consistent, like interfacing a GC'ed language with C that's not
reducible to a strongly typed subset, or mixing C routines that make
conflicting memory management assumptions.

For instance, when you'd program in say, ML
(or an isomorphic subset of the HLL), the system would be fully aware
that your source constitutes the declared semantics of the program,
and not the object compiled by a particular compiler.
If you'd later interface it to a higher-order module written in Prolog,
you'd use a meta-program that implements a semantics that correctly extends
both Prolog and ML, and you'd obtain a meaningful program.
If you'd later interface it to a low-level memory-twiddling module
written in C assuming things about the ML implementation, then you could too,
even though the extended semantics then required for ML become incompatible
with the previous one used for interfacing with Prolog.

Actually, both of the above programs could run at the same time,
so that the same ML module could be used simultaneously using
two incompatible extensions to the ML semantics.
So a same source could have several object files (which in turn,
could be further transformed in several distinct ways),
each corresponding to a particular meta-programming technique.
Among the mutually incompatible meta-programming techniques
that might be used at some point, there will be those corresponding to
the selection of the target architecture, file format and operating
environment (e.g. i386, elf, glibc2.1, linux2.0 with redhat5 modified fhs).
All in all, we will fight the onemindedness of current systems.

As to how exactly this will interact with static typing,
I think we can safely postpone the issue of actually implementing
"advanced" type systems (unless we happen to have to use them,
for instance if using linearity to deal with exclusivity of resource access,
or automatic detection that only the second-class compatible subset
of module operations are being used),
as long as we do keep in mind that we might want to use them someday
(i.e. systematic gratuituous type fudging a la LISP should not be considered
a good long-term idea, though it's to be tolerated for expediency).

Enough ramblings for now. Cheers, and happy tunesing! (or tunes singing?)

PS: Eric, I suspect you of being a member of the dreaded Eric Conspiracy
 (see around esr's pages at http://www.ccil.org/~esr)...

PPS: esr has committed a sequel to his Cathedral and Bazaar article,
 available around same place (http://sagan.earthspace.net/~esr/writings/),
 As with previous article, I only agreed 98%. In previous case,
 I disagreed to the conclusion about free software being better than
 proprietary software for practical, not moral reasons, since I think
 that the best moral justification is that it works in practice,
 which, esr agreed, constitutes a posteriori instead of a priori ethics.
 In the new article, I refuse to admit that homesteading happens in the
 noosphere, since it would mean that programming ideas are ownable, hence
 have resourcewise exclusion properties; instead, I think homesteading
 happens in the sphere of *human projects* (as opposed to *programming
 objects*), which indeed have natural mutual exclusion properties.

## Faré | VN: Уng-Vû Bân   | Join the TUNES project!  http://www.tunes.org/ ##
## FR: François-René Rideau |    TUNES is a Useful, Not Expedient System     ##
## Reflection&Cybernethics  | Project for a Free Reflective Computing System ##
Reporter: Mr Gandhi, what do you think of Western Civilization?
Gandhi: I think it would be a good idea.