Tuesday, January 28, 2014

7 Ways to Learn a New Programming Language

1. Read a Book

This is perhaps the most traditional approach. You have to be careful with this one, because in programming things evolve very quickly. If you are looking for some good, up-to-date books on languages, I would suggest The Pragmatic Bookshelf.

2. Watch YouTube Videos and Follow Along

There are an insane amount of YouTube tutorials out there. My main difficulty with learning programming on YouTube has always been finding reliable teachers. I generally trust GoogleTechTalks and TheNewBoston as go-tos.

3. Start a New Project

Simply learn by doing! It is probably best to do this after you have had some form of a primer on the language. This is one of the most effective ways I have learned new languages. Just think about what you want to build, open google and stackoverflow (keep them handy for language-specific questions) and start coding away!

4. Complete Koans

Koans (path to enlightenment) are a superb way to gain some understanding about a new programming language. Usually test driven, they make you fix small "errors" in code files that emphasize some little feature of the language. Koans are generally incremental so by solving them, a broader understanding of the language is gained.

5. Practice with Cyber-Dojo

This is another tool that you may want to use after you have had some primer on the language you are trying to learn. Cyber-dojo is a cool tool for practicing TDD. It isolates programmers from bloated IDEs so that they can focus on problems, code and tests. Cyber-dojo values finding solutions over the actual solution itself. This makes it a great resource for learning a language, purely from a "writing and testing code" perspective.

6.  (If you like Math) Practice with Project Euler

If you can't come up with projects to work on, ProjectEuler presents some fun mathematical challenges that (should) grow harder as you progress through the list of problems. It's fun to develop a code-base around ProjectEuler solutions.

7. (If you like Biology) Practice with Rosalind

Like ProjectEuler, Rosalid is a collection of programming-esque problems. Unlike ProjectEuler, Rosalind problems are centered around Biology. Very cool, and fun.

Extra Tips

  • Some languages have online, interactive teaching tutorials which can be cool to check out.
  • If an language has an REPL, it can be helpful to play around in it or keep it open as you develop (so you can try code as you think of it). The instant feedback of a REPL is priceless in learning.

Controversial Programming Opinions I Agree With

I recently came across Bill the Lizard's blog post about controversial programming opinions. Shockingly, some of these really threw me off guard. Others, however, I kind of agree with. I'm fairly new to this development thing, but I would still like to take my chance to chime in on some of these "controversial" opinions that I fully agree with.

5. "Googling it" is okay!

So, there's been a lot of debate about whether google is helping or hindering us. One of my favorite articles about google's psychological affects argues that we are becoming reliant on google for "mindshare" (the process of delegating memory tasks to people around us). Some people are disturbed by the idea that google could be "replacing our memory" but I see it as a good thing, and here's why:
  • If we didn't have google to quickly retrieve information for us, we would have to use some other form of reference (dictionary, textbooks) which are expensive, are not always available, and have a longer look-up time. Or maybe we would just neglect to pursue correct information altogether (let's face it, we're pretty lazy).
  • Consider the quotes: "I never commit to memory anything that can easily be looked up in a book" and "Never memorize what you can look up in books." (Einstein) and ask yourself, "does this apply to the opinion 5?"
  • There is too much information to store it all in your mind. I mean, don't get me wrong, there are plenty of things we should know as citizens and craftsmen in general, however, computer science is growing by the second. We can't know it all. Personally, I'm thankful that google knows things that I don't.

6. Not all programmers are created equal.

The gist of this one says that it's wrong to think that the amount of experience a developer has will indicate how good of a developer he (or she) is. I think Coding Horror has a few important points to make about this when he writes about becoming a better programmer, without programming.

7. I fail to understand why people think that Java is absolutely the best “first” programming language to be taught in universities.

