Lambda the Ultimate

I'll take this opportunity to mention Orc, a language in the process calculi tradition that I really like. It's combination of simplicity and expressiveness is amazing. Unlike some other process calculi, Orc does not make unreasonable assumptions (like mobility) about what properties are implementable in a distributed system. Here's a draft implementation of Orc in E, which is transparently distributable and seems to have distributed object-capability security.

AFAIK, Orc has little to do with the transaction topic which began this thread, other than simply factoring out the site call into an assumed atomic step (i.e., a top-level transaction whose internals are outside the concerns of Orc).

Orc is new to me, and is new, I think, to LtU.

Any sort of atomicity in a concurrent setting means you are dealing with some sort of notion of transaction, although I believe that the ABZ paper is talking about fully ACID transactions.

The papers at the page you l;ink to seem mostly to be concerned with Orc-as-practical-language for builing distributed systems: is there a good paper for the core formalism you can recommend?

A Tree Semantics of an Orchestration Language.

Also, his talk slides contains a good summary of the semantics.

The Orc site call is mostly just a black box to Orc. I think I misspoke -- Orc does not attribute any significant atomicity properties to it that I can see. So really, we should just start a discussion of Orc outside this thread.

So really, we should just start a discussion of Orc outside this thread.

It's here.

It's probably worth noting that Montanari and Zavatarro (both authors on one or more of the references mentioned in the original post) have also done work on developing formalizations of the actor model based on process calculi.

... as to what people view as the advantages of process calculi (named channels that can move messages, channels may have properties) relative to actors model (named objects with message queues).

Points after having worked with both:

• Process calculi can be a bit more general than the actors model, as evidenced by the Join Calculus... i.e. an 'actor' is effectively a 'process' holding: the receiving end of exactly one named many-to-one asynchronous channel, and sending ends of several many->one channels.
• But, in turn, that generality makes the system considerably more fragile and less scalable. In particular, process calculi have many choices about which channels on which they are to wait for messages. This subjects them to deadlock that can be difficult to detect statically in a distributed protocol, and tends to exacerbate any failures (disrupted or lost messages, links, or nodes).

A situation might be taking a transactional message from one channel, entering a transaction, then wait for a message on a different channel. Unless the caller knows in advance the implementation details of this process, the caller cannot be expected to orchestrate the correct processes into delivering a transactional message on that second channel. And needing to know the implementation details of the callee makes for an unscalable and non-distributable system.

With actors model, even with support for replies (so long as said replies are consistent), distributed transactions become relatively easy to understand without knowing or worrying about which 'channels' a process involved in a transaction might be reading from.

Anyhow, I can say that my attempt at transactions on the process calculi ended with me leaving to find a model that would be more robust in cases of disruption and ignorance of implementation. But, then, I assumed internet distribution as a starting place. The authors of this paper, admittedly written many years ago, seem to assume local operations.

I must admit to being somewhat disappointed. I imagined or assumed, apparently erroneously, that someone working on transactions for process calculi would have taken as much care as I did in ensuring that: transactions are fully distributed (no common 'log', transactions interact across processes without knowing in advance which processes will be involved), that no 'transaction manager' learns about any capabilities to which the actors it is managing did not already have access, and that transactions can be readily interrupted or preempted by higher priority messages in the inbox.

Well, I've only read the first third of the paper. Perhaps they can turn their abstraction of a central log into a distributed one. I'll keep on it (it's taking a while to get through the notation).

I don't know the literature around the actor's model well enough to make an informed comment, but my subjective impression is that process algebras, and the CCS family in particular, have sharper theories of observational equivalence.

With respect to the fragility question, most process algebras are not intended as programming languages, but as formalisms for investigating concurrency. There has been work on trying to use proces algebras as a foundation for more tractable programming languages. My impression is that, while the Join calculus, a formalisation influenced by Boudol and Berry's Chemical Abstract Machine, has fans here, Hoare's CSP has had more influence than other formalisms on the design of programming languages. Occam was very overtly influenced by CSP, as I gather was Ada's task model and Concurrent ML. Erlang seems to have been significantly influenced by both CSP and the Actor model.

Probably the most constructive approach to answering David's question would be to make a list of programming languages whose support for concurrency was influenced by established formalisms for concurrency, determine the nature of the influence, and try to figure out what the experience of programmers says about the practicality of the formalisms. And again, I am not knowledgeable enough to make much of a start on this task...

Appendix 3 of Will Clinger's PhD dissertation, Foundations of Actor Semantics, discusses the relationship between CSP and Atolia, a realisation of the Actor model. The discussion is rather informal, but maybe serves as a good starting point for thinking about the relationship between process calculi and the Actor model, because I've found Clinger's treatment of the Actor model to be more lucid than most.

Clinger's dissertation (both the appendix you mention, and parts of the main text) do a nice job of comparing and contrasting actors and CSP. That said, it's important to note that the "CSP" that Clinger refers to is the notional programming language that Hoare described in his 1978 CACM article, rather than the process algebraic version of CSP that appeared in Hoare's later book. The two versions of CSP differ in a couple of key ways. The most significant differences are probably that the 1978 version of CSP only permits processes to be defined sequentially (hence the name "communicating sequential processes"), and that the 1978 CSP requires processes to be named, and defines communications in terms of process names rather than channels.

Given the wide variety of process calculi that exist, each with their own advantages and disadvantages, I doubt there's any one answer to your question. I suspect that process calculi favour anonymous processes and named channels because it makes algebraic reasoning easier, and makes it easier to define processes compositionally. Conversely, the name-based messaging scheme used in the actor model made dynamic topologies much easier to represent, and its asynchronous nature provides a more direct representation of distributed computation.

makes it easier to define processes compositionally.

Individual actors aren't composable; that is one of the weaknesses of actors model. However, even some of the older literature on Actors model goes with some detail into the composition of actor configurations.

Actors model based programming languages would do well to include an additional layer, above the actors, for coordinating them - i.e. hooking their abstract definitions together, deciding which actors have access to which names, leaving it somewhat abstract so a few names can be injected and a few names can be exposed. This additional layer makes up for what seems to be one of the two greater weaknesses in actors model relative to the various process calculi.

The other problem is message scheduling for realtime and embedded operations. Programmers should be able to control the scheduler within a configuration in order to prevent any one part from getting too far ahead of the others, to limit the memory consumption of the whole configuration, and to simplify reasoning about order of message arrival when it is useful to do so.

Process calculi, with their ability to wait on two or more channels and optionally support bounded buffer channels, already embody that sort of synchronization. Even so, they benefit from a coordination layer.

Given the wide variety of process calculi that exist, each with their own advantages and disadvantages,

While attempting to select a model well suited for the language (for open distributed gaming) I've been developing, I've studied a great many of them, including CSP and Join Calculus and Pi Calculus and Kell Calculus and Mobile Ambients and (to a lesser degree) CCS. I originally planned to go with a variation on CSP... at least up until I decided that distributed transactions and distributed process accounting would be really nice to have and couldn't fit them into the CSP design in any clean manner.

Fitting transactions in with join calculus had similar difficulties. I've yet to try fitting them into CCS, pi calculus, kell calculus, mobile ambients, etc.

Actors make it easy to track the cause of activity by use of a bit of extra metadata/context attached to messages. This can also carry certificates and such, so offering a potential for security models somewhat orthogonal to capability security, and allowing for process accounting.

While not a full process calculus, the Orc orchestration language might be of interest.

I played around with Orc quite a bit recently. It is, after all, mentioned in an earlier post of this thread.

Orc isn't a process calculus, it's more a process coordination language, and seems in particular to be dataflow language. That sort of dataflow or process coordination facility is, I think, something that should be integrated in a layer above actors or process calculi languages.

From what I've read, the Orc 'where' pruning combinator is very difficult to properly encode in a process calculus (most calculi don't have notions of explicit termination). Don't have the paper handy, but I read one paper where they tried to encode it in the Join Calculus, but they couldn't emulate it perfectly. That suggests that Orc can't just be bolted on top.

