Archive for January, 2007

Milliways and the equivalence of programming languages

Friday, January 26th, 2007

It’s been known since the time of Turing that what’s computable in one reasonably powerful programming language is computable in every other one. As a result, we can say that large classes of programming languages are ‘equivalent’ in the sense that they can emulate each other. However, not all programming languages have natural equivalents of all the others’ features.

This is the idea behind Greenspun’s Tenth Rule:

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

The usual corollary is “including Common Lisp”. We could say the same for C: most C compilers are implemented in C and compile themselves. Similarly, the Glasgow Haskell Compiler is written (mostly) in Haskell. Actually, given that C is the implementation language for so many interpreters, it’s easy to see that one could, in principle, write a program in language X by directly creating the abstract syntax tree and passing it to an “evaluate” function, all in C.


(more…)

Posted in code, computing, Haskell, TCS, thinking aloud | No Comments »

QOTD VII

Monday, January 15th, 2007

Found on Wikiquote:

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.

— Brian Kernighan

Posted in computing, funny, QOTD | No Comments »

The essence of functional programming

Friday, January 5th, 2007

Here’s an interesting toy language/Turing tarpit for you: Lazy K.


You may already have seen Unlambda, which is essentially the lambda calculus in programming langauge form. (Actually, as its name suggests, it doesn’t actually have any lambdas – it’s really based on the equivalent SKI combinator calculus.) However, Unlambda is a horrible dirty – ahem, I mean impure functional language because 1) it isn’t lazy and so programs in it can sometimes gratuitously fail to terminate, and 2) it has an exception to the evaluation rules (the d ‘function’) and side effects (the .x function prints the character x). Also, in Unlambda version 1 there is no way to do input.


Lazy K is no easier to write programs in than Unlambda (that’s hardly the point, is it? :). But it solves all these problems: it is lazily evaluated; there are no side effects; and you can do input.


(more…)

Posted in computing, TCS, thinking aloud | No Comments »