Lambda the Ultimate

It is unclear to me whether you're focusing upon the performance aspect or the semantic one.

I pointed out how they are semantically the same, and I'm trying to find out if anyone has exploited this equivalence as hints for specialization.

it is very difficult to treat staging as an instance of partial application. Without sufficient support for first-class program elements, the converse is equally difficult

Can you cite an example of a partial application that cannot be equivalently represented by a closure and a runtime generated function that has the arguments embedded in the instruction stream?

Seems to me, you can compile all partial applications into code templates with "holes" for the arguments. Something similar was done for runtime code gen in Cyclone.

Partial application and staging are not semantically the same.

Every closure is a partial application, semantically.

Partial application is often inflexible compared to staging because not all staging produces functions. Staging, in general, may also generate types, typeclasses, namespaces, aspect-oriented rules, and so on. I would not know how to introduce typeclasses to a Haskell program by use of "a closure and a runtime generated function that has arguments embedded in the instruction stream".

You cannot "compile all partial applications into code templates with 'holes' for the arguments" unless you restrict partial-application to AST-compatible constants (such as integers and floats and strings). Many potential arguments for partial application do not have an equivalent representation in stateless "code". That said, performance may still benefit from specializing an algorithm to these runtime arguments - or even to their current state.

The paper you referenced in the OP avoids many of these issues by using a simple language.

So they aren't semantically the same. But there is still much performance benefit available from compiling those closures (and other partial-applications).

Partial application is often inflexible compared to staging because not all staging produces functions. Staging, in general, may also generate types, typeclasses, namespaces, aspect-oriented rules, and so on.

I'm not sure I see the problem. Type erasure ensures that all these distinctions are eliminated at runtime, so all you're left with are functions and products.

Either a function is parametric over a type/type class/namespace/etc., and so a stage-n type/type class/namespace/etc. fits in automatically, or it's not parametric, in which case it exists at stage-x where x >= n.

Consider a language executing in CPS form: I think it's then trivial to see that all staging produces functions, that is, the function that continues the computation.

You cannot "compile all partial applications into code templates with 'holes' for the arguments" unless you restrict partial-application to AST-compatible constants (such as integers and floats and strings). Many potential arguments for partial application do not have an equivalent representation in stateless "code".

Not sure I follow. If you have a universal representation for all values as is typical in polymorphic functional languages (ie. pointer-sized), then the technique I described seems pretty straightforward. I'm not sure how statelessness enters consideration.

If you define 'staging' such that a programmer cannot distinguish staging from simple function evaluation, then of course there won't be a problem (except with the utility of your definition).

A few common examples of staging that I've seen:

• fetch a schema for a relational database; generate the correct data types and functions to store, marshall, serialize, query the database, and even typecheck the code using the database
• fetch an image from the disk (perhaps a splash-screen), convert it to TGA, and store it directly into the generated binary (as an example of data integration in general)
• typechecking, itself, could be considered a stage - especially in the more typeful programming languages (that, for example, make dispatch decisions based upon types)

Not all staging occurs at runtime.

If you have a universal representation for all values as is typical in polymorphic functional languages (ie. pointer-sized), then the technique I described seems pretty straightforward. I'm not sure how statelessness enters consideration.

Not all things you can capture in a closure or partial-application are 'values'. References to open sockets and file handles and state, for example, can be captured by a closure, but typically not in what I would call a "code template". Did you mean to use that word-phrase with a very broad interpretation?

If you define 'staging' such that a programmer cannot distinguish staging from simple function evaluation, then of course there won't be a problem

I'll note that I explicitly referred to "staged compilation", and provided a reference to be as specific as possible as to my meaning. I'm not sure when this became about other types of staging, because I've been very specific as to the type I'm interested in, ie. runtime execution.

Not all things you can capture in a closure or partial-application are 'values'. References to open sockets and file handles and state, for example,

These are referenced by values as well, namely, the value naming the handle. By 'value', I mean an entity for which the language runtime has a defined semantics. In the case of sockets and file handles, these are FFI values.

can be captured by a closure, but typically not in what I would call a "code template". Did you mean to use that word-phrase with a very broad interpretation?

Here are Cyclone's templates used in runtime code generation, to eliminate any ambiguity as to my meaning.

Closures are certainly semantic

The circles that I've run in would not agree. By the definitions I'm accustomed to, closures are an implementation technique for higher-order functions, and not normally a semantic concept. (Unless your language is a bit perverse and exposes the closure of a higher-order function as something that can be explicitly manipulated in regular code.)

I am curious what definitions you are accustomed to that would have you understanding 'closure' to be an 'implementation technique'.

'Closure' describes a relationship between first-class functions and lexical context - in particular, that the first-class function expression implicitly captures ('closes over') referenced free variables of the lexical context, and that the lifetime of those references will be at least as long as the lifetime of the closure. Alternatives to closures would include use of dynamic scope, scripting, perhaps forcing programmers to explicitly copy referenced values into an object. This understanding of a closure tells us nothing about how to implement a first-class function.

In computer science, a closure is a first-class function with free variables that are bound in the lexical environment. Such a function is said to be "closed over" its free variables. A closure is defined within the scope of its free variables, and the extent of those variables is at least as long as the lifetime of the closure itself. - Wikipedia

There are, of course, many implementation techniques for closures. The original, operational definition of a closure from Landin was developed for a language with pervasively mutable state, so involved reifying a mutable environment and associating it with some control code. But languages that restrict mutation can often implement closures by simply copying values. And it is feasible to implement closures by deferred compilation (the subject of the OP).

I do not consider the definition of 'closure' any less semantic than the definitions of 'first class function' and 'lexical scope'.

I'm with Leon. I understand "closure" to be an environment and a function pointer. There's some wiggle room on how the environment is stored (e.g., hierarchically or not), but I wouldn't consider a specialized function implementation that inlines the partially applied arguments to be a "closure".

Yup. Though for another variation on closures, the EoPL interpreters implement closures by storing the complete environment at the point of creation, along with the abstract syntax tree of the function.

I'm aware of four implementation techniques for HOFs:

1. Closures (probably the most commonly used)
2. Lambda lifting
3. Defunctionalization
4. Dynamic compilation (probably the least used, but the one everybody thinks of first)

Each is a bit different. But of course, CS vocabulary has quite a bit of variance too, and is far from standard.

I think that's an apt breakdown of my exact thoughts. Point 4 is along the lines I was thinking, and it's the least used because it ends up being very inefficient if you have a language with pervasive curry-style functions due to (I think) I-cache flushes.

Maybe some background will help people understand what I'm looking for: in reading about the great techniques in partial evaluation, staging, and supercompilation, a repeated theme is the poor predictability of the analyses.

I'm trying to see if there's been any work to reduce the automation and take a more naive/literal approach. My starting point is an operation that is used pervasively and is semantically simple, yet can be efficiently implemented by runtime compilation in certain contexts: partial application. So the developer wouldn't need to learn any new constructs to generate efficient code at runtime, except perhaps an idiomatic way of exploiting partial application.

Ultimately, I'm looking for something simpler than the automated inference techniques by exploiting this semantic equivalence.

I think we would do quite well with profiling and programmer annotations. Programmer annotations would be akin to seq or par, instead suggesting or forbidding runtime compilation of curried functions.

Profiling could be performed effectively at runtime or during trial runs, depending on the domain (long-lived servers vs. embedded). A potential technique would be to add a call-counter and 'birthdate' to each closure, in order to perform hotspot analysis and lifetime per closure and call-site - then heuristically decide which to compile. Further profiling would tell us which compiled closures are actually profitable.

