Lambda the Ultimate

Ebook readers are not fundamentally new. They were also invented in concept form at Xerox PARC in the 70s. It was called Gyricon.

Also, I believe I read not too long ago that the core idea behind PageRank was invented in the 1950s?

Distributed revision control is not new it's just been "renewed" is all.

I wrote the first umpteen versions of GNU Arch which was one of the first of the recent batch. Independently others were also renewing the idea.

I got the idea from the practices that formed around Usenet, mailing lists, FTP sites, tar files, the standard unix program "diff" and Larry Wall's "patch". Things were less uniformly automated back in the late 1980s and early 1990s but we were using distributed revision control. The tools we were using grew out of earlier practices mainly in the early unix community. I also drew on some ideas from 1980s research in globally distributed, decentralized file system technology.

GNU Arch brought in incremental improvements to automation, naming revisions, and automation of "smart" patching strategies. Other systems then and since made similar incremental improvements.

All of the innovations in that area since around the time I started GNU Arch have been incremental improvements of the sort I described above, incremental performance improvements, incremental user interface performance, and improvements in explaining these systems to prospective users.

I think that distributed, decentralized revision control *seems* new to so many people these days for two main reasons: first, standard industry practice through the 90s (and still largely today, I gather) was to use centralized client/server revision control - so the recent systems created "aha!" moments for a lot of users; second, while I knew a lot of the history when making GNU Arch I think a lot of people who have helped develop recent systems have been independently re-discovering well known stuff, unaware of history.

Distributed revision control is not new it's just been "renewed" is all.

Fully agreed, except that Alan Kay's definition of "new" in this situation was "1980 or later", which describes most of what you've mentioned. The guy's just turned 70, I think he can be forgiven for thinking of the last three decades as "current"!

first, standard industry practice through the 90s (and still largely today, I gather) was to use centralized client/server revision control

Heh. My impression, being out in industry, is that "standard practice" has been "no revision control whatsoever, maybe a shared network drive if you're lucky", gradually moving to "centralized revision control with pessimistic locking because merging confuses people".

Maybe in another decade when the baseline is up to something equivalent to SVN, then industry can start getting used to decentralized systems...

My impression, being out in industry, is that "standard practice" has been "no revision control whatsoever, maybe a shared network drive if you're lucky", gradually moving to "centralized revision control with pessimistic locking because merging confuses people".

This is exactly why I've been determined to integrate revision control into my programming language, making it a full-blown modeling kit, with support for just-in-time model production. You cannot solve social problems without examining social habits. There are also revision control systems that do work, such as Photoshop Document files, but they do not scale.

The guy's just turned 70, I think he can be forgiven for thinking of the last three decades as "current"!

Thanks for sharing this. I always wondered why nobody actually acts on Alan Kay's wisdom and attempts to profit from it. -- Just to be clear, Alan is essentially saying that any idea a 20 year old is working on today has already been done by somebody over the age of 50, and that the 20 year old's biggest obstacle will be marketing that idea and social engineering. The medium is the message.

If you paint the past in broad strokes then sure, you'll sing it before, and again, that it's all just little bits of history repeating.

But we didn't have Priority R-trees in 1980. We didn't have Concurrent Constraint Programming or Functional Reactive Programming. We didn't have HLSL.

I would say that painting the past in broad strokes looks an awfully lot like hand-waving.

We didn't have Concurrent Constraint Programming or Functional Reactive Programming.

Apart from an elegant denotational semantics, I am not sure if functional reactive programming adds anything to JP Morrison's ideas of flow-based computing from the 1970s! I've also suggested similar thinking to Conal via e-mail, suggesting the important issue is not a model for reactive programming, but teaching programmers patterns of use in the model, so that they can effectively solve problems using the model.

As an aside, for HLSL, if you read the original book on cg, you would know that Randima Fernando said that the based the design on C, and that they deliberately avoiding being revolutionary and just trying to be practical, since they didn't really know what people would use it for, they just strived for what they knew people were familiar with.

Revolutionary? What does that word mean, technically?

It seems to me that incremental advances can lead to qualitative improvements. Reducing the overhead for IPC, for example, can make 'practical' entirely new avenues for developing code.

Don't commit The Fallacy of The Beard. :-)

the important issue is not a model for reactive programming, but teaching programmers patterns of use in the model, so that they can effectively solve problems using the model

You might classify these patterns on a continuum between two points:

At one end of this continuum, there are the patterns that exist solely to work around the constraints or design-bugs in the model or its straightforward implementations, such as (for FRP) those for avoiding time-space leaks and supporting push-pull updates for efficiency. To avoid singling out FRP, I'll also mention the visitor pattern, cloning, explicit caching, and vast array of insecure concurrency patterns often seen in OOP and Actors models.