Yes, I imagine many process models would not be designed to support the pruning combinator. Of course, the potential for processes to be terminated asynchronously at arbitrary states of completion is not a property that persons wishing to reason about the correctness of processes have sought to support!

On that note, dealing with graceful termination actually does integrate well with this topic: distributed transactions in a process calculus or actors model. You could easily fire up multiple parallel transactions, decide a winner, then abort (with nice, clean, ACID semantics) the activities of the competing transactions. And, with that, you have pruning. I had a similar thought a while back, before seeing Orc, that involved using distributed actors model transactions to support constraint-based distributed programming with side-effects across arbitrary third-party systems. The main difference from pruning would be that the processes wouldn't all run in parallel; rather, one might run a few, make observations on their results, then tweak the inputs for future runs, and take advantage of ACID transactions to keep everything clean.

That aside, Orc has its own (implicit) underlying process model... one in which 'processes' may be killed at any time. Thus, Orc in particular cannot be "bolted on top" of arbitrary other process models. (Technically, Orc only stops doing local work when it kills processes... anything that Orc initiated in remote resources is simply left violated and abandoned. Orcs are nasty creatures. ^_^ You can't spell slaughter without laughter!)

Every workflow language has a process model... sometimes an implicit one, or sometimes based on the processes assumed by the designer of the workflow to be prevalent. The earliest flow based languages ran upon a process model where 'processes' have two basic per-instance inputs (environment vars, stdin) and two basic per-instance outputs (stdout, stderr), each of which were bounded buffers. This is ignoring the arbitrary authority-rich access to the entire OS and filesystem.

A capability-rich workflow language would, no doubt, have focused on providing named (and potentially typed) capabilities to each process (where 'process' may be a single 'object' or a whole configuration) and each process would export one or more capabilities for further integration. However, to create such a language would require a process model that inherently enforces strong capabilities, such as the Actors model (or Join calculus).

If one is to create a coordination and composition language for Actors model, or for Join calculus, or for CSP, or for mobile ambients, and so on, then one would be wise to keep the properties and features of the process model in mind when designing that layer. Orc wouldn't be the choice for coordinating join calculus. One would find something else.

Having an explicit process model allows one to enforce properties about the system as a whole through the process model, and allows one to reason about the system as a whole through the same model.

Having an explicit workflow language allows the compiler to push optimizations from invariant properties and knowns about the particular workflow back down through the process models, such as killing code paths that it knows won't execute, combining processes for efficiency, and intelligently scheduling messages within the workflow to achieve realtime and hard memory properties. Both of these are good things.

Those properties are why I believe a workflow language should be 'on top of' an explicit process model, in a higher layer. (Even having just one standard 'good enough' workflow language is better than where most actors model and process calculi languages are today... Erlang and E, I speak of you!)

But I never proposed Orc to be the workflow language of choice!

Orc wouldn't be the choice for coordinating join calculus. One would find something else.

I don't know, the Orc combinators seem pretty general. Now that I think about it, they're very close to lazy stream processing combinators, with >x> as map, <x< as taking the head of the stream (and terminating the generator), and || as a non-deterministic cons. Perhaps I lack the imagination to see what might be more suitable.

I agree that a process model is needed, I just figured Orc was fairly agnostic to it, since there are no restrictions on the properties of "sites".

I agree that a process model is needed, I just figured Orc was fairly agnostic to it, since there are no restrictions on the properties of "sites".

Orc has an implicit process model, which means you need to look at the implicit restrictions on the properties of the 'sites', including (1) their capacity for asynchronous termination and ability to propagate this termination through other sites with which they may be involved, (2) lack of capability security - ability for 'sites' to send or receive messages to resources and processes that weren't explicitly handed to them in the workflow, (3) common data format for propagation of values in both input and output streams, etc.

Perhaps I lack the imagination to see what might be more suitable.

More suitable for what? You need goals/features/constraints before your imagination can do any work for you. Orc has its own goals. If your goals are the same as Orc's, you'll get along quite well.

Example desiderata I have for a process orchestration language on Actors model would be:

1. to support type safety and static analysis of configuration: to look at a configuration and know whether there are any incompatibilities between messages received and messages handled, or to ensure certain properties (e.g. compatibility with realtime and fixed memory limits)
2. to support capability security: to guarantee a configuration doesn't have access to any resources (actor IDs) that weren't either explicitly part of its functional construction or provided by me
3. to support locality: to specify that certain subsets of actors operate on a local machine, and to perform related optimizations (such as eliminating exception-handling code for missed messages due to local failures)
4. to support distribution: to allow actor-configurations to be pushed 'near' named resources that might be on remote machines, in order that they can downsample inputs and make decisions remotely thereby reducing latency and bandwidth costs, with 'nearness' possibly being limited by trust:
   • component Y contains sensitive capabilities and should be mobilized only to a remote server I trust (which, if I were Google or DoD, might still be close to the target)
   • component X can be mobilized very close to the remote resource even if it is untrusted so long as the remote resource is willing to verify X as safe... e.g. via certified prover/proof-bearing code
5. shutdown, pickling, and hot-swapping: the ability for a programmer to specify desire to freeze, pickle, move, hot-swap components of an active configuration, etc. during runtime.
6. to support mobility: the ability to automatically follow other mobile resources, within the trust limits of distribution

Example desiderata for another actor configuration/orchestration language that might compile to the prior one... including automatic distribution of appropriate middleware:

1. define sensor and data fusion rules that produce more data and useful events then push them to subscribers
2. hook into common databases, provided by resource ID, to determine which sensors and data sources are available obtain this information
3. compile these rules down to the necessary process configurations
4. support dynamic entry and exit of sensors and data services, automatically monitor for such events and begin fusing them
5. automatic downsampling of bandwidth-intense streams (video,audio) to achieve graceful degradation based on downstream resource availability
6. automatic integration with other active rules sets, in order to share common rules or allow one to pipe high-bandwidth streams and data Akamai-style (increased latency but reduced bandwidth cost)

Anyhow, I could come up with a number of similar properties sets. Once the desiderata are known, it becomes clearer whether or not the combinators of any particular language are appropriate.

The combinators Orc provides are suitable for its purpose: fetching and combining information from several sources (sequencing), then combing through it to make decisions (pruning). That is just one sort of process coordination one might desire.

I don't know, the Orc combinators seem pretty general.

Do they still? They achieve some limited forms of process coordination. In some senses 'Generality' is easy to achieve... it is difficult to make useful languages that aren't Turing complete. Orc combinators are 'general' in that they allow you to specify which process communicates with some other process. But in other senses...

Orc combinators wouldn't make it easy to express or achieve any of the desiderata listed above, much less the collective sets thereof. I expect one would end up fighting the language, constructing frameworks and middleware and such, to achieve desired patterns of computation behavior. It would be rather like sloshing through a tarpit.

(1) their capacity for asynchronous termination and ability to propagate this termination through other sites with which they may be involved,

I don't think that's strictly necessary, particularly in the distributed case. It's definitely desirable to dispose of any local resources however, which involves basically aborting any OS threads executing in a task subtree. In the distributed case, I would imagine that you can only reclaim any local resource used in the communication, and perhaps send an abort() message to the service only as a courtesy. Defective clients are to be expected in any realistic open network however. For this, Orc provides timeouts.

(2) lack of capability security - ability for 'sites' to send or receive messages to resources and processes that weren't explicitly handed to them in the workflow,

Orc doesn't place any such restrictions on sites. It doesn't mean the language in which Orc is embedded cannot impose such restrictions. Orc is just an embedded parallel/distributed orchestration sublanguage.

(3) common data format for propagation of values in both input and output streams, etc.

Not sure I follow. Sequential composition/map, can operate on any language types.

to look at a configuration and know whether there are any incompatibilities between messages received and messages handled

I'm not exactly sure what you mean here. Can you give an example of an incompatibility?

or to ensure certain properties (e.g. compatibility with realtime and fixed memory limits)

This is indeed difficult to achieve. I've only seen a few papers dealing with analyzing or bounding resource usage in process calculi. Do you think it's really feasible? I would expect Orc could at least do soft-real time. Searching turned up this paper on a real-time semantics of Orc.

to support locality: to specify that certain subsets of actors operate on a local machine, and to perform related optimizations (such as eliminating exception-handling code for missed messages due to local failures)

I think this is orthogonal to Orc's purpose. Ditto for the other properties you mention. Orc obviously isn't a full fledged language, I just think of it as an EDSL for orchestrating parallel and distributed execution. The host language will need the facilities for reflection, serialization, live upgrade, etc.

Orc combinators are 'general' in that they allow you to specify which process communicates with some other process.

I expect that the Orc combinators permit local reasoning of distributed computation, which I think is a fundamental foundation for any higher level distributed execution framework. So yes, you probably would be sloshing through a tarpit, but only because someone has yet to build a suitably simple and general Orc-equivalent for organizing "actor configurations" and "execution locality annotations", etc.

However, the idea is that those are all language services exposed to Orc via sites, ie. Orc is parameterized by the features of the host language via site calls. Is this orthogonality not as real as I seem to think?

I don't think that's strictly necessary, particularly in the distributed case.

This inconsistency really means that pruning is: 'return the first value and maybe shutdown the other processes'. Since this is not how the pruning operator is advertised, either said documentation is incorrect, or the implementation is incorrect.

Defective clients are to be expected in any realistic open network however.

True. It's pretty telling that Orc potentially forces systems to be defective.

Orc doesn't place any such [capability support] restrictions on sites. Orc is just an embedded parallel/distributed orchestration sublanguage.

The Orc combinators might not place such a restriction, but Orc is a full language, offering plenty of 'fundamental' sites that can be accessed in the construction of any other site and that offer distributed coms.

This has an impact on the number of arguments necessary to make the whole system work (high implicit capability means fewer arguments necessary), which in turn impacts how appropriate/practical the combinators are in actual practice.

Sequential composition/map, can operate on any language types.

That's quite a claim. Regardless, you're once again equating 'composition/map' with 'Orc', which I believe is a mistake, a bit like saying: "Oh, you're using Haskell!" to anyone that happens to be doing functional programming.

incompatibilities between messages received and messages handled

I'm not exactly sure what you mean here. Can you give an example of an incompatibility?

You receive a tuple. You only understand integers.

[Realtime] is indeed difficult to achieve. I've only seen a few papers dealing with analyzing or bounding resource usage in process calculi. Do you think it's really feasible?

Yes, it is certainly feasible, at least within bounded subsystems of processes. That is, one will be able to compose a group of processes and tweak the scheduling rules and possibly fuse a few processes (partial-evaluation) to guarantee:

1. the amount of work per message is not dependent upon the number of previous messages processed
2. that individual messages that meet certain properties (e.g. binary tree of fewer than 1000 nodes) will be processed in a number of computation steps and amount of overhead memory bounded by constant numbers (even better if you can give bounding functions on message size to the memory and steps)

These two properties are sufficient to support realtime operations. Importantly, however, is getting the scheduling right... if messages 'build up' within the subsystem beyond some constant amount, it will fail to be realtime.

I think [locality] is orthogonal to Orc's purpose. Ditto for the other properties you mention.

I agree. But it is not orthogonal to process orchestration in general. This is part of what I was trying to point out to you: you claimed that 'Orc' combinators are pretty general for purpose of process composition and coordination. They are not. Whether they are sufficient or 'general' depends on your purpose. "Orc has its own goals. If your goals are the same as Orc's, you'll get along quite well."

Orc obviously isn't a full fledged language, I just think of it as an EDSL for orchestrating parallel and distributed execution.

Fundamental sites make Orc a full-fledged language by almost every measure I can think of (Turing complete, can be used to implement libraries and applications, supports state and functional transformation of it, etc.). I don't wish to argue definitions of 'full-fledged language', but I would ask what you believe would be additionally required to qualify Orc as one.

The host language will need the facilities for reflection, serialization, live upgrade, etc.

I'm not certain where you're thinking 'the host language' happens to be explicitly exposed as underlying Orc, but I suppose you're talking about lower layers in general. Regarding that much, I agree: if the aforementioned properties are desired, they must be supported by the process model atop which the orchestration language is defined.

But they must also be supported by the process orchestration/composition/coordination language. For example, to perform 'hot swapping' you must be able to identify a subsystem of processes to be replaced and the subsystem to replace it... and doing that is really the job of the coordination language.

I'm honestly not interested in reflection... I hate features that require giving up both security and potential optimizations.

However, the idea is that those are all language services exposed to Orc via sites, ie. Orc is parameterized by the features of the host language via site calls. Is this orthogonality not as real as I seem to think?

Orc provides 'fundamental sites' as part of its definition, and makes assumptions on the process model underlying those sites.

Anyhow, even if you're just talking about Orc's primitive combinators, rather than Orc as a whole, even then one would need greater support from the composition language to actually perform such behaviors as live upgrade. No other part of the system is likely to have the capability to identify a whole subsystem of an operation.

This inconsistency really means that pruning is: 'return the first value and maybe shutdown the other processes'. Since this is not how the pruning operator is advertised, either said documentation is incorrect, or the implementation is incorrect.

I don't think those are the specified semantics. The authors are well aware of the fact that, in general, you can't abort a site's computation (their language was originally applied to web service invocations after all). All you can do is prevent further local processing of any replies. See the wording used in the user guide:

When G publishes its first value, that value is bound to x in F, and then the execution of G is immediately terminated. A terminated expression cannot call any sites or publish any values.

They don't specify that the site call itself is terminated, just that the Orc expression that made the call cannot process any further values. In other words, the only termination guarantee is local.

That's quite a claim. Regardless, you're once again equating 'composition/map' with 'Orc', which I believe is a mistake

Assuming you can inject arbitrary function calls into an Orc expression as a site call, I'm not sure what's so controversial here.

You receive a tuple. You only understand integers.

I'm not sure what you're getting at. So functions can't operate on types they're not meant to operate on. Insert a site call which transforms the data from the received type to the required type.

the amount of work per message is not dependent upon the number of previous messages processed [...] that individual messages that meet certain properties (e.g. binary tree of fewer than 1000 nodes) will be processed in a number of computation steps and amount of overhead memory bounded by constant numbers (even better if you can give bounding functions on message size to the memory and steps)

So something like 'sized types' which provides structurally inductive bounds on the size of terms and data. Sounds reasonable. Always thought that was a promising avenue of research.

Fundamental sites make Orc a full-fledged language by almost every measure I can think of

I don't consider the fundamental sites specified by the authors as core to Orc itself. The semantics of the combinators and site calls is core to Orc. Is Orc without any sites Turing complete? Quite possibly, since Orc expressions can reference themselves, but I'm not certain.

Perhaps by "Orc", you are referring to the language they implemented for the JVM? I first came across Orc before an implementation really existed, so when I think "Orc", I think only of the semantics of the combinators and sites which is how I was introduced to it. This is why I consider Orc to be an EDSL. Of course, I also wrote a semi-functional implementation, Orc.NET a few years back, which is another reason I consider it an EDSL, and why I'm not tied to the Orc == the author's JVM implementation mindset.

Anyhow, even if you're just talking about Orc's primitive combinators, rather than Orc as a whole, even then one would need greater support from the composition language to actually perform such behaviors as live upgrade.

If I were to hazard a guess, I would say that if you want an Orc expression to support live upgrade, then you just need to have a provision for it by wrapping it in a generic upgrade expression:

// pseudo-Orc: upgradeSite provides a new Orc expression to
// execute in place of the original call
// if e() returns first, it simply returns the value
// if upgradeSite() returns, computation is aborted/pruned,
// then a new upgradeable computation is started with the provided
// Orc expression

def upgradeable(e, upgradeSite) =
  (if(x is UpgradeMsg) upgradeable(x, upgradeSite) else x)
      <x< e() || upgradeSite()

In principle, this is similar to how I would expect Erlang to provide upgrade: a tail call to the new server loop. In general, I don't like languages that hide too much from the programmer, but this is fairly transparent. I think the above solution, while possibly incomplete, is simple enough that the few minutes it took to describe it means a complete solution is feasible.

They don't specify that the site call itself is terminated, just that the Orc expression that made the call cannot process any further values.

It seems to me that 'cannot call any sites or publish any values' is a much stronger specification than 'cannot process any further values'. I suspect that the Join calculus implementation you spoke of would have not been problematic with the weaker specification you describe.

Assuming you can inject arbitrary function calls into an Orc expression as a site call, I'm not sure what's so controversial here.

I'm afraid you lost me. Did you just apply 'assuming' as a counter to 'controversial'?

You receive a tuple. You only understand integers.

I'm not sure what you're getting at. So functions can't operate on types they're not meant to operate on. Insert a site call which transforms the data from the received type to the required type.

I suspect you have lost the original context regarding which you asked about 'incompatible messages', which was: "1. to support type safety and static analysis of configuration...". Sure, you can fix the problem in the code by inserting a transformation. But, to do that, you must notice the problem before running the code.

simple enough that the few minutes it took to describe it means a complete solution is feasible

With Turing completeness, I can't argue the solution infeasible.

The better question is: how much does a complete solution invade the code for sites? Any property or feature that must be achieved by invasive code disciplines on part of the programmers, possibly even through libraries, should not be considered a property that the language supports.

I don't like languages that hide too much from the programmer

'Too much' is a fairly dynamic quantity.

It seems to me that 'cannot call any sites or publish any values' is a much stronger specification than 'cannot process any further values'.

I don't see how. Any other site calls are suspended waiting for a reply, so terminating the expression means any replies are ignored, so no further calls can be made or values passed along.

Regardless, even if my characterization isn't synonymous with theirs, they don't specify any termination requirements for site execution. Pruning is semantically a purely local termination of an executing Orc expression.

I suspect that the Join calculus implementation you spoke of would have not been problematic with the weaker specification you describe.

You can judge for yourself. They argue the semantics are probably preserved, though perhaps not the spirit.

I'm afraid you lost me. Did you just apply 'assuming' as a counter to 'controversial'?

The entire intention of site calls is to invoke host language functions, so the "assumption" isn't a really stretch, hence the puzzlement over what's so controversial. I can't conceive of a reason one would want host language functions that are not callable as sites.

I suspect you have lost the original context regarding which you asked about 'incompatible messages', which was: "1. to support type safety and static analysis of configuration...". Sure, you can fix the problem in the code by inserting a transformation. But, to do that, you must notice the problem before running the code.

Yes, I remember the context. Orc is compatible with static typing, especially if you just view it as a lazy stream processing language, so the combinators are roughly:

val (>>): 'a list -> (a -> b) -> 'b list
val (||): 'a list -> 'b list -> ('a,'b) Either list
val (<<): 'a list -> 'a

The better question is: how much does a complete solution invade the code for sites?

Right, by 'feasible', I mean usable by mere mortals.

Any property or feature that must be achieved by invasive code disciplines on part of the programmers, possibly even through libraries, should not be considered a property that the language supports.

I'm skeptical that live upgrade can really be transparent to the programmer.

'Too much' is a fairly dynamic quantity.

Agreed, though in general one can almost always move towards "more abstraction", but it is very difficult or impossible to move towards "more concrete" if your language provides a high fundamental level of abstraction (for instance, lazy evaluation as the default is one of these IMO).

I edited my previous post, so it's hopefully readable now. I sometimes forget that others aren't on big wide screens. :-)

