Lambda the Ultimate

Thanks Sean for pointing this out. This is a good bridge to what I want. I really didn't know anything about the Scala module system.

Unfortunately I need to look up the difference between class instance and object, because in the weird little corner of the programming world I live in, they are the same thing. ;-)

Weird thing is, that Scala itself seems to be unsure about the difference as well:

scala> object HelloWorld {
       |   def main(args: Array[String]) {
       |     println("Hello, world!")
       |   }
       | }
  defined module HelloWorld

In Scala, object and module are the same thing within the compiler implementation. The way I think about it is that modules in Scala can be accessed from any stable value, where stable means the value is immutable with a complete type. So essentially, modules in Scala are first-class values with a few restrictions on how they are referenced.

It actually gets better: packages in Scala are stable values although you can't use these values at run time. You can "import" definitions from a module/value at any level in your code, so:

class C { def d() = "hello" }
val c = new C
import c._ 
d()

works. Its actually quite elegant once you get used to it.

can be used at run-time in Scala 2.8, via the "package object" construct.

Modules can be linked in cycles as of Scala 2.6, using lazy vals. With those, cross-module linkages aren't evaluated until first use. This does make initialization order more difficult to reason about, but often it simply does the right thing.

Other advantages: If you declare all your module's dependencies as either abstract values (for single dependencies) or self-types (for related groups of dependencies), then completeness of dependency provision becomes statically checkable. If you miss providing a dependency, your code simply won't compile. It's a lovely, "scale-free" way to structure applications, once you master a few simple tricks. The best resource for understanding Scala's objects as modules is the original paper on it: http://lamp.epfl.ch/~odersky/papers/ScalableComponent.pdf .

Useful information thanks. Funny thing was that I learned a fair amount of Scala a few years ago, but I didn't fully grasp what they were getting at with this paper back then. I thought they were just saying that traits and mixins are great. Now I can see that there is more subtlety to it that that

The part that I don't know, and maybe rereading the paper will help, but maybe you can also help me, are what are the "few simple tricks" needed to make the system work well.

The first trick is simply to be able to think of modules as something that can be abstracted. Not a big stretch for the LtU crowd, but it can be an aha! experience for a lot of programmers.

After that

• Modules are coded as traits. Unfortunately this applies to both abstract and concrete modules, which causes some confusion. Concrete modules are still coded as traits, but with some of their values bound.
• Dependencies on single objects are declared via abstract values.
• The various ways of making abstract values concrete (subclassing mixing in, and by specifying during instantiation) correspond to different ways dependencies can be bound (provided by self, provided by another module, dynamically bound at runtime).
• Single dependencies my be grouped together into abstract modules, coded as traits.
• Dependencies on other modules are coded as either inheritance or self-types. I prefer self-types for such "requires" relationships, retaining inheritance for "is-a" relationships, but others choose one or the other based on convenience.
• Module composition is via mix-in, often anonymously. It's not unusual to see an application spun up as
  val app = new Object with WebModule with DaoModule with ProductionDbModule with Log4jLogging with Monitoring
  If any of your cross-module dependencies can't be found in that long list, compilation of that line will fail.
• Cyclic dependencies require binding with lazy values. Lazy values can also be used to enforce that component initialization occurs in dependency order. Component shutdown order, sadly, must be coded by hand
• A lot of stuff that usually has to be re-implemented at the module level for two-level languages comes free when your module language is your object language. In particular, your modules can use encapsulation annotations and abstraction over types, just like normal classes do. Stuff that is tricky in most module languages becomes trivial. For instance, conditional binding is just an if statement. Your modules can even define methods, although the use-cases for that are pretty rare.

This is all very sexy, and gets even more sexy when combined with run-time module systems like OSGi.

Thank you very much David, this is very enlightening. I did have an "aha moment" reading your post, here:

A lot of stuff that usually has to be re-implemented at the module level for two-level languages comes free when your module language is your object language.

This helped me realize two things:

• Newspeak and Scala both use the object language as the module language.
• The languages that I am most familiar with have two-levels: one for objects and one for modules

