Beta Reduce? What? Why? A Brief History
You might be wondering why I've decided to name my personal website
(blog, what-have-you) what I did. The reason is, and this is probably
not too surprising, because I'm a huge freaking nerd. This blog post
is both a quick overview of my history as a geek, and a justification
for why I named my personal website after an operation for
manipulating expressions in something called lambda calculus.
The Early Days
When I was a kid in grade school I loved math. Up until about grade 5
or so I would actually do exercises out of my assigned math books just for fun.
I nearly lost my mind when I learned my first “theorem”, and I was the only
kid in my class who knew more than two significant digits of pi. However due
to a combination of laziness and not really giving a shit, I was never picked
out for special placement or anything like that. Also, I probably just wasn't
bright enough. Anyhow, aside from doing the occasional algebraic simplification
just for fun, I was also somewhat interested in encryption. Not enough to
go off and teach myself boodles of number theory (that would come later), but
I did toss together the occasional Caesar cypher. Lastly I was also interested
in technology - pretty much all of it. I didn't have an interest in computers
specifically until I was in my. teens, but when I was younger I used to tinker
around with gears and pulleys and stuff, and also dick around with electricity.
I loved batteries.
All this is just to add some weight when I say: I was a dweeb. Never anti-social,
but I had a keen interest in science and technology. One time I asked my grade 7
teacher, jokingly, where I could find some plutonium (I had just read a book on
nuclear energy). If this were today, I'd have been kicked out of school.
Securing A Future Through One-up-manship, and Buring My Eyes Out
In high-school I began to take in interest in computing. I was connected to the
Internet for the first time, and many late nights of Starcraft and MSN were
had. I never really used the computer for anything other than a consumption
device, until I met some jerk in the grade above me. This jerk had just taken
a computer programming class and was boasting about how awesome he was because
he could create scrolling messages in HTML. I wasn't impressed, but it gave me
some kind of uncontrollable urge to become better than him in every way at
programming. Probably because a) he was a jerk, and b) he was so proud of his
crappy little website. By the time I was able to take the class I had taught
myself all of the material and then some. The course covered basic web design,
which I destroyed him at, and also an introduction to DOS programming with
QBASIC. My final project was a Pac-Man clone with decent-ish enemy AI. I barely
knew what a sub-routine was. Flash forward through a course the year later that
covered Visual Basic and a self-administered course on C, C++, PHP and Perl, and
I thought I was hot shit. With nothing else to fall back on (here's that
laziness again) I applied for Computer Science at my local university. I was
rejected. So I went back, drank a lot of coffee, raised my calculus grade from
barely a 50 to a 95, and applied again. This time I was met with success.
I went through my first year without incident, and by this time programming was
my life. I programmed for school, I programmed for fun, I programmed for money.
Then came the eye surgery. Part of being a dweeb is wearing glasses. I wore
glasses. By the end of my second year of university my eyes were stable enough
to make me a candidate for laser eye surgery. Of course I did it. However the
aftermath was that for pretty much the rest of the year my eyes were so dry that
I couldn't stand to even look at a computer screen for longer than 15 minutes.
Suddenly that theory course I had just taken started to look a lot more interesting.
If my programming days were limited, maybe I could be a bad-ass theoretician! From
my discovery of programming until about now I never really cared about math.
Why bother anymore? I had a new fun thing to do! But deep down inside I still
enjoyed mathematics, and it ended up saving me in the long run. With my new set
of dry-ass eyes and a rekindled love of symbol manipulation, I dove deep and
heavy into the theoretical underpinnings of computing and computation.
During this dive I came across something that completely blew me away. I was
reading up on the theory of computation and came across a little thing called
the Lambda Calculus. It's a formal system for representing mathematical
calculations in an entirely unambiguous way, and it's also expressive enough
to encode any calculation that a real computer can do. In essence, it's the
worlds simplest, purest programming language - one that you can do with a
pen and paper! I was in love. In the span of an afternoon I was able to
combine together my love of computers and programming with my previous love
of mathematics. Also my eyes weren't as dry anymore, so I could program again!
Things were really coming up daises.
Lambda calculus is a very simple system (it uses “calculus” in the real sense,
that it it's a system for performing calculations, so don't think rates of
change, or finance): Expressions are either simple variables, like x; lambda
expressions such as (lambda (x) t), where t is just another expression; or
applications, such as (t a), that is, evaluate the expression t with variable a.
I'm obviously glossing over a lot of details, but imagine we have an expression
that looks something like
where the expression
(+ x 1) just adds 1 to whatever value we bind to x. We
then apply it to other expressions like so
The result of the above computation is the number 5. Things can get even
crazier when you start binding lambda expressions to variables of other
lambda expressions and so on
(lambda (f) ((lambda (x) (f (x x))) (lambda (f) (lambda (x) (f (x x))))))
The whole idea of reducing an expression by one step is called Beta-reduction
in the literature. And that's where this blog gets its name. By the way, the
above equations are actually programs written in a language called scheme. It is
a member of the Lisp family, and it is beautiful.
It was a long story, but the short of it is: everyday geek grows up, trades his
love of math and science for computing (probably due to being a lazy git), only
to rediscover it (and bridge the two) in an unexpected way. Nowadays I'm a
PhD student working in the area of knowledge representation and reasoning,
and I get my fill of math and programming every day.
Stay in school kids.