These techniques are 'black box' but seem to provide a pretty good solution to the problem. You seem to want some sort of static analysis technique, but I think the best you'd do is an expert system developed from a bunch of heuristics developed from a bunch of profiles. This isn't a peephole optimization; it takes a lot of context to anticipate whether time and space costs of compiling will pay for themselves.

These speed up average execution time, but they do not help predictability of these optimizations, which is what I'm after. If you're in a game loop, you need to guarantee that certain operations are as fast as they can be.

MetaOcaml's staging annotations are great in that sense, but by all I've read, they're difficult to get right (the finally tagless papers acknowledge this).

Partial applications are very straightforward though, so if there's a way to extract some staging information with little additional programmer intervention, that would ideal. For instance, consider adding a "specialize" keyword that when applied to any partial application, generates a specialized version of it using the arguments at the call site, or it generates a compile-time error if it cannot. Similar to the "tailcall" keyword which guarantees a call is a tail call, which we've discussed here in the past.

Yeah, I suppose there are two aspects to predictability of optimization: knowing or controlling where an optimization will be applied, and knowing where an optimization will actually be profitable. Programmer annotations provide the former, but not the latter. Profiling supports the latter, but not the former. I would suggest using both, but there is some complexity cost.

consider adding a "specialize" keyword that when applied to any partial application, generates a specialized version of it using the arguments at the call site

I have. That's the sort of feature I meant when I mentioned programmer annotations.

Interesting.

Someone corrected me on this view a few years ago, and I have the vague impression it was you, Matt. I was explaining that we couldn't reasonably have 'closures' (where I meant a function pointer and a reference to environment) in a distributed programming language. I remember being patiently told that, if I restrict variables to immutable, I could simply copy them into the function and it would still have closure semantics from the programmer's POV.

