Beta Reduce? What? Why? A Brief History

Introduction

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.

Revelation

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

(lambda (x) (+ x 1))

where the expression (+ x 1) just adds 1 to whatever value we bind to x. We then apply it to other expressions like so

((lambda (x) (+ x 1)) 4)

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.

… Okay

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.

 
comments powered by Disqus