Regular expressions are another example of a little language - expressive yes but not Turing complete. This is an extract from my book Trick of the Mind which explores what it is to be a programmer.

The Trick Of The Mind - Programming & ComputationalThought

Buy Now From Amazon

Chapter List

1. The Trick Of The Mind

2. Little Languages
      Extract: Little Languages Arithmetic
      Extract: Regular Little Language

3. Big Languages Are Turing Complete

4. The Strange Incident of The Goto Considered Harmful
      Extract: The Goto Considered Harmful

5. On Being Variable  

6. Representation

7. The Loop Zoo
      Extract The Loop Zoo
      Extract Advanced Loops
   

8. Modules, Subroutines, Procedures and Functions
      Extract Modular Programming

9. Top-Down Programming 

10. Algorithms
       Extract: Binary Search 
       Extract: Recursion ***NEW!!

11. The Scientific Method As Debugging 

12. The Object Of It All
       Extract Why Objects 

Once you have the essential idea that a set of static texts can actually be something dynamic when read as a set of imperative commands then you have the main idea of programming – the rest is practice and familiarity. 

Of course, the few commands that we have introduced are not enough to do everything we could possibly want, but it is a start. There are some key concepts that we need to tackle to get to the full capabilities of a programming language. In fact, because the programming language that we have met so far is so restrictive and simple it is often referred to as a "little language" or, in more recent jargon, a Domain Specific Language, DSL. Most full programming languages have a number of little languages within them. For example, the drawing language that we have introduced is often part of a bigger language, most notably Logo, but also Python and others.

Little languages are interesting because they show what an essential component of algorithmic thought is all about, but this isn’t the whole story. Almost as important is the fact that little languages turn up in contexts that have, seemingly, nothing to do with programming at all.

In chapter but not in this extract

• Arithmetic as a Little Language
• BODMAS
• Arithmetic Expressions and Programming
• Why Are Arithmetic Expressions Like They Are?

Regular Expressions Little Language

Our second example of a little language is very much a key part of modern programming – regular expressions. This is a good example because it shows clearly why little languages are useful and where they fail to be able to do everything you could possibly want.

The problem that a regular expression tries to solve is specifying a pattern of characters that might occur in text. In programming a sequence of characters is generally called a “string”, shortened from “string of characters”, and this is the jargon we will use.

A regular expression is a specification for a particular target string that you might be looking for in another string. For example, suppose you are looking for the word computer in an arbitrary string of text, then you could use the regular expression computer to specify it. Yes, a sequence of characters is its own regular expression. If you use computer to search for a string then it will match only the exact same string:

"I think there is a world market for
                      maybe five computers." 
                                            computer
                                             match!

So far so boring, but now consider that you want to specify the word computer followed by any single letter. You can do this using a wildcard character, usually. (a single dot or full stop) which matches any character. So computer. matches computer and computers

"I think there is a world market for 
                          maybe five computers." 
                                                computer.
                                                 match!

But it also matches computerx and computera and so on…

The idea is that you can include some special characters in a regular expression to extend what matches beyond the simple and obvious. To continue the explanation we need a slightly more versatile but less realistic example.

Consider the problem of matching a string like ABA or ABBA and so on – basically any number of As followed by any number of Bs and any number of As. A simple regular expression for the first example, is ABA (i.e. itself), but this doesn’t match any of the others. To do this we need to learn about quantifiers. The simplest is the asterisk quantifier which causes the character it follows to match any number of times. For example, A*B*A* is a regular expression that matches any number of As followed by any number of Bs and any number of As. So it matches all of the examples.

Notice that we now have a regular expression that specifies a set of strings some of which are longer than it is. You can see that this suggests that this is a powerful approach.