# Introduction

A while back I was researching the most efficient way to check if a number is prime. This lead me to find the following piece of code:

I was intrigued. While this might not be the most efficient way, it’s certainly one of the less obvious ones, so my curiosity kicked in. How on Earth could a match for the `.?|(..+?)\1+` regular expression tell that a number is not prime (once it’s converted to its unary representation)?

If you’re interested, read on, I’ll try to dissect this regular expression and explain what’s really going on. The explanation will be programming language agnostic, I will, however, provide `Python`, `JavaScript` and `Perl` versions of the `Java` code above and explain why they are slightly different.

I will explain how the regular expression `^.?\$|^(..+?)\1+\$` can filter out any prime numbers. Why this one and not `.?|(..+?)\1+` (the one used in `Java` code example above)? Well, this has to do with the way String.matches() works, which I’ll explain later.

While there are some blog posts on this topic, I found them to not go deep enough and give just a high level overview, not explaining some of the important details well enough. Here, I’ll try to lay it out with enough detail so that anyone can follow and understand. The goal is to make it simple to understand for any one - whether you are a regular expression guru or this is the first time you’ve heard about them, anyone should be able to follow along.

# 1. Prime Numbers and Regular Expressions - The Theory

Let’s start at a higher level. But wait, first, let’s get every one on the same page and begin with some definitions. If you know know what a prime number is and are familiar with regular expression, feel free to skip this section. I will try to explain how every bit of the regular expression works, so that even people who are new or unfamiliar with them can follow along.

## Prime Numbers

First, a prime number is any natural number greater than `1` that is only divisible by 1 and the number itself, without leaving a remainder. Here’s a list of the fist `8` prime numbers: `2, 3, 5, 7, 11, 13, 17, 19`. For example, `5` is prime because you can only divide it by `1 ` and `5` without leaving a remainder. Sure we can divide it by `2`, but that would leave a remainder of `1`, since `5` = `2`*`2` + `1`. The number `4`, on the other hand, is not prime, since we can divide it by `1`, `2` and `4` without leaving a remainder.

## Regular Expressions

Okay, now let’s get to the regular expression (A.K.A. regex) syntax. Now, there are quite a few regex flavors, I’m not going to focus on any specific one, since that is not the point of this post. The concepts described here work in a similar manner in all of the most common flavors, so don’t worry about it. If you want to learn more about regular expressions, check out Regular-Expressions.info, it’s a great resource to learn regex and later use it as a reference.

Here’s a cheatsheet with the concepts that will be needed for the explanation that follows:

• `^` - matches the position before the first character in the string
• `\$` - matches the position right after the last character in the string
• `.` - matches any character, except line break characters (for example, it does not match `\n`)
• `|` - matches everything that’s either to the left or the right of it. You can think of it as an or operator.
• `(` and `)` delimit a capturing group. By placing a part of a regular expression between parentheses, you’re grouping that part of the regular expression together. This allows you to apply quantifiers (like `+`) to the entire group or restrict alternation (i.e. “or”: `|`) to part of the regular expression. Besides that, parentheses also create a numbered capturing group, which you can refer to later with backreferences (more on that below)
• `\<number_here>` - backreferences match the same text as previously matched by a capturing group. The `<number_here>` is the group number (remember the discussion above? The one that says that parentheses create a numbered capturing group? That’s where it comes in). I’ll give an example to clarify things in a little bit, so if you’re confused, hang on!
• `+` - matches the preceding token (for example, it can be a character or a group of characters, if the preceding token is a capturing group) one or more times
• `*` - matches the preceding token zero or more times
• if `?` is used after `+` or `*` quantifiers, it makes that quantifier non-greedy (more on that below)

### Capturing Groups and Backreferences

As promised, let’s clarify how capturing groups and backreferences work together.

As I mentioned, parentheses create numbered capturing groups. What do I mean by that? Well, that means that when you use parentheses, you create a group that matches some characters and you can refer to those matched characters later on. The numbers are given to the groups in the order they appear in the regular expression, beginning with `1`. For example, let’s say you have the following regular expression: `^aa(bb)cc(dd)\$`. Note, that in this case, we have `2` groups. They are numbered as follows:

