Lambda the Ultimate

what are the closest things to that in previously existent languages? i mean, the 'shove it into the compiler somewhat' approach? i don't really understand fully but it sounds a little bit like the web continuations stuff e.g. from the Racket world.

See also the dedicated topic for these introductions.

I wasn't really interested in getting Silverlight for this.

Gilad was the most prepared speaker, and was very focused on his agenda, as always. There are probably plenty of mathematical issues with general evolvable software. I wonder how familiar he is with these? Who [else] is?

Gilad's given many different names to his agenda over years. I favor his most recent one.

I've been studying a closely related problem for years - open distributed computing, with graceful degradation of services under disruption and network partitioning. I eventually decided that the problem of 'upgrade' should be framed in more continuous terms - in particular, of live programming. You can collapse the common issues surrounding upgrade vs. orthogonal persistence into just the issue of how to effectively develop a 'live programming' language - albeit at a grand scale (open distributed live programming) with all sorts of relevant security concerns. Developing an effective live-programming language will require controlling how some concepts are expressed.

I disagree with Gilad on a significant point. He wants to "co-evolve" data and programs. But from a live-programming POV, it is far more convenient if 'state' is kept to the edges of the system. The more state you can push to the edges of the system, the better you'll be for ensuring sensible - ideally, fully or partially retroactive - semantics after a change in code.

Once most state is at the edges of the system, there is little a need to 'co-evolve' the two; rather, the majority of code is simply propagating, composing, adapting, and transforming logical 'views' of systems, making inferences. The system should be able to keep running before, during, and after a change. Ideally, the system after the change should keep running as if the code had always been in its new form. (Bonus points for retroactive effects!) Which paradigms effectively fit this? Dataflow programming, functional reactive programming, flow-based programming, publish/subscribe models, temporal logic programming, temporal constraint programming, functional relational programming, event stream processing, complex event processing, tuple spaces, blackboard architectures, etc. - all sorts of research has been done on building runtime-composable systems, and all those lessons apply to live programming!

But OOP is a horrible paradigm for this purpose (and merely terrible for almost every other purpose ;). It introduces all sorts of irreversible state with object constructors, object reference sharing, message creation and delivery, etc. The only way to avoid those evils is pretty much to reinvent flow-based programming (that is, favor a fixed number of top-level objects, externally configured) and effectively foresake OOP.

Unfortunately, most of the aforementioned paradigms sacrifice either object capability security or open modularity. OOP achieves both of those properties, but sacrifices reversibility (and thus live programming, persistence + upgrade). Are we stuck with 'pick two'? I don't believe so. My Reactive Demand Programming (RDP) model achieves all three properties, using bi-directional reactive dataflows between agents.

In RDP, the particular issue of agents statefully keeping references is dodged by favoring 'unstable' references - your reference is valid only for so long as a stable dataflow is continuously providing you that reference, and thus there is always a clear and stable and continuous 'chain' of authority in the system. I actually consider this clear chain of authority to be a major advantage over OO-based ocaps, especially for the command-and-control domain.

I think you and I both agree on this, but it isn't clear how researchers are actually tackling this problem. The papers from this years S3 conference for example don't seem interested in these problems. And what about SPLASH? One of the invited research themes was about evolvable software. Instead we got keynotes about (1) automatic programming using non-scalable genetic programming techniques and a pipe dream of this being useful for trillions of lines of code (2) novelty search as an alternative way to approach problem solving tasks.

Computer scientists are really stupid when it comes to thinking about what constitutes Very Large Scale Software. They don't even know what the buzzword they are using means. They seem to imply things such as the strange idea that it is their job to re-pair systems nobody can even understand. I just don't understand it. According to the 2009 Standish Report, we don't know how to manage software projects with $10M budgets, let alone trillions of lines of code. And the very idea of trillions of lines of code being a target just shows a complete non-understanding of the need for plug-ins and modularity in most software systems. [Edit: There was only one paper I saw that really seemed to fit the call for papers, To Upgrade or Not to Upgrade: Impact of Online Upgrades across Multiple Administrative Domains]

