Ruby Video
Talks
Programming with Something
Tom Stuart
@tomstuart
#ruby
#functional-programming
#abstract-syntax-tree-ast
#programming-languages
#ruby-internals
#procs
Summarized using AI

Programming with Something

by Tom Stuart

In his talk "Programming with Something" at RubyConf 2021, Tom Stuart explores the concept of manipulating programs as data structures using Ruby. His presentation builds on a previous talk from 2011 titled "Programming with Nothing," where he demonstrated the power of using procs to represent data structures and perform operations in Ruby. The key topics he discusses include:

  • Representation of Value: Stuart explains how Ruby’s procs can encode numbers and data structures. He illustrates how to encode and decode numbers, demonstrating that even complex structures like lists and pairs can be processed similarly.

  • Implementation of Custom Objects: The talk encourages implementing personal data structures instead of relying solely on Ruby's built-in procs. By creating custom implementations, programmers gain a deeper understanding and control of the functionality behind their code.

  • Evaluation Logic: Stuart emphasizes the need to evaluate the structures created and outlines an approach for interpreting them, drawing on concepts from computational theories, particularly referencing Alonzo Church’s work on expression reduction.

  • Decoding Process: He discusses decoding the results back into useful information, introducing constants within the abstract syntax tree to facilitate the conversion back to recognizable Ruby values.

  • Performance Optimization: Towards the end, Stuart compares the efficiency of his implementations with Ruby’s performance, discussing methods to enhance speed, including using the secd machine, first proposed by Peter Landin, which separates the evaluation from rewriting expressions, resulting in significant performance improvements.

Stuart concludes that understanding the underlying mechanisms of programming languages not only enhances one's skill set but also opens up pathways for creating more efficient programming languages in the future. His demonstration of encoding operations like the fizzbuzz illustrates not just the theoretical underpinnings but practical applications of these concepts. He encourages viewers to explore the provided code examples on GitHub, reinforcing the idea that underlying simplicity can lead to powerful expressions within programming language design.

00:00:11.120 Hello RubyConf! My name is Tom, and I'm a senior staff engineer at Shopify. Today, I'm here to talk to you about programming.
00:00:17.760 Almost exactly ten years ago, at the end of October 2011, I gave a talk called "Programming with Nothing" at the Ruby Manor conference in London. Although the details of that talk aren't crucial, I'll briefly summarize its conclusion to build on it today.
00:00:25.439 In that talk, I demonstrated that it is possible to write useful programs in Ruby using only procs. This is because we can encode any data structure with procs and implement operations on those encoded data structures.
00:00:36.480 For example, one way to encode a number as a proc is to call it once with a function p, then again with an argument x, allowing p to be called on x a fixed number of times.
00:00:49.920 So, the encoding of the number three would call p three times. If you're not familiar with the pointy arrow and square brackets syntax, it's simply a more concise way of writing a lambda and call, and I'm using it here to keep the code compact.
00:01:02.640 Not surprisingly, this encoding lets us represent numbers as large as we like, such as five, fifteen, or one hundred. These encodings are legitimate because we can convert them back into Ruby numbers whenever necessary. For instance, if we take the Ruby proc that adds one to its argument and call it on the Ruby zero object three times, we get the Ruby three object. Similarly, this also works for one hundred, and if we call it zero times, we simply get the original Ruby zero object back.
00:01:28.080 The encodings of numbers are not only legitimate, but they are also usable for computation. We can implement operations like increment, decrement, addition, and subtraction in the same way. These operations are a bit complex, so I won't delve into the specifics, but the important takeaway is that they work.
00:01:42.560 For example, I can add an encoded five and three together to yield an encoded eight and then check its Ruby value to confirm the computation. Similarly, I can raise an encoded two to the power of an encoded eight, and when I decode it, I get the Ruby number 256 as expected.
00:02:10.319 We can encode even more complex data structures like pairs and lists, which include operations such as checking for the empty list, fetching the first list item, or obtaining the rest of the items. More complex operations can generate an encoded list of all encoded numbers within a certain range or map an arbitrary function over an encoded list.
00:02:28.879 This framework provides us everything we need to fully implement FizzBuzz, with all its data and operations encoded as procs. At the end of my "Programming with Nothing" talk, I showed that we can inline expand all these constants, which represent other procs, to achieve a complete FizzBuzz implementation that is syntactically just procs.
00:02:54.160 I can demonstrate that by pasting it into a terminal and using some helper methods to decode it into a Ruby array of Ruby strings. There you go! It does slow down a bit towards the end as the numbers get larger, but it takes about eighteen seconds to print them all.
00:03:20.720 So, ten years later, I'd like to explore this topic further. That talk demonstrated that an extremely minimal subset of Ruby is still a fully capable programming language. Essentially, we are leveraging almost all the computational power of Ruby while only relying on a tiny fraction of its features.
00:03:48.000 In this talk, I want us to better understand that fraction by implementing it ourselves from scratch. This involves posing three questions. Firstly, could we represent these encoded values ourselves without using procs and their built-in behavior to represent numbers, lists, and so forth? Could we design and implement our own objects to achieve this?
00:04:00.799 Secondly, if we create our own objects for encoding values, can we explicitly evaluate them and recreate the computational behavior we get for free with procs? Lastly, if we can successfully recreate that behavior and perform computations with our objects, can we decode the results back into useful information afterward?
00:04:25.919 If we can do all three, we would no longer rely on Ruby's built-in implementation of procs to bring our encodings to life. We could construct our own implementation that we understand and control, and I believe that would be pretty cool.
00:04:51.120 Let's start with the first question: can we represent these encoded values ourselves? Can we roll up our sleeves and create our own honest, hard-working, artisanal data structure to represent encoded values, instead of lounging around expecting Ruby to be accommodating enough to let us use as many procs as we desire?
00:05:05.120 Well, yes, I believe we can. Let's consider some arbitrary Ruby value encoded as procs—this was the encoding of the number three. There are really only three kinds of syntax appearing here. Firstly, there are some variables—four in total, named p and x. Secondly, there are three calls. Finally, there are two proc definitions, each with a parameter name and a body.
00:05:17.280 The outer definition has the parameter name p, whose body is another proc definition. The inner one has the parameter name x, which contains the three nested calls. Notice that the parameter name isn't a variable; it's a special syntax for proc definitions to specify the name of the parameter, much like how a method parameter creates a local variable.
00:05:49.920 This flexibility in wiring up connections provides procs with enough computational power to achieve the functionality I described in the previous talk. This simplicity is excellent news because if we want to represent an expression like this, we need only concern ourselves with representing variables, calls, and definitions.
00:06:10.080 Those are the only three structural features visible in any of these encoded values, even in a substantial one like FizzBuzz. You can think of this as a wiring diagram that connects parameters to variables intricately, achieving its computational behavior.
00:06:30.160 We can create our own representation using structs, defining classes for variables, calls, and definitions, each with relevant components. A variable will just have a name, a call will consist of a receiver and an argument, and a proc definition will have a parameter name and a body.
00:06:48.000 To make these structs easier to work with, we can implement an inspect method on each class, allowing their instances to be formatted nicely when we examine them. Now we can create a new variable with the name x, a new call using this variable as the receiver and argument, or a definition whose body contains that call.
00:07:05.680 They will superficially resemble the real thing since these inspect methods format them like Ruby source code. However, they're not real variables or procs; they're structures made from objects whose behavior we control. For instance, we could create a composite structure to represent the encoding of the number three.
00:07:27.120 When we examine the structure of this representation, we see that it resembles a tree. There is a top-level definition including a parameter name, another definition containing yet another parameter name, and within it a call with further nested calls and variables. This kind of structure is known as an abstract syntax tree.
00:07:48.400 Thus, this is the abstract syntax tree of the proc encoding of the number three.
00:08:04.480 Representing these encoded values as trees is not overly complicated. However, if we already possess one of these encoded values as a Ruby proc in memory—like three or FizzBuzz—how can we convert it into our abstract syntax tree representation? I can conceive a few cumbersome methods to do this.
00:08:42.000 One approach is querying MRI for its YARV bytecode instructions, and then we might be able to analyze the proc's structure. Alternatively, we could utilize the disassemble method to generate a human-readable version and process that. If the proc was loaded from a file, we could also use its source location to find out which line it's on and read it in as a string, then apply Ripper from the standard library to parse that string into a structure we can evaluate.
00:09:01.360 However, I'm not keen on either of these options. The first is limited to MRI since YARV is MRI-specific, while the second relies on having the source code of the proc available as a file, which we might not if it was constructed at runtime.
00:09:23.760 Instead, I propose a third option, which involves using the behavior of a proc to reveal its inner structure. This way, we rely solely on the proc's functionality without making any assumptions about its origin or the Ruby internals.
00:09:40.000 For instance, we can query a proc like three about its parameters. This allows us to determine that it has one required parameter, named p. Pulling out the parameter name gives us half of the information we need, but how do we derive its body? We can think about a simpler case, like a proc called identity that returns its argument.
00:10:05.920 From the external perspective, we know that its parameter is called x, but we can't directly access its body. However, we understand that whatever argument we pass into the proc will replace all occurrences of x in its body. So, if we create a variable named x for that purpose and call the proc with that variable, we’ll simply receive the body back—in this case, the variable x.
00:10:21.520 This reveals that the proc's parameter is called x and its body is also the variable x. Now, let’s take another example, a proc called omega, which refers back to itself. We create a variable named the same as its parameter, but when we call that proc with our variable, an exception will occur because its body refers to the square brackets method on the variable we passed in.
00:10:37.520 This retrieves the struct square bracket method, looking up values based on a numeric index. To take advantage of this, we can redefine the square brackets method in the variable class to build a new call object, remembering the variable itself and the argument passed.
00:10:55.680 So, calling the proc again will yield a representation of its body. Finally, we can create a variable p and call the proc with it, receiving another proc back, which is the inner proc body.
00:11:17.440 This process gives us all the information necessary to reconstruct the original Ruby proc with our own representation. So, we need to wrap this technique into a method. Don’t worry about trying to decipher the code right now. It’s all available on GitHub if you’re interested, so just let it wash over you.
00:11:39.440 The main concept is to create a from_proc method that converts a proc into an expression. We accomplish this by creating a new variable object named after the proc's parameter, calling the proc with it as an argument. This way, every instance of the proc's parameter in its body is replaced by that variable object.
00:12:03.440 Next, we recursively convert the result in case the body of the proc is another proc, and we finally build a new definition object to return. We also need to replace the square brackets method on the variable, call, and proc classes to convert any receivers and arguments from procs using the method we just defined, wrapping the results in a call object.
00:12:27.120 I’ve chosen these three classes because they can all appear as the receiver inside a proc we’re converting. When we evaluate any proc body that contains a call, it will use this replacement method and create an instance of our call class without calling anything directly.
00:12:42.000 Note that in any production code, we would need to clean up these monkey patches later, as they might disrupt other code expecting the original methods. Now we can convert the proc encoding of three into our own representation. You can see it’s an instance of our definition class.
00:13:00.639 Likewise, for the proc encoding of FizzBuzz, there's our converted version, which is also a definition object.
00:13:14.880 Now that we have a representation of these proc encodings, we need to evaluate them ourselves so that we are not dependent on Ruby procs to execute computations, like adding two and three or FizzBuzz. This requires us to implement a method called evaluate that processes an abstract syntax tree.
00:13:29.600 However, it’s not obvious what that evaluation entails. A variable will refer to the parameter of some proc it is inside, potentially allowing us to retrieve an argument, while a call will have a receiver and an argument needing evaluation as well. For a definition, we will need to evaluate its body eventually, but not immediately—only when it is involved in a call elsewhere.
00:13:49.919 It sounds complex, and I’m not clever enough to solve this by myself, but fortunately, a mathematician called Alonzo Church wrote a paper in 1935 that outlines this process.
00:14:05.519 This paper addresses the same decision problem that Alan Turing took on by inventing Turing machines, and it's still incredibly insightful today, even being over eighty-five years old. For instance, it contains wonderful ideas about how to represent numbers as expressions resembling procs, the foundation of my previous talk.
00:14:24.480 So, thank you, Alonzo, for your contributions. The paper also discusses operations we can perform on these expressions; operation number two is called reduction, which refers to the process when you call a proc with an argument.
00:14:41.200 In Church's notation, the way to evaluate a call involves replacing all occurrences of the variable x in expression m with n. Here, x is the proc's parameter, m is the proc's body being called, and n is the argument used.
00:15:03.200 To examine this reduction idea with regular Ruby procs, let’s consider a proc p that takes a greeting and a name, returning an interpolated string. If I call it with the string 'Hello,' we get another proc back. However, the conceptual underpinning is that the argument 'Hello' has replaced the variable greeting in the body of p.
00:15:21.440 You might interpret the result as the body of p, but with one of its variables filled in with a value. If we then provide a second argument, the string 'RubyConf,' both variables are replaced with their corresponding values.
00:15:41.440 In Church’s paper, he explains that when we have numerous proc definitions and calls composed into a larger expression, each repeated reduction operation gets us closer to a fully evaluated result.
00:15:59.600 I will briefly show you how we can implement this operation on our abstract syntax tree representation. First, we need a helper method named replace, which takes a variable's name to replace, an expression to substitute, and an original expression for that replacement.
00:16:16.640 This method recursively traverses through the abstract syntax tree of the target expression. Whenever it finds a variable whose name matches the variable we’re replacing, it returns the replacement expression instead of the original variable.
00:16:34.240 An interesting situation arises when it encounters a definition whose parameter name collides with the name we’re replacing; in that case, it simply halts and returns the original definition. Since any variables with that name inside the definition's body must reference that parameter, we shouldn’t alter them.
00:16:51.760 As a side note, please be aware that a more complex implementation would be required if the replacement could contain variables whose names do not refer to any parameters. However, that’s not a concern in the cases we’ll be addressing.
00:17:06.720 Now, let's see how the replace method operates. Suppose we create three variables, a, b, and c, forming an expression that calls a with b and c as arguments. Using the replace operation, I can effectively swap out b for another expression, such as the identity proc we introduced earlier.
00:17:22.080 Alternatively, we might replace a or c instead, resulting in expressions where either variable has been substituted. Once we have the replace operation functioning, we can utilize it to reduce an expression by finding opportunities to pull out the definition body and substitute its variables.
00:17:40.000 To help with this, we’ll need another tool to ascertain whether an expression constitutes a value—a successful result of evaluation. Because we derive values by encoding procs, only proc definitions can count as values, while calls and variables cannot.
00:18:01.440 Moreover, we can implement Alonzo Church's reduction operation on expressions. In Ruby, since the evaluation strategy is left-to-right, we must navigate to the next part of the expression in the same sequence to replicate its behavior.
00:18:22.880 In general, we would reduce the left-hand side of a call, addressing the receiver first. If the receiver is already a fully reduced value, we would shift to reducing the right-hand side, which is the argument.
00:18:39.760 It's only in the specific scenario where the receiver is a definition and the argument is a value that we replace the parameter with the argument within the body of the receiver, as Church indicated.
00:18:55.680 To effectively evaluate an expression, we need to continually reduce it. For example, if I create expressions for adding one and two, followed by a call to add using one and two as arguments, I can keep reducing it.
00:19:11.840 If none of the patterns in the reduce method match, that indicates we can no longer reduce further, and thus the evaluation has concluded. As noted, we end with definitions at the top level, but since Church only explains how to reduce calls with variable replacement, it's logical we would stop here.
00:19:29.920 This can easily be wrapped in an evaluate method that calls the reduce method until none of its internal patterns match, allowing us to evaluate the entire expression in a single step.
00:19:49.760 Great! We have effectively represented and evaluated these values. Moving to the third problem: how do we decode the evaluation results to make sense of them?
00:20:05.760 You might have noticed that applying the addition of one and two yielded a result that looks different from what we previously identified as the encoded three, which is a bit problematic. These encoded values are only useful if we can revert them back into their Ruby equivalents.
00:20:22.160 However, if this abstract syntax tree doesn’t align with our conception of what three should appear as, how can we recognize it? To remedy this, we need to integrate the concept of a constant, which acts as an atomic value we can carry around, even without any behavior.
00:20:38.560 Constants will also be included in our abstract syntax trees, alongside variables, calls, and definitions. Constants feature names like variables but lack any inherent meaning, essentially serving as placeholders.
00:20:57.120 For constants to be useful, we must establish support for their evaluation. First, we need to enhance the value determination to include constants as recognized values, along with any calls where a constant is the receiver. Since constants lack behavior, we want them to remain inert in the face of function calls.
00:21:14.480 Now, if we take the outcome of adding one and two, followed by calling it with two defined constants—let's call them increment and zero, although the names are irrelevant—we observe that when evaluating this, we can interpret the results according to how many times the first constant appears.
00:21:32.400 If we invoke this conversion method on an encoded number, we receive the accurate Ruby integer back even if its structure is more complex than the simplest representation.
00:21:54.640 Thus, we have examined the capability to represent, evaluate, and decode these proc-encoded values ourselves rather than relying on Ruby’s proc implementation to complete the tasks.
00:22:11.200 This is a thrilling realization, and I believe it retroactively validates the challenges faced while programming with nothing initially. By confining ourselves to writing programs in this restricted Ruby subset, we have created opportunities to fully comprehend and implement that subset from scratch.
00:22:28.480 It feels empowering to have this level of insight and control over the underlying machinery in the process of computation, rather than just understanding the programs operating on top.
00:22:45.440 Here's a quick demo of converting the FizzBuzz proc into an abstract syntax tree and then interpreting that as an array of strings using our evaluate method.
00:23:02.400 As you can see, it works fine but there is a downside—it takes nearly two hours to print all the numbers up to one hundred, which is not practical.
00:23:19.840 Naturally, one might ask if we could speed things up. Our own approach requires two hours to execute FizzBuzz compared to approximately eighteen seconds for the native Ruby procs. While we can do the evaluations independently, improving performance would be advantageous.
00:23:43.520 Fortunately, in 1964, computer scientist Peter Landin published a paper titled "The Mechanical Evaluation of Expressions," which addresses this issue. This paper outlines a specification we now recognize as an abstract machine for evaluating expressions.
00:24:05.920 The machine's state consists of four data structures: stack, environment, control, and dump, leading to the nomenclature of the SECD machine. The control component is particularly crucial as it represents a command list waiting execution, while the stack contains intermediate evaluation results.
00:24:24.880 Each step of the machine updates its state according to the control commands that direct future actions.
00:24:40.480 Although I can't delve into every detail today, here's a high-level overview of the functioning of this system.
00:25:00.480 The sluggishness of our earlier implementation stems from it constantly rewriting expressions to replace variables, causing their sizes to balloon, which ultimately slows down processing. Landin’s concept centered around maintaining an environment to remember names and values of all variables currently in scope.
00:25:21.760 Instead of rewriting expressions, we retain their original forms while adding binding names and values to the environment as we proceed.
00:25:39.760 So, if we want to evaluate a proc definition being called with an argument, we merely extract the body's definition and create a new environment storing the argument's value during that evaluation.
00:25:57.440 This means we no longer need to rewrite anything; we remember the value of parameter x, enabling us to retrieve its value from the environment when any occurrence arises in the body.
00:26:16.560 To execute this effectively, the machine must be cautious about evaluating definitions since variable bindings in the current environment will be needed later.
00:26:34.560 Landin also invented a data structure called a closure, which couples a definition with its current environment to wrap them together as a singular value.
00:26:55.360 Ultimately, environments and closures are key reasons the SECD machine is more efficient than our expression-rewriting approach.
00:27:11.920 The good news is that we can practically translate the SECD machine’s transition functions into Ruby. This involves direct translations from the definitions in the original paper, with additional cases to evaluate closures and constants properly.
00:27:30.320 While it's certainly feasible to write this more efficiently in Ruby with imperative stack manipulation methods, this version maintains a cleaner correspondence with the foundational concepts of the paper.
00:27:48.960 Here's how the SECD machine performs; it's substantially faster than before, completing tasks in roughly three minutes instead of two hours, marking a fortyfold improvement.
00:28:06.480 Despite this progress, we can enhance performance further.
00:28:23.680 As the SECD machine operates within a loop and contains a switch statement, it's not overly difficult to re-implement it in C, compiling it into native code to achieve additional speed.
00:28:41.120 In C, we can declare a struct for various expressions—variables, calls, definitions, closures, and constants—along with structs for managing the stack, environment, control, and dump.
00:28:58.960 These serve as four distinct types of linked lists for simplicity. Moreover, a more efficient implementation would involve allocating our own contiguous heap to maintain these as a genuine stack.
00:29:16.240 Then, we can translate that destructive version of the evaluating method directly into C, incorporating cases to handle our five types of expressions while facilitating the updates to state during receiver-argument applications.
00:29:34.640 This simplified version doesn't release any allocated memory for environments, closures, or new expressions, meaning a garbage collector would be necessary for real-world scenarios.
00:29:52.920 After compiling the C code as a dynamic library, we can link it to Ruby via the FFI gem. The only requirements are specifying the C data structures and designating which C functions to link as Ruby methods.
00:30:10.560 Some additional helpers are necessary to translate Ruby abstract syntax trees to and from C structs for seamless integration into the evaluation function. Let's skip that for now.
00:30:28.720 Running FizzBuzz with this setup now completes in approximately one minute— three times faster than its Ruby version. While it's not an astronomical improvement since the Ruby variant was already fairly efficient, it is still worthy.
00:30:45.920 As we ponder further optimization possibilities, I won't delve into those intricacies right now, but decades of research have explored ways to enhance the original SECD machine's performance.
00:31:02.720 For instance, during execution, it dynamically translates the original expression into a command list, a process we could opt to perform beforehand, compiling expressions into instructions to expedite execution.
00:31:23.360 Once we generate a command list for the machine, we could translate each one into C or native machine code, eliminating the need for interpretation.
00:31:40.720 If you're interested, follow the link provided at the video's end for more insights into the details of these techniques.
00:31:56.880 What we have explored represents the initial stages of compiling a basic functional language; the extensive research that has taken place since the creation of the SECD machine has unveiled numerous tricks and optimizations for enhancing compiler efficiency.
00:32:12.560 Ten years ago, I concluded "Programming with Nothing" by asking what the purpose of it all is. At that time, I asserted that we had observed an incredibly minimal language possessing the same computational power as Ruby.
00:32:36.480 The only fundamental distinction between that stripped-down language and full Ruby is expressiveness, not capability. The unique charm of Ruby for us comes from how it balances that expressiveness alongside other crucial factors such as performance, safety, and simplicity.
00:32:55.919 In order to answer this same question now, after having previously considered how to code in such a limited language, we’ve seen today how to actually implement that language ourselves.
00:33:10.760 We now possess the fundamental blueprint for constructing and operating our own programming language, equipped with the minimum features required for Turing-complete computation.
00:33:30.080 The earlier talk revealed that this language could write any program; today, we’ve confirmed it can also be engineered in just a few pages of code.
00:33:49.920 From this realization originates a considerable legacy of functional language implementations, many of which are simply optimized or feature-rich versions of what I've just presented.
00:34:05.680 What we've explored represents merely the beginning. A seemingly simple concept like the SECD machine is the first step in an ongoing journey of improvements that ultimately equip us to create languages that are efficient, expressive, and rapid.
00:34:21.760 That's everything I wanted to share with you today. I realize I didn't give you ample opportunity to thoroughly comprehend or read any of the code presented.
00:34:30.080 Everything is available on GitHub if you're interested in taking a look and exploring it to understand how it operates better. I hope you found some of this engaging or entertaining; if not, my apologies.
00:34:49.280 Nonetheless, I genuinely appreciate your time and attention. Thank you very much for watching.
Edit
Explore all talks recorded at RubyConf 2021
+92