Here's why I agree with this one:
  • Although OOP is a good thing to teach, universities (perhaps unfortunately) have to cater to a variety of majors, not just computer science. OOP is not necessary for many engineering students (e.g. electrical engineers who program chips in C and Assembly).
  • Java is difficult to "ease into." Intro to programming classes are just that, an intro. They should illustrate basic concepts. Java has a lot of overhead. For example, in Java, the classic "Hello, World" program has overhead that teachers, upon first exposure to students, are forced to wave their hands at. Right off the bat students are told to "just ignore 80% of what they're typing, just to make the computer say hello." Whereas, in simple languages like Python and Ruby, "Hello, World" can be as simple as a print statement and a string, two simple intro concepts that are isolated and less distracting than embedded classes.
  • For more advanced classes, a language like Java may be appropriate; however, there is a lot of speculation going around that Java is on the decline in the industry. The point is, even if it is the current, best language to teach -- it won't always be. It will die.
  • Java is a great language for teaching OOP, I'll give it that. But it fails to illustrate certain, slightly advanced, fundamental programming concepts (that schools like to teach) like pointers, manual memory allocation, etc... So even for advanced classes it isn't capable of teaching some slightly more advanced concepts.
  • I am, personally, fine with schools using Java, it is a good language. The statement that "it is absolutely the best" is flawed in that, it's just one of many excellent programming languages. To anyone who thinks otherwise, I would highly suggest Guido's PyCon keynote in which he criticizes language holy wars and trolls.

9. It’s OK to write garbage code once in a while.

  • It's better to write quick garbage code that does the job and later refactor it than it is to be an Artist.
  • Proof of Concept (POC) code is just proving a point. It doesn't necessarily need to be later maintained, read or extended.
  • Writing crappy code is part of learning to write better code. Also, refactoring your bad code can help you learn how to refactor others' bad code.

18. If you’re a developer, you should be able to write code.

Assuming "developer" means "one who constructs software" it seems necessary to be able to "stack the legos." Similarly to you can't break an omelette without breaking some eggs, you can't construct software without writing some code.

There are the opinions I find myself pretty much for. Please feel free to disagree in comments and let my know what you think.

Tuesday, April 23, 2013

Determinant in Haskell

In linear algebra, the determinant is quite a useful operation that can be done on matrices. To further my understanding of Haskell, I decided to program a solver for systems of equations. One of the best ways to do this dynamically is through Cramer's Rule which needs to be able to calculate determinants. So, here's my recursive code for finding determinants:

determinant :: (Num a, Fractional a) => [[a]] -> a

determinant [[x]] = x
determinant mat =
 sum [(-1)^i*x*(determinant (getRest i mat)) | (i, x) <- zip [0..] (head mat)]


So, in this code, the base case is a 1x1 matrix. The getRest function simply returns the matrix without the head row (topmost) and without the \(i\)th column.

The code and tests are available on my github.

Wednesday, April 10, 2013

Creating a Sine Function in Haskell

Using Taylor Series derivation I found the following infinite sum expression for sin:
\[
  \sin \left(x \right) = \sum_{i = 1}^{\infty} \frac{x^{2 i - 1}}{\left( 2 i - 1 \right)!} \left( -1 \right)^{i - 1}
\]
The exact derivation is available as a PDF on github.

The translation of this sum into Haskell code was simple:

sin' :: (Num a, Fractional a) => a -> a
sin' x = sum [sinTerm x i | i <- [1..33]]


sinTerm :: (Num a, Fractional a) => a -> Integer -> a
sinTerm x i = (x^oddTerm / fromIntegral (factorial oddTerm))*(-1)^(i-1)
  where oddTerm = 2*i - 1


So, this code is pretty straight forward, if you wanted to get more accuracy on the results you could change "33" to be some greater value (33 says that we will sum up 33-1=32 terms of the taylor series).

Of course this code references factorial which is defined simply as:

factorial :: Integer -> Integer
factorial 1 = 1
factorial n = n * factorial (n-1)


As usual, code and tests are available on github.

Wednesday, March 27, 2013

Proof by Induction Example

Proof by induction is a powerful, accepted tool for producing not only mathematical proofs but also proofs of algorithms in computer science and other fields as well.

The concept of proof by induction, is generally described as being a three step process:
  1. Prove a base case (in many cases we call this \(P(1)\)).
  2. Assume that the \(k\)th case is true (we call this \(P(k)\)).
  3. Show that the \(k+1\)th case is true (we call this \(P(k+1)\)).
As can be seen \(P(1) \rightarrow P(2)\), since our base case has been established at \( P(1)\) and we have shown that for our \( k+1\)th case, when \( k = 1\) (i.e. \(P(2)\)) our proposition stands. This can be further extended to show that \( P(2) \rightarrow P(3) \rightarrow ... \rightarrow P(n)\).

So, in less-mathematical terms, proof by induction is as simple as proving some proposition is true for some starting value, and then verifying that it is true for the next one, and the next one, continuing on as far as it needs to or, in other words, to the \(n\)th value.

The following is a simple, somewhat standard example.

Problem

