Lambda the Ultimate

Thanks for the information about that I'm going to read them right now. They all look like great places to start. I consider myself reasonably informed on all the theory involved in all this but that doesn't mean I can tell what will work in practice.

The outage may have just been a temporary interruption (it's hosted on a free web host that doesn't have any illusions about five 9s but its free and otherwise decent. its loading for me right now, if not I'll start seriously investigating.)

Calling a module system namespace management is stretching it. It's like calling Java classes namespace management, whereas, to me, namespaces seem like an orthogonal feature to both.

Namespace management is a central aspect of any useful module system. Of course, it's far from being the only one. But it's not orthogonal either.

I would assume ML had namespaces if I could write stuff like: "inria.fr.Functor.apply." Now I only see a series of (parameterized) grouped declarations. A module in ocaml's sense is just a pure declaration of a construct.

Your mileage may vary on your definition on what modules or namespaces are, but if I take the java/C view on it, ocaml's modules have little to do with it.

[ Let's continue this discussion until we got the p.o. right ;) ]

I would assume ocaml had namespaces if I could write stuff like: "inria.fr.Functor.apply."

And you can. You just nest modules. No idea, though, whether that does or does not constitute "a pure declaration of a construct", and if I should worry about that...

if I take the java/C view on it, ocaml's modules have little to do with it.

Er... What has C possibly to say about namespacing, except that, apparently, you can live with its complete absence?

Oh come on. You get the point, I'll call it C++ then. You happy now?

As far as I see, MLs modules are mostly used for introducing structured types, not, as per the Java/C++ convention, to order declarations in a certain scope. To me, those are different things.

And yes, you should bother. The question is central to what namespaces are for: For organizing modules, or for organizing software in a space where there are just a lot of different publishers.

That's why is chose the inria.fr.Functor example. What if glasgow.edu.uk also publishes it's own Functor definition?

I didn't understand what you meant about C either. Maybe it's just that I've never been a big user of C++, but I would never have assumed that a comment about C referred to a feature of C++.

Yeah well. Most people I know hardly make the distinction since they normally happily use C++ extensions such as arrows all over the place where old ANSI C forbids that. It was a typo and could have been clear from context.

There's no need to get defensive... I didn't mean to criticize you, I just wanted to point out that Andreas wasn't the only one who misunderstood.

Not defensive at all, just thought it was clear from context. So, I'll publicly state it was a typo, sorry for that, also excuses to Andreas then. For the rest, let's get back on topic.

What 'arrows' are you referring to? The only thing I can think of in either C or C++ that I would describe as an 'arrow' is the syntax for accessing members of a struct via pointer, foo->bar, which is ANSI C.

Hmm, I distinctly remember compilers complaining when I used that in C sources, but I can't say I ever bothered about it. C99? Hmm, found a reference in a C91 book. It ain't K&R C?

The foo->bar syntax goes back to at least the mid 70s. See, for example, page 5 of the 1974 version of the C reference manual.

I definitely remember C giving warnings about using C++ extensions in C code. I must a) either have remembered it wrong (using <<?) or b) it complained about something else (referencing something which was declared in C++ style)?

Nah, I remembered correct. Must have been a compiler bug.

Don't know which compiler but back not too long ago (grin) I know some C/C++ compilers, such as Borland's for example, would do double duty just based on file name extension. I can easily imagine such compilers making some warnings along this line (good for the C++ adoption curve back then - C++ as just a "better C" was a big sell to crufty non-OO C programmer reactionaries :-). Cut my own teeth on Zortech C++ (grin again), and think it was that way as well - but it's really been way too long to be sure.

It probably was something easy like some implementor thinking that since '->' occurs a lot in Java/C++ sources, it ain't C, therefor my sources when compiled with strict conformance gave warnings, therefor a baffled me thought it ain't C.

Propagation of mistakes.