At the other end of this continuum are the patterns by which the model is advertised, supporting various properties as: a given separation of concerns (goal from strategy, content from presentation, error recovery from error handling policy, X from Y for many different X's and Y's), local reasoning about concurrency or security or timing or failure modes or safety or any number of properties, modularity in various forms (declarative dependencies, parametric abstraction, hidden models), life-cycle support (interactive or live programming, runtime upgrade, code distribution, version control, extensibility or pluggability, persistence), performance (utilization, parallelization, throughput, efficiency,latency, load-balancing), verifiability (formal proofs, type-safety, information flow analysis), debugging or auditing (deterministic replay, traces), and various other features (undo, automated backtracking, and so on).

And between those two points lie patterns that bridge the gap between the "ideal" and the "real", and make the model practical for integration with the real-world. A different set of patterns for these purposes will result in a very different 'program language'. Basically, you end up developing a new model within the other, and this new model adds some properties and subtracts others, and you end up with what, from a practical viewpoint, is really a new language. It wouldn't bother me to hear: "I don't program in Haskell. I program in Yampa." or "I don't program in C++. I program in Boost." Or "I don't program in C. I program in SQL+CGI." In fact, I suspect that I'd prefer it.

Presumably, to the extent your reality matches your model, you wouldn't need to Greenspun a new model within the first one. As a corollary, the value of your model for a given purpose is diminished by the same extent to which you rely upon patterns to make it useful (especially disciplined or cooperative patterns which hinder composition with modules or libraries written using different patterns).

For better or worse, "the real" isn't "natural". The reality our models must bridge is: clocked CPUs, COM and CORBA and SQL and FFIs, questionable process models, multi-tier cached memory with funky discrimination at the RAM/HDD layer, networks and firewalls, monitors and keyboards and mice, etc. This reality changes on us on a not-so-irregular basis: add webcams, add GPUs, add a bunch of CPU cores, add SOA, recognize that JavaScript+DOM has effectively become a target for code-generation.

Thus, even programming models that target a model of 'natural' reality need to still bridge the gap between that 'ideal' and the reality that faces them. But I would suggest that, in-the-large, the artificial features blend together and tend to obey greater laws. Thus, only models of 'natural' reality will scale. Which model of 'natural' reality to target remains a question worthy of much debate. Physical reality should probably fit in there somewhere. But what of social, economic, and political realities? trust, policy, legitimacy, responsibility, resource and service markets, etc. Related: Should we treat 'values' as 'immutable' things, or should 'values' be adaptive terms in a model that itself changes over time under the influence of a society?

So how do we create a new in-the-large model? Well, historically, we give it a spiffy name (like 'Service Oriented Architecture' or 'CORBA' or 'REST' or 'Blackboard Architecture' or 'Ruby on Rails'), then we provide an architectural implementation and various adapters to existing systems. There is often some sort of distributed language involved.

Unfortunately, though, this approach can easily tend towards 'painful', since what it teaches is the model without providing a suitable notation for it.

Apart from an elegant denotational semantics, I am not sure if functional reactive programming adds anything to JP Morrison's ideas of flow-based computing from the 1970s!

Of course. What possible difference could notation make? I'd say computer science hasn't come all that far from machine code! Total agreement, here. :-)

Revolutionary? What does that word mean, technically?

Proteins instead of gears, at least for Alan Kay in his famous OOPSLA keynote.

It seems to me that incremental advances can lead to qualitative improvements.

Making gears nano-scale changes everything, because they become sticky and don't spin. At that point one needs a leap. Peter Norvig indicates a comparable leap in the opposite direction with data being available at Google's scale. For most of our daily tasks we don't actually need leaps or revolutionary solutions.

It wouldn't bother me to hear: "I don't program in Haskell. I program in Yampa." or "I don't program in C++. I program in Boost." Or "I don't program in C. I program in SQL+CGI." In fact, I suspect that I'd prefer it.

Isn't this already the perspective of the job-market, where expertise is fused with commodity fetishism? "I don't use relational databases, I use Oracle", "I don't program ERP systems, I program SAP" etc.

It only looks like a leap when we make a big change all at once. Otherwise, everything is incremental. Though I've never tried it myself, I hear you can boil a frog that way; put a live frog in tepid water, then slowly raise the temperature...

Isn't this already the perspective of the job-market, where expertise is fused with commodity fetishism? "I don't use relational databases, I use Oracle", "I don't program ERP systems, I program SAP" etc.

Not on the resumes I've read :-)

But we didn't have Priority R-trees in 1980. We didn't have Concurrent Constraint Programming or Functional Reactive Programming. We didn't have HLSL.

