Wednesday, February 22, 2006

 

It's been a while...

But when you've been having as much fun as we have, why blog? The move in early December went well, but we're still not settled in. There are many (more) boxes to unpack, and small jobs to do around the house. It's been hard to find the time inbetween all of the BBQ's that we've enjoyed! More seriously, I've been pondering and reconsidering a lot of the assumptions that I've taken for granted in computing. It's a long story, and I'll eventually get around to writing about it here, but it all started with questioning whether stack-based architecture were really that good. I have written about this before, but I've taken a bit more time to try and think about the issues. In many ways I've come full circle: C is a direct descendant of CPL (which begat BCPL, which begat B, which begat C), and there are clear links between BCPL and the denotational semantics of Strachey. The big innovation of C is that pointers are first-class object in the language, and that almost everything in C can be referenced by a pointer, including functions. Functions in C are not themselves first-class entities. This constrasts with some functional languages (e.g. Scheme), where functions are first-class. A quick spin through SICP has whet my appetite for learning more about functional programming languages. A really important innovation in Scheme was the handling of continuations, in effect, giving the programmer direct control over the branching constructs of the language. Syntactically rich languages (C, Python, Java etc...) just do not allow a programmer to (easily) invent new control constructs, and this can restrict the paradigms that can be expressed in the code. (I refuse to consider cpp macro hacks as being easy). Steele demonstrated with the RABBIT compiler that alternative control mechanisms (continuation passing style) are not just feasible, but that they can be preferable. This leads to Monads, which are another approach to achieving modularity (and that I don't yet fully understand!).

At this point you're most probably wondering how all of this relates to stack-based virtual machines. The amazing thing is that there are some quite deep connections to all of this material. Fundamentally, both of the stack- and register-based virtual machines can provide an intermediate representation of a program inside a compiler, and it is important to be able to reason about the transformations that a compiler makes to ensure program correctness. From the Church-Turing thesis we know that the lambda calculus is a somewhat clumsy but sufficient intermediate representation. So when an alternative intermediate representation is proposed (e.g. a stack machine) a reasonable question to ask is whether it has the same expressive power as the lambda calculus, and if not, to clarify what the limitations of the alternative representation are. So at the base of everything we have the lambda calculus, which directly influences functional programming. To overcome the low-level nature of the lambda calculus many different mathematical models of semantics have been developed, and much of the thinking about semantics has had a direct influence on the programming languages that we use today. For instance, assertions in program code can be attributed to Tony Hoare through his invention of triples (precondition/statement/postcondition) for reasoning about programs. I'll try and write a little bit about these topics (and more!) in the coming weeks. There is some really great stuff to talk about.

Finally, you'd better be quick if you want the gh.erk.in domain name - the ast.oni.sh domain has already been registered...


This page is powered by Blogger. Isn't yours?