Friday, January 3, 2014

How functional programming has motivated me to relearn math

Ok, I will admit it.  The first thing that attracted me to learning a lisp dialect was the coolness factor.  There's a saying about being a Smug Lisp Weenie.  To wit, we have this chart that I first saw several years ago:
http://lukewelling.com/wp-content/uploads/2006/08/programmer%20hierarchy.pdf

Actually, this chart was made by someone who only works with "pure" software programmers.  Whomever made this chart must have never run into the HDL (eg Verilog or VHDL) guys, as they would most prominently have been at the top.  Nevertheless the point is well made that other programmers feel that Lisp programmers feel they are superior to everybody.  Just read some of the reviews on Amazon.come for the classic SICP book by Abelson and Sussman and see how some people feel about lisp (or scheme) programmers.

I felt like there must be something about Lisp to inspire such a love/hate dichotomy.  For those who hated it, was it just a case of sour grapes?  Those who couldn't "get" lisp simply derided it as a defense mechanism?  My first experience with lisp was...well, confusing.  We had to do a little bit of lisp programming at my university's Artificial Intelligence class.  To say I had no clue how lisp worked was an understatement.  I mean 'car' and 'cdr'?

Regardless, a few years later (ca 2010), there was this new language Clojure that everyone was talking about.  I also recall reading around that time this hilarious article http://www.secretgeek.net/lisp_truth.asp.  I remember busting out laughing over and over, even though I hadn't yet grokked any lisp dialect.  Surely, a language that could inspire a page as funny as that had to have something go for it.  Not to mention that lisp is the 2nd oldest continuing language around.  So I decided to dip my toes into the Clojure waters and see what all the fuss was about.

It was hard.  Real hard.  I mean, how can you have a language without assignment?  Without for loops?  Where there isn't even technically a variable (as the oxymoron "constant variable" would surely indicate)?  It quite literally took me months to wrap my head around this bizarre concept.  To be honest, I think a good deal of the difficulty of the language wasn't so much around the "lispiness", it was was around the functional aspects.  Lisp and Scheme aren't pure functional languages (technically, neither is Clojure, but it is moreso than either Lisp or Scheme as all data is immutable and most sequences are lazy).  The idea that lisp is stupid because of all the parenthesis is....well stupid.  In fact, it's what makes lisps so beautiful and magical.  Lisps are already almost in their raw abstract syntax tree.  There's also very little syntax required to learn.

But what does all this have to do with math?  Functional programs are very closely related to the idea of mathematical functions.  The Fortran and Algol descended languages have at their core the idea of a Von Neumann machine.  The language they model closely resembles the hardware it runs on.  This imperative approach of modifying registers or memory is basically what Turing machines are about.  If i ever make gobs of money, I will try to buy an old lisp machine.

But I digress.  Lisp was really designed as a symbolic evaluator, and rather than follow the Turing/Von Neumann model of computation, it took the lambda calculus as derived from Alonzo Church as its basis for computation.  Although turing machines and lambda calculus are functionally equivalent (they have the same computational power), their expressiveness is worlds apart. 

I recently tried looking at some papers and books on denotational semantics and the lambda calculus, and I realized just how much math I have forgotten.  So, as bathroom reading material (yeah yeah...too much info), I have my old discrete math and formal languages and automata theory books that I can peruse.  I'm amazed how much I have forgotten.  Things like modular arithmetic, bijections, counting (set theory), equivalence relations and so on.

This is the heart of computation.  While most software engineers are content with learning the new fad of the year (hmmm, hadoop seems popular now, or maybe I better learn objective-c so I can write a bright and shiny iPhone app), I am more fascinated by the foundation of computation itself.  But it's also hard.  In all honesty, learning some new library is really not that hard.  What interests me more than programming with hadoop...is the science behind hadoop itself.

And it all starts with math, and lots of it.  It's not easy.  I remember Discrete Math to be insanely hard.  I had to retake linear algebra and abstract algebra.  Automata Theory wasn't a walk in the park either.  And learning all this math helps a software engineer design better algorithms or come up with more novel ways to solve a problem.

Now that the holidays are over, I'm going to resume my data structures project, and maybe tinker around with some other CS fundamentals.