Recursive Queries - Iterative Awesome

Recursive Queries - Iterative Awesome.

I’ve taken to trying to push my skills in SQL lately. Driven by recent requests for more complex reports or wanting to simplify some code. After all, when it comes to your declarative data mangling needs, SQL is hard to beat.

This particular adventure was into ‘Recursive Queries’, or ‘Common Table Expressions’. My database application of choice is PostgreSQL.

This type of query is super useful if you have, or would like to be able to, structure your data in a tree or graph like manner. But…

  • You don’t want to leave the convenience of an existing relational database
  • Graph databases are a bit too new or too heavy for your needs
  • “You can pry <SQL Compliant Database> from my cold, dead, segfaulting hands!”

Lets see if we can build a useful view of our ‘Wibbles’. Here is out Wibble structure:

-- Build a house for our Wibbles.
CREATE TABLE wibbles (
       id            SERIAL     PRIMARY KEY,
       fub           VARCHAR(8) NOT NULL,
       wub           INT        NOT NULL,
       parent_wibble INT        REFERENCES wibbles(id),
       CONSTRAINT un_fub UNIQUE (id,fub)
);

Lets put the Wibbles in there…

-- Invite some wibbles to stay in the new digs
INSERT INTO wibbles (fub,wub,parent_wibble) VALUES
  ('chair',    0, null),
  ('lavalamp', 3, null),
  ('fudge',    1, 1),
  ('choc',     2, 3),
  ('cake',     9, 2),
  ('feet',    12, 3),
  ('pants',   11, 4)
;

This gives us the following Wibble family tree:

lavalamp
|
`- cake

chair
|
`- fudge
 |
 +- choc
 |  |
 |  `- pants
 |
 `- feet

You can see how you could query for the top-most wibbles:

SELECT * FROM wibbles WHERE parent_wibble IS NULL;

 id |   fub    | wub | parent_wibble
----|----------|-----|---------------
  1 | chair    |   0 |
  2 | lavalamp |   3 |
(2 rows)

Or we could find the descendants of ‘chair’:

SELECT * FROM wibbles WHERE parent_wibble = 1;

 id |  fub  | wub | parent_wibble
----|-------|-----|---------------
  3 | fudge |   1 |             1
(1 row)

But that doesn’t return all the Wibbles! But you’re not always going to be able to eyeball your data and know if a query is returning enough data. Were you to rely on this query, you would have to keep querying the database until there were no more results. Replacing the ‘parent_wibble’ value with the new potential ancestor on each iteration.

  • Concerned Reader: “But that’s madness, surely there is a better way?!”
  • Me: “I’m glad you asked, dear reader. And don’t call me Shirley.”

… I’m hilarious

This helpful shenanigan is a ‘Recursive Query’. They are a variation on ‘Common Table Expressions’. We’ll start with those as they are useful too.

Common Table Expressions let you;

Separate large, or complex query components into manageable pieces. Providing an alias in the process:

WITH fudge_kids AS (
     SELECT * FROM wibbles WHERE parent_wibble = 1
)
SELECT wub FROM wibbles WHERE parent_wibble IN (
       SELECT id FROM fudge_kids
);

Here is an example from the PostgreSQL docs:

WITH regional_sales AS (
        SELECT region, SUM(amount) AS total_sales
        FROM orders
        GROUP BY region
     ), top_regions AS (
        SELECT region
        FROM regional_sales
        WHERE total_sales > (SELECT SUM(total_sales)/10 FROM regional_sales)
     )
SELECT region,
       product,
       SUM(quantity) AS product_units,
       SUM(amount) AS product_sales
FROM orders
WHERE region IN (SELECT region FROM top_regions)
GROUP BY region, product;

This turns complex queries into something more manageable and approachable. Helpful for eyes that are new, or tired from debugging. Recursive queries build on this structure, adding a base case, and an iterative step.

Without further ado, lets view our wibbles in a new light:

WITH RECURSIVE fobs(id, fub, parent_fub) AS (
     SELECT id, fub, ( null :: varchar(8) ) FROM wibbles WHERE parent_wibble IS NULL
     UNION
     SELECT w.id, w.fub, f.fub
     FROM fobs f, wibbles w
     WHERE w.parent_wibble = f.id
)
SELECT * FROM fobs;

 id |   fub    | parent_fub
----|----------|------------
  1 | chair    |
  2 | lavalamp |
  3 | fudge    | chair
  5 | cake     | lavalamp
  4 | choc     | fudge
  6 | feet     | fudge
  7 | pants    | choc
(7 rows)

There’s a lot going on now, so as is the custom in these situations, lets break it down. First we declare our intentions and describe our results table, and give it a name:

WITH RECURSIVE fobs(id, fub, parent_fub)

