Sunday, November 27, 2011

Abstract Algebra presented in a non-intimidating way (esp. for developers)

Hi.

I think math is really cool, but, most people (sadly) don't think so. This includes many programmers who in fact enjoy many of the same things that mathematicians do, but, are more practical for most of the time.

I'll show you why abstract algebra (in particular, group theory) is really cool, and why you don't have to be a freaking genius to get it.

Firstly, in order to understand most of this, you'll need to understand a tiny bit of Set theory, and to save time, I'll just refer you to wikipedia for that one (you just need to understand basic unions and intersections).

Let's begin with a simple definition, of a group (note: for hardcore types, this isn't fully rigorous because I haven't defined what an operation is, but, you get the idea).

A group is defined:

1)

A set (usually called $S$) with an operation attached (we call the operation $*$), so, if $G$ is a group,
$G = <S, *>$

2) Closure is one property that all groups must have in order for them to be a group. Closure means:

If $G = <S, *>$ and $x \epsilon S$ and $y \epsilon S$, then $x*y \epsilon S$

Note: $*$ does NOT NECESSARILY MEAN MULTIPLICATION!

3)

All groups have an identity element $e$, such that ( we are still considering the group $G$ with operation $*$):

For all $x \epsilon S$, $x*e = x$

4)

All elements in a group have an inverse,

If $a \epsilon S$, $a^{-1} \epsilon S$ such that:

$a * a^{-1} = e$

5)

The operation $*$ is associative. That means:

$(a*b)*c = a*(b*c)$

Alright, why in the world would anyone in their right mind define something like that?!

Let's take a step back, and understand where this comes from.

Around the 19th century or so, people realized that elementary algebra wasn't the only type of algebra that existed. There were all kinds of other algebras, like matrix algebra, and vector algebra and boolean algebra, and all these new all these new kinds of algebras kept cropping up with all these new rules (like, matrix multplication isn't commutative, that means: $A*B$ is not necessarily equal to $B*A$ when $B$ and $A$ are matrices) because mathematicians now had to solve all kinds of new problems.

And, the problem was, mathematics was losing its "connectivity", all these new algebras had little to no connection to each other, and it was very difficult to make progress in a few of these algebras at once.

Then, there was a clever idea. All of these algebras still were only doing a few operations on a set (or crossproducts of sets) and then were equating those operations on sets. That's how abstract algebra came along. Mathematicians realized that they could define "algebraic structures" (i.e. define algebraic systems so they followed a few axioms), and prove things about those algebraic structures, and any algebra that was then invented that could be proven to fit that algebraic structure would automatically have all the properties that people had proved about those structures!

Basically, if you came up with a new algebra, called "Cheese Algebra" and it has all these funny rules, but, it handles only one operation and you can prove that Cheese Algebra has all the properties of a Group, you're done! That means that all the things people have proven for Groups are automatically true for Cheese Algebra!

Isn't that awesome?

Let's try it.

The definition of a group is pretty simple, but, there are a few catches. First and foremost, the $*$ operation is not multiplication. Read the sentence over again. And again.

Secondly, in a group $a*b$ is not necessarily equal to $b*a$. Groups in which this is true are called Abelian groups and they make your life much easier, but, not all groups are like that.

Then, there are some basic theorems about groups that can be proven, and these are some important ones:

  • A group has a single, unique identity element
  • Every element of a group has a single, unique inverse
  • $(a_1*a_2*a_3* ... * a_n)^ {-1} = (a_n^{-1} * a_{n-1}^{-1} * a_{n-2}^{-1} * ... * a_1^{-1})$
  • $(a^{-1})^{-1} = a$
Let's prove a couple of them.

The first one is pretty easy, we assume there are two identities, $e_1$ and $e_2$ for a group $G = <S, *>$ and this would mean,

$e_1*e_2 = e_1$ (consider $e_2$ as the identity element)
$e_1*e_2 = e_2$ (consider $e_1$ as the identity element)

Which means $e_1=e_2$, which is a contradiction.

The second one is really similar, so, I won't go into the details.