\( \forall n \in \mathbb{N} \), prove that: \[ \sum_{i = 1}^{n} i = \frac{n \left( n + 1 \right)}{2} \]

(This is saying that if we sum up all the numbers from one to \(n\), that sum should equivalently be calculable by \( \frac{n \left( n + 1 \right)}{2} \))

Proof

 Before we start the proof, it's useful to...
\[
  \text{let } P(n) =  \sum_{i = 1}^{n} i
\]

Now...

Proof by Induction

Step 1: Prove base-case, \( P(1) \):

So, the sum of all number from one to one is:
\[
  P(1) = \sum_{i = 1}^{1} i = 1
\]

Now we verify that our formula works for \( n = 1\):
\[
  \frac{n \left(n + 1 \right)}{2} = \frac{1 \left(1 + 1 \right)}{2} = \frac{2}{2} = 1
\]

It checks!

Step 2: Assume that \( P(k) \) is true:

So, here we are assuming that:
\[
  P(k) = \sum_{i = 1}^{k} i = 1 + 2 + 3 + ... + k = \frac{k \left( k + 1 \right)}{2}
\]

Step 3: Show that \( P(k+1) \) is consistent:

So, \( P(k+1) \) looks like, (replacing \(n\) with \( k + 1\)):
\[
  P(k+1) =  \sum_{i = 1}^{k+1} i = 1 + 2 + 3 + ... + k + (k + 1) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}
\]

Noticing that \( 1 + 2 + 3 + ... + k \) is the same as \( P(k) \) from Step 2:
\[
  \frac{k \left( k + 1 \right)}{2} + \left( k + 1 \right) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}
\]

Multiplying both sides by \(2\):
\[
   k \left( k + 1 \right) + 2\left( k + 1 \right) = \left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]
\]

Distribute \(k\) and \(2\) on the left, add the \(1\)s on the right:
\[
  k^2 + k + 2k + 2 = \left( k + 1 \right) \left( k + 2 \right)
\]

FOIL the right:
\[
  k^2 + k + 2k + 2 = k^2 + 2k + k + 2 \text{      $\square$}
\]

It's really as easy as that!

Simple Partial Differential Equations Example

I am really enjoying my current partial differential equations class, so I thought I'd share an example problem. Note that this is probably one of the simplest problems in partial DE.

Problem

\begin{equation}
  \text{(1)    } k^2 \frac{\partial^2 U}{\partial t^2} = \frac{\partial^2 U}{\partial x^2}
\end{equation}
\begin{equation}
  \text{(2)    } U \left( 0, t \right) = 0
\end{equation}
\begin{equation}
  \text{(3)    } U \left( L, t \right) = 0
\end{equation}
\begin{equation}
  \text{(4)    } U \left( x, 0 \right) = 0
\end{equation}
\begin{equation}
  \text{(5)    } \frac{\partial U}{\partial t} \left( x, 0 \right) = f \left( x \right)
\end{equation}

Solution


We are looking for a solution of the form:
\[
  U = XT
\]
Where \(X\) is a function of \(x\) and \(T\) is a function of \(t\).

Translating (1) to match the expected solution, we get:
\[
  k^2 XT^{\prime\prime} = X^{\prime\prime} T
\]

Dividing each side by \( XT \):
\[
  k^2 \frac{T^{\prime\prime}}{T} = \frac{X^{\prime\prime}}{X}
\]