It seems at least one common definition - the one at the top of the Wikipedia for the last three or four years - agrees with the more 'semantic' understanding of closures. (Closures are typically implemented with a special data structure that contains a pointer to the function code, plus a representation of the function's lexical environment (e.g., the set of available variables and their values) at the time when the closure was created. - Wikipedia 2006-2011)

As we consider languages with just-in-time or hotspot compilation, or distribution of first-class functions, or other powerful and confusing devices under-the-hood, we really must focus on the programmer's POV - i.e. the closure semantics, what means 'language support for closures' in terms of language interface, rather than a particular implementation.

It seems unfortunate that the term 'closure' is used for this purpose at all, since it overloads a perfectly good algebraic meaning.

Someone corrected me on this view a few years ago, and I have the vague impression it was you, Matt. I was explaining that we couldn't reasonably have 'closures' (where I meant a function pointer and a reference to environment) in a distributed programming language.

How would you characterize Waterken? Or do you consider distributed objects to be different from closures?

Objects, in general, are a different concept from closures. You can profitably have both concepts in a single language, e.g. if you can define anonymous classes within a function the 'closure' aspect would allow you to capture the lexical environment within each class instance.

Closures can serve as a poor man's objects, and vice versa, but the two are not generally equivalent with respect to type-system integration, reflection, and management of state.

In my own language, I have agents (instead of objects) and closures, but the closures are immutable.

I've not studied Waterken much beyond its security patterns, so can't answer your question in more specific terms.

Closures can serve as a poor man's objects, and vice versa, but the two are not generally equivalent with respect to type-system integration, reflection, and management of state.

Do you agree that the encapsulation of state for both abstractions poses the same challenges in a distributed context? Waterken supports just such a semantics for objects, where a cryptographic identifier can designate a delegate (object+method pair), which is exactly a closure. You can even tease them apart and designate the method reference via a name, and it's state via a cryptographic identifier.

I'm just trying to understand why you think you couldn't do this.

Use of cryptographic URLs is not something I would qualify as 'support for closures in a distributed programming language' because you did not distribute (replicate or mobilize) the closure.

The difficulty with distributing closures is a bit higher than for distributing objects, in part because it is unclear to which 'closure' any particular unit of 'state' actually 'belongs'.

I don't think (present tense) you cannot support distribution with closures. I simply use immutable, pure closures and use another primitive for the state element.

a cryptographic identifier can designate a delegate (object+method pair), which is exactly a closure

From an expressiveness POV and others, that simply isn't true. A library can support yurls to object+method pairs without any support for binding ('closing over') open variables using the lexical scope in anonymous functions or classes. It's a hasty generalization to say "x is like y in aspect z, therefore x is a y".

The reason it is called a "closure" is that an expression containing free variables is called an "open" expression, and by associating to it the bindings of its free variables, you close it. - Ake Wikstrom - Functional programming Using Standard ML

Use of cryptographic URLs is not something I would qualify as 'support for closures in a distributed programming language' because you did not distribute (replicate or mobilize) the closure.

The closure was distributed, but it was not mobile. I think the distinction is important, and it looks like you're redefining an established term. Waterken objects satisfy every meaning of distributed object I've come across, but I agree they are not mobile objects (well, some are, but you have to annotate them as such).

Of course, you could serialize the closure entirely into hidden form fields, and in fact, this is what I'm doing in my unreleased web framework. This was one aspect where I disagreed with the Waterken approach of leaving state server-side by default.

The difficulty with distributing closures is a bit higher than for distributing objects, in part because it is unclear to which 'closure' any particular unit of 'state' actually 'belongs'.

Not sure I follow. Do you mean it's more difficult to ensure encapsulation? You can ensure encapsulation is respected via encryption as well, ie. encrypt the serialized closure state.

It's a hasty generalization to say "x is like y in aspect z, therefore x is a y".

Except that's not the case here. x is like y in every meaningful respect. A delegate encapsulating a (object, method selector) pair, with only an "apply" operation accepting the remaining arguments is in every sense exactly a closure. In what way are they different to you?

Regarding your quote, I have a simple question: if I give you two cryptographic identifiers, one naming a "true closure" by your definition, and one naming a delegate as described above, both of which accept the same number and types of remaining arguments, can you distinguish via any sequence of operations on these opaque identifiers that one is a "true closure" and one is not? If you cannot, is there truly a meaningful distinction between them, at least in the context of a distributed system?

I did not say you don't have distributed closures. I said you don't have language support for distributed closures.

It would be misleading to claim language support for plain old local closures if your language could not create them. Similarly, if you want to claim language support for distributed closures, you darn well better have significant support for specifying (in a language) how your closures are to be created and distributed. In practical terms, your language must also support you in reasoning about behavior, performance, and security of the resulting program despite the many fallacies of distributed systems.

The Waterken protocol and framework might qualify, but use of yurls is not a sufficient argument.

You could serialize the closure entirely into hidden form fields, and in fact, this is what I'm doing in my unreleased web framework. This was one aspect where I disagreed with the Waterken approach of leaving state server-side by default.

I agree that server-side state should be avoided when feasible for message-oriented web-services. Server-side state can introduce all sorts of GC issues, scalability snags, and denial-of-service vulnerabilities. Much better to associate most state with a 'connection' concept that has a clear disruption stage.

But serializing 'stateful' closures is not generally possible (that is, without sacrificing consistency and other nice properties). You'll run into a snag when serializing two closures that share a state reference, or serializing the same closure to two independent consumers.

The difficulty with distributing closures is a bit higher than for distributing objects, in part because it is unclear to which 'closure' any particular unit of 'state' actually 'belongs'.

Not sure I follow. Do you mean it's more difficult to ensure encapsulation?

Not quite. Closures on a mutable environment are more expressive than typical objects with respect to ownership and access to mutable state. More expressiveness is often a good thing for the user, but it causes a problem for the language implementor: fewer invariants to optimize against, and more cases to handle correctly. It can be difficult for a language (or a programmer) to know 'what the bounds are' when distributing a closure to a remote host. Just how much of the jungle will be sent along with that banana?

You can ensure encapsulation is respected via encryption as well, ie. encrypt the serialized closure state.

I enjoy E's use of sealers/unsealers as semantic primitives for a distributed programming language. For my language, I plan to use them for all sorts of things - information-flow security, and modeling abstract types. Actual encryption doesn't need to happen, though it is a useful implementation technique for these primitives.

Except that's not the case here. x is like y in every meaningful respect. A delegate encapsulating a (object, method selector) pair, with only an "apply" operation accepting the remaining arguments is in every sense exactly a closure. In what way are they different to you?

The underlying premise of your argument (and your 'simple question') is that attributes observable to the consumer are the only "meaningful respects". You are claiming that since both techniques leave you one "apply operation from accepting the remaining arguments", they are the "in every sense, exactly" the same.

But, if I accept your premise, I would also need to accept an argument that all Turing-complete languages are alike "in every meaningful respect" because the languages allow writing programs where an end-user could not tell the difference while observing from the outside. I would find such an argument absurd, and so I must reject your premise.

Expression and composition and are also very "meaningful respects". It remains the case that objects and closures have significant differences in how they are expressed and composed, how they are typed. The ease or difficulty of expression has a significant impact on which programs are written in the first place.

I did not say you don't have distributed closures. I said you don't have language support for distributed closures.

Ok, so what does it mean for one to have language support for distributed closures? Let's suppose a language like C# which has delegates/lambdas which can close over state. This should satisfy your requirements for qualifying as a closure.

This delegate is compiled as an anonymous class that I can reflect on in exactly the same way I can reflect on other objects, and export in the way Waterken does (pass-by-ref), or I can break it open and export all the closed over values (pass-by-copy). Does either or both of these approaches constitute language support for distributed closures?

But serializing 'stateful' closures is not generally possible (that is, without sacrificing consistency and other nice properties). You'll run into a snag when serializing two closures that share a state reference, or serializing the same closure to two independent consumers.

This is perhaps the meat of the matter. Waterken handles this by unilaterally declaring that all state is immutable, and that only values encapsulated in Ref<T> will be treated as mutable state. Drastic, but not uncommon in functional languages; this is in fact exactly how SML and OCaml treat mutable state.

I haven't decided what to do about this case myself, other than discourage shared mutable state by largely ignoring it as Waterken does. I hinted previously how transactions seemed to fit naturally here. Each request gets its own copy of the store, and the changes are only committed back on an application-specific event. As you pointed out in that thread, this semantics mimics a Worlds-type model.

In any event, I don't see why your argument doesn't apply equally to objects. Unless you believe that closures encourage more mutation than objects do, and thus exacerbate this problem?

It can be difficult for a language (or a programmer) to know 'what the bounds are' when distributing a closure to a remote host. Just how much of the jungle will be sent along with that banana?

A good question. Waterken takes the position of pass-by-ref by default, unless you explicitly mark a class pass-by-copy. The object must then have a specific structure to implement the copy semantics. Certain primitive values, like integers and strings, are pass-by-copy by default. This is consistent with Waterken's "safe and secure by default" approach.

But, if I accept your premise, I would also need to accept an argument that all Turing-complete languages are alike "in every meaningful respect" because the languages allow writing programs where an end-user could not tell the difference while observing from the outside. I would find such an argument absurd, and so I must reject your premise.

If they were local values, then I agree the premise may be flawed (depending on your language), but these are not local values. In the domain of distributed objects, a remote delegate and a closure are semantically equivalent, since we can only send messages to these opaque references. Without some form of distributed "eq" or reflection operation, they are indistinguishable.

My distributed programming language may view such opaque references as closures allowing the composition that HOFs allow, and yours may view them as objects permitting a different set of compositional operations. But intrinsically, the state management and distribution of either seems to pose the exact same challenges.

And this was my original question: I don't see how object state and closure state are different for distribution purposes, ie. you support distributed objects, but implied distributing closures was infeasible.

export in the way Waterken does (pass-by-ref), or I can break it open and export all the closed over values (pass-by-copy). Does either or both of these approaches constitute language support for distributed closures?

No, but you're getting there.

You'd additionally need integration with the type-system to recognize latencies and concurrency properties, possibility for disruption, and possibly limitations on reflection. You'll probably want at least semi-transparent distribution (where a local closure can act like a remote one).

For pass-by-copy you would be in violation of the language's semantics unless you also used some sort of linear typing for all the mutable closed-over variables. You might instead need to support a consistency protocol (akin to live distributed objects).

Critically, you also need the ability to distribute a closure without passing it. That is: I place a free-standing closure on Sandro's machine, then I call my closure, and my closure starts interacting with services on Sandro's machine. This is one of the most important patterns in distributed programming, and requires an expression distinct from passing a closure as an argument. One possibility is to declare the closure should be hosted 'nearby' one or more of the YURLs - which just happen to be on Sandro's machine.

Language support for distribution means a lot more than just serialization. It means remaining absolutely faithful to the language semantics, and having decent semantics for distribution.

Waterken handles this by unilaterally declaring that all state is immutable, and that only values encapsulated in Ref will be treated as mutable state.

That does simplify things. I used a similar approach for some of my earlier language designs - using a special type for mutable state (but not quite an IORef due to potential latency and disruption issues when accessing one remotely).

transactions seemed to fit naturally here. Each request gets its own copy of the store, and the changes are only committed back on an application-specific event. As you pointed out in that thread, this semantics mimics a Worlds-type model

Transactions might help, but distributed transactions raise their own pains - and are very difficult to integrate with foreign services and FFI.

In any event, I don't see why your argument doesn't apply equally to objects.

You're ignoring the problem of distributing those Ref<T> elements, deciding where they 'live'. It's easy to overlook problems when you choose to ignore details. Start tackling that problem, and you'll see why the 'boundaries' on objects (a clear inside and outside) are a rather useful property when distributing them.

Waterken takes the position of pass-by-ref by default, unless you explicitly mark a class pass-by-copy. The object must then have a specific structure to implement the copy semantics. Certain primitive values, like integers and strings, are pass-by-copy by default. This is consistent with Waterken's "safe and secure by default" approach.

I see. Objects are at best second-class in the protocol, then - enough support for some useful applications, but not very compositional.

If they were local values, then I agree the premise may be flawed (depending on your language), but these are not local values.

I do not believe this argument is a reasonable one.

In terms of 'local values', your argument is essentially that you can wrap both (object,method) pairs and closures such that they have the same, opaque type. Other program operations cannot peek inside the opaque type, except by executing it. Therefore, you claim, closures and objects are the same.

That would be a wrong conclusion. You could certainly claim that the opaque type is the same. You could make a reasonable argument that the types of (object,method) pairs and closures are compatible after construction via the opaque type. But you cannot rationally argue that closures and objects are the same with regards to other semantic properties, nor may you reasonably claim that semantic properties other than this compatibility are irrelevant.

Local vs. distributed isn't a valid excuse for the distinction you want to make - not when many languages have 'opaque' types even locally, and especially not for a distributed programming language where 'local' is a relative term even within a single application.

You'd additionally need integration with the type-system to recognize latencies and concurrency properties, possibility for disruption, and possibly limitations on reflection. You'll probably want at least semi-transparent distribution (where a local closure can act like a remote one).

Ok, let's assume these are all needed, it seems to me that these exact same challenges also apply to objects.

As for handling latencies and concurrency, all remote closures would return futures.

That is: I place a free-standing closure on Sandro's machine, then I call my closure, and my closure starts interacting with services on Sandro's machine. This is one of the most important patterns in distributed programming, and requires an expression distinct from passing a closure as an argument.

Are you talking about mobile code again? I don't think mobile code is strictly necessary for distributed programming, though it's certainly very useful. In any case, how do you get that closure on my machine, or start it running without passing it as an argument? All you have are messages, so this mobile code has to be sent or designated via an argument at some point.

You're ignoring the problem of distributing those Ref elements, deciding where they 'live'. It's easy to overlook problems when you choose to ignore details. Start tackling that problem, and you'll see why the 'boundaries' on objects (a clear inside and outside) are a rather useful property when distributing them.

The behaviour of Ref<T> is provided by the backing store used in the distributed application. In Waterken, by default this is a single-threaded Vat-based object store, so the reference always live in the same Vat. However, there is no reason the ref couldn't be backed by a cluster, or a distributed database. If that's not what you mean, then I'm afraid you're going to have to be more specific.

I also don't see how the inside and outside of a closure aren't just as clear as they are with an object. A captured value is inside, an argument to the closure is outside.

I see. Objects are at best second-class in the protocol, then - enough support for some useful applications, but not very compositional.

I don't follow. What would make them first-class?

But you cannot rationally argue that closures and objects are the same with regards to other semantic properties, nor may you reasonably claim that semantic properties other than this compatibility are irrelevant.

But the distributed objects/closures are in fact semantically the same since all we can do is send the same messages to them, and receive the same replies. They are observationally equivalent, and the semantics of distributed programming consists of sending and receiving messages. What other semantic properties are there for distributed objects?

Even if you add some sort of distributed eq, any alleged type the remote opaque reference may report cannot be trusted unless you also trust that host. So the semantic properties of closures and object delegates are distinguishable only within a trust boundary. That's not the general case, and certainly not a pattern a distributed programming language should encourage IMO.

mobile code again? I don't think mobile code is strictly necessary for distributed programming, though it's certainly very useful

You cannot reasonably claim language support for distributed closures until your language can (among other things) construct one. And you cannot construct a distributed closure without distributing a closure. A closure may include ad hoc code. Therefore, distributing (aka mobilizing) code is strictly necessary if you want to claim language support for distributed closures. QED.

Some sort of code distribution is a prerequisite for distributed programming. Code needs to end up on the remote CPUs somehow, whether through sneaker-net, apt-get, or an app-store. A relevant question, especially for convenient distributed programming, is the extent to which our languages will support this essential requirement.

for handling latencies and concurrency, all remote closures would return futures

Yes, that's a very useful approach - especially if you can pass the futures to other hosts/vats.

A related typing issue is that a closure, to be distributed, needs more than a remote type: it also cannot hold any references to local types - unless those will be distributed along with the closure. Supporting this discipline would also be part of type-safety.

how do you get that closure on my machine, or start it running without passing it as an argument? All you have are messages, so this mobile code has to be sent or designated via an argument at some point.

A programmer must somehow designate a 'location'.

The actual distribution may occur alongside other protocol-level features such as distributed garbage collection, overlay routing, survivable networking, and (per your earlier suggestion) distributed transaction services. In terms of Waterken, protocol-level features could interact with a few pre-determined URLs that might be computed by stripping a base URL from any YURL. Basically, negotiating code-distribution is a host-level operation, effectively an ambient authority.

For my language, I use objects to designate locations: a developer can declare that one object is to be hosted 'nearby' another object. (I technically use agents instead of objects, but the idea is the same.) If I have a YURL to an object on Sandro's machine, I am free to say that my object should be hosted 'nearby' that YURL. Typically, this declaration would result in my object being hosted upon Sandro's machine. However, I treat 'nearby' as a constraint and another way to achieve the same constraint is for Sandro's machine to mobilize (or replicate) the remote object to my machine - so long as that does not violate other constraints or security concerns. Sensors and actuators and FFI services would be generally treated as immobile.

This declarative approach results in mobilizing 'cliques' of objects: object A wants to be nearby object S on Sandro's machine; objects B, C, and D all want to be nearby A. In a vat-based system, where vat semantics are exposed within the language, it may be preferable to construct remote mini-vats rather than individual closures, in order to support locality within the distributed vat. (You'd potentially have cliques of vats.)

