Lambda the Ultimate

You found it syntactically cumbersome to pass references explicitly; I doubt you'll find it any less syntactically cumbersome to detail the effect types.

It should be easy if we restrict imports, along the lines of Lua and Racket. For example, you could restrict access to global variables using something like an "import only" statement. A module could have an "import only" statement, which would restrict the imports of its submodules and procedures. Each procedure could have something similar, which would restrict the procedures it called, and code blocks could restrict the imports of procedures in them. Furthermore, at any point in which it would be valid to declare the type of a procedure, that procedure's imports could be restricted using an "imports only" declaration. You may be thinking along the same lines as me toward the end of your post.

More relevantly, what would be the type of an object or procedure that accesses a global variable in a restricted manner? Could you pass such objects or procedure references to untrusted code? How will your type-system be detailed enough to distinguish between procedurally restricted, indirect access to a variable or effect, vs. full access? The ability to pass such controlled authority to other objects is the basis for any number of valuable POLA patterns, such as revocable powers.

If I understand you correctly, that would have to be accomplished using traditional OO data hiding, just as it is in an object capability model. So, for example, let's say we want to allow procedure Foo restricted access to A, which we have imported or constructed ourselves. We could create or import an object B that has a reference to A and then pass B to Foo. Foo would then have access to A only through B's interface. I'm trying to provide a superset of the functionality of an object capability model.

The same thing could be accomplished by having multiple interfaces to the same object. Instead of "interfaces," let's call them "permissions." If we define a partial ordering over permissions and let method m have permissions P1,...,Pn and require permissions R1,...,Rn corresponding to n parameters, then we should not allow any method m' without permission P' >= Pi corresponding to object o to pass o as the ith parameter to m. Furthermore, if Pi > Ri for some i, then m possesses a greater level of permission than it requires from its caller. Such an m should be included in a class definition corresponding to the type for parameter i. Methods might have to be included in more than one class definition.

We could then use "import only" statements to restrict access by granting various levels of permissions.

I've seen something similar before.

[... much digging ...]

Ah, yes. Matej Kosik did a lot of work on Taming of Pict _related and did something similar with regards to import restrictions. You might find it interesting.

The same thing could be accomplished by having multiple interfaces to the same object. Instead of "interfaces," let's call them "permissions."

Supporting multiple interfaces is handled effectively via 'facet pattern'. It is unclear to me what you are attempting with partially-ordered permissions.

Personally, I prefer to save myself the trouble and represent interfaces to objects as a record containing a distinct capability per 'method'. This is much more flexible, allowing one to mix and match without raising indirection. 'Objects' become logical entities, evolving graphs of agents and services potentially distributed across multiple hosts, with partial replication for the less synchronization or security sensitive subsets.

Anyhow, I'm still not seeing how you're winning anything with regards to syntactic convenience. You've now listed use of ocap mechanisms anyway, massive extra annotations for 'permissions' for methods, and detailed 'import only' statements - to escape the challenge of occasionally passing an extra parameter around or performing constructor injection. Other solutions, such as implicit parameters, would seem to solve the 'problem' simply and effectively.

I've recently grown interested in Gilad Bracha's Newspeak, which forbids 'imports' entirely. Instead, modules are parameterized. You inject the dependencies of a module upon construction of a module instance.

good stuff. Thank you for digging.

Anyhow, I'm still not seeing how you're winning anything with regards to syntactic convenience.

The contortions are mainly to have a statically checkable system, which might be nice in a systems programming language. The idea is to do whatever we can at compile time in order to avoid contortions at runtime.

I'm personally more interested in 'merging' the compile-time and run-time. This can go two directions: Live programming, persistent programming languages, and JIT move compile-time into the run-time. Partial-evaluation and staged languages move run-time into the compile-time.

Either technique reduces the dichotomy, and reduces the number of distinct 'concepts' users must understand to grok the language.

Staging with an object-capability language would (ideally) allow a developer to securely provide authority to a set of objects that will exist at runtime. The set of authorities provided by the developer could be distinct from those provided by the user. The code could then coordinate authorities of the developer and the user to useful effect.

Live programming with object-capability languages has pretty much the same story, excepting that we grant a live reference to the end-user rather than granting an executable.

I've spent a bit more time figuring out what you meant with the permissions. I've seen something similar before with Richard Kulisz's "Grand Unified Capabilities" model - which never obtained credibility in the ocap community. RK's GUC can be modeled with plain 'object' capabilities via facet-pattern.

Whereas RK had a bitfield of specific permissions for read/write/create/watch and so on, you described a set of permissions as granting access to each method. If you represent the set of methods as a bitfield, then each 'permission' value P1..Pn (and R1..Rn) would correspond to a mask of bits. Partial ordering is easily computable: (Px >= Py) is computed by (0 == (Py & ~Px)).

RK applied these masks on the references between objects. Every reference effectively holds a pointer and a bitfield. You suggest making this bitfield 'statically typed'. It is an interesting idea. The notion of 'public vs. private' methods is subsumed by the more flexible permissions you are suggesting.

OTOH, I've long considered the monolithic 'class' structures problematic for other reasons (relating to modularity, dependency management, garbage collection, security, and distribution), so I consider breaking 'objects' down into composable graphs of components with exposed facets to be a significant victory all its own.

Whereas RK had a bitfield of specific permissions for read/write/create/watch and so on, you described a set of permissions as granting access to each method. If you represent the set of methods as a bitfield, then each 'permission' value P1..Pn (and R1..Rn) would correspond to a mask of bits. Partial ordering is easily computable: (Px >= Py) is computed by (0 == (Py & ~Px)).