Any other site calls are suspended waiting for a reply,

You assume that the other expressions are 'waiting'. That is not necessarily the case. If you have 'val x = (A|B|C)' and B returns prior to A or C spin up to issue calls, or if A and C are spinning in a loop emitting messages while not waiting on replies, there will be considerable difference between 'cannot process any further value' and 'cannot call any sites'.

I can't conceive of a reason one would want host language functions that are not callable as sites.

Yet that does not preclude the possibility of a host language supporting functions that are not callable as sites, or that have terrible terrible semantics if called twice (making them unsuitable for chaining), or that have interdependent ordering, or that otherwise break the orchestration model.

Orc is compatible with static typing, especially if you just view it as a lazy stream processing language

I agree that Orc is compatible with static typing. But this argument is due to you and I not seeing eye-to-eye on the 'orc is just notation atop a host language' issue.

I'm skeptical that live upgrade can really be transparent to the programmer.

Not all aspects of live upgrade can be transparent (especially policy). But certain components must be transparent and/or lifted into a higher layer (i.e. essentially deep transforms over the entire expression/composition) if they are to work in a consistent manner that is minimally disruptive.

It is very difficult or impossible to move towards "more concrete" if your language provides a high fundamental level of abstraction (for instance, lazy evaluation as the default is one of these IMO).