Gilad on the other hand I can generally understand. But what theories are there out there right now for discussing what he is talking about? I've been looking at this issue for a year and a half now as part of my language/vm's metasystem, and there just aren't that many good theories to start with that I can see. In the database world, we understand topics like change data capture and schema mapping at least somewhat theoretically and databases is the domain that gave us the idea of orthogonal persistence for languages.

Something I forgot to include above was that Gilad and MarkM supposedly sat next to each other on the plane to Redmond from Reno (from SPLASH to PDC). Gilad supposedly asked MarkM if he thought his vision was possible, and Gilad summarized MarkM as saying it was impossible - MarkM then butted in to say he wouldn't go that far, only that it was an extremely hard problem we don't currently understand. It's kind of curious Mark would say this since he pushed for automated persistence as part of the E language project. He would seem to have as good as grasp as anybody about the subject. Gilad also clearly understands the issue somewhat, since he talks about serialization as part of his justification for why the virtual machine's execution shouldn't depend on types, in his Pluggable Types manifesto.

I do think something we all can agree on is that the minimum requirement to make such an idea happen is the object capability model. No other approach can handle dynamically federated, dynamically distributed systems. That's an ultimate problem when you think about "permanent services". A service might store your program code and your "data", but if it ultimately has external dependencies, then you've got a dependency management issue and no guarantees on how that will work. There is only a small subset of interesting services that can have a single permanent service.

[Edit: Something that wasn't really discussed was how poorly system's today handle administrative controls. I read a report a few months ago about how Microsoft is getting hell from its biggest partners right now because the Operating System insists on updating itself even during critical business hours, and there is no good system for giving the administrator control over upgrades and rollbacks. The way Windows is designed really isn't meant for allowing businesses to define what high availability periods they have, and can't tie the notion of high availability to the business process, since high availability really depends on the business cycle; some business time periods are more critical than others (e.g. end-of-month closing, necessary for timely filings to SEC and other regulatory bodies, etc.).]

I disagree with Gilad on a significant point. He wants to "co-evolve" data and programs. But from a live-programming POV, it is far more convenient if 'state' is kept to the edges of the system.

I am not sure I understand. As I have read Gilad's literature, he has snuck in very slyly the suggestion that at a bare minimum modules must be re-entrant in order to talk about introspection and hotswapping in a meaningful way. He hasn't really expanded much upon this as far as I'm aware.

If I understand you correctly, your "three properties" are reversibility, object capability security and open modularity.

Once most state is at the edges of the system, there is little a need to 'co-evolve' the two; rather, the majority of code is simply propagating, composing, adapting, and transforming logical 'views' of systems, making inferences.

Sort of. The big win is when there is no feedback loops between the input/output relations of two agents. Flow-based models necessarily try to solve problems in such a way that flows (the wires) are deterministic, trying to avoid bad feedback loops. I don't think the fact this trick exists necessarily precludes other ways of thinking about what it means to co-evolve data and code.

If I understand you correctly, your "three properties" are reversibility, object capability security and open modularity.

I could name a bunch more important or useful properties - incremental computation, eventual consistency, glitch-freedom (which is much weaker than consistency), control of latency costs from indirection, demand-driven resource management, etc. I've a huge checklist written down that I review for every user-story and design change.

Based on the user-stories I've worked through and discussions I've had in the workplace, developers will often resist intermediate services if their use is likely to increase latencies. That's a huge psychological and performance barrier against fine-grained services ever gaining wide acceptance. OTOH - if combined with code-distribution, JIT or specialization, and orthogonal persistence - one could actually improve latencies by use of 'another layer of indirection'. That smashes away a psychological and performance barrier to Gilad's vision. I discussed a few of these issues a little while ago, starting here.