Speaking of FRP, I found an interesting paper from the 70's on modelling circuits reactively, but that guy has probably faded into obscurity by now :)

I mentioned this problem to Dave Thomas once at OOPSLA, that everything seems to have been done in the 70s, and he wrote a blog post skewering me on it. I didn't say this was a bad thing, but he heard what he wanted to hear...I still love talking with Dave though, he's a very fascinating guy having been there and done that.

Fully agreed, except that Alan Kay's definition of "new" in this situation was "1980 or later",

Ah. Oops.

Heh. My impression, being out in industry, is that "standard practice" has been "no revision control whatsoever, maybe a shared network drive if you're lucky", gradually moving to "centralized revision control with pessimistic locking because merging confuses people".

:-). Maybe it's a unix thing. My experience starts in 1983 at a shop that was doing both unix and RSTS development - two separate teams, mostly. The RSTS guys did indeed not use version control. The unix guys did. Every shop I encountered after that used version control.

I very much agree that things have changed around branching and merging. "Back then" creating branches and doing merging were not ordinary activities. There would be meetings, arguments, permission granting and so forth. Branches started to come more commonly into day to day practice as it became more common for their to be release management teams - branches were used to snatch a snapshot to clean-up for release while the developers continued on on the next version.

At least as of a few years ago, the most commonly used "revision control system" (and I use the term loosely) for development in a Windows environment was Microsoft Visual SourceSafe, a crippled system that compares poorly to CVS, and supports only per-file exclusive locks as a means of avoiding edit conflicts. When I said "merging" above, I wasn't even talking about merging branches.

More recently, I think SourceSafe has finally been overtaken by the hot, exciting new source control technology in industry--namely, Subversion.

Sigh.

But I fear this is getting badly off-topic for LtU, so I'll leave it at that. In a feeble effort at relevance, I will at least note that the state of affairs in industry regarding acceptance of modern programming language concepts is substantially less dismal than that regarding revision control.

In a feeble effort at relevance, I will at least note that the state of affairs in industry regarding acceptance of modern programming language concepts is substantially less dismal than that regarding revision control.

They seem equally dismal to me. It took 20 years to get parametric polymorphism into popular industry languages, and even longer for first-class functions.

I have you're talking about C#, because what's in Java aint parametric polymorphism. :-)

Yes, C# gained generics around 2001/2002 I believe, which is 19 years after Damas-Milner.

Parametric polymorphism as a PL feature is much older: it dates back to at least Reynolds' 1974 paper, or arguably, Girard's thesis from 1972. There already where ideas for Algol-68.

Damas-Milner introduced polymorphic type inference into PL, which still hasn't found its way into mainstream languages (wannabe "type inference" support like in C++XX and the likes notwithstanding). Likewise algebraic datatypes or pattern matching, which are also about to turn 30.

20 years until mainstream adoption actually seems rather optimistic in the context of PL. I think that reality is even more depressing. For example, it took about 35 years for GC to hit the mainstream.

Parametric polymorphism as a PL feature is much older: it dates back to at least Reynolds' 1974 paper, or arguably, Girard's thesis from 1972.

Right, my bad for conflating the two. Then again, it depends where you want to draw the line for adoption too, as Ada had generics in 1987 and C++ adopted them with templates in the mid 90s (at least the proposal for the STL was adopted IIRC).

C++ adopted them with templates

Are you kidding? :-)

Only a little. Still, templates' generics by specialization seems to meet the minimum requirements.

I think the "automatability" is key here. Automation didn't work until we knew how to integrate 3-way diffs into a source control system. I wouldn't call the step from "knowing which diffs to apply to incorporate new code into your system" and "knowing how to construct an SCS that could figure this all out itself" at all an incremental one. Who first figured that out?

I know a bit of the history, but my knowledge of the ultimate sources of certain ideas is lacking. I'd love to see a timeline with all of the key transmissions of ideas from one implementor to another.

I'm not sure where 3-way diffs first showed up.

In general, Walter F. Tichy's 1985 "RCS - A System for Version Control" is a key node in the cite tree at least as much as I've seen it.

He, in turn, cited Marc J. Rochkin's 1975 "A Source Code Control System" (which certainly makes no mention of 3-way diffs).

The thing about 3-way diffs is that they aren't that huge an advance over regular diff plus heuristic-based patching.

Here, for example, is how I observed unix development to typically go back in the 1980s:

Bell Labs or UC Berkeley or whomever hands out a unix distribution. Various recipients make local changes. To share these, often, some unix shop would diff their modified version against the original distribution and send out that diff. People would apply it to their modified versions.

In the early days of the GNU project, also, a lot of development was in that style.

People were "doing" 3-way merges and understood them pretty well for a long time. The tools steadily caught up.