This means that we can refer to the characters matched by them later using backreferences. If we want to refer to what is matched by `(bb)`, we use `\1` (we use `1` because we’re referring to the capturing group #1). To refer to the characters matched by `(dd)` we use `\2`. Putting that together, the the regular expression `^aa(bb)cc(dd)\1\$` matches the string `aabbccddbb`. Note how we used `\1` to refer to the last `bb`. `\1` refers to what was matched by the group `(bb)`, which in this case, was the sting `bb`.

Now note that I emphasize on what was matched. I really mean the characters that were matched and not ones that can be matched. This means, that the regular expression `^aa(.+)cc(dd)\1\$` does match the sting `aaHELLOccddHELLO`, but does not match the sting `aaHELLOccddGOODBYE`, since it cannot find what was matched by the group #1 (in this case it’s the character sequence `HELLO`) after the character sequence `dd` (it finds `GOODBYE` there).

### Greedy and Non-Greedy Quantifiers

If you remember correctly, in the cheatseheet above, I mentioned that `?` can be used to make the preceding quantifier non-greedy. Well, okay, but what does that actually mean? `+` is greedy quantifier, this means that it will try to repeat the preceding token as many times as possible, i.e. it will try to consume as much input as it can. The same is true for the `*` quantifier.

For example, let’s say we have the string `<p>The Documentary</p> (2005)` and the regular expression `<.+>`. Now, you might think that it will match `<p>`, but that’s not true. The matched string will actually be `<p>The Documentary</p>`. Why is that? Well, that has to do with the fact mentioned above: the `+` will try to consume as much input as it can, so that means that it will not stop at the first `>`, but rather at the last one.

Now how do we go about making a quantifier non-greedy? Well, you might be already tired of hearing that (since I’ve already mentioned it twice), but in order to make a greedy quantifier non-greedy, you put a question mark (?) in front of it. It’s really as simple as that. In case you’re still confused, don’t worry, let’s see an example.

Suppose we have the same string: `<p>The Documentary</p> (2005)`, but this time, we only want to match what is between the first `<` and `>`. How would we go about that? Well, all we have to do is add `?` in front of the `+`. This will lead us to the `<.+?>` regex. “Uhhh, okay…”, you might wonder, “But what does that actually do?”. Well, it will make the `+` quantifier non-greedy. This means that it will make the quantifier consume as little input as possible. Well, in our case, the “as little as possible” is `<p>`, which is exactly what we want! To be precise, it will match both of the `p`’s: `<p>` and `</p>`, but we can easily get what we want by asking for the fist match (`<p>`).

### A Little Note On ^ and \$

Since we’re on it, I’ll take a moment to quickly explain what the `^` and `\$` actually do. If you remember correctly, `^` matches the position right before the first character in the string and `\$` matches the position right after the last character in the string. Note how in both of the regular expressions above (`<.+>` and `<.+?>`) we did not use them. What does that mean? Well, that means that the match does not have to begin at the start of the string and end at the end of the string. Taking the second, non-greedy, regex (`<.+?>`) and the sting `The Game - <p>The Documentary</p> (2005)`, we would still obtain our expected matches (`<p>` and `</p>`), since we’re not forcing it to begin at the beginning of the string and end at the end of the string.

# 2. The Regular Expression That Tells If A Number Is Prime

Phew, so we’re finally done with the theoretical introduction and now, since we’ve already have everything we need under the belt, we’re ready to dive into the analysis of how the `^.?\$|^(..+?)\1+\$` regular expression can match non-prime numbers (in their unary form).

You can ignore the `?` in the regular expression, it’s there for performance reasons (explained below) - it makes the `+` non-greedy. If it confuses you, just ignore it and consider that the regex is actually `^.?\$|^(..+)\1+\$`, it works as well, but it’s slower (with some exceptions, like when the number is prime, where the `?` makes no difference whatsoever). After explaining how this regular expression works, I’ll also explain what that `?` does there, you shouldn’t have any trouble understanding it after you understand the inner workings of this regex.

All of the discussion below assumes that we have the number represented in its unary form (or base-1, if you prefer). It doesn’t actually have to be represented as a sequence of `1`s, it can be a sequence of any characters that are matched by `.`. This means that `5` does not have to be represented as `11111`, it might as well be represented as `fffff` or `BBBBB`. As long as there are five characters, we’re good to go. Please note, that the characters have to be the same, no mixtures of characters are allowed, this means that we cannot represent `5` as `ffffB`, since here we have a mixture of two different characters.

## High Level Overview

Let’s begin with a high level overview and then dive into the details. Our `^.?\$|^(..+?)\1+\$` regular expression consists of two parts: `^.?\$` and `^(..+?)\1+\$`.

As a heads-up, I just want to say that I’m lying a little in the explanation in the paragraph about the `^(..+?)\1+\$` regex. The lie has to do with the order in which the regex engine checks for multiples, it actually starts with the highest number and goes to the lowest, and not how I explain it here. But feel free to ignore that distinction here, since the regular expression still matches the same thing, it just does it in more steps (so I’ll actually be explaining how `^.?\$|^(..+?)\1+?\$` works: notice the extra `?` after the `+`.

I’m doing this because I believe this explanation is less verbose and easier to understand. And don’t worry, I explain how I lied and reveal the shocking truth later on, so keep on reading. Well, maybe it’s not really that shocking, but I wanna keep you engaged, so I’ll stick to that naming.

The regex engine will first try to match `^.?\$`, then, if it fails, it will try to match `^(..+?)\1+\$`. Note that the number of characters matched corresponds to the matched number, i.e. if 3 characters are matched, that means that number `3` was matched, if 26 characters are matched, that means that the number `26` was matched.

`^.?\$` matches strings with zero or one characters (corresponds to the numbers `0` and `1`, respectively).

`^(..+?)\1+\$` first tries to match 2 characters (corresponds to the number 2), then 4 characters (corresponds to the number 4), then 6 characters, then 8 characters and so on. Basically it will try to match multiples of 2. If that fails, it will try to first match 3 characters (corresponds to the number 3), then 6 characters (corresponds to the number 6), then 9 characters, then 12 characters and so on. This means that it will try to match multiples of 3. If that fails, it proceeds to try match multiples of 4, then if that fails it will try to match multiples of 5 and so on, until the number whose multiple it tries to match is the length of the string (failure case) or there is a successful match (success case).

## Diving Deeper

Note, that both of parts of the regular expression begin with a `^` symbol and end with a `\$` symbol, this forces to what’s in between those symbols (`.?` in the first case and `(..+)\1+` in the second case) to start at the beginning of the string and end at the end of the string. In our case that string is the unary representation of the number. Both of the parts are separated separated by an alternation operator, this means that either only one of them will be matched or neither will. If the number is prime, a match will not occur. If the number is not prime a match will occur. To summarize, we concluded that:

• either `^.?\$` or `^(..+?)\1+\$` will be matched
• the match has to be on the whole string, i.e. start at the beginning of the string and end at the end of the string

Okay, but what does each one those parts matches? Keep in mind that if a match occurs, it means that the number is not prime.

### How The ^.?\$ Regular Expression Works

`^.?\$` will match 0 or 1 characters. This match will be successful if:

• the string contains only 1 character - this means that we’re dealing with number `1` and, by definition, `1` is not prime.
• the string contains 0 characters - this means that we’re dealing with number `0`, and `0` is certainly not prime, since we can divide `0` by anything we want, except for `0` itself, of course.

If we’re given the sting `1`, `^.?\$` will match it, since we have only one character in our string (`1`). The match will also occur if we provide an empty string, since, as explained before, `^.?\$` will match either an empty string (0 characters) or a string with only 1 character.

Okay, so far so so good, we certainly want our regex to recognize `0` and `1` as non-primes. But that’s not enough, since there are numbers other than `0` and `1` that are not prime. This is where the second part of the regular expression comes in.

### How The ^(..+?)\1+\$ Regular Expression Works

`^(..+?)\1+\$` will first try to match multiples of 2, then multiples of 3, then multiples of 4, then multiples 5, then multiples of 6 and so on, until the multiple of the number it tries to match is the length of the string or there is a successful match.

But how does it actually work? Well, let’s dissect it!

Let’s focus on the parentheses now, here we have `(..+?)` (remember, `?` just makes this expression non-greedy). Notice that we have a `+` here, which means “one or more of the preceding token”. This regex will first try to match `(..)` (2 characters), then `(...)` (3 characters), then `(....)` (4 characters), and so on, until the length of the string we’re matching against is reached or there is a successful match.

After matching for some number of characters (let’s call that number `x`, the regular expression will try to see if the string’s length is multiple of `x`. How does it do that? Well, there’s a backreference. This takes us to the second part of the regex: `\1+`. Now, as explained before this will try to repeat the match in capturing group #1 one or more times (actually it’s more “more or one times, I’m lying a little bit”) This means that first, it will try to match `x * 2` characters in the string, then `x * 3`, then `x * 4`, and so on. If it succeeds in any of those matches, it returns it (and this means that the number is not prime). If it fails (it will fail when `x * <number>` exceeds the length of the string we’re matching against), it will try the same thing, but with `x+1` characters, i.e, first `(x+1) * 2`, then `(x+1) * 3`, then `(x+1) * 4` and so on (because now the `\1+` backreference refers to `x+1` characters). If the number of characters matched by `(..+?)` reaches the length of the string we’re matching against, the regex matching process will stop and return a failure. If there is a successful match, it will be returned.

### Example Time

Now, I’ll sketch some examples to make sure you got everything. I will provide one example where a regular expression succeeds to match and one where it fails to match. Again, I’m lying in the order of sub-steps (the nested ones, i.e the ones that have a `.`, like `2.1`, `3.2`, etc), just a little.

As an example of where a match succeeds, let’s consider the string `111111`. The length of the string we’re matching against is `6`. Now, 6 is not a prime number, so we expect the regex to succeed with the match. Let’s see a sketch of how it will work:

1. It will try to match `^.?\$`. No luck. The left side of `|` returns a failure 2. It try to match `^(..+?)\1+\$` (the right side of `|`). It begins with `(..+?)` matching `11`:

• 2.1 The backreference `\1+` will try to match `11` twice (i.e `1111`). No luck.
• 2.2 The backreference `\1+` will try to match `11` trice (i.e `111111`). Success!. Right side of `|` returns success

Woah, that was fast! Since the right side of `|` succeeded, our regular expression succeeds with the match, which means our number is not prime.

As an example of where a match fails, let’s consider the string `11111`. The length of the string we’re matching against is `5`. Now, 5 is a prime number, so we expect the regex to fail to match anything. Let’s see a sketch of how it will work:

1. It will try to match `^.?\$`. No luck. The left side of `|` returns a failure 2. It try to match `^(..+?)\1+\$` (the right side of `|`). It begins with `(..+?)` matching `11`:

• 2.1 The backreference `\1+` will try to match `11` twice (i.e `1111`). No luck.
• 2.2 The backreference `\1+` will try to match `11` trice (i.e `111111`). No luck. Length of string exceeded (6 > 5). Backreference returns a failure.

3. `(..+?)` now matches `111`:

• 3.1 The backreference `\1+` will try to match `111` twice (i.e `111111`). No luck. Length of string exceeded (6 > 5). Backreference returns a failure.

4. `(..+?)` now matches `1111`:

• 4.1 The backreference `\1+` will try to match `1111` twice (i.e `11111111`). No luck. Length of string exceeded (8 > 5). Backreference returns a failure.

5. `(..+?)` now matches `11111`:

• 5.1 The backreference `\1+` will try to match `11111` twice (i.e `1111111111`). No luck. Length of string exceeded (10 > 5). Backreference returns a failure.

5. `(..+?)` will try to match `1111111`. No luck. Length of string exceeded (6 > 5). `(..+?)` returns a failure. The right side of `|` returns a failure

Now since both sides of `|` failed to match anything, the regular expression fails to match anything, which means our number is prime.

Well, I mentioned that you can ignore the `?` symbol in the regular expression, since it’s there only for performance reasons, and that’s true, but there is no need to keep its purpose a mystery, so I’ll explain what it actually does there.

As mentioned before, `?` makes the preceding `+` non-greedy. What does it mean in practice? Let’s say our string is `111111111111111` (corresponds to the number 15). Let’s call `L` the length of the string. In our case, `L=15`.

With the `?` present there, `+` will try to match its preceding token (in this case `.`) as few times as possible. This means that first `(..+?)` will try to match `..`, then `...`, then `....` and then `.....`, after which our whole regex (`^.?\$|^(..+?)\1+\$`) would succeed. So first, we’ll be testing the divisibility by 2, then by 3, then by 4 and then by 5, after which we would have a match. Notice that the number of steps in `(..+?)` was 4 (first it matches 2, then 3, then 4 and then 5).

If we omitted the `?`, i.e if we had `(..+)`, then it would go the other way around: first it would try to match `...............` (the number 15, which is our `L`), then `..............` (the number 14, i.e `L-1`), and so on until `.....`, after which the whole regex would succeed. Notice that even though the result was the same as in `(..+?)`, in `(..+)` the number of steps was 11 instead of 4. By definition, any divisor of L must be no greater than L/2, so that means that means that 8 steps were absolutely wasted computation, since first we tested the divisibility by 15, then 14, then 13, and so on until 5 (we could only hope for a match from number 7 and downwards, since `L/2 = 15/2 = 7.5` and the first integer smaller than `7.5` is `7`).

## The Shocking Lie

As I mentioned before, I actually lied in the explanation of how the multiples of a number are matched. Let’s say we have the string `111111111111111` (number 15).

The way I explained it before was that the regular expression would begin to test for divisibility by `2`. It would do so by first trying to match `2*2` characters, then `2*3`, then `2*4`, then `2*5`, then `2*6`, then `2*7`, after which it would fail to match `2*8`, so it would try its luck with testing for divisibility by `3`, by first trying to match for `3*2` characters, then for `3*3` characters, then for `3*4` and then for `3*5`, where it would succeed. This is actually what would happen if the regular expression was `^.?\$|^(..+?)\1+?\$` (notice the `?` at the end), i.e., if the `+`following the backreference was non-greedy.

What actually happens is the opposite. It would still try to test for the divisibility by `2`, first, but instead of trying to match for `2*2` characters, it would begin with trying to match for `2*7`, then for `2*6`, then for `2*5`, then for `2*4`, then for `2*3` and then for `2*2`, after which it would fail and, once again, try its luck with divisibility by `3`, by first trying to match for `3*5` characters, where it would succeed right away.

Notice, that in the second case, which is what happens in reality, less steps are required: 11 in the first case vs 7 in the second (in reality, both of the cases would require more steps than presented here, the goal of this explanation is not count them all, but to transmit the idea of what’s happening in both cases, it’s just a sketch of what’s going on under the hood). While both versions are equivalent, the one explained in this blog post, is more efficient.

# 3. The Java Case

Here’s the piece of Java code that started all of this:

If you remember correctly, I said that due to the peculiarities of the way String.matches works in Java, the regular expression that matches non-prime numbers is not the one in the code example above (`.?|(..+?)\1+`), but it’s actually `^.?\$|^(..+?)\1+\$`. Why? Well, turns out `String.matches()` matches on the whole string, not on any substring of the string. Basically, it “automatically inserts” all of the `^` and `\$` present in the regex I explained in this post.

If you’re looking for a way not to force the match on the whole string in Java, you can use Pattern, Matcher and Matcher.find() method.

Other than that, it’s pretty much self explanatory: if the match succeeds, then the number is not prime. In case of a successful match, `String.matches()` returns `true` (number is not prime), otherwise, it return `false` (number is prime), so to obtain the desired functionality we negate what the method returns.

`new String(new char[n])` returns a `String`of `n` null characters (the `.` in our regex matches them).

# 4. Code Examples

Now, as promised, it’s time for some code examples!

## Java

Although I already presented this code example twice in this post, I’ll do it here again, just to keep it organized.

## Python

I’ve expressed my sympathy for Python before, so of course I have to include this one here.

## JavaScript

Java is to JavaScript as car is to carpet.

That’s a joke I like. I didn’t come up with it and I don’t really know its first source, so I don’t know whom to credit. Anyways, I’m actually going to give you two versions here, one which works in ES6 and one that works in previous versions.

First, the ECMAScript 6 version:

The feature that’s only available in ECMAScript 6 is the String.prototype.repeat() method.

If you gotta use previous versions of ES, you can always fall back to Array.prototype.join(). Note, however, that we’re passing `n+1` to `join()`, since it actually places those characters in between array elements. So if we have, let’s say, `10` array elements, there are only `9` “in-betweens”. Here’s the version that will work in versions prior to ECMAScript 6:

## Perl

Last, but not least, it’s time for Perl. I’m including this here because the regular expression we’ve been exploring in this blog post has been popularized by Perl. I’m talking about the one-liner `perl -wle 'print "Prime" if (1 x shift) !~ /^1?\$|^(11+?)\1+\$/' <number>` (replace `<number>` with an actual number).

Also, since I haven’t played around with Perl before, this seemed like a good opportunity to do so. So here we go:

Since Perl isn’t the most popular language right now, it might happen that you’re not familiar with its syntax. Now, I’ve had about 15 mins with it, so I’m pretty much an expert, so I’ll take the liberty to briefly explain the syntax above:

• `sub` - defines a new subroutine (function)
• `\$_[0]` - we’re accessing the first parameter passed in to our subroutine
• `1x<number>` - here we’re using the repetition operator `x`, this will basically repeat the number `1` `<number>` of times and return the result as a string. This is similar to what `'1'*<number>` would do in Python or `'1'.repeat(<number>)` in JavaScript.
• `=~` is the match test operator, it will return true if the regular expression (its right-hand side) has a match on the string (its left-hand side).
• `!` is the negation operator

I included this brief explanation, because, I myself, don’t like being left in mystery about what a certain passage of code does and the explanation didn’t take up much space anyways.

# Conclusion

That’s all folks! Hopefully, you’re now demystified about how a regular expression can check if a number is prime. Keep in mind, that this is far from efficient, there are a lot more efficient algorithms for this task, but it is, nonetheless, a fun and interesting thing.

I encourage you to go to a website like regex101 and play around, specially if you’re still not 100% clear about how everything explained here works. One of the cool things about this website is that it includes an explanation of the regular expression (column on the right), as well as the number of steps the regex engine had to make (rectangle right above the modifiers box) - it’s a good way to see the performance differences (through the number of steps taken) in the greedy and non-greedy cases.

If you have any questions or suggestions, feel free to post them in the comment section below or get in touch with me via a different medium.

EDIT:

• Thanks to joshuamy for pointing out a typo in Perl code
• Thanks to Keen for pointing out a typo in the post
• Thanks to Russel for submitting a Swift 2 code example
• I didn’t want to get into the topic of regular/non-regular languages and related, since it’s theory that isn’t crucial for the topic of this post, but as lanzaa pointed out, there is a difference between “regex” and “regular expression”. What was covered in this blog post wasn’t a regular expression, but rather a regex. In the “real world”, however (outside of academia), those terms are used interchangeably

# Introduction

My first encounter with Python was a part of the introductory course to programming. Well, I actually played with it on my own before, so I already was familiar with its syntax when the course began, but I didn’t do any real project in it before that course. Even though I thought it’s a great language to introduce people to programming, I wasn’t a big fan of it. It’s not that I disliked the language, it was more of a “meh” attitude. The reason was simple: there was “too much magic”. Coming from a background of languages such as C an Java, which are a lot more explicit in terms of what’s going on under the hood, Python was the complete opposite of that.

Another issue was that Python seemed a lot less structured: writing large, complex programs seemed to be a tougher task to achieve than, for example in Java, where you have some strict rules when it comes to the structure of the program (for instance the one public class per file rule), Python on the other hand, gives you a lot more freedom in such things.

Another thing is strict typing and debugging: since Python is an interpreted language, finding bugs wasn’t as easy: if you have a syntax error in C, the program will simply not compile, on the other hand, in interpreted languages, the problem might go unnoticed for quite some time, until the execution reaches that particular line of code. Trying to pass a string where an integer is expected? `cc` will go crazy at you, while Python’s interpreter won’t mind at all (there are some tool that address that problem though, like mypy, but I’m talking about vanilla Python). What I just mentioned here is a general downside of interpreted languages and are not exclusive or particular to Python, but those were some of the main reasons of my initial attitude towards it.

One more thing that I found a little annoying is the required indentation. Our teachers (that were great, by the way!) sold that as being a “good thing”, since “it forced us to a cleaner code writing style”. And that is true, but it was a bit annoying, when your code doesn’t work as expected, you analyze the code trying to hunt the bug and can’t seem to find it, until after some time you notice that one of the lines in your `if` statement has an extra space.

I had a discussion with a colleague about Python, telling him how I’m not sure why I wasn’t a huge fan of the language before, he asked me with a laughing tone “What’s not to like about Python? The fact that it reads almost like English?”. The answer to that question is “yes”. Since the language does so many things for you under the hood, sometimes it’s not clear what’s happening. Let’s take as an example file reading. Suppose you want to read the contents of a file and print them out, line by line. Here’s how you could do it in C:

Now the same thing in Python:

Now, many people will consider that as an advantage, however, while in the first case it’s pretty clear what’s happening:

1. We obtain a file pointer to a file
2. Read the bytes from each line into a buffer, and then print that line from that same buffer
3. Close the stream

In the Python’s example none of that is obvious, it just sort of “magically” works. Now, while one might argue that it’s a good thing, since it abstracts the programmer away from the implementation details (and I agree with that), I like to know exactly what’s happening.

It’s interesting that many of the things that I mentioned as disadvantages, I now consider advantages. To be fair, there is no “magic” in Python, if you dive in a little deeper, you’ll find out that there is no actual magic involved, it’s just the way the language interprets your code, and from that perspective, I find it fascinating. If you share the same feelings, I suggest you to investigate further about how the language works, if something seems like “magic”, find out what’s actually happening, things will become a lot clearer and that “magic” will turn into “convenience”.

My opinion on those points has changed a lot, specially after I decided to give the language another go, in fact I’m now a big fan of Python! Now you might be wondering where I’m going to try to convince you that learning Python is a good idea, don’t worry that part is coming next. As a closing point to the introduction, I want to mention that this was my personal feeling towards the language, was just a personal preference. I didn’t try to convince people that they should learn C, because if you’re programming in Python “you’re not a real programmer” (in fact, I don’t believe in that). When people asked me which language they should learn as their first, I usually suggested Python, for many of the reasons that I mentioned above as “disadvantages”. My feelings were mostly based on my personal interests, I was doing some more low-level stuff at the time, so as you might imagine, Python didn’t fit in that picture.

# Python: The Good Parts

After jacking the title for this section from a popular (and great) JavaScript book, it’s time to begin the topic of this blog post: why you (yes, you!) should learn Python.

## 1. Universal Scripting Language

This was one of the main reasons why I decided to give Python a second go. I was working on various projects with various people, naturally different people used different operating systems. In my case, I was usually switching between Windows and Linux. To give a concrete example, on one of the projects I wrote a script that automated testing in a project, only to realize that I was the only one who was taking advantage of it, since it was written in `PowerShell` and I was the only one using Windows. Now there was natural “bash is so much better” from my colleagues, while I tried to explain them that `PowerShell` followed a completely different paradigm and that it had its strong points (for example, it exposes the `.NET` framework interface), it’s an Object-Oriented scripting language, quite different from `bash`. Now I’m not going to discuss which one is better, since that’s not the focus of this post.

So how could this problem solved? Hmmm… now, is there a language that is script-friendly and runs on all major operating systems? You’ve guessed it, that language is `Python`. Besides running on all major operating systems, it also includes functionality useful for scripting out of the box. The standard library includes a handful of utilities that provide a common interface for operating system dependent functionality. To provide a simple and straightforward example, let’s assume that you wanted to get a list of names of all files in a directory and then do something with those names. In UNIX, you’d have something like:

While in PowerShell, you’d go with something similar to:

An equivalent functionality in Python can be achieved with:

Now, besides running on Linux, MacOSX and Windows, in my opinion, it’s also more readable. The example above is a very simple script, for more complex examples the difference in readability is even more obvious.

As I mentioned earlier, Python comes with great libraries out of the box, for the purpose of replacing shell scripting, the ones that you’ll find the most useful are:

• os - provides OS independent functionality, like working with paths and reading/writing files.
• subprocess - to spawn new processes and interact with their input/output streams and return codes. You can use this to launch programs already installed on your system, but note that this might not be the best option if you’re worried about the portablity of your script.
• shutil - offers high-level operations on files and collections of files.
• argparse - parsing command-line arguments and building command-line interfaces

Alright, let’s say you get the point, cross-platformness (is that even a real word?) and readability sounds great, but you really like the UNIX-like shell syntax. Good news, you can have the best of the both worlds! Check out Plumbum, it’s a Python module (more on that topic later on), whose motto is “Never write shell scripts again”. What it does is mimics the shell syntax, while keeping it cross-platform.

### You Don’t Have To Ditch Shell Scripting Altogether

While it’s possible to completely substitute shell scripts with Python, you don’t have to, since Python scripts naturally fit into the command chaining philosophy of UNIX, all you have to do is make them read from `sys.stdin` (standard input) and write to `sys.stdout` (standard output). Let’s look at an example. Let’s say that you a have file with each line containing a word and you want to know which words appear in the file and how many times. This time we don’t want to go “all Python”, we’re actually going to chain the `cat` command with our Python script, which we’ll call `namecount.py`.

Let’s say we have a file called `names.txt` with the following content:

``````cat
dog
mouse
bird
cat
cat
dog
``````

This is how our script will be used: `\$> cat names.txt | namecount.py`. And `PowerShell` folks: `\$> Get-Content names.txt | python namecount.py`.

The expected output is something like (order might vary):

``````bird    1
mouse   1
cat     3
dog     2
``````

Here is the source of `namecount.py`:

``````#!/usr/bin/env python3
import sys

def count_names():
names = {}
name = name.strip()

if name in names:
names[name] += 1
else:
names[name] = 1

for name, count in names.items():
sys.stdout.write("{0}\t{1}\n".format(name, count))

if __name__ == "__main__":
count_names()
``````

Having the information displayed unordered is not the most readable thing, and you’ll probably want that ordered by the number of occurrences, so let’s do that. We’ll use the piping mechanism again and offload the job of sorting our output to the built-in commands. To sort our list numerically, in descending order all we have to is `\$> cat names.txt | namecount.py | sort -rn`. And if you’re using `PowerShell`: `\$> Get-Content names.txt | python namecount.py | Sort-Object { [int]\$_.split()[-1] } -Descending` (you can almost hear the UNIX folks complain about how verbose the PowerShell version is).

This time our output is deterministic and we’ll get:

``````cat     3
dog     2
bird    1
mouse   1
``````

(As a side-note, if you’re using `PowerShell`, `cat` is an alias for `Get-Content` and `sort` is an alias for `Sort-Object`, so the commands above can be also written as: `\$> cat names.txt | python namecount.py` and `\$> Get-Content names.txt | python namecount.py | sort { [int]\$_.split()[-1] } -Descending`)

Hopefully I have convinced you that Python might be a good substitute at least for some of your scripts and that you don’t have to ditch shell scripting altogether, since you can incorporate Python scripts into your existing workflow and toolbox, with the added benefits of it being cross-platform, more readable and having a rich library collection at your disposal (more on that later on).

## 2. A Lot Of Great Libraries

Python has a very rich library collection. I mean, there is a library for almost anything (fun fact: if you type `import antigravity` in your Python interpreter, it opens a new browser window which leads you to that xkdc comic, now how awesome is that?). I’m not a big fan of programming just by “stacking one library onto another”, but you don’t have to. Just because there are a lot of libraries, doesn’t mean that you have to use them all. While I don’t like to just stack libraries one onto another (which looks more like CBSE) I obviously recognize their use and do use them.

For example, I decided to play around with Markov Chains, so I came up with an idea for a project: grab all of the lyrics from an artist, build a Markov Chain with that and then generate songs from them. The idea is that the generated songs should reflect the artists style. So I hacked around with that project for a bit, and the result was lyricst (this is more like a proof of concept than a complete, fully tested project, as I said, I just hacked around for a bit, so don’t go to hard on it. It does include a command line-interface and some documentation with examples, if you want to play around). I decided that a great place to get lyrics form would be RAPGenius, since it’s actively used and usually up to date).

So to get all of the artists lyrics, I would have to scrape them from the website and work with HTML. Luckily, Python is great for web scraping and has great libraries like BeautifulSoup to work with HTML. So this is what I did, used BeautifulSoup to get all of the info from the page I needed (which was basically the song lyrics) and then use that info to build MarkovChains. Of course I could’ve used regular expressions or built my own HTML parser, but the existence of such libraries allowed me to concentrate on what was the real goal for this project: play around with Markov Chains, while also making it more interesting, then let’s say, just reading some text from files.

## 3. Great For Pentesting

If you’re into penetration testing or simply like to hack around with stems, Python is your friend! The fact that Python comes pre-installed on almost any Linux and MAC OS machine, has a rich library collection, very comprehensive syntax and is a scripting language, makes it a great language for that purpose.

Another reason why I decided to give Python a second go (besides the one mentioned in previous section) is that I’m interested in security and Python seemed like a perfect choice for pentesting. One of my first encounters in that world was Scapy (or Scapy3k, for Python3) and tell you what, I was impressed. Scapy is used for network packet creation, capture and manipulation. It has a straightforward API and great documentation. You can easily create packets on various layers (I’m talking about the OSI model) or capture them for analysis and modification. You can even export the `.pcap` files and open them in WireShark. It doesn’t stop at network packet capture though, there is a wide array of great libraries for that purpose, but I’m not going to cover them here, since that is not the topic of this post and it deserves a post just for itself.

Some of you might say, “Oh, that’s great, but I’m interested in exploiting Windows machines, and those don’t come with Python pre-installed”. No worries, you can always compile your Python script to a standalone `.exe`, using py2exe. The executables can get a little big (depending from the number of libraries you’re using in your script), but usually it’s nothing major.

If you’re intrigued, however, check out this list of Python pentesting tools. At the end of this post I also include some book recommendations.

# 4. A Hacker’s Language

Python is a very malleable language. You can customize the way it works in many ways. From altering the way imports work to messing with classes before they are created. Those are just some of the examples. This also makes it very powerful scripting language (as mentioned in section 1) and great for pentesting (section 3), since it gives you a lot of freedom with your scripts.

I won’t go deep into those topics, but I will describe the “WOW” moment that I had with this. So, I was doing some webscraping (Python is great for this task!), and one of the tools I used was BeautifulSoup. This was one of my “learning Python” projects. BeautifulSoup’s syntax for working with HTML is very clean and intuitive and one of the reasons for that is the fact that Python gives you a lot of freedom when it comes to customizing its behavior). After playing a bit with the API, I noticed that there was some “magic”. The situation was similar to this one:

What the code above does is creates a BeautifulSoup instance from the string passed as the first argument. The second argument just tells that I want to use the Python’s built-in HTML parser (BeautifulSoup can work with various parsers). `soup.p` returns a `Tag` (`bs4.element.Tag`) object, which represents the `<p>` tag passed as the first argument.

The output of the code above is:

``````<p class="someclass">Hello</p>
``````

Now you might wondering, “where’s the magic part you were talking about”? Well, this part comes up next. The thing is that the code above can be adapted to any tag, even the custom ones. This means that the code below works just fine:

The output is the following:

``````<foobarfoo class="someclass">Hello</foobarfoo>
``````

When I realized that that works just fine, I was like “whaaaaa?”. Now, the first example can be easily implemented, I mean the most straightforward way is just to define an attribute (instance variable) for every possible HTML tag, and then during parsing assign values different from `None` to them, in case those elements are found. But this explanation does not work for the second example, there is no way that could’ve been done for all possible string combinations. I wanted to know what was going on and how it was working, so I cracked open BeautifulSoups source code and started digging. It’s probably no surprise that I didn’t find any attributes named `p` and the parsing functions didn’t assign values to them. After some googling, I found what was going on: magic methods. What are magic methods and why they are called like that? Well, informally, magic methods are methods that give the “magic” to your classes. Those methods are always surrounded by double underscores (for example `__init__()`). They are described in the DataModel model section) in Python docs.