To 'run' an object, I would call it normally, just as I would any remote object or closure. In a well-designed and well-implemented distributed programming language, it should be easy to avoid extra round-trips by packaging initial call(s) in the same message as the object. For my own language, this extra step is moot: agents are, by nature, autonomously active - observing and deciding and demanding.

Ref<T> is provided by the backing store used in the distributed application. In Waterken, by default this is a single-threaded Vat-based object store, so the reference always live in the same Vat. However, there is no reason the ref couldn't be backed by a cluster, or a distributed database. If that's not what you mean, then I'm afraid you're going to have to be more specific.

Distribution of state (figuring out where it is distributed), and management of the resulting state, is a deep and interesting problem that you seem to believe is rather shallow. I urge you to explore it more thoroughly, or at least stop dismissing it. Your recent suggestion - clustering and distributed databases - tend to be far too computationally expensive to secure (since you need to secure them against their hosts) for use as a language primitive.

Vat-based storage is reasonable, but the question becomes: which vat?

Closures do not help us answer this question - there is no clear relationship between where closures live and where state lives. Objects provide a simplistic boundary - an inside and an outside - that provides a simple answer. (This is simplistic because concurrent or individually-distributed objects have horrible compositionality properties with respect to deterministic and atomic updates.)

If you want vat-based semantics, I'd suggest vats be the basis of distribution. That is, rather than constructing a remote object, you spawn a remote vat that happens to contain an initial set of objects. Vats also provide a boundary - an inside and an outside, and an easily analyzed limit upon the lexical environment a closure is allowed to capture as 'local' vs. 'remote' - and thus resolves several issues. Vats have a few compositionality issues of their own (behavior of two vats composed is quite distinct from using one monolithic vat), but still compare well to many competing designs.

What would make [objects] first-class [in a distributed language]?

The same way you make a feature first-class in any language: remove the gotchas and ad hoc limitations and arbitrary rules, keep it parametric, achieve 'closure' of the language so that the operations one can express are consistent and valid. In a distributed programming language, a type or feature that does not distribute is certainly not first-class.

What other semantic properties are there for distributed objects?

The semantic properties for a feature or expression in a distributed programming language are the same as for any other language: expressiveness, compositionality, type, type safety, progress, well-timing, responsiveness, determinism, concurrency, parametricity, closure (in the algebraic sense), among others.

Beyond that, there are important non-semantic properties - ease of implementation, risk of time or space leaks, optimizability, scalability, emergent plug-in extensibility and modularity, integration with testing and documentation, implicit robustness and resilience under error conditions (and malice), integration with graphical or gesture-based construction, ability to produce clear error-reports for type or syntax errors, and so on. Semantic and syntactic 'noise' and other forms of accidental complexity that clutter our programs are heavily influenced by language.

All of these properties, and more, are potentially important.

For distributed closures vs. distributed objects in particular, the semantic differences are in expressiveness and compositionality. There are also several differences in the non-semantic properties.

But the distributed objects/closures are in fact semantically the same since all we can do is send the same messages to them, and receive the same replies. They are observationally equivalent [...] distinguishable only within a trust boundary.

The semantic (and syntactic) differences of two different ways of expressing programs are most obvious while you're expressing the program (or studying it, afterwards). This is true whether you're talking about closures vs. objects or Lisp vs. Blub.

But your argument has effectively been that "different ways of expressing the same program are not 'externally' distinguishable, therefore different ways of expressing programs have equivalent semantic properties". That argument remains absurd whether you're talking about closures vs. objects or Lisp vs. Blub.

the semantics of distributed programming consists of sending and receiving messages

Messages are a convenient abstraction, relatively easy to implement atop our current technologies. Streaming data is the other easy-to-implement abstraction. But both have a lot of bad properties at scale (in terms of expressiveness, compositionality, robustness and resilience, scalability, reasoning about consistency and progress).

