Still Alive

Hey, long time. Having a snow day here, which is a good day to catch up. My son got sick this summer, which knocked me out of commission for a while, but I am back to work now. As promised last June, I have defined the formal semantics of a core language that captures the key ideas of side-effects in a tree-structured heap without sequential programming. I have formulated confluence and soundness theorems that seem plausible (though I haven’t tried to prove them). So I don’t think it will collapse under me like Coherence did. One of the next steps is to build a reasonably usable textual syntax that can be compiled into the core language. By reasonably usable, I mean usable for expressing small examples up to a hundred lines of code, which is the minimum I need to communicate the idea to others. The working title of the language is flux.

The other critical step is to formulate a compelling example problem. The Task example – a side effect ordering puzzle – just doesn’t hack it. Thanks to those who were willing to tell me so to my face. In fact I am coming to believe that I must change my whole strategy. My goal is to make programming easier: the needless complexity of programming is killing us all. But our culture prevents us from admitting it. We have been selected for our ability to cope with stupefying complexity, so we tend to glorify it. To say that programming is too hard (for even the smartest of us) is interpreted as an admission of stupidity, which is suicide in our culture. That is exactly what people say when my ideas leak out onto public forums like Hacker News: this stuff is just for stupid people, and I am one of them. I won’t get far solving problems that most people don’t admit they have.

Instead, I am thinking of taking on the old Holy Grail of transparent distributed programming. That is, the ability to build an application as if it were running on a single system, and then partition it across distributed clients and servers without any code changes, while maintaining performance and security. No one seems to care much about software complexity (they just hire more code monkeys), but they get all excited about performance and security. Sequential programming (particularly method calls) is a big problem for distributed processing. Whereas my parallel semantics could work better. More to come on this topic…