RK applied these masks on the references between objects. Every reference effectively holds a pointer and a bitfield. You suggest making this bitfield 'statically typed'. It is an interesting idea. The notion of 'public vs. private' methods is subsumed by the more flexible permissions you are suggesting.

exactly! We're on the same page now.

OTOH, I've long considered the monolithic 'class' structures problematic for other reasons (relating to modularity, dependency management, garbage collection, security, and distribution), so I consider breaking 'objects' down into composable graphs of components with exposed facets to be a significant victory all its own.

I'm not quite sure what you mean here. Maybe you're talking about inheritance? It looks to me like E basically uses delegation instead, along with some syntactic sugar.

You got me thinking, though!

I like the way Haskell separates type classes from datatypes, and the permissions above are very much like Haskell type classes. Parametric polymorphism is used at runtime to distinguish between datatypes, but the class of a datatype in a function is always known at compile time.

Let's throw out the word 'class' above and just talk about permissions and datatypes. Permissions are basically like interfaces or Haskell type classes. We're left with this from above:

If we define a partial ordering over permissions and let method m have permissions P1,...,Pn and require permissions R1,...,Rn corresponding to n parameters, then we should not allow any method m' without permission P' >= Pi corresponding to object o to pass o as the ith parameter to m. Furthermore, if Pi > Ri for some i, then m possesses a greater level of permission than it requires from its caller.

Okay, now since we are basically considering a permission an interface or type class, we ought to be able to simply refer to the permission a method has for a particular parameter. A permission doubles as a type class. Here's some pseudocode:

permission write
permission read

data A = ...
data B = ...

f :: read -> write -> Void
f (A a) (B b) = ...

g :: write -> read -> Void
g (A a) (B b) = ...

This says that f both possesses and requires read access for its first parameter. g both possesses and requires write access for its first parameter. and similarly for the second parameters.

This decouples datatypes from type classes. It's a little bit confusing, though. In this case, f does not have the permission to call g a b, and g is not defined on g b a. So f cannot call g on a and b in any way. It has the right permissions and the right types, but they're swapped. Even though it's confusing, we should know whether or not a method is defined for a datatype at compile time.

I just realized that it is confusing because, unlike Haskell, the type of a method does not at all constrain its definition; it only constrains the other methods it is allowed to call.

The tricky thing is handling methods with more permissions than they require. Those are special from a security and engineering perspective, since they allow untrusted code to call more trusted code. Let's call them "taming methods" for whatever parameter they have escalated permissions for. If a method m is a method is defined for a datatype D passed as a parameter that it is a taming method for, then m must be declared in an access control list for D. An access control list is something like a class definition, but it doesn't really matter where exactly it is; it could even be spread out over the source. It only matters that it is managed by trusted code. Taming methods would also need special annotation, unless they all had unrestricted access to datatypes.

We can add polymorphism (parametric or subtyping) independently by creating a separate union or hierarchy among the datatypes.

Oh, and we don't need modules. Instead, just let methods import and export permissions of their own. A method m cannot call another method m' unless it exports a permission at least as great as the one m' requires. As usual, methods with greater permissions than they required would have to be managed by trusted code somehow. But we can have namespaces if we want them.

isn't it all a matter of fractal zoom? might not the little components be classes?

Fractal zoom? There's glory for you!

The issues I have with 'classes' is that they combine too darn many responsibilities: function, namespace, containment, ownership, object-graph construction, unit of identity (and thus state, synchronization, communication, and capability), maintenance of helper code.

Breaking these responsibilities apart doesn't necessarily result in 'little' components, but does result in more composable, reusable, independently GC-able, independently distributable, and securable components.

In object-oriented analysis methodologies used in real-time engineering, a class just represents a problem domain entity.

It would be nice to go back to this simpler way of thinking, rather than have classes serve too many responsibilities. However, it does not make sense to me to come up with individual concepts for all these things, and split them up into knobs you tune. Classes are the right concept, the problem is methodology.

The issue with splitting these responsibilities up, so far, has been explored in pluggable type systems, but usually at a cost to REPL speed.

In popular programming languages, a 'class' creates state, defines functionality that uses state, combines functionality - a particular group of methods, creates objects, hooks objects together, maintains a namespace, and describes a 'type'. In languages without GC, classes also manage memory of the 'child' objects. These are programming-language responsibilities, not 'domain' responsibilities. Combining all these responsibilities into one language structure hinders development of reusable components.

Beyond that, they tend also //serve// too many domain responsibilities.

I'm using the word 'class' with the connotations from popular OO programming languages, not domain analysis. I would expect that to have been be clear from context. But I understand that your tendency to put a UML spin on everything isn't so different than my tendency to put a distributed programming spin on everything.

I do not agree that classes are the 'right' concept, not at all, at least not for programming languages.

Rather than looking to pluggable type systems, look to languages and programming models that never made mistake of introducing the OO 'class' in the first place...

The ability to pass such controlled authority to other objects is the basis for any number of valuable POLA patterns, such as revocable powers.

Oh, and is there a book or a paper with some of those patterns?

Most of them found through erights. But that site is painful to navigate, so I'll point you to a few subsections:

Secure Distributed Computing of the E wiki has a section dedicated to POLA patterns.

Cap-talk mailing list archives available for search and perusal.

Capability documentation from e-lib is very approachable.

Robust Composition (thesis) is of intimidating size and depth.

Horton's Who Dunnit [ltu] achieves user responsibility tracking via capabilities.

There is plenty more out there. Capabilities go back to the 70s and were part of the secure design for a major operating system of the time, key-kos.

Information flow seems significantly stricter (in a good even if unsound-in-a-production-setting way).

I think something like Fine is more in the direction of what's going on (and, like E, in a more modular way than shared globals).

Both of these look promising, thanks!