[Edit: this is actually a response to the post below, but I just thought this thread continued long enough. Hey, I agree, I looked it up myself, arrow is in C. I just distinctly remember a warning on using C++ constructs in C code, not an error, and being baffled by that message myself. I am pretty sure it was a wrong-issued warning which gave me the impression arrow isn't in C. ]

One might easily get a C++'ish error message in a hybrid compiler, such
as:
"err: foo.c:182 operator '->' not overloaded for type Foo
Maybe some crap like that.

It's easy to support "Inria.Fr.Functor.Apply" in the OCaml module system. Ur's module system is essentially the ML system, and it allows you to view nested directory structures in exactly this kind of way. It only takes a tiny preprocessing step to support this with any ML module system realization.

So either you do, or you don't, implement namespaces with a small preprocessing step.

Won't simple binding handle the first extension you desire?

xmlname:sum="math:sum"
xmlname:print="misc:print"

Minus language specific issues (like delaration syntax, const qualifiers, etc.), shouldn't we be able to simply write:

/* import machinery stuff */
...
/* resolve use of a few locally unqualified names */
val sum = math:sum
val print = misc:print
/* Example use of names */
int incrPrint(int x) = print(sum(x, 1));

I'm sleep deprived right now; I may well be missing some important capability related to moving this normal language binding capability into the regular namespace machinery. If so, I know someone will let me know :-)

No, I don't think that's equivalent.

If I say

xmlname:sum="math:sum"

then after that the identifier denoted by the lexeme "sum" is the same as the identifier denoted by the lexeme "math:sum".

If instead I say:

val sum = math:sum

then the lexemes "sum" and "math:sum" denote different identifiers - but presumably each denotes an identifier bound to a common value.

Interesting. I want to get it, but right now I can't wrap my head around "two identifiers are 'the same' identifier." I guess a nap hasn't cleared my head :-)

Lately I've been (way too lazily) implementing a sorta-kinda ML'ish language in Scheme (Racket), which supports import time renaming via prefixes and so forth. So anywho, I have a mental model of id's bound to values, including to reference values for mutable lvalues - the binding itself never changes. So "q = M.r" is no different than, say, "a = 1; b = a": there's no difference in the relations R(q,M.r) and R(a,b). For imported types, the semantics are similar - just an immutable "type foo = M.ty" style binding of a name to a type instead of a term. Yada yada.

So I imagine my thinking is kinda stuck in one direction.

I'm sure there's a counter example that distinguishes simple name/value (or name/type) binding from some notion of "two identifiers are the 'same' identifier" - but I can't think of it right now.

So given a hide+exp+imp-identifiers module system (plus renaming-style convenience features), it strikes me that alpha substitution of any 'renamed' imported identifiers with the fully qualified module+identifier names in an importing module would yield a semantically equivalent module, yes? (???)

Hmmm, I think I'm gonna learn something today :-)

S.

See my answer to Anton, below.

It isn't that "two identifiers are the 'same' identifer".

It is that "two lexemes denote the same identifier."

In a case insensitive language, foo and FOO are distinct lexemes which (in appropriate contexts) denote the same identifier.

then after that the identifier denoted by the lexeme "sum" is the same as the identifier denoted by the lexeme "math:sum".

By the usual definitions of the terms "lexeme" and "identifier", this is incoherent. It implies a redefinition of those terms which seems likely to have several unfortunate consequences.

It destroys the usual 1:1 relationship between lexemes at the lexical level and identifiers at the syntactic level. It becomes necessary to use a term other than "identifier" to refer to what we normally call identifiers, because identifiers would now be a separate domain of values to which lexemes can be bound in arbitrary ways. If the term "lexeme" is used for this purpose, it erodes the normally clear distinction between the lexical and syntactic views of a program. It introduces an extra layer of indirection which duplicates the functionality of the usual binding of identifiers to values.

Given that multiple identifiers can be bound to the same value in most languages, this all seems very unnecessary.

By the usual definitions of the terms "lexeme" and "identifier", this is incoherent. It implies a redefinition of those terms which seems likely to have several unfortunate consequences.

It destroys the usual 1:1 relationship between lexemes at the lexical level and identifiers at the syntactic level. It becomes necessary to use a term other than "identifier" to refer to what we normally call identifiers, because identifiers would now be a separate domain of values to which lexemes can be bound in arbitrary ways. If the term "lexeme" is used for this purpose, it erodes the normally clear distinction between the lexical and syntactic views of a program. It introduces an extra layer of indirection which duplicates the functionality of the usual binding of identifiers to values.

