pathological programming
goodmath | August 11, 2006Todays tasty treat: a variable-free nearly-pure functional programming language: Unlambda.
Unlambda is based on the SKI combinator calculus. The [SKI calculus][ski] is a way of writing lambda calculus without variables, and without lambda. It's based on three combinators: S, K, and I:
1. S = λ x y z . x z (y z)
2. K = λ x y . x
3. I = λ x . x
Given only S and K, you can actually write *any* lambda calculus expression - and therefore, you can write any computable function using nothing but S and K. I is often added for convenience; it's just a shorthand for "SKK".
You can do recursion in SKI…
goodmath | August 4, 2006Today's treat: [Thue][thue], pronounced two-ay, after a mathematician named Axel Thue.
Thue is a language based on [semi-Thue][semi-thue] grammars. semi-Thue grammars are equivalent to Chosmky-0 grammars, except that they're even more confusing: a semi-Thue grammar doesn't distinguish between terminal and non-terminal symbols. (Since Chomsky-0 is equivalent to a turing machine, we know that Thue is turing complete.) The basic idea of it is that a program is a set of rewrite rules that tell you how to convert one string into another. The language itself is incredibly simple; programs written…
goodmath | July 28, 2006I was hoping for a bit of a vanity post for todays pathological programming language in honor of my 40th birthday (tomorrow), but I didn't have time to finish implementing my own little piece of insanity. So it'll have to wait for some other occasion.
Todays pathological programming language is a really simple monstrosity called ["Whenever"][whenever]. Whenever is a programming language where programs get executed in *random* order, and there are *no* variables. The only state, the only way of manipulating information in a Whenever program is by manipulating the collection of executable…
goodmath | July 21, 2006 Today, we're going to take a look at a brilliant language called Befunge. Befunge is the work of an evil genius named Chris Pressey.
Normal programming languages are based on a basically one-dimensional syntax; the program is a string, a sequence of characters, and it's processed by reading that string in a straight-ahead fashion. But that's not Befunge! Befunge is something like a two-dimensional turing machine: it says that the program and data are written on a two dimensionaltorus. Each instruction in Befunge is a single character, and where it's located on the torus is crucial. (In…
goodmath | July 14, 2006In real life, I'm not a mathematician; I'm a computer scientist. Still a math geek, mind you, but what I really do is very much in the realm of applied math, researching how to build systems to help people program.
One of my pathological obsessions is programming languages. Since I first got exposed to TRS-80 Model 1 BASIC back in middle school, I've been absolutely nuts programming languages. Last time I counted, I'd learned about 130 different languages; and I've picked up more since then. I've written programs most of them. Like I said, I'm nuts.
Anyway, I decided that it would be amusing…