This next section is a union of two queries that must return the same type of results. The first section is the base case, or starting point of the query. I have to add a type annotation here as PostgresSQL needs a bit of help in this instance.

SELECT id, fub, ( null :: varchar(8) )
FROM wibbles
WHERE parent_wibble IS NULL

The results of that query are then fed into next query under the name of the entire expression, ‘fobs’, in this case. This is the part of the query where you connect the individual results to one another.

SELECT w.id, w.fub, f.fub
FROM fobs f, wibbles w
WHERE w.parent_wibble = f.id

You can see we select the wibbles where their parent matches the current wibble. The results of both queries are then combined using ‘UNION’. Which removes duplicate rows (more on this later). This gives us a Common Table Expression which we use as before:

SELECT * FROM fobs;

If we adjust our starting point (base case) query, we’re able to find the descendants of a particular wibble:

WITH RECURSIVE fobs(id, fub, parent_fub) AS (
     SELECT id, fub, ( null :: varchar(8) ) FROM wibbles WHERE fub = 'chair'
     UNION
     SELECT w.id, w.fub, f.fub
     FROM fobs f, wibbles w
     WHERE w.parent_wibble = f.id
)
SELECT * FROM fobs;

 id |  fub  | parent_fub
----|-------|------------
  1 | chair |
  3 | fudge | chair
  4 | choc  | fudge
  6 | feet  | fudge
  7 | pants | choc
(5 rows)

Now with one query we’ve found the parent wibble and their descendants!