20 Replies to “Still Alive”

  1. Don’t give up! You’re so right about the difficulty of programming and how crazy our tools are. The better I get at programming the more I realize how bad I (and we all) am (are).

  2. Welcome back, Jonathan. I hope your son is OK. I know what it means to have a sick child.

    Regards,

    Peter

  3. Is transparent distributed programming worth pursuing, though?

    I have spent a lot of time analyzing as much proposals for this as I can, and I think what my opinion boils down to is this: There is no sufficiently smart compiler that can replace problem domain expertise, and quite often in order to improve performance we need to move from nondeterministic execution strategies to more deterministic ones; this move is the very essence of “architecture”, since the more deterministic our structure becomes, the more we can point out arches like “flying buttresses” in the Chartres cathedral.

    I also think there are some very fundamental laws of Nature that we don’t fully understand or have written down yet, that really guide what we can and cannot achieve in the scope of distributed programming, transparent or otherwise.

    1. Z-Bo,
      I agree that there have been no really satisfying solutions to date, and that it is a fundamentally hard problem. But I am not trying to make the compiler magically know how to distribute functionality. It has to be decided by the programmer. The point is that such decisions should be independent of the semantics of the program. You shouldn’t have to hard-wire the network architecture into your code. We do that big time when we build apps with HTML+JavaScript+Web-framework. Perhaps the distribution decisions are specified with annotations, or perhaps with refactorings, but in either case, the semantics of the program are guaranteed to remain the same. What I bring to the table is a parallel semantics that distributes more effectively than procedure and method calls.

      1. Good. Sounds like you have a different use for the word transparency than what I’ve read in the literature. Be careful with this when writing a paper about it, as it might get rejected on the pretense that you are solving a different problem (and implicitly reviewers will suggest your work is inferior dribble).

        I am facing basically the same issues in what I am chasing after. Alan Kay has been immensely helpful in giving me stuff to read. The big problem is its a lot to read. Currently I am looking at effect systems from first principles. Will yours be rooted in Curry-style or Church-style effects? I think Curry should be the default, but I am struggling to put into words why.

        1. I mean by transparency that distribution does not affect semantics. What is the meaning in the literature?

          I am impressed that you got Alan Kay’s attention. But what are Church and Curry style effects?

          1. I’ve always thought that the literature seemed to suggest that the compiler / runtime decides for you how to split your code across “tiers” or whatever. Maybe I am wrong.

            I’ve heard some computer scientists tell me stories of how they slightly misunderstood the use of some terminology, like “online” partial evaluation, and how it made them look dumb. Something I fight with constantly is learning the appropriate vocabulary to describe what to me should be blindlingly obvious to everyone. I hate it. People tend to prefer taking something they already know and perturb it just slightly, rather than envision from scratch how something could work. The difference for me is that pre-existing examples only illustrate how bad things are.

            Curry-style vs. Church-style dichotomy comes from Filinski’s work on effects using monads. To be honest, I am not convinced this is a useful dichotomy, but its the best precise vocabulary we have for describing effects. Actually, I don’t know if Filinski introduced this characterization or not, but it is what I use to frame it in my head. Lately, I’ve been thinking about going in a new direction, but I’m trying to be more precise in my reasoning lately and abandon “from the gut” urges to do more ad-hoc / less mathematically sound approaches.

            The bottom line is if you read literature on effect type-systems, I am sure you will find discussions of the differences. They boil down to this summary: For Church, meaning depends on type. To Curry, meaning doesn’t depend on the type. The gist of my point-of-view is, Why the unnecessary dependency? Do we really gain much from the extra machinery? Can we do just as good without it? Can we plug in different type systems, and allow types to be optional, etc? Here is my unsubstantiated claim: I think the Curry-style effect system is better for distribution, since I believe it can more easily model the famous CAP Theorem and let programmers not just transparently distribute, but rather declaratively make trade-offs using the CAP Theorem as a model. I think this is going to be crucial going forward. Implicit in your comments above is that programming difficulty is stationary and we just have to catch up. No. Programming will only get harder as system’s get bigger. We’re on a treadmill that is moving faster than we are. And it hurts falling off those things.

            As for Alan Kay, it took a lot of balls for me personally to write to the FONC mailing list for the first time and kind of call him out. I don’t know if he likes my moxie or not, but I think we have a lot in common. Whatever I can learn from him is great. He didn’t educate me on the differences between effect systems, though. He has provided more general reading material; what he gives me is Perspective. I don’t know why more people don’t try talking to him. He’s simply brilliant. I think it is because his brilliance is deceptive and it is easy to underestimate him.

            Cheers,
            Z-Bo

        2. Yes, learning the tribal dialect is crucial to communication. Especially knowing the right informal catch-phrases that describe a situation. No dictionary defines these – you need to hang out long enough in a subculture to learn their dialect before you can talk with them. And you can’t reasonably expect them to learn your private dialect.

          I guess you would call my effects Curry-style, as I don’t have a type system, just an effect system. It came as a surprise to me, as I expected to need types, but as I formalized the system I found they were unnecessary.

          I don’t understand Filinski’s work, but I really haven’t tried, as my eyes glaze over at the mention of monads. They really ought to be called gonads, because they seem to be mostly an intellectual dominance display. Too bad there aren’t many females who are impressed. Anyway monads are a way of encoding sequential imperative programming, so I don’t much care anyway, as I want to go beyond that.

          1. Well,

            If you are creating an effect system, you should definitely read the Disciplined Disciple Compiler – Haskell Ph.D. thesis. It is the most comprehensive coverage of effect systms anywhere. There is some more recent stuff, but the guy — Ben Lippmeier — really did an amazing job. I doubt your eyes will glaze over. If they do, for shame. 😉

            As for Filinski’s work, it is more abstract than programming language design. He is kind of more concerned with what things mean rather than how to execute them. A distinguishing characteristic worth noting when criticizing him.

          2. Thanks, I haven’t run into Lippmeier’s work before – I’ll check it out. BTW, I didn’t mean to criticize Filinski. I just get really turned off by the highly abstract theory coming out of the FP community. I get the feeling that they don’t share, much less understand the concerns of working programmers, so I lose interest. Backus’ 78 Turing Award lecture on FP was what originally inspired me to do programming language research. I just haven’t found much in common with them since.

  4. The Scala people are doing some work on multi-core advances to Scala and there is this GridGain which allows easy programming of multi-machine systems. The guy in charge of GridGain came to Hong Kong and did a demo for us at the Java user group, its an easy way to scale out a programming problem to n computers. You can write a single program in one window and it has functions which are executed on multiple computers. Also not related to GridGain, you can do transactional object properties in Scala.

    “The other critical step is to formulate a compelling example problem.” – I think you need multiple simple examples and a simple implementation library that other people can use as well so people can adopt it easily. Ideally in Scala (hint hint, please!).

    Apart from this, I really see Coherence and Subtext as very useful but not fully implemented, even if they are not perfect systems it shouldn’t matter. Perfect systems don’t necessarily get adopted, simple systems which make peoples life easier and are easy to adopt are taken up by people more quickly.
    Excel wasn’t a perfect system, it was adopted. I’m sure lots of people made more perfect spreadsheets before Excel and they were not adopted.

    Also I think that your trying to make programming easier, but I think you should re-state the problem as trying to be a God. Sadly, God is a very overloaded term, I mean we are Gods of the binary realm but we use tools and methods which do not fit at all with what a God would use. I think you need to adjust you imagination to see yourself as a God, then to try to work out what would a God use to create things, to create software or to adjust data in a world.
    Make different assumptions, assume the computer you are working on is infinite in computing power and memory, assume your visual display takes up all of your retina. What would you want? You would want the powers of a God, to be able to time travel backwards and forwards, to have all data treated to be able to be treated equally, like numbers are treated equally. Then similar operations can be applied to all data no matter what the data is, just like in maths.

    So the problem isn’t defined as how do you program a computer better, but how could a God use a system that a God would want, what would that system be like?

    1. Thanks for your advice Phillip. I think I agree with your God metaphor. I see it as trying to imagine what programming will be like in 50 years. At that point, all of our hardware and software technology will be pitifully primitive and irrelevant. So we need to discard all our assumptions that are based on compatibility and performance considerations. I have found that when you look very carefully, almost EVERYTHING about programming is dictated by compatibility and performance. In fact most people act as if those are the only important issues.

      So what can we possibly say about programming in 50 years? We know the speed of light isn’t going to change. We know human nature and intelligence aren’t going to change. Perhaps surprisingly, I think that tells us a lot. That might be worth a separate post.

  5. I second the recommendation of Lippmeier’s thesis. He also wrote a bit about his ideas on his blog (also recommended) while writing the thesis.

  6. I look forward to seeing some details on ‘flux’.

    I’ve also been pursuing distributed programming, but my more recent designs make it explicit in the semantics. That is, you can build a program as if it were running on multiple systems, then run it on a single system, but not vice versa. In E (erights.org) this property is called ‘semi-transparent’.

    The distribution problem is bigger than performance and security (though those are big, too). A few more issues include disruption, partitioning, discovery, extension, flash crowds, scalability, quality of service, synchronization, garbage collection, and keeping behavior of the system predictable. I’ll be interested in hearing how you tackle these problems.

Comments are closed.