Since we have a function of only \(T\) on the left and only \( X \) on the right, we know that these are equal to a constant.
\[
  k^2 \frac{T^{\prime\prime}}{T} = \frac{X^{\prime\prime}}{X} = constant = \left\{\begin{array}{lr}
  0 \\
  -\lambda^2 \\
  \lambda^2
\end{array}   \right.
\]

The notation above says that the constant can either be \(0\), some negative number (as forced to be negative by \( -\lambda^2 \)) or some positive number (forced by \( \lambda^2 \)).

Case \( constant = 0 \):

Finding \( X \):
\[
  \frac{X^{\prime\prime}}{X} = 0 \Rightarrow X^{\prime\prime} = 0
\]

Integrating both sides:
\[
  X^{\prime} = A
\]
Where \( A \) is an arbitrary constant.

Integrating again:
\[
  X = A x + B
\]
Where \( B \) is an arbitrary constant.

Finding \( T \):
\[
  \frac{k^2 T^{\prime\prime}}{T} = 0 \Rightarrow T^{\prime\prime} = 0
\]

Integrating both sides:
\[
  T^{\prime} = C
\]
Where \( C \) is an arbitrary constant.

Integrating again:
\[
  T = C t + D
\]
Where \( D \) is an arbitrary constant.

Since \( U = XT \):
\[
  U = \left(A x + B\right) \left( C t + D \right)
\]
Therefore, this satisfies (1).

Looking at (2), we have:
\[
  U \left( 0, t \right) = 0 \Rightarrow \left(A (0) + B\right) \left( C t + D \right) = 0 \Rightarrow B \left( C t + D \right)= 0
\]

This implies that \( B = 0 \), so:
\[
  U = A x \left( C t + D \right) = x \left( C t + D \right)
\]
satisfies (1) and (2); note that the constant \( A \) was absorbed into the other constants (since they are, after all, just arbitrary constants).

Looking at (3), we have:
\[
  U \left( L, t \right) = 0 \Rightarrow L \left( C t + D \right) = 0
\]

To make this true, we can't change the value of \( L \) because it is a constraint, so the only option is to make \( C = D = 0\).

So,
\[
  U = 0
\]
This, however, is an uninteresting solution for \( U \). So, we examine the next possible constant.

Case \( constant = -\lambda^2 \):

Finding \( X \):
\[
  \frac{X^{\prime\prime}}{X} = -\lambda^2
\]

Multiply both sides by \( X \):
\[
  X^{\prime\prime} = -\lambda^2 X
\]

Using methods from differential equations (DE), we know that we can solve this by subbing \( \alpha^2 \) in for \( X^{\prime\prime} \) and \( 1 \) in for \( X \):
\[
  \alpha^2 = -\lambda^2
\]

Taking the square root of both sides we get:
\[
  \alpha = \pm \lambda i
\]

From DE we know that this fits the form \(\alpha = b \pm c i \), where the answer the the DE is:
\[
  X = e^{bx} \left[ A \cos \left( c x \right) + B \sin \left( c x \right)\right]
\]
Where \(A\) and \(B\) are arbitrary constants.

Therefore:
\[
  X = e^{0x} \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right] = \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right]
\]

Finding \( T \):

\[
  k^2 \frac{T^{\prime\prime}}{T} = -\lambda^2
\]

Multiply both sides by \( \frac{T}{k^2} \):
\[
  T^{\prime\prime} = -\frac{\lambda^2}{k^2} T
\]

Using methods from differential equations (DE), we know that we can solve this by subbing \( \beta^2 \) in for \( T^{\prime\prime} \) and \( 1 \) in for \( T \):
\[
  \beta^2 = -\frac{\lambda^2}{k^2}
\]

Taking the square root of both sides we get:
\[
  \beta = \pm \frac{\lambda}{k} i
\]

From DE we know that this also fits the form \(\beta = b \pm c i \), where the answer the the DE is:
\[
  T = e^{bt} \left[ C \cos \left( c t \right) + D \sin \left( c t \right)\right]
\]
Where \(C\) and \(D\) are arbitrary constants (not necessarily the same as \(A\) and \( B \)).

Therefore:
\[
  T = e^{0t} \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]
\]

Since \( U = XT \):
\[
  U = \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right] \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]
\]
Therefore, this satisfies (1).

Looking at (2), we have:
\[
  U \left( 0, t \right) = 0 \Rightarrow \left[ A \cos \left( 0 \right) + B \sin \left( 0 \right)\right] \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0
\]

\(\cos \left( 0 \right) = 1\) and \( \sin \left( 0 \right) = 0\), so,
\[
  A \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0
\]

This implies that \( A = 0 \), so:
\[
  U = \sin \left( \lambda x \right) \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]
\]  
satisfies (1) and (2); note that the constant \( B \) was absorbed into the other constants (since they are, after all, just arbitrary constants).

Looking at (3), we have:
\[
  U \left( L, t \right) = 0 \Rightarrow \sin \left( \lambda L \right) \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0
\]