The specific magic method that allows BeautifulSoup to have this functionality is `__getattr__(self, name)__` (`self` in Python refers the object instance, similar to `this` in Java). If we go to the docs, here’s what we’ll find in the first paragraph:

Called when an attribute lookup has not found the attribute in the usual places (i.e. it is not an instance attribute nor is it found in the class tree for self). name is the attribute name. This method should return the (computed) attribute value or raise an AttributeError exception.

So what happens is that if you try to access an attribute that does not exist `__getattr__(self, name)` of that object will be called, with `name` being the name of the attribute you tried to access as a string.

Let me show you an example. So let’s say you have a `Person` class with a `first_name` attribute. Let’s give the users of our API the ability to access the same value using `name`. Here’s how our class will look like:

Let’s play a little with the class above in the interactive console:

``````person = Person('Jason')
>>> person.first_name
'Jason'

>>> person.name
'Jason'

>>> person.abc
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 7, in __getattr__
AttributeError: Person object has no attribute 'abc'
``````

This means that we can just “make-up” object attributes on the fly, isn’t that awesome? So you can make your `Dog` secretly be able to “meow” as well, besides barking:

``````>>> snoop = Dog()

>>> snoop.bark()
Ruff, ruff!

>>> snoop.meow()
Meeeeeeow
``````