That's due to today's language tools. There are ways to support both... where higher abstraction truly allows more flexibility and control in the lower layers. Most of these ways involve proof-bearing code.

'Lazy evaluation' is neither more nor less abstract than 'strict evaluation', and you can emulate either one with the other. More abstract would be achieved by the total functional programming, where lenient, lazy, and strict are all available (and indistinct except regarding performance).

I edited my previous post, so it's hopefully readable now. I sometimes forget that others aren't on big wide screens. :-)

For this, I thank you.

If you have 'val x = (A|B|C)' and B returns prior to A or C spin up to issue calls, or if A and C are spinning in a loop emitting messages while not waiting on replies, there will be considerable difference between 'cannot process any further value' and 'cannot call any sites'.

There are no values in Orc except those created by site calls. Thus, "spinning in a loop emitting messages" means calling sites. So either a site call is in progress and the Orc scheduler is waiting for a reply, or a call is soon to be issued. Both of these are terminated, and the former requires only that any value returned by the call is dropped as you can't necessarily terminate in-progress calls.

Yet that does not preclude the possibility of a host language supporting functions that are not callable as sites, or that have terrible terrible semantics if called twice (making them unsuitable for chaining) [1], or that have interdependent ordering [2], or that otherwise break the orchestration model.

All of which can be handled within the model. [1] Use promises. [2] Create a properly sequenced Orc expression. Can you think of an example that cannot be lifted into an Orc computation?