At one point (around about the time CVS was created) there was enough empirical confidence in this technique that an age old debate about locking policies in revision control took a new turn. That was one of the key selling points of CVS over RCS and SCCS - that you could use it day to day without having to lock files. (CVS also began to automate common branching and merging practices.)

So, if you want to dig around for the history of fancy merging - I'd suggest starting by asking Larry Wall. His "patch" program was highly influential. I've no idea what in it was original or where he might have gotten his ideas.

Finally, ok, you know there is something kind of new around the time of GNU Arch. I don't think GNU Arch was the first but I'm not sure what was. And I got the idea from the original goals list of SVN though I don't think they've actually yet quite fully implemented this goal as well it was done in GNU Arch:

"Whole tree version control."

All of the systems up until around that time were revision control for individual files. If you rename, create, or delete files or directories the older systems don't help much and sometimes get in the way. That was one of the hard problems I had to solve (although I can't swear someone else hadn't solved it first): how to "diff" trees of files and directories and how to "patch" that tree structure.
That much is "newish".

It really bothers me when the main page for a site is anything other than HTML; when I download a document, that should be obvious from the URL. In my browser, the above link resulted in a download named 'download', without any other distinguishing information.

Here's a quick summary. Let me know if I misunderstood.

Kayia is a graph grammar where each vertex controls two values, either of which may represent edges. Additionally, each vertex receives arguments based on a set of directed edges to that vertex. Those edges necessarily arrive from other vertices. Those other vertices may be distributed throughout the expression of the Kayia program, which lends Kayia a more declarative feel than functional programming.

Input to the program is logically expressed by updating the program (perhaps by associating some vertices with hardware devices). Output from the program is by evaluating some 'final' vertices, which in turn requires evaluating all the arguments to it (vertices with an edge to the final vertex), eventually propagating back to the initial inputs. This could fit efficiently into a 'continuous' and 'concurrent' evaluation system, using push-pull evaluation techniques.

Abstraction seems to occur by prototype or cloning, which itself might be expressed as a vertex.

Safety analysis is ignored in the paper. It is unclear whether one is allowed to form cycles in this graph, but - in accordance with the metaphor promulgated in the paper - I suspect doing would easily send a Kayia program into epileptic fits except in the rare cases where there is rapid convergence on a fixpoint.

That's a great summary. Thanks, David.

On the paper itself, I would suggest that you avoid using 'special numbers' to describe primitives and values and such - at least to start. Instead, describe programs with English labels. You can mention in passing that it's all just pairs of numbers (with configurable definitions) under the hood, and list a few of the numbers you use.

Overall, the approach seems solid. The organization of the program supports:

• greater plug-ability than functional programming, since sub-programs can essentially 'publish themselves' by naming a vertex that represents a shared directory or registry
• greater security than logic programming, since vertices themselves can be subjected to object capability model composition techniques
• live & reactive programming; you can update the abstractions and inputs while the system is running, and the outputs will change accordingly
• push-pull efficient updates to outputs; a lot of implicit caching is feasible
• by adding a few graph-rewrite primitives to the KM, i.e. 'when Condition is true, become subgraph Y', one could support reactive state machines, which are (IMO) among the best approaches for handling mutable state (keeps state updates local and voluntary)
• one can easily "hook" into an existing program, i.e. for debugging purposes one can essentially probe any vertex in the system and see what its output is, and do so from within the system (no special tools needed)

I like it, overall. Properties such as self-pluggable modularity, and security, are important to me. Kayia reminds me of some of my own recent design work :-). You might also find some parallels with Ugo Montanari's "Graph Grammars and Constraint Solving" and related work.

However, it is unclear to me how I'd express recursion. Fair examples for recursion are factorial and Ackermann. I don't mind terminating systems, but if I can't express Ackermann, I'm not a happy camper.

Similarly, it is unclear how to draw a request-response pattern that allows for multiple request-responses to operate concurrently, and also allows for demand-driven operation. For example, how could we have a vertex representing a database resource, and apply to it vertices representing SQL queries (which might change over time)?

I would express recursion by cloning the function itself. As for request-response, it would use message passing. The message can have attributes of priority, etc. It's the SQL queries that apply to the database resource, and are responded to based on events and messages. (Email me if I misunderstood something there.)

So you are saying that cloning of an axon can be part of its evaluation? and similarly for SQL, you would fire off messages?

Neither of those seem to effectively fit into the Kayia model explained in the paper. For a given recursive operation, you generally do not know how many 'clones' (function calls) you will need in advance of seeing all the inputs and potentially running the computation. And while message-passing could be handled with some graph-rewriting, to model it breaks that 'continuous result' property associated with and live reactive systems.

Where do you believe Kayia would fit into a programmer's toolkit? What would it replace?