This now brings me to the point, where I need to be sure that I understand all of the implications. I am used to languages where modules have static global mutable data. Like in Python, where if a module is included by two other modules, they share any data members of the modules. As a programmer, this is convenient sometimes, but can cause a lot of problems in scalability.

In languages like Newspeak and Scala it seems that modules get instantiated, right? So if you want sharing of module-level data it has to be done explicitly, by passing the reference to the instantiation of the shared module. You don't get sharing by default.

When trying to understand this, I often think of the stdin and stdout streams in C. They are implemented as global data. If I redirect them it has global repercussions. So in a new language, I may want something like this encapsulated in a module. Now in a Python like module system, they are still just global data. Any module that redirects them affects all other modules, which can lead to disastrous effect if different modules try to redirect them as well.

Now from what I understand about the Newspeak/Scala approach is that I can put these as data members of a module, and then pass the module explicitly to other modules who want to use them. Otherwise, a module may instantiate the IO module explicitly, and get the default mappings, and never get overridden by another module.

Am I making sense, and describing things accurately here?

In Scala an "object" declared at top level is a "singleton" that is visible everywhere. In that sense a top level object in Scala is exactly like the more common notions of module that are just namespacing plus a bit of implementation hiding. Scala might have more sophisticated ways to compose modules but in the end Scala's top level objects are free to have shared mutable variables, IO services, etc. just like a Python module.

Newspeak, on the other hand, is trying much harder to eliminate the kind of ambient authority created by globally accessible variables and services.

In languages like Newspeak and Scala it seems that modules get instantiated, right? So if you want sharing of module-level data it has to be done explicitly, by passing the reference to the instantiation of the shared module. You don't get sharing by default.

Right. For both Scala and Newspeak, modules are objects, and need to be instantiated. As for sharing needing to be done explicitly,
this is the case in Newspeak, as far as I understand it. Scala does allow for top-level shared state, if you declare a top-level "object" with mutable state. That's probably a bad design choice for your application, but is how call-out to third-party shared-state dependencies is sometimes done. I don't know how Newspeak does this, since this sort of hack (and I agree, it is a hack) is specifically against Newspeak design principles.

In some ways, I think of Newspeak as taking the scalable component abstractions concepts to their logical conclusions: All dependencies are abstract, and must be explicitly plugged together. Your architecture is just the top couple of layers of your object graph. This results in dramatically testable and configurable systems, where everything is fully re-entrant and dependencies that would be conflicting in other systems can peacefully co-exist as just different bits of heap. Scala breaks this by having top-level objects, by allowing references via fully-qualified names in a global namespace, and by requiring such fully-qualified names for object instantiation.

Hope this helps, although I admit I'm still working some of this out myself. (I half-expect Martin Odersky or Gilad Bracha to pop up to hammer me on any points I've screwed up.)

No worries.

I could not have it summed up better.

I recall reading a great Scala blog post where the blogger explores the possibility of using Scala's classes, singleton objects, type members and Scala's other machinery to see how closely Scala's module capabilities could match ML's module system.

That said, I've not yet seen a more thorough treatment of the issue of Scala and (parameterized) modules. Love to find something.

I'm also seeking a module system, one with some balance between simplicity (Turbo Pascal's unit/interface/implementation/initialization or a Scheme style module/import/export/rename/etc.) but also some degree of flexibility regarding parametricity and mutually recursive module references. Hmmmm....

I've been both coding in PLT scheme and reading up on their Unit system. While compelling in most of the parts I can grok, I find that the few papers (and the current sparse system documentation) I've found seem to describe subtly different systems (over time, I presume).

Also, with PLT's units in particular, I've sought 1) some description of straightforward mechanics that would accompany the use of PLT style units as the dominant "module system" for frequent and common "use cases," 2) more precise implications for the mechanics of compilation and linking (particularly whether such a system can work with a "stock" system linker) and so on and so forth. So far I'm not attracted to PLT's support of the unit system and then a related and/or integrated but still separately usable "regular" scheme module system.

Scott

Might you have been referring to one or the other of those two informative postings? wherein "the blogger explores the possibility of using Scala's classes, singleton objects, type members and Scala's other machinery to see how closely Scala's module capabilities could match ML's module system?