But this argument is due to you and I not seeing eye-to-eye on the 'orc is just notation atop a host language' issue.

Do you agree that Orc is still Orc if you redefine some of the fundamental sites? ie. keep the semantics of the combinators, and the semantics of site calls, but with a different set of fundamental sites.

requires only that any value returned by the call is dropped as you can't necessarily terminate in-progress calls

And that much is trivial to implement. But it does seem much weaker than was claimed by the developers of Orc.

All of which can be handled within the model.

No, all of which can be handled by savvy programmers. The model is not handling them. Perhaps it is a matter of viewpoint, but any time you essentially appeal to completeness as a measure of 'support', I am going to reject your appeal. Support means something more to me than "programmers can hammer that square peg into this round hole".

Do you agree that Orc is still Orc if you redefine some of the fundamental sites? ie. keep the semantics of the combinators, and the semantics of site calls, but with a different set of fundamental sites.

Unless the 'fundamental' sites were described to be outside the 'standard library', I would say they are part of Orc's definition. You'd have a different language, albeit with similar primitives, if they were changed. The standard library includes anything that comes along for the ride along with everything that may need re-implemented to get 'standard Orc' code running on other systems. This includes 'sites' like 'Rtimer' that are declared in the user guide you linked, chapter 1.3. Orc also includes everything in 'Cor' (chapter 1.2), which is described as a 'subset' of Orc.