I favor a far more RESTful basis of communication, and not just for queries. REST has a lot of nice properties for distributed systems, even though they map less directly to today's communications technologies. Publish/subscribe architectures, temporal logic programming, concurrent constraint programming, tuple spaces, functional reactive programming, and my reactive demand programming are all language designs in this general direction. The recent post on CALM is also in this direction, focusing upon 'consistency and logical monotonicity'.

And you cannot construct a distributed closure without distributing a closure. A closure may include ad hoc code. Therefore, distributing (aka mobilizing) code is strictly necessary if you want to claim language support for distributed closures. QED.

So in your terminology, distributing objects then involves distributing the code for the methods as well? If not, you would seem to have an inconsistency. And if it does involve distributing method code, how then are distributed closures difficult where distributed objects are not? I still haven't got a clear answer on this. Given we're obviously using different terminology, perhaps you can provide a trivial illustrative example where distributing a closure is difficult but an object is easy.

Some sort of code distribution is a prerequisite for distributed programming. Code needs to end up on the remote CPUs somehow, whether through sneaker-net, apt-get, or an app-store.

The code that ends up on the remote CPU is a proxy in all the distributed systems I'm familiar with, because the hosts are mutually suspicious in general. The mobile code systems you're talking about are very different. The meaning of "distributed" in the capability community involves mutually suspicious objects, so general code migration is generally not considered viable. Sounds like you're talking about parallel/clustered systems with trusted nodes where code can migrate freely, or a restricted DSL ala SQL whose safety properties are known and which can be safely executed on any host. The latter is not a common requirement of a "distributed system".

There are many deployed distributed systems with which you would have to integrate that would not support mobile code. Are they not distributed systems in your parlance?

Vat-based storage is reasonable, but the question becomes: which vat?

The Vat in which the 'create local reference' operation was issued. I don't think the problem is shallow, rather I don't see how it's relevant to the question of why closures are difficult to distribute, but not objects. The same mutation issues are at play in both contexts.

Closures do not help us answer this question - there is no clear relationship between where closures live and where state lives. Objects provide a simplistic boundary - an inside and an outside - that provides a simple answer.

This whole paragraph is confusing. It seems like you're confusing "code" with "closure". Closures are a bundle of state and code, just like objects. I have no idea why you're separating the state from the closure, when you do not do the same for objects.

But your argument has effectively been that "different ways of expressing the same program are not 'externally' distinguishable, therefore different ways of expressing programs have equivalent semantic properties".

Not at all. My argument has been that a program calling out to an external service cannot distinguish between one implemented with an "object delegate" or a "true closure", and so there is no distinction at this layer of abstraction. I don't care how a higher level layer chooses to reify the low-level abstraction, ie. as an object or a closure. At the interoperation layer via which all systems must talk to one another, all you can do is send messages over a wire, and the two are indistinguishable.

In any case, the fundamental issue seems a disagreement over what a closure is: you seem to think that closures are separable from their state in a way that objects are not, and I really don't see why. In most common depictions, closures are simply an object with a single "apply" method. Thus, any argument you present that objects are easily distributed but closures are not must be flawed, because a trivial transformation from a closure to an object representation would suddenly make the closure distributable. Unless of course you're using a non-standard definition of "closure".

In most common depictions, closures are simply an object with a single "apply" method.

That would be a function object (often called a functor, just to irritate mathematicians).

That is NOT the same concept as a closure.

It seems like you're confusing "code" with "closure". Closures are a bundle of state and code, just like objects.

It seems like you're confusing "closures" with something else.

Closures do not 'bundle' state with code.

A closure may capture a reference to stateful elements of the lexical environment. In general, any function that returns one closure may return a tuple of closures that all share the same environment. No single closure can be said to be 'bundled' with the state.

in your terminology, distributing objects then involves distributing the code for the methods as well?

Yes.

how then are distributed closures difficult where distributed objects are not?