The third one is a bit different, you first prove $(a*b)^-1 = b^{-1} * a^{-1}$ and then use the associative property of groups.

Okay, so, what does this mean?

Well, each of these properties hold for every algebraic system that's a group!

So, for example, matrices (the ones that do have inverses) form a group under the operation of multiplication, so, we've figured out a bunch of cool properties about matrices, like

The inverse of the inverse of a matrix is the matrix itself.

And, we haven't dealt with a single $a_ij$ component (although we would in proving that "inverseable" matrices do indeed form a group under multiplication)!

Also, the real numbers (excluding zero) form a group under multiplication, so, we can say this, too,

The reciprocal of the recipocral of a real number is the real number itself.

And, vectors form a group under addition (this one's really easy to prove, I suggest you try with the axioms given, hint: the identity is the vector <0,0,0>), too:

If you negate the negative of a vector, you get the vector itself.

Notice that the inverse operations change with each of them, but, the idea is still the same, so, with the single idea of a group, we've solved problems in a bunch of different areas of mathematics.

Let's try something a bit more complex, let's solve an equation on a group. What does that mean? Well, we can't use our knowledge of existing algebra, we can only use the axioms about groups, and the things we proved from them in order to solve the equation.

Now, I'll show you the equation, but, try solving it first if you can before looking at the solution, it'll give you a different kind of appreciation for the solution.

Solve the equation $a*x*b = c$ for $x$ in terms of $a, b, c$, which are constants.




Solution
=======
Multiply both sides by $b^{-1}$,

$a*x*b*b^{-1} = c*b^{-1}$

Since $b*b^{-1} = e$,

$a*x*e = c*b^{-1}$

Since, $a*x*e = (a*x)*e = a*x$,

$a*x = c*b^{-1}$

Now, since each element of the group has a unique inverse, we can take the inverse of both sides of the equation, and the equation will still hold true:

$(a*x)^-1 = (c*b^{-1})^{-1}$

Which is the same as:

$x^{-1}*a^{-1} = b*c^{-1}$

Multiply both sides by $a$,

$x^{-1} = b*c^{-1}*a$

Take the inverse of both sides again, and notcie $(a^{-1})^{-1}$,

$x = a^{-1}*c*b^{-1}$

Yay!

Now, what's (again) really cool, is that this works for every, single freaking algebraic system that you can think of that's a group. Matrices with multiplication? Done. Real numbers with multiplication (aside from 0)? Done. Vectors with addition? Done.

Abstract algebra doesn't stop there, it defines all these structures that have similar properties like Rings and Fields that you can use to prove things in a bunch of different algebras in one fell swoop.

I hope you liked this article, and I'd love your feedback, email me at dhaivatpandya at g mail dot com, or comment below :)

EDIT: I forgot to mention some applications to CS.

Alright, you guys know how Haskell?

Haskell (and any ML-type language, really) uses something known as Algebraic data types, which basically let you specify datatypes that follow certain axioms, in a way.

Even though it is completely your responsibility to make sure that these structures form some kind of helpful algebra, the relation is still there.

And, about classes in OOP languages, there's a very close correlation.

You can very nearly think of classes as a algebraic structure that have many operations (methods) and elements (fields, variables, etc.), but, this isn't a perfect correlation because of many things that OOP languages let you do that are functionally "impure", and mathematics is a completely pure functional language (which is why it maps to Haskell so nicely), there is no state.

Friday, November 25, 2011

Node.js is pretty awesome

This'll be a small post, so, yeah.

I first started event-based loops with Twisted (http://twistedmatrix.com/trac/), and I had absolutely NO idea what I was doing.

I was doing all kinds of nonsensical things (I still have my code), like trying to read user input from stdin with raw_input() in a callback function. I slowly got better, and gradually learned more about what types of functions blocked, etc. etc. But, that took a while. And, if I needed to write production-ready code straight off the bat, I wouldn't have been able to do it (i.e. I would have written the code, it just would really, really suck).

Then, I tried out eventmachine and libeio, and they were all pretty similar, and I still had to be pretty careful about what type of code I was writing (one has to think less and less about this type of stuff the more you do it), and it wasn't really flowing.

Then, I found out about node.js.

Unlike a lot of people, I wasn't drooling over it or anything, mostly because it uses Javascript, and I didn't really think that moving Javascript over to the server side would help any. This conclusion was mostly rooted from the fact that I always troubled myself with writing cross-browser JS, and that's a painful task. But, with node, that disappears. There's only V8, to hell with all the other parsers and compilers that developers have come up with.

Javascript, if written for only one interpreter/compiler, is pretty usuable, and actually pretty fun. The prototype object system stops getting in the way, because you're provided with Object.create() which IE ... let's not talk about IE :)

The point with node is, its really, really hard to write completely blocking code, because javascript doesn't have anything like File IO that blocks with which you can shoot yourself in the foot!

The things I could write in a short amount of time literally skyrocketed, because I didn't have to worry so much about putting the wrong call in the wrong place, and could just concentrate on getting the application logic down.

There are, however, a few cinches that you have to deal with. Firstly, there's no tail call optimization in v8, even though it has been requested (http://code.google.com/p/v8/issues/detail?id=457). This is mostly because of some stupid things done in the spec, but, Node would be a lot better for me if this request was fulfilled. Secondly, if you are a server-side developer, getting used to JS will be pretty ... different, that's not really bad, but, it might slow you down.

So, all in all, I highly recommend you check out Node.js, and try writing something simple (like a chatroom or something).

Feedback welcome.

Saturday, November 19, 2011

PHP sucks (but, some frameworks don't)

I started web development with PHP, and I've decided I've had enough. Why? Keep reading.


PHP (the language) sucks. There, I said it. 



  • 1029380128301928301823 Globals
  • Object system hacked on
  • C extension system sucks
  • Documentation sucks (read more; no, I'm not drunk)
  • Has a terrible community
  • All in all, designed by total idiots. 

You've probably heard this a ton of times before, but, here it is again. THERE ARE JUST WAY TOO MANY GLOBALS. Why in the world does md5() need to be global? Do you seriously use md5() in every single file?


This is also a common occurrence, why on the planet are things like the order of  haystack and needle the same everywhere? Is it really that hard to do?

All in all, the language lacks continuity; it lacks grace. It doesn't have any precise definitions for anything, there are always exceptions (a bit like the English language), unlike something like Python, which tries its best to be properly defined and easy to relay to someone. In my eyes, if a language has a simple grammar, but, it is still powerful enough for use, I consider it excellent (Lisp/Clojure comes to mind).

The Object System. Everyone's probably saying, "Hey! Its just like Java, what's wrong with it?!". Firstly, Java isn't the all-glorious object system everyone wants. Secondly, atleast most libraries and APIs in Java are based around objects and classes, whereas for PHP, its just a few bajillion globals, with classes if anyone wants to use them (which new programmers conveniently ignore because they can, and it leads to projects with a few hundred functions, and no classes and everything held together with <?require's and <?include's and global mutable state).

Another horrific massacre is the C extension system for PHP. If you haven't tried (I have), don't do it, you'll regret it in your later years when macros will show up as nightmares. It shows you that the interpreter is this humongous blob of macros, held together by large if-else statements and switch'es, and it also tells you that you have to deal with this if you want to get any work done with the so-called "API". And, there's all this stuff that's dependent on Zend, and if they change their mind about something in the API, it all comes crashing down on you. Almost NOTHING is optimized. The things that have been optimized turn out to be this convoluted mess of unnecessary variables and unused heap space.

Documentation. Everyone seems to be telling me that the documentation for PHP is absolutely wonderful. When I type in "php mysql" into google, I get http://php.net/manual/en/book.mysql.php. Which would be all fine and dandy if I was a new web developer that just needed to get my darn code to connect to mysql, but, dig deeper and you'll find out that this actually references the dangerous "mysql_" set of functions, which should have never been invented, and everyone should have been using PDO instead. Of course, the documentation doesn't tell me ANY of this, and just tells me how to install it, and how to go about making dangerous commands to MySQL. And, the comments on the documentation contain possibly the worst code that has ever put foot on planet earth, and newbies (especially on #php on Freenode) use them quite freely and get very confused and disappointed when their website gets hacked, or the code refuses to work when another user is running, etc.

The community is also terrible. Every time I try to tell someone that they should maybe put the cryptographic functions in their own class, they (basically) accuse me of heresy and remind me what the Spanish Inquisition did to heretics. The community loves newbies, definitely, but, the people who aren't experts with PHP end up giving really bad advice (like not using PDO because its too complicated for small projects), and the ignorance just keeps spreading.

If you look at the interpreter code, it'll be quite obvious why I say my last bullet point. The lexing code has a ton of repeated rules, crap that's never actually used in the parse tree and even more inconsistencies that are defaulted, and, whenever an elegant solution is possible the code is instead splattered with regular expressions. The parser gets even worse in this regard, with part of the lexing done in the parser.


Now, here's another statement I'm making about PHP.

(some of) PHP's frameworks and their developers are excellent.


A good example is Kohana (http://kohanaframework.org/). This framework is well thought out, expressive, and easy to use. Takes a couple of hours to learn and gives you full MVC out of the box, with database connectivity and everything. The developers really know what they're doing, and they try to make sure that Kohana is top quality code and stays well maintained. These developers have climbed the difficult hills of PHP with all its intricacies, and have come out victorious and you can see that in their code.

But, that still doesn't cut it for me.

Its a bit like trying to build the Eiffel Tower on top of a wooden log house. Yes, the eiffel tower is a great feat of engineering, but, its built on a log house, you can't expect it to be too stable. That's the case here, Kohana is AWESOME, but, its built on PHP, and I'd still be much more productive in Python or Ruby or maybe even Perl!

What's the alternative?

I highly suggest Python and Flask (http://flask.pocoo.org/) as an excellent combination for beginners, and Django for more experienced Python developers.

There are also many other options, such as Ruby on Rails (I like this too, but, the lack of documentation sort of makes it difficult for me), Node.JS, Web::Simple (for Perl, not too popular, but excellent, IMO), etc. etc.


Stay away from PHP if you're a freelancer if $10/hr seems bad


Because PHP has such a low barrier for entry, there are hordes of terrible developers that are up for hire on websites such as freelancer.com, and others. They sink to bottom prices, deliver terrible quality work, and there's thousands of them.

There's this funny story that I usually use to give an example. Before I realized I wouldn't make any money, I used to be quite active on freelancer.com, usually bidding on PHP projects. For one such project (it basically consisted of writing PHP for a AJAX app that needed to continuously poll), I bid $\$150$ (which is quite low for all the code I had to write, about $\$15$/hr), and there was another man (who had not-so-good ratings), who said he would do it for $\$40$. I warned the employer that he would not do the job properly, and you'd have to hire someone for a rewrite of the code, but, he (obviously) disregarded my arguments, and hired the $\$40$ guy. And, what happened? The $\$40$ guy procrastinated and delayed, wrote a bunch of crap code that basically checked the server every 10 seconds for this static file, which he modified with this Perl script that he set up a cronjob for, and it was overall a terrible hackjob. After 2 weeks, the employer had to hire again (he did hire me this time around).

Because of these types of scenarios, its very difficult to do well as a freelancer in PHP, IMHO.

So, I'm moving away from PHP to greener pastures, and I hopefully won't have to come back.

Wednesday, November 2, 2011

Encryption/Ciphers Part 3 - Knapsack Cryptosystem (a)

Encryption/Ciphers Part 3 - Knapsack Cryptosystem (a)

Hi everyone. As always, if you haven't done so, I highly recommend atleast skimming through the last two articles, as I use terminology from them in this article. And, I'll be adding more posts about the encryption series, so, if you would like to keep updated, I would suggest you follow this blog.

Also, the Knapsack Cryptosystem will be broken into two parts, one that describes the Knapsack problem and the next that shows Knapsack cryptography.

Also, I made a mistake last time (which, unfortunately, no one noticed early enough), I forgot to do a push on the github repo, so the Vigenere code was not up, well, now it is.

So, lets get started.

The Knapsack Cryptosystem was invented in the late 70's, and now has been broken, but, it still is an awesome introduction to public key cryptography, and is quite a bit more elegant than RSA, which involves a lot more complicated math.

So far, we've talked about a monoalphabetic cipher (the Caesar Cipher), and a polyalphabetic cipher, which both require one piece of information to encrypt and decrypt. Now, we will consider a new type of cryptography, known as a public key cryptosystem. The most simple (in my opinion) example of this type of system is known as the Knapsack Cryptosystem, or Backpack Cryptosystem, or Volumes Cryptosystem, you'll see why these why all these names mean the same thing in just a minute.

Firstly, what's a public key cryptosystem? Well, in such a system, there is not just one piece of information needed to encrypt and decrypt (the shift index in the Caesar Cipher or the passphrase in the Vigenere cihper), there are two things needed, one key to encrypt the plaintext, and another to decrypt the ciphertext. Usually, the two keys are called public keys and private keys. Every recipient in the system has a public key that everyone knows about (including possible attackers), but, messages encrypted with that public key can only be decrypted with the recipient's personal private key, which is kept secret from everyone.

That concept is sometimes hard to bend your mind around, and there's no better way to understand it than an example given by Wikipedia (http://en.wikipedia.org/wiki/Public-key_cryptography), so, I'll just quote it:

"An analogy to public-key encryption is that of a locked mailbox with a mail slot. The mail slot is exposed and accessible to the public; its location (the street address) is in essence the public key. Anyone knowing the street address can go to the door and drop a written message through the slot; however, only the person who possesses the key can open the mailbox and read the message."

Notice I said usually a lot for the definition of public key cryptosystems, because there are other uses known as digital signatures, which aren't the focus of this article (but, maybe later on).

So, getting more particular, what's a Knapsack cryposystem? Well, firstly, we'll look at the Knapsack problem.

Say you have Knapsack (or backpack, or bag, or whatever the heck you call it in your country) of volume $V$, and you have $n$ items of various volumes $a_1, a_2, a_3 ... a_n$, using none or multiple of each of these items, is it possible to completely fill the Knapsack?

Lets make an equation out of that:

$V = a_1x_1 + a_2x_2 + a_3x_3 ... a_nx_n$

This problem, when given $V$ and $\{a_1, a_2, ... , a_n\}$, may have none, one or many solutions. Finding a solution to an arbitrary Knapsack problem is extremely difficult, in fact, all the approaches currently available (more on this later) are not very far from just using bruteforce to try out all $2^n$ combinations. That makes it an ideal candidate to base an encryption system on.

But, due to reasons that you'll find out about, if the equation has multiple solutions, it doesn't work for public key cryptography. So, when does it have a unique solution (if any at all)?

Lets call a sequence of $a_i$ "superincreasing" when each $a_i$ is larger than the sum of all the preceding ones; that is,

$a_i > a_1 + a_2 + a_3 + ... a_{i-1}$

If the $a_i$ are superincreasing, the Knapsack problem has a unique solution (again, if any). Let's look at an example to see why this is true:

Say we have the equation

$11 = 2x_1 + 3x_2+6x_3+13x_4$

Since $13>11$, $x_4 = 0$. So,

$11 = 2x_1 + 3x_2 + 6x_3$

$2+3<6$, so, we must include atleast one item of volume $6$, so $x_3 = 1$.

$5 = 2x_1 + 3x_2$

Again, we operate the same way, noting $2<3$, and then getting $x_1 = 1, x_2 = 1$.

And, we've solved it! A proof of why all Knapsack problems containing $a_i$ that are superincreasing is not difficult to formulate, and I encourage you to try it yourself (consider it an excercise, if you'd like). Also, the Knapsack problem is an excellent introduction to dynamic programming (that's how I learned DP), and, if you care about such things, I would check this out: http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf

I'll be posting the next part of the Knapsack cryposystem blog in a day or two. I split it into two parts because the Knapsack problem and the cryptosystem both together are at on of material to have to digest so quickly.

As always, feedback extremely welcome, and thanks for the upvotes, Redditors. If you would like to keep updated with this series, I highly encourage you to follow this blog.