And that much is trivial to implement. But it does seem much weaker than was claimed by the developers of Orc.

I just checked some of their papers again, and they repeatedly say that they place no restrictions on the semantics of site calls, in which case it is clear that whether a call can be aborted must depend on the site (in fact, abort() for an in-progress call can be exposed as another site). Orc expressions are under the control of the Orc evaluator, and so can be terminated arbitrarily, but invoked sites are not and so may or may not support early termination.

No, all of which can be handled by savvy programmers. The model is not handling them.

Not all programmers can derive a monadic structure for I/O. Us mere mortals will just have to use the safer abstractions provided by the more advanced developers. If a particular site has a certain semantics, it's up to the end user to ensure its proper use, as is the case in any language. This is not a failure of the model, it is simply the nature of the beast.

No. I understand Orc to be a language that includes 'fundamental sites' and such. Indeed, they describe such components to be subsets of Orc, and they further declare that objects in the language are used as sites, and I'm taking them at their word (whereas it seems you're taking your earlier impression as though such an impression defines Orc).

Ok, which Lisp is the true Lisp? Which ML is the true ML? Alanguage founded on the Orc combinator and site semantics will be every bit Orc the same way that OCaml, SML, SML/NJ, etc. are each an ML. I don't give Orc any special distinction just because the authors went ahead and built a JVM language implementation with particular choices for fundamental sites. Their earliest paper on Orc, which defines the denotational tree semantics, makes no mention of any fundamental sites.

I wouldn't call any new Orc-derived language "Orc", but I would certainly call it "an Orc", just like you would call a new ML "an ML". Similarly, I would call any embedded DSL implementation "an Orc EDSL", even if the fundamental sites are slightly different. I don't see how that's unreasonable or inconsistent with standard conventions.

I wouldn't call any new Orc-derived language "Orc", but I would certainly call it "an Orc", just like you would call a new ML "an ML".

I'd accept that... but if 'an Orc' comes from the original developers as a later version of stuff written in earlier papers, I'll accept it only in the same way I'd accept that Ruby 1.9.1 is 'a Ruby'.

Us mere mortals will just have to use the safer abstractions provided by the more advanced developers. [...] it's up to the end user to ensure its proper use [...]. This is not a failure of the model, it is simply the nature of the beast.

If you fail to classify situations like this as failures of the model or language, then you would be inconsistent to make claims about failures of any Turing complete language or model, because you can always say: "let an advanced developer abstract it, and it's up to us end-users to ensure the proper use".

I can't accept such appeals to completeness. If, to achieve a feature, you must use a framework, apply a design pattern in an ubiquitous manner, or otherwise leak implementation details from the library or abstraction, then said feature cannot be claimed to be supported by the model or language. If the language or model has a purpose in a domain that requires this feature, then the absence of said feature is a failure of the language or model. This definition gives me a fair measuring stick by which to compare languages.

If you don't believe the situation you describe has all the hallmarks of a model or language failure, then I'm curious: how is it that you distinguish features from failures in complete languages and models of programming?

If you fail to classify situations like this as failures of the model or language, then you would be inconsistent to make claims about failures of any Turing complete language or model, because you can always say: "let an advanced developer abstract it, and it's up to us end-users to ensure the proper use".