There are many more than three important properties. But the three you listed are still quite important to the cross-domain integration and upgrade issues. I think 'reversibility' has other meanings, though, so I'd avoid listing it as you did without context. One might substitute 'reversibility' for 'reduced temporal coupling' if we need a word-phrase that can stand on its connotations rather than its context. (I define temporal coupling as the extent to which the state of a system is a function of when it was created.)

at a bare minimum modules must be re-entrant in order to talk about introspection and hotswapping in a meaningful way

That really isn't necessary - not unless you assume stateful paradigms for the modules. With temporal logics or reactive systems, for example, there is no need for a dialogue about hotswapping; one simply changes the available pool of dependencies or the injection policy, and the new dependencies are derived on-the-fly. They further may be JIT'd and specialized into the derived system behavior. This is because, in reactive systems, dependency-injection is stateless.

And general introspection is often a bad idea from a security perspective. And if we use special ocaps for introspection, we are less likely to much need reentrancy since inspecting meta-data does not necessarily introduce a cycle with inspecting the data.

I believe that Gilad has been struggling with his vision because he's starting from an implicit perspective: he wants this vision of full-service computing to come true in an OO model - in Newspeak. He speaks of full-service computing in terms of 'objects' and 'object synchronization'. Everything is implicitly framed by this assumption, by the OO paradigm.

Building full-service computing on OO is a bit like building a city on a swamp. It's doable in some informal sense, but the first thing you'll do is smash away the swamp with all sorts of infrastructure... at which point it's no longer recognizable as a swamp (except that you'll be living with a lot of bugs ;). With OO, that 'infrastructure' happens in the form of self-discipline, synchronization frameworks, design patterns (unum, live distributed object) - generally to the point where it's no longer recognizable as textbook OO.

The big win is when there is no feedback loops between the input/output relations of two agents. Flow-based models necessarily try to solve problems in such a way that everything is deterministic, trying to avoid bad feedback loops.

Feedback isn't all bad. Constraint satisfaction can be expressed as a closed fixpoint loop in a dataflow, and would retain the benefits of reactivity. Self-regulating systems can be expressed as open feedback loops. What is a problem is a divergent loop, which is similar to cyclic method calls or other infinite loops in the sorts of problems it can cause. Divergence of a closed loop, for example, is a violation of 'eventual consistency' properties - there will never be a stable state to synchronize.

But I'd readily agree that we should at least keep loops off the path-of-least-resistance, e.g. by requiring explicit annotations when introducing an expected loop.

If I find time, I'll study how to effectively express and leverage fixpoint loops while avoiding risk of accidental divergence. It seems like a task for a DSL, really.

I don't think the fact this trick exists necessarily precludes other ways of thinking about what it means to co-evolve data and code.

Well, if you get hand-wavy with the phrase, you can think about it however you like. There's glory for you! ;)

Here's what Gilad says on the subject (reordered for focus and clarity):

The Achilles’ heel of orthogonal persistence was the divergence of in-memory data representation and persistent data representation. Orthogonal persistence broke down when old data became incompatible with program data structures. This argued for manual management of the transition between primary and secondary storage.

In our brave new world, programs co-evolve with their data so this is not an issue. The service manages both the application and secondary storage, updating them in lock step. Thus, we have data that is not only orthogonally persistent, but orthogonally synchronized. [...] The applications are compelled to keep their persistent data in silos tied to the application, and communicate with other applications in constrained ways.

It seems entirely clear to me, at least, that Gilad assumes 'data' is uniquely associated with the service, and this data could not be regenerated on-the-fly. This is traditional OO-think - data is bundled with behavior.

My objection was that this is a failing scenario to start with, that the proper test is that you couldn't make this scenario work in live-programming. I expect that even skilled developers would muck it up nigh every time, and rank it on their list of favorite things right alongside DLL hell and debugging rare race-conditions in large projects.

And I'm this pessimistic even about the presumably easy case where current 'state' associated with a service is centralized rather than embedded deeply within the relationships between services. Gilad mentions 'communicating in constrained ways' with other apps - which, reading between the lines, requires self-discipline and a sacrifice of expressiveness. I wonder how many capability security patterns you'd need to sacrifice...