With all due respect I think you are simply mistaken.

I regard a "lexeme" as a sequence of characters, typically that match some regular pattern applicable within a context established by charaters "to the left" of the lexeme. I regard an "identifier" as, as you suggest, a class of objects in an abstract syntax.

I believe my understandings are customary, as illustrated by the following example:

In the new programming language I've defined, identifiers are case insensitive.

I claim that what that typically means that for each identifier (that contains a cased character) there exists more than one lexeme which denotes that single identifier.

I would describe a typical lexical analyzer as a program that takes a source text as input, that recognizes lexemes, and that produces as (ordinary) output (for lexically valid input) a sequence of syntactic objects (namely syntactic objects which are in some sense "primitive" in the grammar for the language being parsed).

You make a separate point here:

Given that multiple identifiers can be bound to the same value in most languages, this all seems very unnecessary.

I disagree. What you are describing (multiple names bound to "the same value") solves one set of problems. What I am describing (how to manage a distributed, decentralized namespace) solves a different set of problems.

For example, the ability to bind two distinct identifiers to a common value is one aspect of procedural abstraction. It is also a mechanism by which two bodies of code, which use common identifiers in incompatible ways, can be composed to produce a third body of code in which all of the named things in either original are named - but naming conflicts have been eliminated.

XML QNames and similar mechanisms solve different problems. In particular, they solve the problem of allowing well behaved (convention-following) programmers to reliably choose globally unique names within a flat, shared name-space with little or no need for ongoing coordination with any central authority. XML QNames contrasted with other solutions (such as simple "naming conventions") have three specific advantages (in my view): They allow names to be organized into abstract hierarchies; they provide a suitable mechanism for abbreviating very long names; and they "pun" nicely -- encourage parsimony -- by being so widely used throughout the W3C family of standards and tools related to those.

Given that multiple identifiers can be bound to the same value in most languages, this all seems very unnecessary.

It seems that there's some value in being able to abstract over identifiers, as evidenced by Scheme's identifier-syntax and Common Lisp's define-symbol-macro.

(I haven't thought this issue through yet, but I was thinking about it recently, so I thought I'd post that here.)

Import qualified is hardly used in Haskell, I didn't know about it and you can read about the complaint here, and I wonder if that is just the effect of being able to abbreviate qualified names? Having said that, abbreviation is a nice feature to have.

Import qualified is hardly used in Haskell

That's sort of true in the sense that it's only really needed when conflicts occur, but then it's pretty indispensable, and commonly used. A grep through the source of about 100 Hackage packages that I have handy reveals 3,357 uses of "import qualified".

The page you linked to is old, ported from the old Haskell wiki and based on an 11-year old email. Haskell has changed a smidgen since then. For a start, Hackage appeared, gained over 2,200 packages, and introduced many more name conflicts than existed in 1999.

Nowadays, the Haskell libraries contain all sorts of name conflicts, because of various reimplementations of basic functions to support libraries like Data.List, newer types like ByteString, and general type classes like Foldable and Traversable.

If you search Hoogle for a common function name like map, you'll find dozens of versions of it, and "import qualified" is commonly used to deal with that. (You can also specify a module abbreviation without the qualified keyword, but that just opens the door to conflicts again.)

In any case, in general, the module systems of all the languages I mentioned support such renaming in some form - something like that is essential to deal with conflicts practically.

Addendum, added in an edit:

This general approach to modules is a simple one that seems to be a sweet spot in terms of practicality. There's also an argument that if you want more sophisticated module system features, you can provide them orthogonally, which avoids complicating the namespace management features of the module system with higher-level semantic constructs.

E.g., in Racket, the basic module system follows the simple model I've described (again, I'm ignoring macros for this discussion.) Higher-order modules are provided as a separate feature on top of the basic module system. I believe one of Matthew Flatt's papers makes the case for this approach.

Haskell does something along similar lines, by providing type classes as a feature orthogonal to modules, instead of providing higher-order modules as in ML. Oleg and Shan cover the equivalences between these approaches.