Isn't this the nature of all languages higher-level than assembly? Why does Haskell include unsafePerformIO?

The FFI to a language has the potential to include many unsafe functions. Do you know of an FFI which guarantees that the use of all linked functions is safe in any setting?

These are the only functions that may be more difficult to use in Orc because of their side-effects. If there are language terms whichi have the same dangers, then either the language itself must have some way to ensure it's proper use, such as monads or linear types, or the language just doesn't impose any discipline for side-effects and lets users deal with it via testing (most call-by-value languages like ML).

Given the above, what legitimate argument is there to exclude functions from use within Orc?

Isn't this [appeal to completeness to defend language properties] the nature of all languages higher-level than assembly?

No. It is not. First, there is the fact that there are many useful languages that are not Turing complete (total functional programming, procedures without loops or arguments, a variety of dataflow languages, Datalog, etc.). Second, appealing to completeness - and neglecting more discriminating propositions that distinguish feature sets meaningfully even among complete languages - is a property of the observer and not a property of the languages being observed.

Why do you even single out assembly? Assembly is complete. If you were to be consistent with your earlier arguments, you should be saying: programming directly in assembly (which can always be run on a virtual machine) has the same feature set as every other Turing complete language. Assembly should, in your eyes, even be entirely suitable in the same domain as Orc. After all, one can always have the advanced developers abstract out the ideas of workflows (sequencing, pruning, parallel operations) and of sites (coroutines) using a few assembly macros and higher-order assembly instructions (that take PCs as arguments) and develop a neat little framework for everything to run inside. One can even wrap an 'upgradeable' interface around such coroutines. It then is "up to the end-user to use these correctly".

And that last appeal has a big gotcha. Said gotcha simply isn't visible until after the "end-user" wants to integrate the abstractions developed independently in two or more different libraries. If those abstractions took out the big hammer and appealed without restriction to completeness, they may involve frameworks, imposed design patterns, possibly even code-walkers... and run high risk of making incompatible or inefficiently (or anti non-functional-property generally not of user's choice) compatible most approaches to "using [the abstraction] correctly".

Why does Haskell include unsafePerformIO? [...] The FFI to a language has the potential to include many unsafe functions. Do you know of an FFI which guarantees that the use of all linked functions is safe in any setting?

That sort of safety is, in this case, a red herring issue except insofar as it stands among the non-functional properties that may become difficult or impossible to achieve the moment you attempt to integrate two or more otherwise well designed frameworks or code pattens that were developed independently.

The earlier use of the phrase "use it safely [correctly]" described, instead, the requirement for a 'mere-mortal' end-user to follow special rules for application of abstractions provided by the 'more advanced developer'.

Given the above, what legitimate argument is there to exclude functions from use within Orc?

You're free to include such interdependent, single-call, etc. functions as described above. My objection is to any claim that they are among functions 'supported by' Orc and its workflow model. We must be extremely careful about composing such functions within Orc expressions: their use results in code patterns/rules/self-discipline being enforced upon users. It only takes integration of two such systems before one has potential for incompatible rules.

Languages make things easy by giving everyone, including all library developers, a common set of rules to follow in order to "use it correctly" and expose in order to "fit in with the language". So long as programmers don't expose something that changes these rules - even if they apply some self-discipline within a modular component - all is fine and dandy. And it is this limitation - making each library component look like a natural extension of the language layer for which it was written - that naturally defines which features a language may be reasonably argued to support and discourages unrestricted appeals to completeness ('it isn't impossible, but you'll need to leak <extra-safety-rules/design-patterns/framework-integration/etc.>').

[Aside: I feel we are too far off topic, and I'm growing bored of the thread. I'll make this my last post on this sub-thread... we need to bring it back around to transactions in process calculi and related systems.]

Assembly should, in your eyes, even be entirely suitable in the same domain as Orc.

Assembly isn't suitable only because current implementations lack the ability to build higher-level abstractions. Given a "functional assembly language" with the ability to build relatively safe embedded DSLs, as one can do in Haskell, I would agree that assembly could be suitable (if portability were not a concern).

My objection is to any claim that they are among functions 'supported by' Orc and its workflow model. We must be extremely careful about composing such functions within Orc expressions: their use results in code patterns/rules/self-discipline being enforced upon users.

This is true of any language that is not referentially transparent, which is just about all of them except Haskell and Clean. "Guaranteed safe composition" has never been a requirement for the practicality or popularity of any language, except perhaps in academic circles.

In the absence of guaranteed safe composition, users will do what they have always done: a) created safer abstractions wrapping the unsafe ones, or b) trial and error until they achieve the desired result (or in very rare cases, c) verify the implementation meets the specification).

While it would be ideal if all functions integrated nicely with the Orc semantics, whether Orc is exposed as an EDSL or as language primitives, it's by no means necessary for success if history is anything to go by, and successful systems will get built either way (though certainly more easily the tighter the integration).

Individual actors aren't composable; that is one of the weaknesses of actors model. However, even some of the older literature on Actors model goes with some detail into the composition of actor configurations.

Certainly, it's possible to develop a scheme for compositional construction of actor systems. Gul Agha, among others, did quite a bit of work on that kind of thing (as you're probably already aware). The point is that compositionality falls out naturally from the use of anonymous processes and named channels, while it requires a bit of work in the actor model (mostly, as I recall, by imposing constraints on how certain actors can behave). Conversely, it's entirely possible to impose constraints on how processes are constructed in order to avoid the deadlock difficulties with process calculi (see, for example, Welch's IO-SEQ and IO-PAR patterns), but such properties don't fall out quite as naturally in process calculi as they do in the actor model.

The point is that compositionality falls out naturally from the use of anonymous processes and named channels, while it requires a bit of work in the actor model (mostly, as I recall, by imposing constraints on how certain actors can behave).