You can also add attributes on the fly, without reflection. `object.__dict__` is a (dictionary)[https://docs.python.org/3.5/library/stdtypes.html#typesmapping] containing the the `object`’s attributes and their values (note that I said `object`.dict, `object` is an object instance, there is also a `class`.dict, which is a dictionary of the `class`es attributes).

This means that the this:

Is equivalent to this:

Both of the versions share the same output:

``````snoop = Dog()

>>> snoop.name
'Doggy Dogg'
``````

At this point you might be thinking, this is all great, but how is this useful? The answer is simple: magical APIs. Have you ever used some Python library that just feels like magic? This is one of the things that allows them to be so “magical”. It’s not really magic though, once you understand what’s happening behind the scenes.

If you’re interested more in that topic, check out the Description Protocol page in the docs.

## The Object-Oriented Aspect

The object-oriented aspect of Python might seem a little “hacked in”. For example, there are no private instance variables or methods in classes. So if you want to make an instance variable or a method private in a class, you’ll have to stick to conventions:

• using one leading underscore (`_`) for non-public instance variables and methods
• using two leading underscores (`__`) for instance variables and methods will mangle their name

Let’s explore an example, suppose you have the following class:

Let’s jump into the interpreter:

``````>>> foo = Foo()
>>> foo.public
'public'
>>> foo._private
'public'
>>> foo.__secret
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'Foo' object has no attribute '__secret'
``````

As you can see, nothing is stopping you from accessing the `_private` instance variable, but what happened in the last case? Does that mean variables starting with `__` are really private? The answer is no, their name is just mangled. In essence, instead of being called `__secret`, its name has been changed to `_Foo__secret` by Mr.Python himself. You can still access it, if you really want to:

``````>>> foo._Foo__secret
'secret'
``````

However, PEP8 suggests to only use leading double underscores to avoid name conflicts with attributes in classes designed to be subclassed. “PEP”, stands for “Python Enhancement Proposal”, it’s used for describing Python features or processes. If you want a new feature to be added to the language, you create a PEP, so the whole community can see it and discuss it. You can read more about PEPs here. And yes, the description of what a PEP is a PEP itself, how Meta is that?

As you can see, Python puts a lot of trust in the programmers.

I won’t go much further into the OO topic here, since again, that deserves a post (or even a series of them) just for itself.

I do want to give you a heads up that it might get some getting used to, it might not seem as “natural” as it is in languages like Java, but you know what, it’s just a different way of doing things. As another example, you don’t have abstract classes, you have to use decorators to achieve that behavior.

# Conclusion

Hopefully this post gave you some insight into why you should consider giving Python a go. This post is coming from someone who feels “guilty” for talking not so good about Python in the past and is now all over the hype train. In my defense, it was just a “personal preference thing”, when people asked me about which language they should learn first, for instance, I usually suggested Python.

If you’re still undecided, just give it a go! Try it out for an hour or two, read some more stuff about it. If you like learning from a book, I also got you covered, check out Fluent Python The section right below has some more.

# Book Recommendations

As promised, here comes the book recommendation section. I will keep this one short, only putting books that I’ve read/had experience with myself.

• Fluent Python - GREAT book about Python 3. Whether you are a novice, intermediate or an experienced Python programmer. Covers the ins and outs of the language.

• Web Scraping With Python - the title says it all, it’s a book about webscraping with Python. You’ll explore how you can scrape the web for content, parse HTML and much more. I would say this book is good for novice and possibly intermediate people in webscraping area. Even if you’ve never used Python before, you can still follow along. It does not go into any advanced topics.

• Black Hat Python - oh this one’s fun! You’ll build reverse SSH shells, trojans and much more! If you want to know how Python can be used in pentesting, make sure you check this out. Please note that this book contains Python 2 code, I do have a repo, however, that uses Python 3.

• Violent Python: A Cookbook for Hackers, Forensic Analysts, Penetration Testers and Security Engineers - more on the same topic as above, you’ll learn how to write practical scripts for pentesting, forensic analysis and security in general.

EDIT:

# Introduction

This blog post is a collection of notes on some more common design patterns. Each design pattern is explained in simple terms and includes an example.

This is written mainly for beginners, but it’s also useful if you need to refreshen your understanding of a certain design pattern. I highly suggest you to further explore each pattern covered here, since this post’s goal is to simply give you an overview of them. I’ve included some additional sources at the end of the post.

I’ve written this mainly because it’s not always easy to understand what a pattern is about in its essence, since many of the explanations out there are either domain-specific or include examples that are somewhat complex. In my opinion, it’s a lot easier to to undestand them once you have a general idea of what the pattern does. This is why I’ve used somewhat “childish” examples here: those should help you concentrate on the pattern and not the domain details.

All of the code examples are in Java, but only the basic syntax is used, so if you’re coming from a language like C# or have basic Java knowledge, you should have not problems in undestanding this post. Even though a specific programming language is used here, the concepts are domain-independent and can be applied to other languages. The default access modifiers for member variables are used, to make the code interpertation more accessible to beginners.

# Design Patterns

## Singleton

The Singleton Pattern ensures that there is only one instance of the class and provides a global point to access that instance.

Java’s implementation of Singleton makes use of a private constructor (to make sure that no one in the application can call the new Singleton(), thus possibly creating more than one instance of the class) and a static method, combined with a static variable (to make sure that there is only one instance of the class in the application, instead of calling “new”, we ask the class itself to provide an instance and since we never directly instanciate it, the method has to be static). The class itself will be responsible for keeping track of its sole instance.

Below is an example implementation in Java. This version uses lazy initialization (the instance of the class isn’t created until it’s first requested via the getInstance() method).

## Command

The Command Pattern encapsulates a request as an object, thereby letting you parameterize other objects (the client) with different requests, queue or log requests, and support undoable operations.

• encapsulates a request by binding together a set of actions on a specific reciever. To achieve this, the actions and the reciever are packaged into one single object that only exposes one method: execute() (it can also have other like undo(), etc). An object from outside doesn’t know what actions will be performed, all it knows is that if they call execute() their request will be serviced.
• parameterize other objects with a command, in a sense that any command object can be passed to the client. The client doesn’t know (or care) what the command is, all it does is call the execute() method.
• the Command Pattern makes it easy to implement queue, log and undo operations

The key in this pattern is an abstract Command class (or an interface), which declares an interface for executing operations. In its most simple form, this inteface has an execute() method. A concrete commad then has an instance variable of the receiever, whose methods are called in the execute(). The command itself doesn’t perform any complex operations, those have to be done by the receiever, and that’s what happens in the execute() method, receiver’s methods get called.

### Example

Let’s say you have a remote control that controls the volume and the on/off state of your awesome sound system. For simplicity, let’s assume that your remote control is actually a single button, which you can reprogram to do different actions (like voulume up, volume donw, on and off).

The first thing to do is to create the Command interface, which in this version, will contain the minimum (i.e. only the execute() method).

Next step will be to create four command classes (TurnOnCommand, TurnOffCommand, VolumeUpCommand and VolumeDownCommand). Each of those classes will have a reference to the receiver (in this case, the sound system), the execute() method and a constructor.

Now, just to demonstrate how the Command Pattern will be used, there will also be a button, which will have a referece to the command, a method to activate the command (press()) and a setCommand() method, so that different commands can be assigned to the same button.

And just to show an example of usage, consider the main class below.

Which produces the following output:

ON! Sound is at 1 Sound is at 2 Sound is at 3 Sound is at 2 OFF!

Note that the command invoker doesn’t know what the command is doing or how it’s, doing it, all it knows is that it has an execute() method. Also note that the execute() is doing very little himself, the main work is done my the receiver through some method.

### Implementing the “Undo” Operation

In its simplest form, the undo operation is pretty straight forward. For example, what would the undo be for the VolumeUpCommand? Well, if that command increases the volume by 1, then the undo would decrease it by one. So the VolumeUpCommand would now look something like this:

Besides that, the undo() method would also have to be added to the Command interface:

You could also store all of the commands in a list, for example, and that would allow you to go through that list, calling undo() on every command object in there (that would be like a history of actions and you can undo multiple times, just like pressing Ctrl + Z on your keyboard multiple times will do more than one undo).

In a similar manner you could also extend the pattern to other functionality, such as queing or logging.

## Iterator

The Iterator Pattern provides a way to access the elements of an aggregate object (an object that contains an aggregate of something) sequentially without exposing its underlying representation.

So let’s say you have an object that contains a collection of items and you want to iterate through every item. But there is a problem here: let’s say you know what items you’re accessing, but you don’t know how they are stored, they might be in an ArrayList, HashMap, LinkedList, etc. Now how can you abstract the internal implementation (i.e. how the items are stored) away and have an interface that allows you to access those elements in a consistent manner, whichever the internal implementation is. The answer is (you’ve guessed it!) the Iterator Pattern.

So as mentioned before the Iterator Pattern allows you to step through the elements of an aggregate without knowing how the things are represented under the hood. It also allows to write polymorphic code that works with any of the aggregates (it doesn’t matter if it’s an ArrayList, a HashTable or even a LinkedList, it’s an aggregate, that’s all we care about).

The Iterator Pattern takes the responsibility of traversing the elements and gives that responsibility to the iterator object, not the aggregate object. This makes all the sense, since the aggregate object doesn’t have to know how to iterate through items, all it has to know is how to store and manage them. It has to know which objects have been traversed already and which ones haven’t.

In its simplest form, the Iterator Pattern consists of an Iterator interface, which contains two methods: * next(), which returns the next object in the aggregation that hasn’t been iterated through yet. * hasNext() which returns a boolean indicating whether there are more items to be iterated through.

### Example

Let’s say you asked two of your friends to provide a list of their favorite songs. Your idea is simple: iterate through both of the lists (lists of songs, no one is talking about Java Lists here) and display the info of each one of the songs (title and author). You then realized that you didn’t specify the format in which you want the songs to be sent (ArrayList, HashTable, LinkedList, etc) and you need to be able to iterate over the lists in a consistent way, without depending on the type of the aggregation.

You’ll have to create a concrete iterator for every type of the aggregation, so let’s say one of your friends send the songs in an HashTable and the other in a LinkedList.

Below is a possible solution using the Iterartor Pattern.

The application above produces the following output:

``````Name: Still Dre Artist: Dr.Dre

Name: Let's Ride Artist: The Game

Name: What's My Name? Artist: Snoop Dogg

Name: Nas Is Coming Artist: NAS

Name: What Up Gangsta Artist: 50 Cent

Name: Warrior Artist: Lloyd Banks
``````

Note how by using the Iterator pattern we decoupled our application (in this case just the Main class) from the underlying implementation of each aggregation.

All we had to do to our friends code is implement the Iterator interface (which we defined) and add the iterator() method to their classes. If we didn’t use the pattern, when iterating through the list of songs in the Main class, we would have to make a separate method for each aggregation we wanted to traverse.

## Composite

The Composite pattern allows you treat objects and compositions of objects uniformly. It allows you to compose objects into tree structures to represent part-hole-hierarquies (components can be divided into smaller and smaller components).

The idea here is really simple: you have an object A that supports some operations, then you have another object B that is an aggregation of objects of type A. The composite pattern allows you treat both of them using the same interface. Let’s say object A is a sheep and supports the sheer() operation. So to sheer a single sheep you simply call the sheer method on a sheep object. Now, object B is a group of sheep. How do you sheer a group of sheep? Simple, the same way you would sheer an individual sheep: by calling the sheer method on the object B. Note that the object B can contain sheep or other objects of the same type(of the type of object B).

So basically, the composite pattern allows us to ignore the differences between compositions of objects and individual objects.

### Example

In this example, we will use the sheep example introduced above. So the idea is simple: each sheep has a name and the only operation it supports is sheer().

Now, you sheer a sheep by simply calling the sheer() method on it, but how can you sheer a group of sheep? The same way, by calling the sheer() method on it. As mentioned before, the goal is to inore the differences between an individual object and a group of objects, so we will define an abstract class, which is extended by both: an individual sheep and a group of sheep (here, it’ll be called SheepComoponent). This approach will also allow SheepComponents to contain other SheepComponents.

Below is a possible solution to the problem:

The output of the application above is:

`````` Sheering Sheep 1...

Group Name: Sheep Group 1
---

Sheering Sheep 2...

Sheering Sheep 3...

Sheering Sheep 4...

Sheering Sheep 5...

Group Name: SheepGroup 2
---

Sheering Sheep 1...

Group Name: Sheep Group 1
---

Sheering Sheep 2...

Sheering Sheep 3...

Sheering Sheep 4...

Sheering Sheep 5...

Sheering Sheep 6...
``````

## Visitor

The Visitor pattern allows you to add new methods to the classes without changing them too much. You can add operations to a Composite structure without changing the structure itself.

Visitor is very useful when you have some unrelated operations that need to be performed on an object in an object structure and you don’t want to “pollute” their classes by adding new methods to them to perform those operations. This pattern allows you to keep related operations together defined in a separate class. This is very useful when your object structure is shared by many applications, but only some of those applications actually use those extra operations, since visitor allows you to put those operations only in the applications that need them.

So let’s say you have the class code written and now you’re wondering what changes you’ll have to make to the class for it to support the visitor pattern. Okay, make sure you have a piece of paper and pen to write them down. Not really, actually all you have to do is add an accept() method to your class (it’s a convention to call the method accept(), you can name it whatever you want). Yes, that’s it! All you have to do for your classes to support the visitor pattern is add a single method. That’s what we’re basically going to do, except we’re going to put this method in an Interface, we’ll call it “Visistable” (this name makes sense, since the class will be visted by a visitor).

Okay, now how do we create those “visitors”? Simple, first we create another interface called Visitor (again, this name is just a convention). And what will that interface contain? It will contain the new operations we want to add. Now, since we’re putting them in an interface, those operations have to be related (i.e. be somehow related, belong to the same “group”).

Now you might be wondering what will you do if you had more than just one group of operations? Well, in that case you would have to add another accept() method to your Visitable interface (use method overloading).

### Example

Let’s say you have a store and your store sells three products: drinks, food and gadgets. Each of those three objects has a price. Here is how your code looks now:

(Okay, a better choice would be to add an abstract class from which those methods derive, but I want to enforce the idea that the classes don’t have to be related in any way).

Now you are asked to be able to calculate taxes for each product(the tax is 21%). That’s where the visitor comes in. First you’ll create a Visitor interface and add three visit() methods there. Then you’ll create a new class: a concrete visitor, which implements the Visitor interface. Then, we’ll create a Visitable interface and add the accept() method to it, which takes an object of type Visitor as an argument. The Food, Drink and Gadgets classes will implement the Visitable interface. Now your code will look something like this:

Now you are asked to add yet another type of tax: a holiday tax. It’s basically the same as the previous one, except the tax value is now 18% and you always subtract two cents (0.02) from the value after tax (here we’ll ignore that you can get negative or zero values). Well, that’s simple, just create a new class HolidayTaxVisitor, implement the Visitor interface and add override the methods with the requested functionality. Your new class will look something like this:

And now an example application:

The output of the Main class above is the following:

``````Drink price after normal tax: 1.815

Drink price after holiday tax: 1.75

Food price after normal tax: 3.3275

Food price after holiday tax: 3.225

Gadget price after normal tax: 8.7725

Gadget price after holiday tax: 8.535
``````

Now what if you wanted a different group of operations, not related in any way to tax calculation? Let’s say you wanted to be able to print out the name of the class of which an object is instance of. Well, in that case you’d have to create a new visitor interface, for example NameVisitor, create a concrete instance, which implements that interface, for example NormalNameVisitor and add a new accept() method to the Visitable interface.

## Factory Method

The idea behind the Factory Method pattern is to be able to decide which class you want to instantiate dynamically (i.e. at runtime). Basically you will have a method that will return one of several possible classes that share a common superclass. The factory method has this name, because it’s responsible for “manufacturing” an object. This pattern allows you to encapsulate object creation in a method: the factory method.

The typical implementation uses a single class with a single method (the factory method) and this method returns an object based on the input passed as an argument. Which object is it? Well, that depends on the passed parameter.

### Example

Let’s say that you have a Fruit superclass that has two subclasses: Apple and Orange. You want your application to be able to instantiate each one of the subclasses dynamically, because you don’t know which fruit you’ll need (it might depend on the user input, for example).

All you’ll have to do is create a FruitFactory class and add a makeFruit() method to it, which accepts, for example a string and returns a Fruit (note it returns the generic Fruit object, not a concrete Apple or Orange).

To simplify things, let’s say that to create an apple you pass the “Apple” string as an argument and to create an orange you use the “Orange” string.

Below is a possible solution:

The Main class above produces the following output:

``````The fruit is an Apple.
The fruit is an Orange.
``````

## Strategy

The Strategy pattern lets you define a family of algorithms, encapsulates each one, and makes them interchangable. It lets the algorithms vary independently from clients that use it.

This pattern is very useful in cases when you have many hierarchically related classes that differ only in their behaviour. Strategy allows you to confugure every induvidual class in the hierarchy with one of the many behaviours. Another use case for it is when you have many variants of an algorithm.

### Example

Let’s say you have the class structure below:

Now you are asked to create a Bird class, which is also a subclass of the Animal class. The thing about the Bird class, is that it needs to be able to fly. You must also keep a common interface for all of the three subclasses, that means you can’t just add a fly() method to the Bird class, from now on every animal must print “Can’t fly!” or “Flying!” when the fly() method is invoked on an Animal object.

So how can we solve this? Well, we surely can just add a “fly()” method to the abstract class (or implement an interface) and override its behaviour in every subclass. But this creates several problems:

• code duplication.
• the change in super class will break the code in subclasses.
• implementing an inteface wich only has one method in it is usually a bad approach.

So what can we do to avoid those problems? Well, since all of our classes only differ in one behaviour (some fly and some don’t) it’s the right time to use the Strategy pattern!

What we’ll do instead is instead of inheriting the ability to fly, we will compose the class with objects which have the correct ability built-in (in out case we will only add one object).

This approach will give us many benefits, for example:

• it’s possible to create many types of “flying” without affecting the Animal class or any of its subclasses (since the “types of flying” are separate classes).
• we are decoupling, that means we are encapsulating the behavior that varies(in our case the behaviour is the ability to fly).
• it’s possible to change the ability at runtime. That means we can, for example, create an object that couldn’t fly before and make it flyable!

What we’ll do is create an interface called Fly, it will only have one method: fly() (which is the behaviour we want to encapsulate) and then for every “type of flying” we will create a subclass, each one implementing the Fly interface (in our case it will be two classes: CanFly and CantFly). We’ll also have to add a new varibale to the Animal class of type Fly.

Anyways, here is a possible soluition using the Strategy pattern, with an example of a client application that uses it:

The main class produces the following output:

``````Mittens: Can't fly!

Rufus: Can't fly!

Tweetie: Flying!

Rufus: Flying!
``````

## State

The State pattern allows to modify its behavior when its internal state changes. The object will also appear to change its class. It actually mimics the finite state machine: you have different states and certain actions make you transition from one state to another.

This pattern encapsulates every state into a separate class (all those states derive from a common class). If you have an object and you completely change its behavior, it appears that the object changed it class (in reality you will just be using composition to give the appearance of class change by referencing different state objects).

The State pattern is a great way to get rid of if statements, but it usually requires a large amount of extra classes to be created.

Each state has a reference to the object whose state it represents and is able to change it dynamically (usually through a setter method).

## Example

Too keep it simple, consider the following problem: You have an automatic door with two buttons: open and close. You have four states:

• open
• closed

The transitions between the states are intuitive: for example, if a door is closed, by pressing the open button, the door will go to the “open” state. To simplify, you can’t interrupt an opening/closing action(there are no intermediate DoorOpeningState and DoorClosingState classes).

What you’ll do is create an abstract DoorState class, with two operations:

• openDoor()
• closeDoor()

Then, you will create two subclasses: DoorOpenState, DoorClosedState. Each one of the states will have a reference to the Door object (passed as an argument in the constructor) whose state it represents and it will be able to change its state through the setStateMethod() which will be a part of the Doors interface.

In this example, the Door class will contain references to every possible state which will be instantiated when a new Door object is created.

Below is a possible solution to the problem.

The output of the application above is:

``````Opening door... New state: DoorOpen.

Closing door... New state: DoorClosedState.

``````

## Abstract Factory

The Abstract Factory pattern provides an interface for creating families of related or depended objects without specifying their concrete classes.

The idea if an abstract factory is to define a common interface for a group of factories, then use those factories to produce objects. It provides an abstract type for creating a family of products and subclasses of that abstract type define how those products are produced. To use a specific factory, you’ll have to instantiate it and pass into some code that is written against the abstract type.

#### Factory Method vs Abstract Factory

It’s important to understand the difference between the Abstract Factory and the Factory Method patterns. While both are really good at decoupling applications from specific implementations, they do it in different ways. Both of the patterns create objects, but they do it in a different way:

• Factory Method uses classes - the objects are created through inheritance.
• Abstract Factory uses objects - the objects are created through object composition.

Often the Abstract Factory uses Factory Methods to implement its concrete factories. The concrete factories use a factory method to create their products (they are used purely to create products).

### Example

Consider the example from the Factory Method section. Well, here we also have fruit, except that one of the farmers has discovered a new sort of fruit: the Advanced Fruit. What distinguishes a “normal” Fruit from an AdvancedFruit? Well, unlike the “normal” Fruit, all AdvancedFruit have guns and engines!

The farmer in question is only producing AdvancedApple and AdvancedOrange types of AdvancedFruit, so those are the ones that will be covered in this example.

What distinguished an AdvancedApple from an AdvancedOrange? Well, while AdvancedApple has a BlueGun and a V16Engine, the AdvancedOrange has a RedGun and a V8Engine.

Hmmm… Isn’t that a good place to use the Abstact Factory pattern to abstract out the specific gun and engine creation? Note, that both, advanced apples and oranges have guns and engines, except that they are of different types. We sure can come up with a common abstract interface to produce those pieces of equipment and then have two specific implementations of those: one for the advanced apples and one for the advanced oranges.

When defining an abstract interface for out factories we have to question what makes an AdvancedFruit an AdvancedFruit? Well, it’s the fact that every AdvancedFruit has an Engine and a Gun.

Out abstract interface only will have to methods: makeEngine() and makeGun() (we’ll call it the AdvancedFruitFactory). Then in AdvancedAppleFactory and AdvancedOrangeFactory we’ll make those methods return the correct Engine and Gun objects.

Now every advanced fruit will receive a concrete factory in its constructor, because it’s through a method call on the AdvancedFuit object, that the specific engine and gun will be “given” to it.

Below is a possible solution to the problem:

The output of the Main class is as follows:

``````Name: Generic AdvancedApple Gun: Blue Gun Engine: V16 Engine

Name: Generic AdvancedOrange Gun: Red Gun Engine: V8 Engine
``````

## Template Method

The Template Method defines the skeleton of an algorithm in a method, deferring some steps to the subclasses. This pattern allows the subclasses to change certain parts of the algorithm without changing the algorithm’s structure.

So let’s say you have a generic algorithm, for example an algorithm for making tea. The general(abstract) idea is simple:

1. Boil water.
2. Put tea bag in cup.
3. Pour in the boiled water(still hot).

The general algorithm is simple, however it can vary. Some prefer tea bags, while others prefer to use loose leafs. Some like to pour in water at 100ªC, while others prefer it a bit cooler. Some like to add condiments and some don’t.

So there are variations to the algorithm, but in essence, the algorithm doesn’t change.

That’s where the Template Method comes in. Basically you define an abstract template method, and then let the subclasses customize parts of it(or even the whole algorithm). This customization is obtained using method overriding and the so called hooks (mehods that return True/False).

### Example

Consider two types of cars: SportsCar and CityCar. The generic algorithm for car creation is the following:

That’s the general algorithm that all cars follow, the SportsCar however, doesn’t have air conditioning or radio and it uses a different type of wheels (sports wheels), while the CityCar uses regular wheels has A/C and radio. All of the cars must have a chassis, a body and windows.

A possible solution using the Template Method can be found right below:

The output of the client application is:

``````Sports Car Production Begin!
---

Sports Car Production End!
---

Sports Car Production Begin!
---

City Car Production End!
---
``````
• The template method is declared final because we don’t want the subclasses to be changing the algorithm.
• Have some “hooks” that return booleans, to decide whether we should run a certain method or not.
• Make a method abstract when you want to force the user to override the method.
• Create a hook when you want to make a part of your algorithm totally optional.

## Observer

The Observer pattern defines a one-to-many dependency between objects so that when one object changes state all of its dependents get notified and updated automatically.

A good analogy is a newspaper. A newspaper (the Subject) can have zero or more subscribers (Observers) and every time a new edition comes out (the newspaper, i.e. the Subject changes), the subscribers receive the new edition in the mail (i.e. the Observers get notified and updated about that change.

### Example

Of course you could put each “observer” in an infinite loop testing whether there has been a new status update or a new like, but that would be extremely uneficient! The Template pattern provides a much more elegant and resourse-friendly solution.

Below is a possible solution to the problem:

The output of the application is as follows:

``````Status: Second status update!|**| Last Liked: FistLike

Status: Second status update!|**| Last Liked: SecondLike

Status: Third status update!|**| Last Liked: SecondLike

Status: Third status update!|**| Last Liked: SecondLike

Status: Third status update!|**| Last Liked: SecondLike

Status: Third status update!|**| Last Liked: ThirdLike

Status: Third status update!|**| Last Liked: ThirdLike

Status: Third status update!|**| Last Liked: ThirdLike

Status: Forth status update!|**| Last Liked: ThirdLike

Status: Forth status update!|**| Last Liked: ThirdLike

Status: Forth status update!|**| Last Liked: ForthLike

Status: Forth status update!|**| Last Liked: ForthLike
``````

## Decorator

The Decorator design pattern allows you to attach additional responsibilities to an object dynamically. It provides a flexible alternative to subclassing for extending functionality.

This is usually a great choice of a pattern whenever you want to be able to add responsibilities to individual objects dynamically (at runtime) without affecting other objects. The responsibilities you add can be withdrawn later on, also dynamically. Sometimes extension by subclassing is simply impractical: you you might have a large amount of independent extentions and that would produce an explosion of subclasses and every time you added a new extentsion, you would have to create another subclass, which only aggravates the problem. The pattern gives you the capabilities of inheritance, but with functionality added at runtime.

### Example

Let’s say a car dealership is selling a certain model of a car. It’s base price (for model with no extras) is \$100.000, but you can also add extras like AirConditioning(extra \$5.000), Spoiler(extra \$3.000) and a custom BodyKit (extra \$15.000).

One way to solve this would to create a subclass for every possible combination, but that would give you 7 subclasses just for the cars(3! + 1 = 7)! And what if you wanted to add another extra? You can understand the way this is heading…

This seems like the right place to use the Decorator pattern. We want to add responsibilities dynamically.

First, we’ll create the Car interface, which is the common interface for every car and every extra. Then, we’ll create a BasiCar model, which represents the most basic car, which then will be decorated by extras. All of the extras derive from the CarDecorator, which, just as the BasicCar, implements the Car interface. The decorator will store a reference to the object it decorates. In the decorator’s superclass we want to implement the interface of the object that that group of decorators will be decorating.

Here is a possible way to solve this exercise:

The application outputs:

``````Basic Car Model |**| Price : 100000
Basic Car Model + Body Kit |**| Price : 115000
Basic Car Model + Body Kit + A/C |**| Price : 120000
Basic Car Model + Body Kit + A/C + Spoiler |**| Price : 123000
``````

Note, that on second and third “decorations” you are actually passing a CarDecorator and not a BasicCar object, so when you call getDescription() on one, it calls the getDescription() on another, until a getDescription() reaches a plain return of a string (here it happens in the BasicCar class). This is why it’s both, the decorator and the decorated (the car) must implement a common interface.

The Adapter design pattern converts the interface of a class into another interface that the client expects. Adapter lets classes work together that couldn’t otherwise because they have incompatible interfaces.

This is usually the right pattern to go with when you want to use an existing class without modifying it, but its interface doesn’t match the one that you need.

Adapters in OO are just like adapters in real life. Have you ever needed to use an electronic device with an US AC plug in Europe? Well, since the European wall outlet (the client) expects a different “shape” of adapter what do you do? Change the wall outlet? Of course not! You use an adapter to adapt the US AC Plug into a Europe AC plug, as shown in the image below (image from www.safaribooksonline.com).

(This is kind of off-topic, but not all European wall outlets looks like that, in fact I believe I’ve never encountered one that’s of the same shape as in the image, but they do exist.)

### Example

Let’s say that you have a duck simulator application. What does it do? Well, it simulates ducks by invoking quack() and fly() methods on various ducks.

Everything has been going good, until your users demanded that you include turkeys from another popular simulator “Turkey Simulator” straight into your game. The developers of “Turckey Simulator” are willing to share they turkey classes from they gigantic turkey database with you. That’s great, except for one thing: all of the turkey classes have a different interface: instead of the quack() method, they have gobble() and despite the fly() method having the same name, they don’t really fly the same way as the ducks do. You are certainly not going to change every class provided by the “Turkey Simulator” team, since that would take too much time and you would have to do that to every new turkey added, besides that, to ensure the quality of the turkeys used, they gave you the permission to use their code, but not modify it.

To solve our problem, we will create a new TurkeyAdapter class, which will store a reference to the turkey that it is adapting into a duck as well as implement the same interface as the Duck class is using.

Below is a possible solution using the pattern:

The application outputs the following:

``````Duck
---
Flying!
Flying!
---

Turkey
---
Flying a short distance.
Flying a short distance.
Flying a short distance.
Flying a short distance.
Flying a short distance.
Gobble!
---
``````

There are two kind of adapters: class adapter and object adapter. This text only covered the object adapters. Class adapters aren’t possible in Java, since they require multiple inheritance.

The only difference between a class and an object adapter is that in the in class adapters, the Target and the Adaptee are subclassed to create the Adapter. In object adapters object composition is used to pass the requests to an adaptee. Below is the class adapter UML.

The Facade pattern provides a unified interface to a set of interfaces in a subsystem. Facade defines a higher-level interface that makes the subsystem easier to use.

This pattern also allows you to avoid tight coupling between clients and subsystems, as well as provides a simple default view of the subsystem that is good enough for most clients. Only the clients that need more customizability will look beyond the pattern.

So in other words, the pattern allows you to take a complex subsystem and make it easier to use by implementing a Facade class, that provides one, more simple interface. It not only simplifies an interface, as well as decouples a client from a subsystem of components.

### Example

As an example consider that you have a home theater system installed at your place. Suppose it consists of a DVD player, a projector, a screen, a sound system and lighs. Each one of the components is defined in it’s own class:

Okay, now let’s say you want to watch a movie. In order to do that, you have to perform a few tasks:

1. Turn the screen on
2. Turn the projector on
3. Turn the DVD player on
4. Set the sound to `5`
5. Set the light’s intensity to `1`
6. Start the DVD playback

The code to do that without using the pattern would look something like this:

Here are some issues with that approach:

• It’s complex
• Let’s say you want to reset everything after the movie is over, wouldn’t you have to do everything again, but in reverse order?
• If you decide to change your system, and let’s say put your phone on silence when the movie starts, as well as set the volume to `7` instead of `5`, you’re going to have to change your code in every place you’ve used it
• Wouldn’t it be as complex to play a music CD or turn on the radio?

So what can we do here? The complexity of the current approach is evident. Facade pattern to the rescue! What we’re going to do is create a Facade for our home theater system. To do this, we’ll create a `HomeTheaterFacade` class which exposes a few methods such as `watchMovie()`, `stopMovie()`, `playCD()`, etc.

What are going be the contents of those methods? Well, it’s going to be all that complex code that was mentioned above. Here is a possible implementation:

Now to watch a movie all we have to do is call the `watchMovie()` method on the `HomeTheaterFacade` object. The code is now a lot simpler and if we at some point decide to change the steps in any of the methods, the only place where we need to modify the code is in the `HomeTheaterFacade` class, since you decoupled your client implementation from any one subsystem.

Here is how the application that uses `HomeTheaterFacade` would look like:

It produces the following output:

``````Get ready for the movie...
Turning Screen On...
Turning Projector On...
Turning DVD On...
Volume set to: 5
Intensity set to: 1
Starting movie playback...
Ending movie playback...
Stopping movie playback...
Intensity set to: 5
Volume set to: 0
Turning DVD Off...
Turning Projector On...
Turning Screen Off...
``````