So, we need to pick a value for \( \lambda \) that causes the above expression to always be zero. We find that there are an infinite number of them (everywhere \( \sin \left( n \pi \right) \) where n is a natural number (better suited to match the solution than an integer). So, because of this, we find that:
\[
  \lambda = \frac{n \pi}{L},\, \forall n \in \mathbb{N}
\]

So, subbing in for \( \lambda \), we have:
\[
  U = \sin \left( \frac{n \pi x}{L} \right) \left[ C \cos \left( \frac{n \pi}{L k} t \right) + D \sin \left( \frac{n \pi}{L k} t \right)\right]
\]
Which satisfies (1), (2) and (3).

Looking at (4), we have:
\[
  U \left( x, 0 \right) = 0 \Rightarrow \sin \left( \frac{n \pi x}{L} \right) \left[ C \cos \left( 0 \right) + D \sin \left( 0 \right)\right] = 0
\]

\(\cos \left( 0 \right) = 1\) and \( \sin \left( 0 \right) = 0\), so,
\[
    U \left( x, 0 \right) = 0 \Rightarrow \sin \left( \frac{n \pi x}{L} \right) \left( C \right) = 0
\]

This implies that \( C = 0\), so,
\[
  U = \sin \left( \frac{n \pi x}{L} \right) \left( D \right) \sin \left( \frac{n \pi}{L k} t \right)
\]
Satisfies (1), (2), (3) and (4).

Since constraint (5) is non-zero, I will evaluate it lastly. For now, I claim that:
\[
  U = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \sin \left( \frac{n \pi}{L k} t \right)
\]
\( \forall n \in \mathbb{N}\), also satisfies (1), (2), (3), and (4). This claim is justified because, as show above, constraint (3) is satisfied for all values of \( n \). So, for whatever \( n \) I pick from the natural numbers (\( 1,2,3...\), \(\mathbb{N}\)) the resulting \( U \) will also be an answer. So, summing together the infinite answers for \( U \) still meets the problem's criteria. \( D \) became \( D_n \) because \( D \) is not necessarily the same thing for any \( n \) value.

So, considering constraint (5), we need to first find \( \frac{\partial U}{\partial t}\):
\[
  \frac{\partial U}{\partial t} = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right) \cos \left( \frac{n \pi}{L k} t \right)
\]

Looking at the actual constraint, (5):
\[
  \frac{\partial U}{\partial t} \left( x, 0 \right) = f \left( x \right) \Rightarrow \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right) \cos \left( 0 \right) = f \left( x \right)
\]

Since, \( \cos \left( 0 \right) = 1\):
\[
  f \left( x \right) = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right)
\]

By the Fourier sine series, we know that the coefficients are given by:
\[
  D_n \left( \frac{n \pi}{L k} \right) = \frac{2}{L} \int_0^L f \left( x \right) \sin \left( \frac{n \pi x}{L} \right) dx
\]
We include \( \left( \frac{n \pi}{L k} \right) \) because it does not match the Fourier series and needs to be divided out.

Solving for the actual coefficients:
\[
  D_n = \frac{2 k}{n \pi} \int_0^L f \left( x \right) \sin \left( \frac{n \pi x}{L} \right) dx
\]

Where our final \( U \) is, as above:
\[
  U = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \sin \left( \frac{n \pi}{L k} t \right)
\]

Now, we could go on to examine the \( constant = \lambda^2 \) case. However, it ends up just being \( 0 \) (and is therefore redundant). You can use methods like those above to come to this conclusion for yourself.

Thursday, March 21, 2013

Nieve Prime Finder in Haskell

To solve a cyber-dojo challenge (implement a function/method that returns the prime factors of a number) I decided to implement a somewhat nieve (but workable) isPrime function in Haskell. Here's the code:

-- Public type-definition
isPrime :: Integer -> Bool

-- Private type-definition
lookForPrimeFrom :: Integer -> Integer -> Bool

isPrime 2 = True
isPrime n
 | n < 2     = False
 | even n    = False
 | otherwise = lookForPrimeFrom n 5

lookForPrimeFrom n i
 | ceiling (sqrt (fromIntegral n))+1 < i   = True
 | (n `mod` i) == 0                        = False
 | otherwise                               = lookForPrimeFrom n (i+2)



This code (to me at least) seems very self-documenting. The more I'm playing around with Haskell, the more I'm enjoying it and seeing its strength as a functional language. I think if I were to map this algorithm into more mathematical notation it would look like:

\[
  \forall n \in \mathbb{N}
\]
\[
  p \left( n \right) = \left\{ \begin{array}{lr}
  0, & n = 1 \\
  1, & n = 2 \\
  0, & \text{$n$ is even} \\
  1, & \nexists m \in \left\{ x \in \mathbb{N} \, | \, 5 \leq x \leq{\sqrt{n}}, \text{$x$ is odd}  \right\}
  
\end{array} \right.
\]

As you can see, this is somewhat nieve; however, the Haskell code really is quite similar to the mathematical notation.