Pages

24 October 2010

Error Message Pun

This came up in conversation:

void monopoly() {
    goto jail;
    int go = 0;
jail:
    return;
}

int main() { monopoly(); }

In GCC, it produces the error:

monopoly.cpp: In function `void monopoly()':
monopoly.cpp:4: error: jump to label `jail'
monopoly.cpp:2: error:   from here
monopoly.cpp:3: error:   crosses initialization of `int go'

Haw haw haw I'm done. A more substantial post is coming soon. Hope you had a good weekend.

20 October 2010

BarCamp Rochester

So somebody on campus decided a couple of weeks ago that it'd be a good idea to organise a BarCamp here in Rochester this coming weekend. I thoroughly approve of the BarCamp philosophy, and saw this as a great excuse to yammer about Prog for a while to a group of people who might be interested and understand anything I say. Heady stuff.

Anyway, I've been putting together a presentation on the current state of programming languages, their future, and Prog's particular approach to bridging the gap. Prog is thoroughly under-documented and constantly undergoing minor revisions as I work on it, but now that I'm forcing myself to speak about it cohesively, I've been forced to cohere many of my thoughts. In order to help myself get these ideas down, and in order to ensure that they're recorded in full in case my public speaking skills fail me, here's basically what I'll be talking about on Saturday.

There's not a lot of disagreement in the major points of where programming languages are headed:

  • Functional Programming (or something like it)
  • Concurrency that doesn't make your head cave in
  • Static Typing to structure development
  • Type Inference to eliminate potential boilerplate from static typing
  • Generic Programming for modularity and clarity

Functional programming is associated with declarative rather than imperative style, the importance of data flow over control flow, immutability of data rather than mutable state, referential transparency of functions, and, as a result of all of these, strong support for concurrency. Unfortunately, FP has consistently been seen as something of an academic, ivory-tower pursuit, despite its obvious utility and even ubiquity. In most functional languages, it's no more awkward to manage state and exceptions than in most imperative languages; the difference is how relevant state is to program flow and correctness. Consequently, FP is seen as having a high barrier to entry because it feels very alien to CS students who, these days, are all spoon-fed Java. Peh.

Prog draws a few important concepts from functional programming:

  • All types are immutable by default
  • Pure, constant functions can be evaluated statically
  • Operations and algorithms are more important than objects.

Now, about concurrency. It's become obvious to everybody and their aunt that concurrent programming is where it's at, or at least, where it will be. Processors have increasingly many cores, and distributed, high-volume systems are commonplace even now. There are a few approaches to concurrent programming, and the one most likely to fail is of course the object-oriented one. I don't mean to be too harsh on OO (at least, not right now), but there's wide agreement that explicit threading and locking in a system designed around mutable objects is difficult. And programmers will eventually give up technologies and philosophies that get in the way of their ability to get stuff done.

The alternatives, though, are promising. The Actor model is a sound mathematical model of concurrent computation that allows, among other things, formal proofs of program correctness (or, more accurately, the absence of program incorrectness) in concurrent systems. Implicit parallelisation is commonplace in languages without mutable state such as Haskell, and even explicit threading is becoming more lightweight and manageable in languages such as Go.

The main problem with concurrency, I think, has been that it's easy to understand but hard to implement, and difficult to verify when trying to account for edge cases, especially in systems based on state. And for ages people have been complaining that immutability makes concurrency easy but mutability is nice and natural for a vast number of applications. What we're seeing, then, is a disparity between the needs of programmers and the hardware they're working with. And hardware insists on going in a difficult direction.

So how does Prog handle concurrency? Well, as in Haskell, unrelated and pure operations can be implicitly parallelised, and the type system provides the required granularity: spawning too many small threads is inefficient in terms of thread-creation overhead, but spawning too few large threads is inefficient in terms of lost parallelisation opportunities. Explicit threading in Prog is still cheap because it's simply a hook into the type system to encourage (but not require) automatic parallelisation.

Further, Prog has intrinsic support for software transactional memory (STM) using so-called atomic regions, which, again, imbue a scope with type information that causes all operations, and the group of operations as a whole, to become atomic (which, for mutable objects, means implicit locking).

In Prog, values have the inherent capability of receiving and acting upon messages; this is simply inversion of control between a function and its arguments. So while in some sense Prog is like Ruby, where “everything is an object”, it is also like lambda calculus, where “everything is a function”. In Prog there is little to distinguish values from functions, just as there is little to distinguish values from types or even metatypes.

So communication between threads is handled using this messaging facility, and a call from one thread to a function in another behaves identically to a thread-local call. Immutable data are shared implicitly, while mutable data are shared explicitly but locked implicitly.

Now, about static typing. A static type system significantly simplifies the processes of static correctness analysis, improves maintainability by localising changes and making errors detectable at compile-time, and creates some measure of assurance of consistent program behaviour. When safety constraints are known and enforcible at compile-time via the type system, the theoretical correctness and consistency of a program becomes much more trustworthy. In addition, purely static typing implies a certain degree of runtime performance improvement over purely dynamic typing.

Prog's type system is static and strictly enforced. A single variant type provides a consistent interface for both dynamic typing and generic programming. As previously stated, all types are immutable unless explicitly qualified as mutable. Types and values are indistinguisable, and static assertions based on type inference are the basis of correctness in generic programming. An expression can be imbued with a context type, which may improve the performance of or otherwise affect its evaluation. As a result of context-selection, unlike in many other languages, Prog functions can be overloaded on return type alone.

Type inference is an absolute necessity in a statically typed system. For one thing, it reduces boilerplate (e.g., C++0x lets you type auto when you don't feel like typing std::list<std::map<std::string, int>>::const_iterator), but it's also essential in generic programming to be able to perform known operations on values of unknown type. Type inference is closely related to overloading: a good example of this is to be found in C++, where function template parameters can be inferred from function arguments. Ideally, type inference does away with needless casting, making necessary casts stand out as hazardous or incorrect. It improves syntactical clarity, and naturally becomes generic programming.

Prog's type inference capabilities are numerous. First, objects are implicitly declared upon their first use, and imbued with the type of their initialiser. Overloading occurs both statically and dynamically, entirely depending on the types that are actually used. Any necessary casts are carried out using explicit, loud, scary, easy-to-find casting operators, and otherwise the syntax is completely freed from any mention of typing where it's not needed. And the type system comes to our aid once more, and ensures that immutability guarantees static evaluation: if an expression is constant, it's statically evaluable; if the type of an expression is constant, it's statically inferable.

Now, here comes the good stuff. I could ramble about generic programming all day. The most common exposure to generic programming that people have in the OO world is templates (or “generics” if you're from that camp). But if you haven't read the work of Alexander Stepanov, you simply must. Generic programming is not just about generic types, but also about generic algorithms and the abstract properties of data structures, most importantly their complexity requirements and guarantees.

Generic programming at its best relies heavily on the iterator model, but Prog generalises this to include ranges as well, which are, at their heart, syntactic sugar for iterators. Prog provides the external constraints that make generic programming possible via the type system. Generic algorithms in Prog can simply accept variant instances and rely on the type system to handle static versus dynamic evaluation, mutability guarantees, and so on. Explicit static assertions verify preconditions and postconditions and protect invariants. Algorithms are thus exposed as cleanly as possible, complexity guarantees are in some cases statically verifiable, and the Prog type system makes all of this super-easy.

As an example, here's a naive C++ implementation of max:

template<class T>
const T& max(const T& a, const T& b) {
  return b < a ? a : b;
}

template<class T>
T& max(T& a, T& b) {
  return b < a ? a : b;
}

This returns the maximum of two values, and is overloaded to accept either constant or non-constant values, such that it can be used as either an rvalue or an lvalue. The Prog equivalent does not require such explicit differentiation, though for strict equivalence with the above it does require a static check that the two values are of the same type:

def max(a : any&, b : any&) : any& {
  assert @a == @b;
  b < a ? a : b
};

Here's another short example of how software transactional memory is expected to work:

def transfer(a : mutable Account&, b : mutable Account&,
    x : int) : bool {

    atomic {
        a.withdraw(x);
        b.deposit(x);
    } except prog::atomic_abort {
        return false;
    };
    return true;

};

And at this point the talk will degenerate in to Q-and-A, but this is a blog, so I guess I'm done rambling. It's not as though I have a massive amount of readership anyhow.

03 October 2010

A Walk in the Woods

When I need to get some really good thinking done, I've learned that there's nothing better for me than to relax and avoid thinking at all for a while. My brain is so glad for the brief holiday that it returns to work with renewed vigour, and accomplishes things as though it was working diligently the whole time I wasn't communicating with it.

There are few places where I can really get into this state—the shower is one that I have in common with many others, but a shower can reasonably be only so long for a number of reasons. Another good place is graveyards: the dead tend to be pretty accommodating hosts when it comes to quiet thinkers.

But I think the best place for me is the woods. Going for a long walk in the woods, trying in vain to confound my irritatingly accurate sense of direction, and getting some exercise are all great things, but they're even better when I get to go for a walk with the deer.

Yes, you read that right. The area around RIT is swarming with deer. On a recent late-night walk, I saw no fewer than a dozen by the side of the road, and that's no exaggeration. So it came as little surprise to me this evening when I ran into a couple of does in the forest.

Now, RIT deer are fairly docile. You'll never get them to eat out of your hand, but they won't spook if you're reasonably nice to them. Usually announcing your presence in a soothing voice and talking to them occasionally is enough to dispel their fears and let you get as close as five feet from them. One was still young and the other fully grown, and the fawn was noticeably more skittish than the adult, so kept her distance more.

I was able to walk with them for quite some time before they decided it'd be a good idea to cross a stream, and, clad in sneakers as I was, I wasn't prepared to slog through ankle-deep mud and knee-deep water. So I made my way through the dry part of the swamp to a hillock where I read Dracula and watched the sunset.

Why am I telling you all of this? What does this have to do with programming or linguistics? Not much, really, but it is kinda nice, and people like stuff like that. And anyway, it got me thinking about the universality of expression, which is something we humans seem to not just take for granted, but often entirely ignore. An animal can understand your intent and your emotions even if it can't grasp the meaning behind what you're saying. Hell, a human can, too; we're not immune. Tone of voice and body language are enormously important, and yet we seem to always get lost in the intricacies of verbalisation.

We should probably just relax and eat some acorns.