The anecdote you quote is a fine example. An important distinction between Scala and Newspeak is that Newspeak has no global namespace. This means that the person designing the VM in your example doesn't get to choose whether to make things global or not. After all, one could (with considerable effort) have made the right choice even in C++. Likewise, in Scala, one is still free to make the wrong choice and define a global object, or use Java packages etc. Hence, this isn't just a question of how easy it is to refactor; it's a question of avoiding the problem up front.

Thanks for chiming in Gilad. This helps make the stratification more clear. I agree with the principle that languages should try to avoid giving programmers the option of making the wrong choice.

I am considering the following module system design, and I wonder if you have any insights as to whether it comes close to satisfying the requirements you describe of a clean module system:

Modules contain types and also have a mutable state. A module can be instantiated more than once. Every instance of a class is associated with a particular module instance, but even if two instance of the same class are associated with different module instances, they are considered the same type. Module instances are first class values, and can be used where a class instance would be.

Classes do not contain static data, but a class instance can access the state of the module instance it is associated with. Modules can import the names of another module, but they must also be explicitly instantiated, in the module initializer.

In effect modules are like classes which allow a single layer of nesting. In my system, I have to work around the fact that class nesting is not allowed. There are obvious advantages to nested classes as described in your papers, but for various reasons I have chosen not to go that route.

So unless I am mistaken, in my proposed design, there is no mutable state in a global namespace. Modules definitions are stateless, but module instances are stateful.

I wonder if some of the advantages offered by the Newspeak module design are present in what I propose? I would also like to know if there are some obvious flaws in the design.

Every instance of a class is associated with a particular module instance, but even if two instance of the same class are associated with different module instances, they are considered the same type.

The originating module should not be the (only) criterion to decide if two classes are same, what if sometime later you decide to introduce parametric polymorphism to modules? Or instantiate separate versions of the same module?

You also need to consider where modules come from, I suppose linked object files? Or maybe packages/libraries?

No that's not what I mean to imply. Two classes are of the same type, if they have the same definition, and belong to the same module definition. This is just as types and packages in Java.

I see no reason for them to not come from both places.

Right, you need to consider the class definitions. There are cases where having the same full name is enough, but it is not necessarily the case.

If the modules come from object files: how do you specify that you want at some point to use the module A from object file K, and at another point the module A from object file L? A configuration may not be satisfied with a single implementation for a particular module considering modules can be instantiated several times.

Two classes are of the same type, if they have the same definition, and belong to the same module definition. This is just as types and packages in Java.

Not quite. In Java a single class in a single module can give rise to an infinite family of types due to parametric polymorphism ("generics").

Also you say "belong to the same module definition" but it can make sense to go with "same module instantiation" rather than "same module definition." In Scala a single class, even one that isn't parameterized, can lead to an infinite family of types for each of its inner classes.

scala> class Foo { class Bar(); def doIt(b : Bar) = "ok"}
defined class Foo

scala> val f = new Foo
f: Foo = Foo@16369fdc

scala> f doIt (new f.Bar) 
res0: java.lang.String = ok

scala> val f2 = new Foo
f2: Foo = Foo@23dd246

scala> f doIt (new f2.Bar)
:8: error: type mismatch;
 found   : f2.Bar
 required: f.Bar
       f doIt (new f2.Bar)

Scala does let you loosen the type constraint if so desired. The above code would work with one small change