Distributing objects is easier than distributing closures because objects have a clear and precisely delineated ownership of 'state' (they own their stateful attributes), whereas closures do not (state is associated with an 'environment', and the environment doesn't have clear ownership).

The code that ends up on the remote CPU is a proxy in all the distributed systems I'm familiar with

I suspect you're familiar with JavaScript, applets, flash, and web applications, to name a few. I did not mean to suggest that native CPU code is being distributed (though it is - people obtain executable binaries and run them all the time, without hardly a verification).

Sounds like you're talking about parallel/clustered systems with trusted nodes

I wonder what gave that impression. My own interest is more towards federated open distributed systems with mutually suspicious system administrators and suspicion of insider attacks.

There are many deployed distributed systems with which you would have to integrate that would not support mobile code. Are they not distributed systems in your parlance?

Yes, they're distributed systems.

But I wouldn't say they support distributed closures.

[regarding where stateful variables or attributes are hosted]: The Vat in which the 'create local reference' operation was issued.

That's a terrible answer if you are at all concerned about latency, disruption, and compositional properties.

My argument has been that a program calling out to an external service cannot distinguish between one implemented with an "object delegate" or a "true closure", and so there is no distinction at this layer of abstraction.

I agree with how you word your conclusion here.

Your previous conclusions were analogous to: "My crayon is yellow and the sun is yellow, therefore the sun is my crayon." What you meant seems to be analogous to: "My crayon is yellow and the sun is yellow, therefore there is no distinction under the color abstraction."

Distributing objects is easier than distributing closures because objects have a clear and precisely delineated ownership of 'state' (they own their stateful attributes), whereas closures do not (state is associated with an 'environment', and the environment doesn't have clear ownership).

This concept of 'ownership' seems nebulous; reachability is the key property.

If one returns a tuple of closures all sharing the same environment, the only properties that matter are whether the bindings are mutable or immutable. If immutable, we can safely flatten the captured bindings into an object record and replicate as needed. Each mutable binding is lifted to a shared storage cell ala Ref<T>, just as if it were shared between objects. Immutability should always be preferred due to its simplicity of course.

Your appeal to 'ownership' is about bounding the scope of mutation. The concepts of 'ownership' and environments are a smoke screen which just clouds the issue.

I think you might be interested in Resolving and Exploiting the k-CFA Paradox. It touches on exactly this relationship between closures and objects as it pertains to the k-CFA problem. All you do is change the representation of closures by a flattening transformation as above, and k-CFA changes from EXPTIME to PTIME. This same sort of transformation applies to this case and makes closures distributable by making them equivalent to objects, and with no loss in expressiveness.

That's a terrible answer if you are at all concerned about latency, disruption, and compositional properties.

Seems like the only viable answer if you care about security though. The Vat must voluntarily relinquish control of the state in some hand-off protocol if you wish to distribute such a storage location. Like the unum pattern.

This concept of 'ownership' seems nebulous; reachability is the key property.

Consistency and performance (latency, bandwidth overhead) and robustness (resistance to disruption) are also key properties.

Reachability analysis or linearity can sometimes allow us to associate state with a particular closure, and a closure with a particular machine, such that we can figure out where to host the state. But that's difficult. Object attributes are much simpler - 'owned' by a particular object.

Each mutable binding is lifted to a shared storage cell ala Ref<T>, just as if it were shared between objects. Immutability should always be preferred due to its simplicity of course.

You seem to be generalizing OO properties from Waterken's idiosyncrasies. I strongly caution against doing so.

The common case for OOP - including, for example, Waterken's host language - is that objects may have mutable attributes, and if developers wish to introduce a 'shared' Ref<T> object, they may do so, but it would be just another object with another mutable attribute.

Making immutability the default is useful for distribution, I agree. Defaults are one of those non-semantic path-of-least-resistance issues that affect how programs are written.

Your appeal to 'ownership' is about bounding the scope of mutation. The concepts of 'ownership' and environments are a smoke screen which just confuses the issue.

No, it's about having a simple and predictable answer for which state gets hosted on which machines when distributing things.

That's a terrible answer if you are at all concerned about latency, disruption, and compositional properties.

Seems like the only viable answer if you care about security though.

In an object capability system, assuming the only candidate hosts are vats holding a read-write reference to the state, there is no difference in authority based upon where the state is hosted. (There would be a problem if you tried to host the state upon a computer that doesn't already hold a full capability to it, such as a cluster or distributed table.)

Therefore, the significant concerns regard such properties as performance (latency, bandwidth costs), robustness (against disruption or partitioning or node failure), and consistency (mostly relevant if you choose to replicate state and keep the replicas synchronized).

Assuming you've decided to distribute closure code that happens to contain a read-write reference the mutable state, you automatically make the remote vat a valid candidate (with regards to security) for hosting the state. Trivially, the host that created the closure is also a candidate. Therefore, you have a decision to make.

Things seem easier when there aren't any decisions to make. This is not such a case.

The Vat must voluntarily relinquish control of the state in some hand-off protocol if you wish to distribute such a storage location.

That's important for consistency, certainly. We don't want a bunch of vats confused as to whether they're the official host of the state.

But this makes no difference in security: every host holding a read-write reference to the state has already been designated authority to damage the 'consistency' properties by writing any darn thing they please.

Reachability analysis or linearity can sometimes allow us to associate state with a particular closure, and a closure with a particular machine, such that we can figure out where to host the state.

Please provide even a trivial scenario where the transformation I described cannot be done automatically. I mean any scenario where the transformation produces an undesirable result such that specifying explicit boundaries manually ala objects is the only solution. Until I have something concrete, I'm afraid your argument will remain unconvincing.

You seem to be generalizing OO properties from Waterken's idiosyncrasies. I strongly caution against doing so.

I'm not, I'm describing the minimal interface for separating mutable from immutable data. This same interface is used by OCaml, SML, and Haskell. The Ref object is not "just another object", it is actually a primitive of the runtime, just like integers and strings.

But this makes no difference in security: every host holding a read-write reference to the state has already been designated authority to damage the 'consistency' properties by writing any darn thing they please.

Untrue. They may have indirect access to the reference through a facet that implements a security policy. If you ship the whole subsystem to another machine, you can no longer prevent extracting that reference and you lose the access control policy you specified on reads/writes.

Please provide even a trivial scenario where the transformation I described cannot be done automatically.

You can do your transformation, but it simply doesn't help you, in general, in deciding where state should be hosted.

sillyExample() {
  x   = 1;
  foo = fun y -> { x += y; return x; }
  bar = fun y -> { x *= y; return x; }
  sendToAlice(foo);
  sendToBob(bar);
  sendToCharlie(foo,bar);
}

Note that the caller doesn't need 'x' anymore, and 'x' doesn't contain any sort of sensitive information, so there would be no benefit in hosting it upon the computer that declared the stateful variable exists. However, it's also unclear where else to host it, since we sent references to x in three directions.

an undesirable result such that specifying explicit boundaries manually ala objects is the only solution.

I have never once claimed that boundaries are the only solution. I have said they are a simplistic solution - one that is easy to implement, and easy to grok, but that (like most 'simplistic' solutions) requires we introduce complex design patterns to leverage effectively.

You must be misreading my argument.

In any case, this whole line of discussion started with you asking me to justify an opinion I held in a retrospective argument from when I understood 'closure' to be an implementation technique - specifically, combining a function and an environment pointer, where an environment pointer typically references a cactus stack. If you had asked, at the time, why I thought closures couldn't be distributed, I'd have asked: how the hell do you propose we manage a cactus stack of mutable references in a consistent and efficient way across multiple computers?

That argument was retrospective because, as I said, it was then that someone explained to me that 'closure' isn't an implementation technique, that 'binding the environment' doesn't need to be a literal environment pointer, that what really matters for a 'closure' is that just the necessary elements of the lexical environment are bound.

Still, closures on a mutable environment do not make it easy to determine where state should be stored. Semantically, closures do not have extrinsic identity, so should be copied rather than referenced.

I'm describing the minimal interface for separating mutable from immutable data. The Ref object is not "just another object", it is actually a primitive of the runtime, just like integers and strings.

A primitive of what runtime? Waterken is written in Joe-E, which is a subset of Java that happens to include mutable attributes. Ref<T> is, indeed, just another object in Joe-E and in Java.

I could name many other OO languages with mutable attributes.

I find your assumptions that distributed objects would use Ref<T> or equivalent to be unjustified. I find your claim that it is "the minimal interface" for distinguishing mutable state to be unconvincing.

I do agree that one should make a distinction between mutable state and immutable values in a language designed for distribution.

Untrue. They may have indirect access to the reference through a facet that implements a security policy.

The premise of my argument, that remote hosts are granted direct read-write access, is a reasonable one. The possibility of interjecting an object to enforce a security policy exists, I agree, but it does not make my argument 'Untrue'.

If you ship the whole subsystem to another machine, you can no longer prevent extracting that reference and you lose the access control policy you specified on reads/writes.

Correct. If I send you an object that wraps some capabilities, you could quite easily peek inside that object and use those capabilities directly. In cases where the object's method code specified some sort of access policy, you could violate it. This is an important fact to recognize for supporting secure code-distribution.

Therefore, you should not distribute code that contains a capability for which such a violation could cause real harm to someone other than the violator, with some exceptions if you can manage incentives (e.g. utilizing Horton). You cannot just blindly distribute code, cannot naively pack up a closure and ship it across the network. Your runtime needs to make some intelligent decisions based upon sensitivity and risk - ideally, dynamic decisions based upon the specific remote destination.

For various reasons we 'trust' some runtimes to properly execute our code - such as the current one - and not others. Achieving maximum code distribution within the limits of this trust, therefore, requires we be sensitive to both policy and destination. Programmers must somehow be able to annotate a distribution/trust policy into their projects, and analyze the resulting information flows.

On a related note, it is just as bad to send sensitive immutable information (say, a Secret document or password or a woman's birthyear) as it is to deliver sensitive capabilities. The whole issue of what may be distributed where is orthogonal to the whole issue of mutable state.

I could discuss how I've been planning to handle this is my language design, but I'd rather take it to another venue.

However, it's also unclear where else to host it, since we sent references to x in three directions.

Ok, now we're on the same page. Again, the issue comes down to mutation. If the bindings were immutable, no problem. Further, if you were to transform this into a program using objects, you'd have exactly the same problem with the shared mutable reference. You could argue that the "problem" with closures is that, depending on your language, they exacerbate this problem because they make it easier to express such problematic programs. But it's very different to say this rules out distributed closures entirely.

Semantically, closures do not have extrinsic identity, so should be copied rather than referenced.

I disagree. Semantically, I would say their identity is the tuple of their bound mutable variables. If there are no bound mutable variables, it has no identity.

Waterken actually takes a slightly different view on this since it assigns everything an identity via its exported crypto identifer. The identity is computed as the crypto hash of the bound state. A mutable reference's "address" in the store is used, so two independently constructed closures with all the same values and shared references will have the same identity.

A primitive of what runtime?

Of the Waterken runtime, the distributed platform which is hosting our application (or equivalent runtime in another language). This is the distributed language that you're writing in. At the level of Java/Joe-E, I agree that Ref is just another object.

The whole issue of what may be distributed where is orthogonal to the whole issue of mutable state.

I disagree, and your argument above seems to contradict this statement, since the only problem with distributing those closures was that they shared a mutable variable. I agree closures over mutable variables can exacerbate this problem though.

If you force all closures to be immutable, problem solved, though you reduce the class of expressible programs. You can reintroduce mutability via some explicit reference constructor, like Ref, or some other storage service.

Similarly, to distribute sensitive immutable state, I would introduce a new constructor for encrypted data, Secret<T>. Ref and Secret are primitives of the distributed runtime, and the rest of the values are declared to be immutable.

Semantically, I would say [closure] identity is the tuple of their bound mutable variables.

As you stated it here, closures with distinct behavior may share the same identity if they happen to bind references to the same set of mutable variables. Did you mean to include the function in the tuple?

If you end up including information to reconstruct the closure in the identity, what you have is effectively an intrinsic identity - same as values possess.

The whole issue of what may be distributed where is orthogonal to the whole issue of mutable state.

I disagree, and your argument above seems to contradict this statement, since the only problem with distributing those closures was that they shared a mutable variable.

There is no contradiction. The problem with distributing closures is figuring out where state should be distributed for hosting, not where state may be distributed. Figuring out the security constraints on distribution is an easier problem than figuring out how to optimize a distribution for consistency and performance within those constraints.

to distribute sensitive immutable state, I would introduce a new constructor for encrypted data, Secret<T>

I am guessing that Secret<T> is intended as an annotation describing a simple binary decision on sensitivity - secret or not, without distinction based upon information domain or observer.

However, in practice, the issue of sensitivity is much richer. For example, it may be that you're willing to share a particular volume of sensitive information with Google and Amazon's servers (e.g. based upon a certification process), but not with an arbitrary remote service. With whom a given unit of information may be shared can vary - i.e. there are some things (information, authority) a typical university student would share with her roommate but not her mother, and vice versa.

If we're stretched for compute resources (CPU, memory, bandwidth), or if Google and Amazon are making a competitive offer, we should seriously consider offloading some of our work to them - so long as we're willing to trust them with that work and that information. But to take advantage of this opportunity requires that we properly embed our secrecy policies in a manner richer than a binary secret-or-not. (We don't want the policies to be too rich, though. They must also be easy to reason about, compute, validate, and distribute. The final decision should be binary and deterministic.)

For the sort of 'binary' decision you mention here, I use cryptographic primitives - the sealer/unsealer pairs introduced to me by E language. These would be an improvement over 'Secret', since you at least could implement some neat policies by hand (shipping copies of the sealer and/or unsealer to trusted vats).

As you stated it here, closures with distinct behavior may share the same identity if they happen to bind references to the same set of mutable variables. Did you mean to include the function in the tuple?

Yes, come to think of it, Waterken has it right: the fully qualified function name, its immutable and mutable state all contribute to its identity. Instances of the same function with the all the same immutable bindings would have the same identity.

The problem with distributing closures is figuring out where state should be distributed for hosting, not where state may be distributed

But I still don't see why this is a problem unique to closures and not to objects. Rewrite that program using with a shared variable, and how do objects not have this problem too? You still have to decide where that shared state variable should be distributed for hosting.

I am guessing that Secret is intended as an annotation describing a simple binary decision on sensitivity - secret or not, without distinction based upon information domain or observer.

I should note that I'm using this abstraction in a simple web framework. So yes, change your type from int to Secret<int> and the value is auto-encrypted on sending the page to the client, and decrypted on receiving a request. Whether the information is divulged as a value, or kept encrypted in subsequent requests is up to the developer when he's building the response.

I agree that sealer/unsealer pairs are a great abstraction, I just haven't hit the need for those cases yet. Most web apps only need a simple trust partition.

But I still don't see why this is a problem unique to closures and not to objects. Rewrite that program using with a shared variable, and how do objects not have this problem too?

If you have objects without closures, you simply don't have shared variables. Any given attribute belongs to a specific object, and thus (if mutable) the state of that attribute will be hosted wherever the object is hosted.

Of course, you still have a problem of deciding where objects should be hosted. Fortunately, objects provide a simplistic answer there, too, because objects have extrinsic identity - one bequeathed unto them by the runtime when new is called. It makes perfect semantic sense to declare 'object A should be hosted near object B' because objects have identity. Saying the same thing with a closure would make as little semantic sense as saying '409 should be hosted near 711'.

I'm using this abstraction in a simple web framework.

My understanding is that Waterken can be used in a few different ways, such as interfacing with other Waterken servers.

For web applications, I'd like to see a client-side equivalent to the Waterken server, with a client-side instance (or vat) per web-app. I want is to support automated 'sharding' of rich distributed applications. That's what 'distributed programming language' means to me: you write the program in one place, hit start, and the result is a (literally) distributed application. Using YURLs, clients could get into contact with other servers - including other clients; capability security eliminates need for a same-origin policy, and code-distribution allows the initial 'server' to act as a broker - hooking systems together then stepping aside. Acting as a broker would help minimize latency and disruption and server scalability issues.

The client-side servers could provide a simple document object model that allows code from the remote server to control the display, but there are plenty of other properties of interest for UI development (such as accessibility, multi-language support, ability to bookmark views) so I'm not especially fond of the imperative DOM seen in modern web apps. I have some ideas for replacements. I figure my initial client-side support will involve either an NPAPI+NPRuntime plugin, or a compile-to-JavaScript technique similar to GWT; I'd rather extend an existing browser than compete with them. But I'm quite some distance from this sort of goal.

It is this richer, widely distributed platform that I consider when I speak of support for 'closures' or anything else. If it's just client-server, it barely qualifies as 'distributed' IMO - you certainly don't start seeing the interesting problems until you've scaled to a larger number of participants with diverse agendas and interests... a large number of systems interacting. In a rich distributed system, the roles grow indistinct and confusing: servers act as clients coordinating and brokering other servers and clients... and clients extend and mashup servers, adding new features, even distributing code to wrap old communication protocols in new ones.

Using Waterken for a simple web app is barely scratching the surface of distributed programming. Create a good Waterken NPAPI plugin and Waterken could be used for so much more. And we could still improve greatly upon Waterken.

If you have objects without closures, you simply don't have shared variables.

But they do have shared variables. Any shared mutable path between two objects has this problem. You're categorically declaring that closures don't satisfy a stricter criteria than objects have to satisfy, and then declaring closures unsuitable as a result.

I'm still convinced that the only reason this would be problematic is mutable state. Depending on your language or the properties of your distributed framework, for instance, immutable bindings, your objection doesn't even apply, so at the very least the general statement that closures can't be distributed is wrong. I do agree that those languages that allow undeclared mutable locals will exacerbate this problem.

As for your hosting association operation (A near B), I expect closures can have the type of identity you would need. If they are immutable, then they can be replicated for every association. If they have some mutable state, the runtime should bequeath an identity as it would any other object, because it is compiled as a function object after all. Content-Centric Networking and Waterken have this right: the encapsulated contents define the identity.

For web applications, I'd like to see a client-side equivalent to the Waterken server, with a client-side instance (or vat) per web-app.

Tyler just released something like that: http://web-send.org/. A JS library for secure introduction across services. Obviously it's only a simple start limited by current browser technology. Mark Miller et al. are working on membranes and such for JS sandboxing too.

As for the rest, sounds interesting, but I don't see any benefit to distinguishing closures from objects. You have mobile code either way, you have entities where identity sometimes matters and sometimes doesn't, and one can be easily transformed into the other.

I agree that Waterken is only scratching the surface, but it's a part of the surface we know how to do somewhat well (secure service composition), but isn't being done by and large. Almost everyone else is working on scaling and availability.

Content-Centric Networking and Waterken have this right: the encapsulated contents define the identity.

'Identity' is a convenient fiction with a lot of philosophical problems. It costs a lot to maintain this fiction. I don't think anyone gets it 'right'... at best, just 'less wrong'.

Waterken is only scratching the surface, but it's a part of the surface we know how to do somewhat well (secure service composition), but isn't being done by and large. Almost everyone else is working on scaling and availability.

I think it's fine that Waterken has limited scope. That keeps the risks low, and still breaks useful ground.

But scaling and availability (and partition tolerance) are also important.

Concern for scaling has a huge influence on my language design. My concern for client-side scalability (e.g. for zoomable user interface, where CPU and memory cost must be proportional to screen real-estate) forbade me language design that requires heartbeats, polling, or periodic events; further, it also caused me to pursue demand-driven resource management. Scaling to a large number of developers and diverse agendas encouraged the pluggable multi-agent approach and a focus on extensibility. Concern about flash crowds and need for rapid or burst scaling had me focusing on reuse of answers and implicit caching. And then there's the normal resource utilization scalability (ability to throw more CPUs and memory at the problem without rewriting anything) which I achieve by focusing most computation into 'fat' relationships between nodes (reactive models), which inherently scales O(N^2) with the number of nodes in the system and may easily be processed in parallel. (Basically, that avoids a scenario where a lot of work is waiting on other work to finish.)

I don't see any benefit to distinguishing closures from objects.

Huh? Logically, you need to distinguish closures from objects before it even makes sense to ask the question of whether it is beneficial to do so. Anyhow, I do not believe you or I will benefit from further discussion, especially since we still don't agree on definition.

That would be a function object [...] That is NOT the same concept as a closure.

By the way, this is incorrect. A "function object" is a closure, but a closure is not necessarily a function object. There are many closure representations and a function object is one of them (see the paper I linked -- also, OCaml and SML use this representation for closures IIRC).

In some languages, function objects may also be closures. The two concepts are independent.

You have a closure if you bind variables from the lexical environment at time of specifying an open expression. Period. That is the only requirement to be called a 'closure'. So, for example, I'd have a closure and a function object if I could do the following:

class Foo {
   int x;
   Foo() { x = 0; }
   Functor<int,int> makeIncrementor() {
      return new Functor<int,int> { 
          int apply(int a) {
             x = x + a;
             return x;
          }
      }
   }
}

makeIncrementor would return a closure because the internal anonymous Functor class happens to bind a reference to the variable 'x' from its lexical environment.

The returned closure would also be a function object because it's an object with a single 'apply' operation.

However, there are many, many languages where function objects (and other objects) cannot cannot bind open variables from the lexical environment, and thus do not support closures. Java and C++ are among them.

Java's inner classes can bind open variables from the lexical environment as long as they aren't mutable, a limitation that developers often work around with an extra layer of indirection.

And to clarify, C++ now doesn't do any capturing but
C++0x will be able to capture or not in lambdas.

Indeed, it has been a desired feature.

Project Lambda is working on getting real support for closures into Java.

C++0x lambda expressions lack some properties of closures (the captured environment is not kept alive for lifetime of the lambda function) but they go 80% of the way and smart pointers can make up most of the remainder. Today, limited lambda expressions are supported by template metaprogramming... but if you want to capture a reference you'd need to use something like 'ref(var)' in the expression.

I don't think it was me, since I don't remember that and I don't think my understanding of the term has changed.

As we consider support for closures in languages with just-in-time or hotspot compilation, or distribution of first-class functions, we really must focus on the programmer's POV - the closure semantics, rather than any particular implementation.

That's question begging, though. Compare to the phrasing "As we consider support for higher order functions..." Anyway, this is purely terminology. I wasn't trying to argue that this definition is better. I was just providing another sample point.

Higher-order functions can be supported in a language without implicitly capturing lexical scope. Closure semantics make HOFs convenient to express and utilize (from a programmer's perspective) relative to many of the alternatives.

How a programmer expresses HOFs is not 'question begging'. If it were, nobody would be concerned that Java doesn't support 'closures' by which they mean 'anonymous classes do not implicitly capture references to data or values of their creating environment'.

I read the paragraph I quoted as "Closures are a semantic property, thus an implementation dependent definition of 'closure' puts the focus in the wrong place." Thus my claim of question begging.

I had previously argued that closures are a semantic feature, therefore my understanding is that I can depend upon that conclusion in later paragraphs. Don't pull them out of context and call them 'question begging'.

Closures describe a semantic relationship between lexical scope and the syntactic expression of HOFs, therefore closures are a semantic feature. Whether they are implemented under-the-hood by an environment and function pointer isn't relevant unless programmers have direct access to that representation.

Closures are defined this way on wikipedia (for at least five years, now), which I would consider an authoritative source for the "common" definition.

I had previously argued that closures are a semantic feature, therefore my understanding is that I can depend upon that conclusion in later paragraphs. Don't pull them out of context and call them 'question begging'.

At issue is the definition of 'closure'. Your link to Wikipedia is on point and seems to support your position. However, the implied reasoning in the paragraph I quoted seems circular to me -- in context. Having 'closure' refer to a particular implementation technique is only putting the focus in the wrong place if 'closure' is also the word that programmers will be using to describe a nested function. In other words, 'closure' shouldn't refer to an implementation technique if 'closure' refers to a semantic entity. Which begs the question.

P.S. My new year's resolution is to never let anyone else have the last word on unimportant quibbles on the internet, and I look forward to continuing this sub-thread throughout the new year.

P.S. My new year's resolution is to never let anyone else have the last word on unimportant quibbles on the internet, and I look forward to continuing this sub-thread throughout the new year.

ROFL, thanks. ;)

I attempted to clarify what I meant with that paragraph.

Word.

I also agree with Matt and Leon. I think one source of the confusion here is that the word "closures" (as I understand them) really refers to a family of implementation techniques which can be applied to a family of related semantics. In my view, "closure" is definitely a term best reserved for the implementation domain, and the semantics are best described using the vocabulary of scope, mutability, lambda abstraction, partial application, nested class definition, etc.

But it's also reasonable to talk about "various implementations" of closures since, as we all know, more than one technique is in that family. But they're all relatively distinct from, e.g., defunctionalization.

Incidentally, it's interesting that this whole discussion arises in connection with partial application, the semantics of which are often not best implemented by closures, at least in the presence of mutable state. Consider the following:

x = 10
g = \ y -> x + y
h = (+) x
x = 20

Are g and h the same function? What should be the value of "g 5" and "h 5"? One reasonable design would have g 5 == 25 and h 5 = 15. In other words, only explicit lambda abstraction ought to close over the mutable location x, while partial application should rather capture the current value of x. This interpretation is the only one, in my view, that makes partial application consistent with total application, and this consistency is pretty important. (One would be surprised if the behavior of h with regard to mutation of x depended on the exact definition of +. Is + a two-argument function or a one-argument function returning a function? In other words, the semantics may depend on whether an application of + is saturated with a single argument, which seems perverse.)

In absence of mutability, I don't know that this distinction exists. In any case, this is more than just terminology. It pays to distinguish closures as implementation from lambda abstraction, partial application and scoping as semantics.

This interpretation is the only one, in my view, that makes partial application consistent with total application, and this consistency is pretty important.

Did you consider a reactive interpretation?

x = 10
g = \ y -> x + y
h = (+) x

f = (h 5, g 5, x+5)
?f => (15,15,15)
x = 20
?f => (25,25,25)

Yes, I did consider that and I grant that it's a consistent and sensible alternative. However, I do think that it represents a much more fundamental change to the languages semantics than we've so far been discussing, and I had in mind a backdrop of "traditional" mutable variables. In a language where all variables are reactive values, I agree that your suggestion is probably the best way to go.