chair
|
`- fudge
   |
   +- choc
   |  |
   |  `- pants
   |
   `- feet

Neat! Notice that the result of a recursive query is a normal table of results. We can order results, filter them with WHERE clauses. All the other useful relational database tools are available to us.

The recursive component of the query can also have restrictions on it to limit the depth of your search. In fact it needs them, otherwise your query will never return. Lets add a threshold to stop searching the descendants of chair.

     SELECT w.id, w.fub, f.fub
     FROM fobs f, wibbles w
     WHERE w.parent_wibble = f.id
     AND w.wub < 10

Once the recursive component returns an empty set, the query is complete.

If that was all we could do, then it wouldn’t be worth writing about. But the fun is only getting started! As this is SQL, you’re able to use the built in functions to build new values in the results. You can concatenate strings together, add numbers, use aggregation functions, etc.

SELECT (number_1 + number_2) FROM number_table WHERE number IN good_numbers;

When combined with recursive queries, some very cool functionality becomes available.

But what if you had data that was not a simple tree form? But a proper graph, with interconnecting nodes. Perhaps even some cycles.

How then to traverse such a structure, whilst only being able to access the row of results that sent you here in the first place? The answer is both infuriatingly obvious, and chock full of possibilities for cleverness.

The answer is to keep track of where you have been, and you’ll be able to decide if you’re still on the right path.

  • Me: “See, simple! Now draw the rest of the owl.”
  • Concerned Reader: *squints*

If these next examples seem familiar, it’s because I copied them verbatim from the PostgreSQL manual page on ‘WITH’ Queries. The documentation is very comprehensive and I recommend checking it out.

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
    SELECT g.id, g.link, g.data, 1,
      ARRAY[g.id], -- <-- A
      false
    FROM graph g
  UNION -- <-- B
    SELECT g.id, g.link, g.data, sg.depth + 1,
      path || g.id, -- <-- C
      g.id = ANY(path) -- <-- D
    FROM graph g, search_graph sg
    WHERE g.id = sg.link AND NOT cycle -- <-- E
)
SELECT * FROM search_graph;

This query will:

  • Navigate the graph’s structure
  • Keep track of the nodes we’ve visited
  • Prevent any cycles from causing the query to loop forever.

There are quite a few pieces involved, some are general concepts. Others obscured by PostgreSQL specific operators or functions. We’ll go through it and see if we can make it a bit more digestible.

We’ve covered the larger mechanics involved, such as WITH RECURSIVE foo AS. So you should be able to identify the primary components of this recursive query. The base or starting query, and the recursive component.

Other parts have some marks against them and we’ll check them off in a bit more detail. I would like to mention that anything here is unlikely to only exist in PostgreSQL. So you don’t need to get all shirty about; “OMG MySQL can do this too !!eleventy".

We’re using PostgreSQL at the moment, so roll with it.

A

This is the PostgreSQL syntax for initialising an ARRAY with a starting value. The purpose is to create the value for tracking our visited nodes as we traverse the graph. We’ll be updating this value later.

Remember that this is our starting or base query. So it must have a value for everything we want to have in the final result. The types must match up.

If you want to find out more about PostgreSQL Arrays, the docs are really quite nice.

B - More on UNION [ALL]

The use of UNION is what combines the results so far, with the results from the next iterative step. The keyword UNION will combine query results and remove duplicate rows.

When used with the optional ALL keyword, it will not remove duplicates. This may produce unexpected results, or in some cases cause the query to loop forever.

C

PostgreSQL syntax for concatenation. In this case it is pushing the g.id of the current node onto the list of visited nodes. If this result in the iterative or recursive component satisfies our WHERE conditions, then the id value is added to the ARRAY.

From the PostgreSQL docs on the concatenation operator ||:

“The concatenation operator allows a single element to be pushed onto the beginning or end of a one-dimensional array. It also accepts two N-dimensional arrays, or an N-dimensional and an N+1-dimensional array.”

You’re of course free to create other structures as you traverse the results. Calculating the cost of arriving at a particular node? Min-Cost-Max-Flow in a query, anyone?

D & E

This is a PostgreSQL expression that combines the expression and the operator of the left of the ANY. Applying it to every value within the array value on the right side. Consulting our very helpful docs again.

expression operator ANY(array expression)

In our case, we use this function to check if the id of the node we’re currently on has exists on the path. This lets us know if we’ve stepped onto a cycle. This expression in our query will return true or false.

We’re able to then use this value in our WHERE clause to avoid including any results where a cycle has been detected. When an empty result is returned from the recursive component of the query, the traversal is finished.

Aside “Why aren’t cycle and path accessed using ‘g.’ ?”’

Note the use of the aliased table names, and that path and cycle are not referenced in the same way; g.id or g.link. This is because these fields only exist on one of the two tables we’re querying, the graph table. So PostgreSQL is not confused about where the field is coming from.

Back to our wibbles…

If we create a similar query for our wibbles. We can see something that can be very very useful when dealing with graph and tree traversals.

Here are some results:

 id |   fub    | wub | parent_wibble |   path    | cycle
----|----------|-----|---------------|-----------|-------
  1 | chair    |   0 |               | {1}       | f
  2 | lavalamp |   3 |               | {2}       | f
  3 | fudge    |   1 |             1 | {1,3}     | f
  5 | cake     |   9 |             2 | {2,5}     | f
  4 | choc     |   2 |             3 | {1,3,4}   | f
  6 | feet     |   8 |             3 | {1,3,6}   | f
  7 | pants    |  11 |             4 | {1,3,4,7} | f
(7 rows)

You don’t have to select things like the cycle or any other column you don’t need in your final results. But you notice in the path column that we constructed, we can see HOW we ended up at a particular result. This is invaluable for debugging.

It may have other applications, but that’s between you and your data. You could present informative, “You’re seeing this because…”, messages for your users, as an example.

Performance

Recursive queries are an expensive operation.

The process of;

  • Querying for results, placing them onto a temporary table.
  • Then using those results to query for results.
  • Add those results (optionally removing duplicates) to the temporary table.
  • Repeat.

Is costly when compared to the more traditional types of queries.

The \timing flag in psql will produce timing information for individual queries in the REPL.

Examine the output of EXPLAIN to see what, if any, optimisations the query engine is able to perform. The use of Common Table Expressions prevents the query engine from making certain adjustments.

With any “performance concern”, there are few hard and fast rules. Excepting that YOU must examine YOUR use case with YOUR data to be able to make a sensible decision.

Conclusion

If you have or were looking to have some graphs as part of your data design. But weren’t sure on how to manage the data. Or how to integrate it without needing yet another application. Or you weren’t interested in writing all that graph traversing/managing code yourself. Recursive queries may be what you need.

I had a lot of fun learning about recursive queries. I hope I’ve been able to shed some light on a very useful tool. Also that I’ve explained them well enough that you feel confident in applying them.

Maths by Discovery!

I’ve been part of a few discussions recently that have been centered around how awesome maths is. Just how much of it can be used to improve your own programming capabilities, and improve the lot of programming for our entire industry. Both as a tool for designing and building, but also for analysis of new concepts and ideas.

Sadly these discussions usually also turn to lament the current state of mathematics instruction. There is often a feeling that the systems are being drilled into us so that we can provide “the right answer” when it is requested of us. There is no sense of discovery, if we are presented with a problem we cannot solve, it must be because we weren’t taught the techniques we need. What else could it be?

Maybe we were taught the right techniques but we were passing notes that day? Maybe we were taught the techniques we needed but we didn’t know that those techniques could be applied in this situation. We look at those people that are “maths people” or “good with maths” and are often left in wonder as they apply these arcane techniques. We throw up our hands and declare ourselves “bad at maths” or just “not a maths person”.

But as some point out during our discussions on these topics, someone points out that this is a crap excuse as there is no such thing as a “maths person”. We simply haven’t found our feet yet. As part of this post I will present my thoughts on a different way of teaching maths and some of the processes around it. I should probably point out that I am one of the “not a maths person” people. I’ve only recently rediscovered mathematics and I’ve still so much to learn. But I’m having a great time doing so, and it would be great if I could share this with more people.

So without further ado, lets get on with the crazy and see where we end up.

Maths by discovery!

A little bit about the problem.

As I alluded to earlier in this post, one the problems presented by the current maths teaching is that we are expected to know ‘the formula’ that is to be used in a given mathematical context. This memorised truth will provide the correct answer provided our rote skills were up to the task. If you don’t know the forumla then you’re either bad at maths or you didn’t pay enough attention that day in class, or some combination there of.

This occurs at even the most basic level, with the droning repetition of the ‘multiplication tables’. 3 * 3 = 9.. 3 * 4 = 12.. 3 * 5 = 15.. and so on it went. Even addition is taught in the same manner, drumming various simple formulae into our heads.

But how else can we expect children to understand? Not treating them like idiots would be a good start, but that’s not possible with the mechanised, standard test driven, approach that is currently used. Why do we wait so long to introduce things like algebra and calculus? These topics are hard right? Well, yes and no..

They are difficult concept if the only thing you’ve ever seen is a number based equation that contains occurrences of problems you’ve been forced to memorise through threats of failure. But just like addition, multiplication and friends, these are built on a grounding of core concepts that are themselves quite simple.

Break the cycle.

So how can we shake things up? Well for a start we need to focus on the how and why of maths and mathematical reasoning. This analogous to the adage of “Give someone a fish, they are fed for a day. Teach them to fish and they will eat for the rest of their life”.

Teaching someone their ‘multiplication tables’ is not required if they understand the core concepts around HOW multiplication works. Sure they might be faster with some calculations cached ahead of time. But with the core concepts learned and practiced then there is no calculation that is beyond them because they understand the mechanism that makes the magic happen.

After long you don’t even need to include numbers in the discussions around the concepts that are being discussed. You’ve cemented the core concepts and suddenly you’re in a position to be able to move to more advanced concepts and build on what exists.

Let’s start with a simple example…

The problem: Define a new operator that demonstrates what happens to the count of apples in a box when a bucket of apples is emptied into it.

Lets call our new operator, bucket. So a simple expression may be

0 bucket 5 = ??

For the sake of argument, the apples fall out of the buckets one at a time into the box. So our expression above becomes

0 bucket 1 bucket 1 bucket 1 bucket 1 bucket 1 = ??

Now as some very clever people have already made plain, there are many aspects of maths that are just Fancy Counting. You count from the value on the left to the end if you will, of the value on the right. Similar to standing there and counting each apple as it fell from the bucket into the box.

We know what addition is DOING now so we can write the first solution using our bucket expression:

0 bucket 1 = 1
1 bucket 1 = 2
2 bucket 1 = 3
3 bucket 1 = 4
4 bucket 1 = 5

Phew, that was annoying but now we know exactly what our addition is doing. It’s counting along from our starting value on the left, it stops when we’ve counted the number of steps provided on the right. However what we have written above now highlights two patterns that are crucial to understanding addition..

The first is what we’ve already mentioned, we’re just counting. Our addition follows a distinct pattern that is easy to follow and replicate. But also it allows us to simplify our bucket operation to something more useful, more on that in a moment.

The second thing to notice is that we have established the Law of Commutativity as it applies to addition. Based on what we know about how our bucket operator works, we know that it counts, starting from the left value, and stopping after we’ve counted the number of steps on the right.

So from our previous example…

2 bucket 1 = 3

1 bucket 2 = ??
	## Count out the steps
	1 bucket 1 = 2
	2 bucket 1 = 3

1 bucket 2 = 3 tada!

We’ve done nothing but count from zero to five and we know two vital aspects of how addition operates. Most importantly we know what addition does and how it actually goes about doing it.

Now we can afford to make some assumptions to speed things along and make our lives a little easier. So..

2 bucket 2 = 4
0 bucket 5 = 5
5 bucket 0 = 5

This is awesome, you’ve just defined your own addition operator and you understand the underlying mechanism of how it actually functions. But this isn’t too dissimilar from the sort of introduction that probably occurs already.

Demonstrating these things on the board in a class room won’t really change things since you’re still working through the same steps you might normally work through. But it’s 2014 and we have access to some amazing tools that can provide a very interesting perspective on these otherwise mundane exercises!

How can we advance these sorts of teachings so that we’re able to demonstrate that so much of mathematics is a combination of very simple steps. How can we empower students understanding such that the idea of new operators or techniques doesn’t immediately mean pages of droning exercises? What if they were able to prove they had an understanding of how the concept operated?

Thankfully we have the capability to do all of that! Lets use multiplication to demonstrate these ideas, building on our shiny new bucket operator which we’ll define first, then showing how it can be used to make multiplication work.

But first there is something we need to discuss.

Interlude about Tools

The tools I will use for this demonstration are the Coq Language and its interactive companion CoqIDE. Although they may seem heavy handed for the task at hand, the capabilities and design of these tools provides a unique method for teaching even the most basic fundamentals of mathematics.

A common mistake would be to start quibbling over syntax or fit for purpose, excessive complexity, or suitability for a class room that is not a university level mathematics class. I don’t particularly care for any opinions on the aforementioned topics because it means you’ve missed the point about what I’m trying to convey.

There may be plenty of other options for environments other than Coq that could be suitable. I will not touch on the specifics of why I chose it in this article, it will most likely come up in part #2, when or if there is one.

We will continue to use our examples from before to demonstrate the next steps of the process. But we also need to introduce some additional rules that will help to keep things sane and relatively easy to follow.

Firstly we will discard the use of numbers as denoted in our original examples. Since we’re after an understanding of the core meaning here, the numbers themselves do not aid us and can be safely ignored. We will however maintain the use of whole numbers equal to or greater than, zero. Or natural numbers.

As per many a canonical example or implementation for Coq, we will use the following definition for our numbers. They can be either Z, which is zero. Or S n, which represents the successor of another natural number. To represent 1 that is simply the successor of zero so S Z = 1.

Inductive nat : Type :=
	| Z : nat
	| S : nat -> nat.

Depending on your audience you may simply hand-wave this away or explain its relevance in more depth. That is entirely up to you. Its purpose is to provide a mechanism for understanding how whole numbers that are equal to or greater than zero work. So that we’re able to keep our definitions simple. Lets keep moving!

Let’s re-define our bucket operator based on what we know..

Fixpoint bucket (n : nat) (m : nat) : nat :=

This first line could be described as mere ceremony, but it gives us a more concrete perspective of our bucket operator. But also clues to other important facts. For our purposes, the Fixpoint at the beginning of the line, for those interested, denotes that we’re about to define a recursive function.

We then name our operator and indicate that it will accept two inputs, both of which must be natural numbers: (n : nat) (m : nat). This may seem trivial, but knowing a particular mechanism will only be given particular types of inputs ensures that your mind is only focused on what is important to its operation.

Finally we declare the result of our operator will be another natural number: : nat. This, like the previous point, may seem like a trivial thing to mention. But like most of mathematics, we need to construct a solid foundation of concrete principles that can be absolutely relied upon. In this case, we declare that our operator will only ever provide us with natural numbers. This ensures that we always know what we’re dealing with when we use it. We don’t have to ponder or consider it, we know.

Now we come to the meaty bit about defining, precisely, how our bucket operator works. Recall that it simply counts, starting from the left value, a number of steps indicated by the value on the right. Only now we must define something that works for any natural number that is provided. Let’s layout our definition and walk through it afterwards:

Fixpoint bucket (n : nat) (m : nat) : nat :=
	match m with
		| Z => n
		| S m' => S (bucket n m')
	end.

Woah nelly there is a lot going on there!! Or is there? If you look closely there are only two lines with which we need to concern ourselves with. The rest fall away as mere syntax or mechanics. The first point to examine is: match m with. This means the following expressions are concerned with the current value of m. This is great for us because it means we can further narrow our focus.

Lets examine our first line:

| Z => n

We know that we’re only looking at the value of m, and we have to decide what we’re going to do if it’s currently a value of Z, or zero. Remember that we’re building addition, and if you take a journey of zero steps, where will you end up? Right where you started! So if someone attempts to n bucket Z then, we know that zero steps from n is n. Woo!

Now lets have a look at the next line:

| S m' => S (bucket n m')

Now we’re doing something a little more interesting. Remember that we’re only looking at values of m. We’ve already handled what happens when m is zero, so now we’re dealing with whenever m is greater than zero, or any S of any other natural number.

When we match like this we’re in effect reducing the value of m to the next lowest number, because we know that S (S Z) is two, and we’ve matched on m thus S m'. So using two as example the value of m' is now S Z because we’ve reduced it by one.

This line is performing one step of our bucket definition. The extra step inside the brackets calls our bucket operation again using the reduced value of m. This ensures that our operator will take as many steps as is required, all the way to zero (Z) and ensure our starting place n is incremented by the correct number of steps. Because when we reach Z for a value of m, our operator will return n wrapped up in the correct number of steps. Producing our new value.

Okay, but… WHY!?

This may seem all funky and weird and why on earth would you try to explain addition that way?! Because we haven’t taken the route of simply droning on with 2 + 2 = 4, 2 + 3 = 5, 2 + 4 = 6 ad infinitum in order to get our point across. We’ve explained the core concept of addition in a way that is reusable and free from the dangers of learning by repetition. Since we’ve conveyed the underlying framework, there is now the foundations for understanding the next thing we explain at a deeper level.

Because we’ve approached this instruction by breaking things down, the same approach can be applied to teaching multiplication. With the added bonus that we can reuse a student created operator, bucket, to help define how multiplication works. This helps demonstrate how mathematics is a sequence of very small steps applied to a much larger problem.

The depth that which the smaller steps is understood, allows for much greater confidence when presented with far more complex problems. This means we’ve begun, and continue with, teaching mathematics by teaching the techniques of problem solving instead of teaching them how to use the formulas they are given.

If a student is already used to decomposing a problem into smaller pieces, identifying what is required at the smaller stages, and working through them. They will already be practiced at establishing their own solutions, or at the very least identifying what is missing. If they can do this, then once limits have been reached, or after problems have already been solved. Introducing the students to formulae that exist for given problems, or well established mathematical techniques provides immense value.

Because you’re no longer saying “use these formulae for these problems”. You’re supporting and empowering their discoveries by presenting work that suddenly has so much more meaning because it is directly connected to their efforts of trying to solve the problem. For some it will validate their efforts, others it may provide the direction they need, or the final piece of the puzzle for others.

The point is to teach techniques for discovery and investigation. To teach skills for creating solutions to the subproblems and techniques for confirming that their solutions will work. Something that most maths teachers have been trying to do for quite a long time no doubt! But the point of this is not to say that maths teachers are doing it wrong, but that the constant repetition is potentially harmful. That it may in fact prevent a deeper understanding of the concepts they are trying to teach.

This may lead to increased difficulty in understanding newer concepts because the same repetition has left gaps in the understanding of core concepts. They’ve just been accepted as correct “because the teacher or textbook said so”.

Finale

To wrap up this particular diatribe, we will continue our little lesson and explain multiplication using the same techniques we established earlier. As well as reusing our bucket operator to demonstrate the reusability of various mathematical concepts as you work towards a larger solution.

Before we begin with defining our new spintastic operator, as before we need to clue in to how it will actually function. What does it DO.

Based on our previous investigations we know that addition is a form of Fancy Counting, and if we examine multiplication it’s highly likely we’ll discover that it is simply more Fancy Counting.

Lets examine the term, ‘multiplication’, similar to addition the term gives us clues as to what it is expected to do. Addition is a process of changing a value by moving a given number of steps from a starting value. 2 bucket 3 produces 5 because we start at 2 and add three more steps to end up at 5.

Multiplication on the other hand is dealing with ‘multiples’. If 5 is the result of adding 2 steps to 3. Then 2 spintastic 3 will produce a result of 3 multiples of 2, or 3 occurrences of 2. This seems like a form of Fancy Counting to me. Lets try it.

2 spintastic 3 = ??
	2 spintastic 0 = nothing ! We have no 2s
	2 spintastic 1 = one 2
	2 spintastic 2 = two 2s
	2 spintastic 3 = three 2s, or [2,2,2]

Well this is interesting, now we have 3 occurrences of 2, or a list of 2s. That doesn’t tell us much though because that’s simply another way of expressing what our spintastic operator is telling us. How can we reduce it to a more simple value? Maybe a final result even!

If you have three piles of two apples in our box, what is one way we can easily determine how many we have? We add them together of course. You have three 2s, so we can take our list of occurrences and simply add them all together to find out our final result!

So…

2 spintastic 3 = ??
	2 spintastic 0 = No 2s
	2 spintastic 1 = 2 (we only have one 2, nothing to bucket!)
	2 spintastic 2 = 2 bucket 2 (getting interesting)
	2 spintastic 3 = 2 bucket 2 bucket 2 (oooh!)

So multiplication is just Fancy Counting after all. Multiplication is just the result of counting all the ‘multiples’ of some other value or occurrence. Do you think we know enough now to be able define our own spintastic operator like we did with bucket? Let’s try.

Fixpoint spintastic (n : nat) (m : nat) : nat :=

Does that seem familiar? Of course it does, it’s nearly identical to our bucket definition from earlier! We’re being very particular and specifying that our spintastic operator will only work with numbers that are equal to, or greater than zero. We also only want a single natural number as a result of this operation. In this case it’s no use to have our operator give us back a list of natural numbers, because we already know that’s what spintastic means.

Lets fill out our definition and discuss…

Fixpoint spintastic (n : nat) (m : nat) : nat :=
	match m with
		| Z => Z
		| S m' => bucket n (spintastic n m')
	end.

Yee gads! Remember fear is the mind killer, the little death that brings total oblivion. There is nothing that we here that we have not already covered or explained. We’re just trying to express our flimsy wordy definition in a concrete form. As before we’ll work through it line by line.

match m with

Nothing new here, as with our bucket operator we’re using the second value m to ensure we create the correct number of multiples of the first value n. We’re just counting.

| Z => Z

This is different! But remember that when you’re counting, if you have nothing of something, how much do you have? You have nothing! This is different to counting with bucket because when we’re counting with bucket we start with one value, and then start stepping. However with spintastic we’re not starting with anything, so if we have zero multiples of something, then we have nothing.

Conveniently this expresses one of the laws of multiplication, in that anything multiplied by zero, is zero! Again, by simply working through how something works at its core, you’ve stumbled on and defined one of its laws.

| S m' => bucket n (spintastic n m')

This is a little more hairy isn’t it? Well, not really. Since from before we know that the S m' is simply us counting down our m value. Because we’re _counting the number of multiples.

But that next part is interesting…

bucket n (spintastic n m')

Recall from before that we’ve established spintastic is Fancy Counting, and that we’re simply counting the occurrences of one of the values, n. Also in order to achieve our final result of one number we need to bucket everything together. But we’re not counting single steps this time, we need bucket together every occurrence of one of our numbers.

So for 2 spintastic 3

spintastic 2 3 =
	bucket 2 (spintastic 2 2)
	bucket 2 bucket 2 (spintastic 2 1)
	bucket 2 bucket 2 bucket 2 (spintastic 2 Z)
	bucket 2 bucket 2 bucket 2 Z

Remember we know that anything bucket Z is the value of simply the value of anything, because we’ve not taken any steps. So we can discard that and our result becomes.

2 spintastic 3
= 2 bucket 2 bucket 2
= (2 bucket 2) bucket 2
= 4 bucket 2
= 6

Show your working. ;)

In this example you can see how we used our existing knowledge of the rules of bucket or addition, and we were able to apply this knowledge to determining how multiplication works! Except instead of forcing the memorisation of multiplication tables for treats, I mean grades. We broke the operations down to its fundamentals and exposed the core mechanism that made it work.

In doing so we demonstrated that one mathematical concept can be explained by using the mechanism of another. We demonstrated that multiplication is another form of addition, both of which are instances of Fancy Counting. One can in fact define one in terms of the other!

We not only exposed how both operators work underneath, but we also revealed some of the laws that apply to them. As an exercise to the reader you can go back to the spintastic operator and see if you can work out what happens if you swap the left and right values around.

Actual Finale

Hopefully you can now see how changing how some aspects of mathematics are taught can completely change the approach to various problems. We remove the aspect of repetition and replace it with investigation and discovery about underlying mechanisms. The aspects that are repeated are techniques for problem solving and breaking down big problems to little ones, building on previously acquired knowledge to enhance our understanding.

I sincerely hope you do not focus on the syntax of my explanations or get hang up on my suggestion of Coq as a tool that could be employed for this sort of instruction. As truly that is far from the point I am trying to make. I am not trying to turn every maths lesson into a programming session and if I’ve conveyed my point sufficiently you will see that it is not what I suggest.

The point is shifting the focus from repetition and memorisation of formulae that are applied in arbitrary situations, to a concentration on pure problem solving techniques such as; Analysis, investigation, experimentation, and discovery. I dare not assume that this approach will work for everyone, there is no such thing! But by focusing on maths as a process of dissection, analysis, discovery, and invention. We might just open more minds to what is possible.

My mum thought it was cool.

If you aren’t aware of the existence of Lisp Flavoured Erlang then you really need to get on that. It is a thing of beauty, combining the true deliciousness of two amazing languages - Lisp & Erlang. This post assumes you’re aware of LFE in some capacity and I will continue without regard for your level of interest.

Primarily because this is a “My Crazy Idea Post(TM)”. You’ve been warned.

Specs and Types

Currently in LFE there is no method (that I know of) for defining type specs for the Dialyzer system to interrogate. So whilst in Erlang you can incrementally provide greater information about your functions like so:

-spec(add_one(number()) -> number()).
	add_one(N) ->
	N+1.

This is something that, because of a slight obsession with Haskell and Idris, is something I’m quite interested in making happen. Additionally taking inspiration from the brilliant “Typed Clojure”. It seems like this is something that LFE could draw some real power from.

I am partial to static types and I am the sort of person that considers them to be a real boon to nearly any application. That said I am able to understand the benefit that comes from ‘incrementally typing’ an application. Providing a base level of surety around certain functionality and expanding it or reducing it as required by emergent circumstances.

My Cray-Cray-Type-Type Idea

LFE is of course a Lisp, and so many of you might be wondering why I don’t just write some macros and call it a day. First, I don’t think macros in LFE can do this because there is no way to generate the spec information in the first place. There may be scan/parse steps involved to generate the attribute information. I don’t think that it’s a huge job but it’s not done yet so I would have to take that into account.

The more I read about Dialyzer the more it seems that simply including support for it within LFE would provide some seriously amazing benefits. If you’re the sort of loon that likes these shenanigans. Pimping it out with a dash of extra functionality could prove useful too!

Such as the so operator from Idris in this highly contrived example:

;; A required persistent truth.
(defun targetInZone ['float 'float -> 'boolean]
	((lat long)
		(and (and (> lat 0)
			(<= lat (doge-arena-limit 'latitude)))
			(and (> long 0)
			(<= long (doge-arena-limit 'longtitude)))))
     ((0 0) 'false))

(defun deployDoge [(float x y) -> (so (targetInZone x y))]
	((lat long)
	 (let ((doge (untasked-doge))
	 (retask-doge doge lat long 'such-investigate)))))

Could be kinda cool.

Interestingly the more straight forward application of types to an LFE application could support the match-lambda functionality in weird and wonderful algebraic ways.

(defun foo [[a] 'int -> [a]] ;; Provide a generic function signature here
	((a b) ['list-float 'int -> 'list-float] ;; More specific constraints
		(: lists map (lambda (x) (wow x b)) a))
	((a b) ['list-int 'int -> 'list-int] ;; are applied to each branch.
		(: lists map (lambda (x) (such x b)) a)))

I’ve not spent enough time with these systems to gain a sufficient understanding of how things work together. From just my initial reading the type system available courtesy of Dialyzer is really really powerful. I am quite literally just thinking out loud about things I think could be fun/cool/useful and not necessarily in that order.

Because this sort of thing in Haskell is sweet.

foo :: [a] -> (a -> b -> a) -> [a]

Dialyzer supports something similar, although you notice the lack of support for the type of the second argument being different to the first.

-spec foo([any()], fun((any(), any()) -> any()) -> [any()]

As some of you may have noticed though, the type specification above includes the deliciousness of polymorphic types. Which in ultra-simplistic terms means types that can take other types as arguments. In the example above, [any()] is an example of a polymorphic type, list(integer()) would be another. This is a tremendously sexy feature and can be used to great effect when documenting, err, I mean typing, your application.

Similar to Haskell (I said similar, go rage somewhere else) you are also able to specify your own types in a module and construct your own type classes, in a manner of speaking! Jumping the gun here as I’ve not finished my initial readings on the intracacies of type classes but here is an example from Learn You Some Erlang on Dialyzer.

-type red_panda() :: bamboo | birds | eggs | berries
-type squid() :: sperm_whale
%% The type for Food is determined in the specification later on
-type food(A) :: fun(() -> A)

In our LFE system we could have something like

(deftypes red_panda_food '('bamboo 'birds 'eggs 'berries)
	squid_food '('sperm_whale)
		(food a) '((fun '() -> a)))

In Erlang the above types are used in specifications like so:

-spec feeder(red_panda) -> food(red_panda());
	(squid) -> food(squid()).
-spec feed_red_panda(food(red_panda())) -> red_panda().
-spec feed_squid(food(squid())) -> squid().

For our delicious LFE version it’d be neat to leverage this awesomeness:

(defun feeder
	#| Match lambdas could support more generic type signatures to enable a quick
		understanding at a high level, with more precise return types being available |#
	['atom -> a]
	((red_panda) [(food red_panda_food)]
		...)
	((squid) [(food squid_food)]
		...))

(defun feed_red_panda [(food red_panda_food) -> red_panda_food]
	(...))

(defun feed_squid [(food squid_food) -> squid_food]
	(...))

There are obviously nicer ways to handle it and I am going to play around with a few different options to see if anything sticks. I’d like to be able to replicate a Haskell type signature style, predominantly because I believe it to be clear and flexible without adding too much noise.

But that’s not even a concern at the moment since (in case you hadn’t noticed) I still have so much to learn regarding the functionality that is offered by Dialyzer and type systems in general. The growth rate of my reading list shows no signs of abating and like everyone else I must content with ‘real world’ things, I’ve no idea of how much I will be able to commit to this. :(

This post is mostly me just airing my thoughts on this, so don’t expect a link to a repo with a PR to try out or papers in progress under my name (on this topic). I think LFE is one of the most awesome languages around at the moment, even from being neck deep in Haskell and Idris experiments. Type systems have so much to offer when they are built to function as a system for stability, surety, and documentation.

So I think LFE could, COULD, really benefit from having access to this sort of functionality and I sincerely hope I will be able to provide a meaningful contribution. All the same, I think it’d be hell cool to be able to whip out super powerful BODOL style types within your already magnificent distributed Lisp app!

Hopefully more to come ! :)

Manky

Sean Chalmers


Software Engineer - Lisp & Haskell Neophyte - NERD of Clan Emacs!

Find Me On: