00:00:14.910
Thank you all very much for coming. This is actually the first conference I spoke at in 2010, and it's really nice to come back here and talk about recursion today. By way of a brief introduction, I'm James. In terms of Ruby, I created a project called Fae, which includes a bunch of WebSocket functionality and is part of the stack that makes up Action Cable. However, I'm not really going to focus on Ruby so much; instead, I'll discuss other languages and several ideas connected by the concept of recursion and why it is important.
00:00:37.180
At one time, recursion was a highly contentious idea in programming. There was a lot of debate in early programming language design about whether it should be included, but now we take it for granted, and we're quite comfortable with it. For example, if you want to recursively delete a directory, you simply start with a file and delete it. If it’s a directory, you must delete everything inside it first, as you can't delete an empty directory. You look up the children of the directory, delete each of those recursively, and then remove the directory itself.
00:01:06.560
Likewise, if you want to spider a website or even the whole internet, you start with a URL. You access that URL and retrieve the corresponding page, then find all the links within that page. For each of those links, you repeat the process recursively. By doing this, you can end up reading the whole internet if you run the program correctly. We are accustomed to writing recursive functions but often overlook recursive structures.
00:01:22.390
We create recursive structures all the time, such as when generating HTML or organizing files on disk. However, we don't necessarily think about these structures in terms of their power and meaning. Let's focus more on these structures and what they can achieve. For example, in JavaScript, inheritance works through a special field called ‘proto.’ When you create an object, its prototype points to another object, creating a chain between them.
00:01:56.490
When you look up a property or invoke a method on an object, JavaScript checks whether the property exists in that object. If it doesn’t, the interpreter looks up the prototype chain to find it. This recursive chain of prototypes helps implement inheritance, and the structure itself allows you to understand how it functions. I would like to explore recursion's importance in three main areas: correctness, performance, and meaning.
00:02:39.670
Let’s start with correctness, specifically, the ability to prove that programs behave as expected. In Ruby, we often use unit testing to confirm that our programs are correct, but unit testing alone is not proof. You can run many unit tests for a program and still not discover bugs. Proof means knowing that something is correct for all possible inputs, and recursion provides a method for proving this.
00:03:02.890
The principle of mathematical induction follows a recursive argument: you assume the property holds for a base case and then use that assumption to prove it for the next case, such as from 'n' to 'n + 1.' For example, if you want to find the sum of numbers from 1 to 'n', you observe that the sum follows the pattern of 'n * (n + 1) / 2.' While you may confirm this with numerous examples, it’s the recursive argument that leads to a proof.
00:03:31.360
For arrays in Ruby, the definition is relatively straightforward, consisting of flat lists of values. In functional programming languages, like Haskell, lists are defined recursively: a list is either empty or consists of a value paired with another list. For example, the list [1, 2, 3, 4] can be represented as one paired with the pair of two paired with three paired with four and then the empty list. This representation forms a recursive structure, akin to a binary tree.
00:04:14.460
In imperative languages like Ruby, we typically define processes for calculating the length of a list or mapping over it. For length, we might start with zero and increment it for each element. To map over a list, we create a new array and compute the result of applying a function to each item, preserving the order. By contrast, in functional languages, definitions express relationships: the length of an empty list is zero, while the length of any other list is one plus the length of its remainder.
00:04:49.439
Mapping over an empty list produces an empty list, and mapping a function over any other list involves applying that function to the first element and then mapping it over the remainder. In Haskell, programming is less about procedural instructions and more about stating that certain relations exist; you express the relationships and let the language handle computation. For example, for the functor composition law: if you map a function G over a list and then apply another function F to the result, it is equivalent to mapping the composition of F and G over the original list.
00:06:38.869
To prove this from a list perspective, take a list with an extra element. For instance, using the definitions of map and previously assumed statements, we can recursively derive compositions. This works even for structures like trees and graphs. Such programming constructs enable the efficient expression of operations through recursion. In contrast, imperative languages require explicit sequences and step-by-step states.
00:07:35.830
In cumulative structures, such as filtering or appending operations in Haskell, the relationships are defined in terms of the underlying types. For example, filtering on a list yields another list depending on whether an element fits the condition or not. The Haskell approach inherently supports lazy evaluation, which allows computations to defer until the results are needed.
00:08:21.160
Now, let’s turn to performance. In performance-driven programming, we often want things to complete quickly. Optimizing performance manually can be quite difficult; however, recursion can be an effective way to express solutions that allow compilers to leverage optimizations. Let's discuss a practical example regarding compiling CoffeeScript files into JavaScript.
00:08:54.950
Imagine you are compiling multiple CoffeeScript files into JavaScript to serve on a website. One approach is to utilize a Bash script. In this scenario, you would set up a directory to store compiled files and iterate through the source files to run the compiler, concatenating the generated files into one artifact.
00:09:37.110
Alternatively, using a Makefile could illustrate a more optimized approach. The Makefile describes the source files and their relationship with the compiled JavaScript outputs. When executed, it does all of the necessary tasks, efficiently managing dependencies between files. If you were to modify just one source file and rerun Make, it only recompiles that specific file, greatly reducing execution time.
00:10:37.480
The benefit of using the Makefile lies in its ability to describe project structures and dependencies effectively. This allows Make to determine the necessary compilation tasks efficiently, reducing redundant processing. As a result, relative changes can yield substantial improvements in performance, while still ensuring correct output. Recursive structures are prevalent in many programming paradigms, yet not all environments exploit this potential as fully as others.
00:11:17.520
The recursive nature of many programming languages allows for optimizations and operations that manifest only when you express concerns around dependency and performance. Another example of this can be seen in functional programming languages like Haskell where constructs are defined in an optimally recursive manner, inherently allowing lazy evaluation of data and structures.
00:12:14.660
The discussion now leads us to the intriguing topic of time travel in programming, the notion that you can run programs backwards. In general, in Ruby, functions take inputs and yield outputs, and you cannot simply provide an output to ascertain what inputs might have led to it. However, certain languages allow for this type of reverse engineering based on the structures involved.
00:13:14.320
For example, consider a language called Micro-Caml. In this language, variables and pairs are defined in simple terms: a variable has a name, and a pair consists of left and right fields. This forms a base structure for building other data structures, allowing for manageable manipulations and alterations of state. When a state is created, it is immutable; you build a new state whenever a change is required.
00:14:09.630
In the Micro-Caml context, we deal with both walking and unification operations. Walking resolves the value of a variable without traversing all of the possible states, while unification attempts to return a new state in which two elements are equal, utilizing the structure of pairs effectively. By implementing goals as functions and expressing the necessary conditions and states, you can compose these operations in various ways.
00:15:05.620
By composing goals, you can form general-purpose computations, akin to a Turing machine. The results can yield meaningful relationships through assertion and definition, leading to computations that appear to know how to operate, even if they don't possess inherent knowledge. Rather than specifying imperative instructions, programming this way expresses relationships and constraints, allowing computations to follow naturally.
00:16:01.440
In summary, recursion and its related structures present significant opportunities for programming. The big picture involves understanding the different methods of utilizing computers to solve problems. One approach involves explicit problem-solving through prescribed instructions, while the other favors expressing relationships and leveraging these structures to derive solutions automatically.
00:16:51.630
The latter represents a movement towards type-2 programming, where the emphasis lies in shaping the structure of a problem rather than crafting the mechanics of a solution. I encourage you to reflect on how you represent problems and find opportunities for your applications to adopt a more structural approach to programming. Thank you very much for listening.