class Foo { class Bar(); def doIt(b : Foo#Bar) = "ok"}

Separating modules and classes is a legitimate alternative - indeed, that is how the Newspeak design started out. I do feel a need to be more careful about the distinction between classes and their definitions. I assume module definitions are stateless - only module instances have state, right?

If module definition M contains class definition C, then two instances of M, m1 and m2, would each have a distinct class corresponding to C.
These two classes are NOT necessarily equal (they could have distinct superclasses, and they implicitly depend on distinct state) and their instances may well have distinct types as well.

As far as imports: I'm not sure I follow. If module definitions refer to other module definitions by name, then there is a global namespace, albeit no global state. Is that the intent? If so, module definitions have hardwired external dependencies that are not parametric. This introduces ordering dependencies when compiling and loading module definitions.

I'm also unclear if you want to statically typecheck your code, and want module definitions to include/induce type declarations.

Thank you very much for humoring my design questions. Apologies to those who may feel this is off topic for LtU, but I can't pass up the opportunity to get pointers from Gilad on designing a module system, ;-)

Here is some pseudo-code which may help frame the discussion:

module M {
  fields {
    // State associated with particular module instances.
    x : int 
  }
  methods {
    // A module initializer
    Constructor(n : Int) {
      x = n;
    }
  }
  classes {
    class C {
      methods {
        Get() : Int { return M.x; }
        Set(n : Int) { M.x = n; }
      } 
    }
  }
}

module N {
  imports {
    M as module1;
    M as module2;
    Console; // Console as Console is implied here
  } 
  methods {
    Constructor() {
       // Construct the module instances
       // Order is specified. 
       // We could even do conditional module instantiation.
       m1 = new M();
       m2 = new M();
       Console = new Console();

       // Construct two different instances of class C, 
       // Both have the same type "M.C", but are associated 
       // with different instances of the module M 
       M.C c1 = new M1.C(0);
       M.C c2 = new M2.C(1);

       Console.WriteLine(c1.Get()); // 0
       Console.WriteLine(c2.Get()); // 1
       c2.Set(42);
       Console.WriteLine(c1.Get()); // 0
       Console.WriteLine(c2.Get()); // 42
    }
  }
}

As I understand it, this is similar to a limited subset of the Scala object/module system. Several important differences: I don't support type or module parametricity over types or modules, only parametricity over values.

I assume module definitions are stateless - only module instances have state, right?

Correct.

If module definition M contains class definition C, then two instances of M, m1 and m2, would each have a distinct class corresponding to C.
These two classes are NOT necessarily equal (they could have distinct superclasses, ...

Yes, that would be true in a more expressive system but not in the one I am proposing. I am only considering a system where modules and types are parametric over values, not types.

... and they implicitly depend on distinct state)

That is true.

and their instances may well have distinct types as well.

I want to disallow that possibility explicitly.

If module definitions refer to other module definitions by name, then there is a global namespace, albeit no global state. Is that the intent?

Yes. But I'm constantly re-evaluating this point.

If so, module definitions have hardwired external dependencies that are not parametric. This introduces ordering dependencies when compiling and loading module definitions.

This makes sense. I have to try and figure out whether I can live with that. I am not entirely comfortable going as far as Newspeak does, with complete parametricity. One of my concerns is the potentially large number of parameters required in very big software. We talked a bit about this on this thread.

I'm also unclear if you want to statically typecheck your code, and want module definitions to include/induce type declarations

I do want to do some static type-checking, as much as possible, and I do want modules definitions to induce type declarations where possible.

I don't worry about an excessive number of parameters. Objects provide aggregation, so one should be able to group things together to manage this. Since I don't have enormous programs, I can't prove this. Time will tell.

I had the impression that classes were values in your system. If they are, and you can parameterize modules by values, then you could have classes and types vary between module instances. Or else you must put some arbitrary restriction on the use of class values, say, insisting that superclasses are fixed.

If classes aren't values you don't have proper abstraction over classes. You'll find yourself needing extra-linguistic hacks like or do without. "dependency injection" etc.

The same applies to module definitions. Your use of constructors for modules is a clear failure of abstraction. If modules aren't first class, eventually you will find a situation where you want to abstract over them. If your module system can't do that, you'll have to invent an extra-linguistic tool or do without.

Put another way: imports don't cut it.

I've read both the blog posts on modules, and there's one thing I'm concerned about with the idea of no global namespace: declarations.

Suppose I want to do a bunch of math, including trig. Presumably that's defined in some other module. Do I have to declare that I want to import something called math and then explicitly list every function I want to use? sin, cos, atan, etc.? Seems like this would ultimately result in a whole lot of declaration, and they'd be prone to typos and so forth.

It seems like it would be desirable to be able to import a whole math package at one go, and this wouldn't necessarily hurt the idea that we could have multiple instances and implementation of the math package.

Thoughts?

It's been years since I've explicitly typed a in import statement, and indeed I rarely even see them, even though most of my source files have at least a handful of them. Any modern IDE will simply make this a non-problem.

I'm a big IDE fan as well, but that doesn't mean that I think it's a good idea to design a language so that it requires an IDE to use. Saying the IDE will do it is the same thing as giving up on the problem. And you still have the question of where does the IDE get its definition of the Math module: is it from a global namespace?

i always find it rather frustrating when somebody says "i don't have that problem, therefore it isn't a problem."

"if that is your problem, it can be solved with any modern IDE". If there's a reason you can't use a modern IDE (there are a very few good reasons for that, and a whole lot of bad rationalizations), then I will admit to not being able to help. I'll also admit to thinking that language level solutions to the problem are unlikely to be very productive, compared to the alternative. Happy to sympathize, though, it you're into that sort of thing.

Doesn't this "modern IDE" argument that keeps popping up these days sound suspiciously similar to the "sufficiently smart compiler" fallacy from the old days?

Since the functionality we're talking about has been shipping in production IDEs for at least a decade now. This isn't vaporware. Some of it is practically legacy.

When you talk about putting something 'in the language' in this context, it really means 'standard text based program,' and it sort of implies that the programmer should be able to get the text right without help from the compiler/IDE. Talk of putting something 'in the IDE' means that a tighter feedback loop with the programmer is possible, e.g. resolving an ambiguity by picking the desired resolution from a drop down box.

I don't think this is either analogous to 'sufficiently smart compiler' buck passing or a fallacy.

"He jests at scars that never felt a wound."

This works in today's IDEs because of the global namespace. In a language like Newspeak, not even class/interface declarations are globally available, so there is no way to guess where a particular name ought to be imported from. (In fact, which messages a given object responds to is not even a static property in any sense, as far as I can tell. But that's almost a different problem.)

The only way I see that an IDE could automate some of this in a language like Newspeak is to build the IDE into the running program image. But even then you have trouble... When editing a class declaration, you'd have to be able to say "Assume this class will be instantiated with these objects as parameters. Now help me figure out what to import." But of course it might be instantiated with some other parameters, and anyway it would be pretty cumbersome.

Without any notion of global namespace, I really don't see where IDEs can get much leverage, and I do think this is a legitimate problem. Maybe it would be enough to rely on naming conventions, combined with the global namespace that is implicitly provided by the IDE itself? Ugly, though, in my opinion. Very ugly.

What properties do you ascribe to global namespaces that cannot be mimicked in a multi-stage programming environment with support for pluggable types and first-class modules?

As you can see, I want you to redefine the argument in terms of not having "to build the IDE into the running program image" - which is a silly dependency and creates all kinds of "bundling" issues. Gilad's argument about not abusing type systems leads to this design consequence. You can now think in terms of caching configuration sets and having a currently-selected-configuration.

Despite not having a global namespace, you can have a default schema to bootstrap things. In fact, this is how IntelliSense "Did you mean to include this reference?" effectively works, except it is generalized. I believe NetBeans can be described as working in the same way; I know NetBeans is capable of caching schemas from the Internet, locally, as of version 6. As with all data interchange problems, the first step is to realize you are dealing with a data interchange problem. The second step is to define a format for interchanging data, and not abuse that format with additional semantics on top of its data interchange responsibility.

An interesting "tools" look into resolving terms and binding them to a configuration has seeds of this idea in Greg Little's MIT masters thesis: Programming with Keywords - there was also an OOPSLA paper about code completion in Eclipse: Code Completion Using Keyword Queries in Java by Greg Little and Rob Miller.

Bottom line: there are many attack vectors to solve the false dilemma you propose.

I like Greg's work, but when you actually go and read the paper...you find that this is still very early research and the system isn't very usable yet.

Designing these tools won't be easy, the challenge is how computers can automatically map program context to what the programmer wants, and how can programmers express what the want? I think if we go for a pure tool solution, where we take existing languages and create super "smart" IDEs, we are probably going to fail. Human meaning is so buried in these languages, through documentation and naming conventions, that it is difficult for the computer to do anything with that even if it can reason about the program's structure.

I think the right solution will be a combination of tool technology coupled with new programming languages that take human intentions more seriously, and allow the computer to reason about this intention more easily.

Ritter et al. Modeling How, When, and What Is Learned in a Simple Fault-Finding Task. Cognitive Science A Multidisciplinary Journal, 2008; 32 (5): 862 DOI: 10.1080/03640210802221999

They use the programming language Soar. For what it's worth, I am not sure the language should take human intentions more seriously. That is a huge design box that is very hard to explore. Geoff Wozniak did a Ph.D. thesis under the support and supervision of none other than Richard Gabriel (see: Structuring data via behavioural synthesis) -- I later pointed Geoff to the idea of coalgebras and behavioral synthesis for hardware chip design. Rather, I think we should build programming languages that allow us to better model how humans might approach solving problems, especially as their knowledge about the problem accumulates over time. The fact we build the models in a formal language is good because it helps eliminate modeling errors, and guarantees a certain degree of engineering/scienece tender, love, and care.

This is a problem with any OO language neh? In Scala, you have to do something like "import Math._" but then you can access those functions directly in your source code without further qualification. This could include implicit conversions that enhance existing types (like doubles and ints) with new methods (like sin, cos).

But a global flat namespace would really help out in the discovery process, because often we don't know where to import from. See this post for a discussion on that.

As far as I am concerned, putting functions in the current namespace and using an external module are separate concerns.

If you want to use the math module then do instantiate it. You can access all its functions through the module instance (eg. MyMath.sin(0.5)).

Importing the module functions in the current namespace, if that is what you want, is a different operation. In fact that probably does not necessitate the module to be instantiated first: just declare that you want to import all functions, or sin cos atan from the math module, and the functions become defined when you instantiate the module in a special place reserved for this use. Eg. the imports section of Heron.

Also, I think that top-level modules are resources that you load from a location external to the program, eg. the file system. As such you can use the compiler command-line to specify their location (like C libraries), or you can use URL loading commands inside the program.

I did investigate this and I completely agree that having modules place all definitions in the global namespace is definitely not a good thing. So I ended up deciding on a system that bears some resemblance to the Python modules, but where modules instantiation is separated from module import.

In the latest release of Heron, modules can't be used until they have been instantiated. When you instantiate a class from another module, you then have to associate it with a particular module instance. Using the syntax new MyClass() from MyModuleInstance.

You can see examples of it in action in the following files:

• TestImport.heron
• TestModuleInheritance.heron
• TestAll.heron

There is another flaw in Python's implementation.

If you launch a script, you are stuck in a relative namespace of addins and cannot refer back to the global namespace. This results again in Python having a very nasty side-effect. Think of launching a script for url parsing and having it stomp on your pre-existing URLParse namespace. The funny thing is Python offers a bevy of ways to do relative addressing, but no global addressing. -- I plan to write a front-page story for LtU talking about global addressing schemes soon, as a PLT researcher asked me for prior art in this area of modularity.

Python's module implementation is lame!

Edit: Where do you assert the outcome of your tests are correct, by the way??

Edit: Where do you assert the outcome of your tests are correct, by the way??

Are you sure you really want to know?
...
I run TestAll and watch the output. There is more unit testing of sub-systems within the source code itself. You have to change the settings within config.xml to get it to work.

I mean, if 10 years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself "Dijkstra would not have liked this", well, that would be enough immortality for me. ~ Edsger W. Dijkstra

A simple suggestion might be to stream the results of each test result to an individual test file, and check those into a repository. Your check-ins will only include regressions, assuming versions are immutable.

In this way, your version control repository test_results will keep track of your overall improvement in the quality of your implementation. You can then notice you have fewer bug reports and more bug fixes as time goes by. I would recommend using GIT for this, as its kick butt performance lends itself well to repository trend analysis such as the one I just suggested.

Good advice, thanks. I did add a Hello World program along with a prime number generator to the Wiki. I'll try to do more over the coming weeks.

More pertinent to this thread perhaps is a new page describing the Heron module system.

Thanks everyone for the enlightening and interesting discussion! I am really happy with the outcome.