Anonymous processes with named channels are, indeed, more immediately composable... i.e. such composition can be readily performed even within the definition of processes. But more 'immediately' doesn't equate in my eyes to more 'naturally'.

By analogy, I find the idea that "procedure descriptions have zero arguments and can be executed to some effect" combines with "functions neither rely upon nor produce effects, have at least one argument, and can return values, values include procedure descriptions" in a manner far more symbiotic, complementary, 'natural' than allowing both procedures and functions to take arguments. If both take arguments, then their domains, or purposes, are overlapping. If functions can rely upon and produce effects, there is no need to have both functions and procedures... but the system as a whole is that much harder to reason about, optimize, verify, reuse, etc. - especially in the presence of modular components and parameter passing.

Process calculi makes for more immediately composed processes, but use of more than a single, named receiving channel for a process in process calculi forces programmers of a process definition to be somewhat more aware of the process's final place in the world (at least with regards to expected protocol, since one can easily deadlock waiting on an incorrectly used channel). This seems (to me) true in much the same way that having effects in a function means you need to know where that function is being used. And, while process calculus is more general than actors model, this fact has about the same value for reasoning about reuse, parameter-passing, the system as a whole, optimizations, etc. as pointing out that argumented procedures can be side-effect free.

Just a thought, but perhaps the fact that individual actors cannot readily be composed without support of a higher level layer should be taken, instead, as a sign that actors fit naturally with such higher level composition languages, whereas the process calculi will tend to overlap domains and compete with composition languages.

"procedure descriptions have zero arguments and can be executed to some effect"

Is this not equivalent to putting all side-effecting code into a monad?

The slight difference between 'procedure descriptions' and 'procedure monad' is in the ability to, in the general case, decompose a description. I.e. a procedure description could be a plain-old-datatype that can be executed with common semantics. IOMonads can rarely be viewed in this manner.

There's no functional difference at all if there is no chance you'll be decomposing procedure descriptions. But decomposition rarely allows one to achieve type-safety (procedure descriptions are a bit like scripts), so composition-only solutions (compositions including parallel, sequential, conditional, on exception, etc.) is usually favored in typed languages.

Is your plan to model binders in the script? ie, when you write something like print getKey, does that translate to a procedure encoded as something like:

let x = run getKey
run (print x)


That looks to me like the only real way to keep procedures transparent since using the ambient language function binders is what makes monads opaque. But that also looks like duplicated work and extra complication. Is the point something to do with your desire to serialize procedures?

That was just the technical distinction, as I understand it, between 'procedure description' and 'procedure monad'. Descriptions, in the general case, are decomposable.

For my own language, I haven't decided one way or another to represent functions and effect types in a decomposable manner (though I have decided to make the same decision for both functions AND effect types). On the one hand there is some case for homoiconic languages and well-typed standard pickles (mobility and distribution semantics, debugging, etc.). On the other hand lies easy-to-achieve type safety and much heavier automated optimizations. (I must have both!)

Is your plan to model binders in the script?

If I understood you, yes. A procedure description would be able to bind return values and promises for replies and forward them with standard semantics into the function used to produce the next procedure (though promises and delayed values receive special handling).

when you write something like 'print getKey', does that translate to a procedure encoded as something like:
let x = run getKey
run (print x)

You would need to explicitly execute getKey 'print !getKey'. Otherwise you'd call 'print' on the 'getKey' procedure description.

That looks to me like the only real way to keep procedures transparent since using the ambient language function binders is what makes monads opaque. But that also looks like duplicated work and extra complication. Is the point something to do with your desire to serialize procedures?

If procedure descriptions are opaque, then so will be function descriptions, and vice versa. I'll need the same ability to type and confirm termination for anything produced by building such descriptions arbitrarily. Thus, monads would also be transparent.

The question is whether or not to make pickled functions and procedures opaque (and, thereby necessarily, primitive).

Weighing in favor of opaque pickling is clean type safety, and optimizations - such as the ability to automatically package function and procedure descriptions with low level proof-bearing code marked for checking by certified (and versioned) proof checkers. That is, it would be easy for a processor-heavy node to cross-compile and ship machine code behind-the-scenes to embedded system nodes along with a cheaply checked proof that the machine code is safe, terminates, is well typed, etc.

As far as my 'plan' goes, I'm leaning somewhat in favor of opaque pickling of functions and procedures. Programmers that need decomposable procedures could still create 'procedure descriptions' in the same manner Haskell allows programmers to create languages using datatypes and writing up an 'eval' function (or a Futamura projection).

But, either way, there will be duplicated work and complication. That just comes naturally with mobility and distribution.

Sorry, I thought we were talking about your personal design, otherwise I would have just asked for a reference.

I don't think I got my question across, but you still basically answered it. It sounds like these procedure descriptions would be "glued together" with functions just as you'd do with monads (rather than a new binder scheme), but that you might have a general introspection mechanism for decomposing functions. I don't think this is necessarily a problem for type safety, though you lose parametricity.

Parametricity is indeed more precise in describing what is lost (at least semantics-wise... the hit to optimizations, and the greater need for extra safety checks and per-node compilers or interpreters, is also huge).

Process calculi makes for more immediately composed processes, but use of more than a single, named receiving channel for a process in process calculi forces programmers of a process definition to be somewhat more aware of the process's final place in the world (at least with regards to expected protocol, since one can easily deadlock waiting on an incorrectly used channel).

...actors fit naturally with such higher level composition languages, whereas the process calculi will tend to overlap domains and compete with composition languages.

Agreed. So the question always becomes: what are the right goals?

Especially given the meta-level programming languages work at - purpose for a language vs. the goal of a design - there's probably no scientific answer to that question.

Given your interest in process calculi and security, you might also be interested in "Tamed Pict" and "Sahara".

Looks promising. I'm certainly interested in memory and CPU accounting. I'll check it out.