When success looks that ugly, we really need to move the goalposts! Rather than attempting to 'co-evolve' data, we should be aiming for 'separate evolution' to the greatest extent feasible. Long-lived non-regenerable data should not be associated uniquely with any application, in the sense that it should be feasible to transparently inject a 'lens' between a service and the data upon which it depends when an interface changes.

Re: to upgrade or not - I favor that the path-of-least resistance should be automatic synchronization, and that if you want to control 'freeze' points you can explicitly code that into the system by use of state and higher-order behaviors.

It's kind of curious Mark would say this since he pushed for automated persistence as part of the E language project.

E actually favours manual persistence (see also here, and the previous LtU thread). There are many tough resource acquisition and security issues with orthogonal persistence, and serialization in general.

The way Windows is designed really isn't meant for allowing businesses to define what high availability periods they have, and can't tie the notion of high availability to the business process, since high availability really depends on the business cycle; some business time periods are more critical than others (e.g. end-of-month closing, necessary for timely filings to SEC and other regulatory bodies, etc.)

Then again, exploits aren't on a business schedule either, so why should fixing system vulnerabilities be on the business schedule instead of the exploit schedule? It would seem businesses are fighting reality, when they should instead be adapting to it.

Right.

I didn't contradict E's design philosophy here. From the link you provide:

Of course, by definition, anything a program does is automated, so what do we even mean by "manual" persistence? We are not arguing against automation, abstraction, and reuse.

By automated persistence, I did not mean to refer to transparent orthogonal persistence, and thus blindly leaking the object graph in an insecure fashion. I simply meant that Mark has investigated the degree to which we might be able to make the difficulties seem to disappear. I assumed this is why Gilad asked Mark, since Mark probably has as good an understanding on the problem domain as anybody.

Edit: Although, on second thought, I think I see your point. I was misleading. Sorry.

Using the phrase "orthogonal synchronization", Gilad was speaking about running two replicas of a general purpose program largely unaware of their replication, potentially disconnected from each other while each updates in response to requests, and then mostly-automatically reconciling their changes into a single joint state that preserves the intent of the separate modifications, while continuing to jointly work.

This is driven by an analogy to distributed version control, which usually mostly succeeds in reconciling separately made changes -- though in the very restricted domain of trees of textual source files and with informed manual developer intervention when needed. I remain skeptical that this result generalizes to arbitrary object graphs and absence of manual developer intervention.

Gilad is skeptical as well, which is why he considers it research. Our disagreement is over whether the better research results are to be found at trying to achieve the full goal, or at trying to find more modest workable restrictions of this goal.

This is a very hard problem, and I am pretty sure doing it automatically is NP-Complete if you don't use heuristics/conventions. I am not sure what paper I read to draw this conclusion, though.

I've been looking at this stuff for two years now, and have been reading diverse areas of CS literature to find a solution, or at least understand the various theories proposed and how they come up short. I've even brought this up in topic of conversation with famous PL researchers via e-mail.

I would vote for "modest workable restrictions", based on my experience and understanding of the limitations of what can be computed. I've already got some ideas down on paper but I don't have experience implementing this kind of compiler / VM architecture. If anything, history has shown in PL theory that you don't need a perfect theory, just a good one with big, powerful ideas (Smalltalk, ML). In the case of ML, the HM type inference cannot handle generalized constraints like subsorts, but that did not stop probably 1,000s of graduate students from getting their Master's or Ph.D. in refining this, e.g. Sulzmann's HM(X) and languages that only permit local type inference for the purpose of component abstraction.

people would first fix the i should have thought fundamental simple basic requisite usability issues with things like mercurial and git, so that i stop being forced to see them as things which lead people down the garden path into horrible impossible confusing merge states, then maybe i'd be willing to give one iota of benefit of the doubt to the idea that these oh so hallowed ideas could be used in a larger wider better context. but i'm not a bitter, withered, whiny person. oh wait.