Our beloved function module() is really going away. As of Lua 5.2 it’s only available with compatibility flags on, and the writing’s on the wall: it is going away for good in Lua 5.3. So, in a new Lua project I wrote this past semester, I decided to write it without using module(), while making sure my code runs on both Lua 5.1 and 5.2 (as a side result, I started the compat52 project, which allows you to write code in a well-behaved Lua 5.2 style and make it run on both 5.1 and 5.2).

So, why I liked module() in the first place? While vilified by some, I think the pros of module() largely trumped its cons. It had indeed some nice properties:

• It provided much-needed policy for interoperability between modules - for the first time people were mostly writing Lua modules the same way and they worked with each other
• It encouraged documenting the module name in its argument, which is especially useful in a world without clearly defined path policies. One would often find out where to put the module by looking at its name. Nevermind the ill-advised suggestion of writing module(...) “so that you can name the module whatever you want” — users of a module must agree on a name so that all other modules that need it can call require() properly!
• It pushed modules that return a table through require() — while Lua’s mechanisms for modules were too lax and resulted in spilling globals too often, consistent use of module() meant that you could rely on writing local foo = require("foo"), which is “environmentally” clean idiom, albeit a bit repetitive.
• You could nicely tell visibility through syntax: private functions declared with local function, public functions with function.
• Apart from the awkward package.seeall argument, use of module() was pretty-much boilerplate-free (I hate repetition in code, from the ugly local print = print idioms in Lua to the redundancy of .h and .c files in C).

So, how to try to retain some of these properties without module()? The solution I found was to adopt some bits of policy, which I list below.

Yes, bits of policy. I know many in the Lua world hate policies, but of course I’m not putting a gun against anyone’s head to follow them. I’m only sharing what works for me and hopefully you may find some use. And don’t worry it’s nothing too esoteric, and it’s mostly cherry-picking some established practices.

Starting from the outside in

Keeping in mind that the goal of a module is to be required by client code, this is how a module foo.bar will be used:

local bar = require("foo.bar") -- requiring the module

bar.say("hello") -- using the module

An interesting observation here is that although we have a hierarchical structure of modules, the practice of loading them into locals means that in use they have to be accomodated in a flat namespace. So here’s Policy Bit #1:

Policy Bit #1: always require a module into a local named after the last component of the module’s full name.

Don’t do stuff such as local skt = require("socket") — code is much harder to read if we have to keep going back to the top to check how you chose to call a module.

Naming modules

Now that you know that your module will end up in people’s locals, please take that into consideration when naming your module. (I wish we had a capitalization policy to separate that nicely, but naming things LikeThis in Lua tends to be used only for object-oriented code.)

The idea is to choose a name that strikes a balance between convenience and uniqueness, and that is usable. And what better way to achieve this other than using this name. So, here’s Policy Bit #2, let’s use the module name in its declaration!

Policy Bit #2: start a module by declaring its table using the same all-lowercase local name that will be used to require it.

So, in the beginning of module foo.bar (which will live in foo/bar.lua), we begin with:

local bar = {}

It’s not a nice self-documenting header as we used to have with module("foo.bar", package.seall), but it’s something. We can improve that with LDoc comments:

--- @module foo.bar
local bar = {}

Don’t name your module something like “size”.

Declaring functions

When I’m scrolling through source code, I like to be able to tell what’s the sphere of influence of the piece of code I’m looking at. Is this a tiny helper function that’s only used below this line in this file? Is it an important function that’s used by other clients, so that an added or removed argument would mean API breakage? Ideally I like to be able to tell that without running back and forth in the code, so I really like visibility to be explicit in the syntax.

We must not declare global functions (or globals of any type, really!) in our modules, so using “globals vs. locals” to tell the difference won’t cut it. We have some alternatives, though. But first, let’s assert one thing:

Policy Bit #3: Use local function to declare local functions only: that is, functions that won’t be accessible from outside the module.

That is, local function helper_foo() means that helper_foo is really local.

This sounds obvious, but there are advocates of declaring all functions, public and private, as local functions and then writing an “export list” at the bottom of the module. Reading code written like this feels to me like a thriller with a twist ending: “haha, I was a public function all along!”

How to write public functions then? We must not declare global functions, but there are alternatives. Say we’re writing a function that will be used in client code as bar.say("hello"). It’s nice that we can declare it just like that:

function bar.say(greeting)
   print(greeting)
end

Policy Bit #4: public functions are declared in the module table, with dot syntax.

Visibility is made explicit through syntax. This is the same idea advocated by those who tell you to name your module tables “M”, except that you’re eating your own dogfood and using the name you expect your users to use. It’s also more consistent, since calls of say() are written bar.say() everywhere, instead of say(), M.say(), etc. (Also, “M.” looks really really ugly and people can’t decide if they want to use “M” or “_M”.)

In case you have speed concerns about having your calls go through the module table: first, this is what your users will go through; second, this is no different than using colon-syntax and dispatching through self and nobody complains about that; third, if you really need it (and have a benchmarked case for it), sure go ahead and make locals for optimization clearly marked as such; fourth, if you’re really after speed you’re probably using LuaJIT and last I heard the value of caching functions into locals is put into question there.

Classes and objects

When talking about classes and objects, it’s then time to talk about things named LikeThis. (If you don’t do OOP, feel free to skip this section!)

As we did above, let’s start look from the outside in: how to instantiate an object. There are two common practices (oh why I am not surprised :( )… you either make a class table with a “new” method, or make the “class object” callable (as a function or a table with a __call metamethod — wait, that makes it three practices…)

local myset1 = Set.new() -- style 1
local myset2 = Set() -- style 2.1 (set is a function)
local myset3 = Set() -- style 2.2 (set is a table)

If your module represents a class, I tend to like style 1 better because:

• it keeps the invariant that modules are tables
• it’s easy to store “static” methods as the other functions of the table
• it’s less magic — I often run modules through for k,v in pairs(bar) do print(k,v) end in the interactive prompt to get a quick look of what they export.
• it just screams “I’m creating an object”

If all your module does is define a class, I guess it makes sense to name the module file MyClass.lua and have the class table be the module table. But I prefer not to do that, because often what we store as “static” class methods in purely OOP languages are really module functions. I still use the uppercase table when implementing the class, like this:

--- @module myproject.myclass
local myclass = {}

-- class table
local MyClass = {}

function MyClass:some_method()
   -- code
end

function MyClass:another_one()
   self:some_method()
   -- more code
end

function myclass.new()
   local self = {}
   setmetatable(self, { __index = MyClass })
   return self
end

return myclass

It’s easy to see in the code above that the functions with MyClass in their signature are methods. Sometimes it’s nice to declare the functions as fields inside the table declaration, but declaring methods separately as in the example above allows you to keep local helper functions closer to where they’re used.

If all the module does is declare the class, the class and module table may be one and the same. If you want to use style 2, we get something like this:

--- @module myproject.MyClass
local MyClass = {}

function MyClass:some_method()
   -- code
end

function MyClass:another_one()
   self:some_method()
   -- more code
end

local metatable = {
   __call = function()
      local self = {}
      setmetatable(self, { __index = MyClass })
      return self
   end
}
setmetatable(MyClass, metatable)

return MyClass

Both methods are acceptable, as long as it’s easy and obvious to tell you’re doing OOP:

Policy Bit #5: construct a table for your class and name it LikeThis so we know your table is a class.

Policy Bit #6: functions that are supposed to be used as object methods should be clearly marked as such, and the colon syntax is a great way to do it.

Don’t make people reading your function have to guess (or look up) if it is a method, a public module function or a local function.

Wrapping up

Return the module table. It’s a bit of boilerplate, but it’s what we have to deal with in a module()less world:

return bar

Policy Bit #7: do not set any globals in your module and always return a table in the end.

To sum it all up, a complete module foo.bar would look like this:

--- @module foo.bar
local bar = {}

local function happy_greet(greeting)
   print(greeting.."!!!! :-D")
end

function bar.say(greeting)
   happy_greet(greeting)
end

return bar

The result is that we type a bit more than we did with module(), and we risk polluting the global namespace if we’re not careful, but with this set of policies, we have:

• fairly self-documented code
• visibility rules readable through syntax
• modules that predictably return tables
• as much consistency and as little boilerplate as possible

…which mostly matches what I liked about module(), to the extent that can be done without _ENV tricks.

I’ve been using these policies successfully in a university project, and my plan is to follow them when I update the LuaRocks codebase to drop the use of module(). Consider your self encouraged to adopt some or hopefully all of them, but most importantly, whatever you do, be consistent! Good luck in this brave post-module() world!

Java (as of version 6, aka 1.6) does not allow you to declare a static HashMap as conveniently as an array. Still, you have the alternative of using a static block in your class to add fields. Take this example:

import java.util.HashMap;

public class StaticHashMapTest {
	private final static HashMap constants = new HashMap();
	static
	{
		constants.put("A", "The Letter A");
		constants.put("B", "The Letter B");
		constants.put("C", "The Letter C");
	}
	/* Rest of your class that needs to know the consts */
}

This works fine. But then you want to map something a little more complex than a string to another string. And I don't mean something very complex... just, say, a string to a string and an integer (yes, you'd like to use some kind of "pair object", but it looks like Java does not have it).

So you go and try to do things The Java Way (tm) and create a tiny class just to hold your two values:

import java.util.HashMap;

public class StaticHashMapTest {

	private class Pair {
		final String name;
		final int number;
		public Pair(String name, int number) {
			this.name = name;
			this.number = number;
		}
	}

	private final static HashMap constants = new HashMap();
	static
	{
		constants.put("A", new Pair("The Letter A", 123));
		constants.put("B", new Pair("The Letter B", 456));
		constants.put("C", new Pair("The Letter C", 789));
	}
	/* Rest of your class that needs to know the consts */
}

This should suffice, right? I even made the Pair class private to my class, to ensure good information hiding (that's what Java is all about, right?). Turns out this fails to compile:

StaticHashMapTest.java:18: non-static variable this cannot be referenced from a static context
      constants.put("A", new Pair("The Letter A", 123));
                         ^
StaticHashMapTest.java:19: non-static variable this cannot be referenced from a static context
      constants.put("B", new Pair("The Letter B", 456));
                         ^
StaticHashMapTest.java:20: non-static variable this cannot be referenced from a static context
      constants.put("C", new Pair("The Letter C", 789));
                         ^
3 errors

The error messages say that my "new" operators are failing due to the use of the "this" variable, which is not there at all! But hey, we can call "new" from a static context, can't we? We just did that when declaring the HashMap itself.

It turns out that the problem is that we're using an inner class. Objects from inner classes hold a "this" reference to their parent object (yes, as in myInnerObject.this.myParentAttribute... go figure), hence the trouble with the implicit "this" reference.

You have to make it a static inner class, which means it doesn't know anything about the enclosing class. Yes, that's yet another meaning for the word "static" in programming. Due to this peculiar meaning, inner classes are the only context where you can use the "static" qualifier to a class declaration in Java.

This, therefore, works:

import java.util.HashMap;

public class StaticHashMapTest {

	private static class Pair {
		final String name;
		final int number;
		public Pair(String name, int number) {
			this.name = name;
			this.number = number;
		}
	}
	private final static HashMap constants = new HashMap();
	static
	{
		constants.put("A", new Pair("The Letter A", 123));
		constants.put("B", new Pair("The Letter B", 456));
		constants.put("C", new Pair("The Letter C", 789));
	}
	/* Rest of your class that needs to know the consts */
}

And that's Java for you.

Lua is a nice programming language, which allows for readable and concise code. One of my favorite idioms in the language is this:

x = a and b or c

which usually works like the C ternary operator, “a ? b : c”, but in a more readable fashion. This works in Lua because the “and” and “or” operators return their matching value when they get a “true” value (anything other than false and nil).

One thing to keep in mind though, is that this is really “and and b or c” and not “a then b else c”. There’s one big difference: when you want to have nil or false in your “then” value.

Lua 5.1.4  Copyright (C) 1994-2008 Lua.org, PUC-Rio
> = true and 10 or 20
10
> = false and 10 or 20
20
> = true and nil or 20
20

An ugly alternative is to do “not a and c or b”, like this:

> = not true and 20 or 10
10
> = not false and 20 or 10
20
> = not true and 20 or nil
nil

But at this point it’s better just to use an “if” statement. (This hack works around the then-as-nil case, but not else-as-nil, of course.)

So, keep in mind that you should use the “a and b or c” construct as if-then-else only if you know that your “b” value is not nil or false.

It’s better, however, to use this construct for what it is. This behavior is not flawed, it is just different, and it has its own uses. For example, it is very useful to check if a table exists:

x = tbl and tbl.key

And to define fallback values:

x = tbl and tbl.key or "missing!"

Note that the above line reads naturally, and you wouldn’t be able to do that with one “?:” operator in C.

Some people often tell me that, due to my various interests, they actually find it weird that I ended up studying Computer Science and not some of the Humanities. I try to explain them that my specific field of interest, programming languages, is actually a Human Science. And that is so for one simple reason: if there was no people, if computing was restricted to computers and there was no human factor, machine language — the binary code that processors actually run — would be enough. Programming languages exist because of people, not because of computers.

This quote puts it rather nicely:

“Programming is a science dressed up as art, because most of us don’t understand the physics of software, and it’s rarely if ever taught. The physics of software is not algorithms, data structures, languages and abstractions. These are just tools we make, use, throw away. The real physics of software is the physics of people.

Specifically, our limitations when it comes to complexity, and our desire to work together to solve large problems in pieces. This is the science of programming: make building blocks that people can understand and use easily, and people will work together to solve the very largest problems.” — Peter Hintjens et al., ØMQ - The Guide

Programming languages are the bridge we use to communicate our ideas to the machine, but also to communicate our ideas among our fellow programmers, and even to ourselves. Like natural languages, programming languages are constantly evolving (at a much faster pace, even!), as we try to balance the tension between being precise and unambiguous and being understandable and eloquent; to be able, in the same piece of prose, to tell a machine what to do and to tell another person what we mean. And this is by no means a matter of numbers.

This post is aimed towards comp sci students who studied lambda calculus but never really “got” the Y Combinator, the best-known fixed point combinator. Lambda calculus does not feature recursion, but using fixed point combinators, we can easily produce recursive functions, making it able to describe all computable functions (in other words, equivalent to a universal Turing machine). Here’s our friend Y:

Y = λf· (λx· f (x x)) (λx· f (x x))

With it, you can write a non-recursive version of a function, apply Y to it, and you get the equivalent recursive functionality, even though lambda calculus does not provide recursive functions. It’s not hard to understand what it does, but the mystery for me was always how it does it.

In my experience, a major barrier to understanding it was having to deal with several unfamiliar things at the same time, each of which makes a different part of my brain uncomfortable: the semantics of lambda calculus, the syntax of lambda calculus, and the problem at hand.

So, to focus on the problem at hand, let’s get rid of the rest.

Semantics of lambda calculus: untyped lambda calculus amounts (roughly speaking) to a very simple functional language with lazy evaluation. All we have is functions, but through smart encodings we can represent numbers and booleans with nicely crafted chains of functions. To simplify things, then, let’s just assume we already have numbers, arithmetic, if/then/else. Next, let’s get rid of lazy evaluation and switch to early evaluation, which is what we’re used to use in typical imperative programming languages. To do this, we’ll have to use this variant of Y, which is called Z:

Z = λf· (λx· f (λy· x x y)) (λx· f (λy· x x y))

Yes, it is a bit longer (we added the blue bits), but believe me, it’s easier to understand, and once you get this, it’s just a matter of recalling lazy evaluation from those functional programming classes and applying the same logic to Y.

Next, the syntax: lambda calculus is made of terms, abstractions and applications, which in programming language parlance are just variables, function declarations and function calls. Therefore, we can simply rewrite it using some familiar notation and get rid of the weird syntax and precedence rules for now. I won’t even use a functional language: let’s take a restricted form of Lua, using only features provided by lambda calculus to make the syntax clearer:

Z = function(f)
       return (function(x)
                  return f(function (y)
                              return (x(x))(y)
                           end)
               end)(function(x)
                       return f(function (y)
                                   return (x(x))(y)
                                end)
                    end)
    end

All right, it’s not exactly readable. But we’ll get there. Assuming you’re comfortable with functions as first-class values that can be returned and passed as arguments, the weirdest thing here is that in the first return we have a function being declared and called “inline”, receiving as a parameter another function identical to itself. Let’s make this flow a bit clearer by using local variables, but strictly as “aliases”. In other words, it won’t run any different, so we don’t use any extra features that are not part of lambda calculus — note that the our use of local variables here will be equivalent to macro substitution:

Z = function(f)
       local f1 = function(x)
                     return f(function (y)
                                 return (x(x))(y)
                              end)
                  end
       local f2 = function(x)
                     return f(function (y)
                                 return (x(x))(y)
                              end)
                  end
       return f1(f2)
    end

Ok, so this is the function we want to understand. It still makes no sense, but we can see that Z calls one function (f1) passing to it an identical function (f2). These identical functions return the result of calling f (the thing we want to make recursive), but giving as its argument another function that uses something that calls itself (x(x)). A strong scent of self-reference in all this — no wonder, as we know the key to recursion is in there somewhere. But let’s stop trying to reverse-engineer it. Let’s build it instead.

First, let’s recall what this function is good for. What we’d like to have is recursive functions, like this one that calculates the factorial:

fact = function(n)
          if n == 0 then
             return 1
          else
             return n * fact(n-1)
          end
       end

But we can’t have this in lambda calculus. Actually, all of it is fine, except for the recursive call to fact(). We don’t have recursion yet.

The best we can do is to write a function that does one step of the recursion and leaves the next step to be done by someone else. Like this:

stepper = function(next_step, n)
             if n == 0 then
                return 1
             else
                return n * next_step(n-1)
             end
          end

However, I said we would only use features provided by lambda calculus, which means we don’t have multiple arguments. Fortunately, through currying, we can get the equivalent to multiple arguments. This is one aspect of lambda calculus which I won’t hide in Lua syntax because it will come handy in our understanding. We’ll need to make stepper like this:

stepper = function(next_step)
             return function(n)
                       if n == 0 then
                          return 1
                       else
                          return n * next_step(n-1)
                       end
                    end
          end

The difference is that now, instead of doing stepper(some_next_step, 5), we have to do stepper(some_next_step)(5).

What this stepper construction makes clear is that we now have a “factory” function that returns our would-be-recursive function, except it only runs one step and uses another function that knows how to run the next step. You can think that stepper(next_step) actually returns a “step”, which is then run by calling it with (5).

But we need a function to run the next step to pass to stepper. How to obtain it? We call the factory to get the next step. Yes, like stepper(stepper).

Indeed, note that if we run stepper(stepper(stepper(stepper(stepper(stepper())))))(5), we get the equivalent result as fact(5). (You can try it in the Lua interpreter!)

Of course, we don’t want to write it like that. The plan, therefore, is to get a function that combines all these calls. It’s time for the combinator:

combinator = function(stepper)
                -- ?
             end

This function is meant to return something to replace all these nested stepper()s, so we want it to return a function that accepts our input argument:

combinator = function(stepper)
                return function(arg)
                          -- ?
                       end
             end

And it needs to run stepper() on the argument, of course, so it computes our desired function. But what will we pass as the next step?

combinator = function(stepper)
                return function(arg)
                          return stepper( --[[ ? ]] )(arg)
                       end
             end

Well, if what we want to produce is stepper(stepper(stepper(stepper(... then maybe what we need is to pass it stepper() again?

combinator = function(stepper)
                return function(arg)
                          return stepper(stepper)(arg) -- no!
                       end
             end

This is wrong because it will only run stepper twice (and of course we know the combinator doesn’t look like this). Think of stepper(stepper) function as it runs. If we pass 5 as the argument we get stepper(stepper)(5). It will get 5 as n and stepper as the next_step argument. It will eventually call next_step(n-1), that is stepper(4). But stepper expects a function as the argument, and not a number. In fact, if we run this in the Lua interpreter we get a type error. (In untyped lambda calculus we have no notion of “type error”, of course: what we get is just a lambda expression that makes no sense for us.)

We need to give stepper a function, so looks like we’ll have to make one.

combinator = function(stepper)
                local some_function = function()
                                         -- ?
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

(Again, I’m using a local variable here strictly as a “macro substitution”, just to make things more readable.)

To find out what to put in some_function, let’s think of what it will be used for. It will be passed to stepper, and therefore be used as the next_step. Does it mean it needs to take the numeric argument, then?

combinator = function(stepper)
                local some_function = function(arg)
                                         -- ?
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

If we’re receiving a parameter, it’s fair to assume we’ll have to do something with it. What we want to do with our input arguments is to run steps on them, so let’s get a step with stepper and do it.

combinator = function(stepper)
                local some_function = function(arg)
                                         return stepper( --[[ ? ]] )(arg)
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

Oh-oh, we’re back to the problem of what to give stepper! Does this mean we got into a loop? Well, note that if we just kept on doing the same, we would get the equivalent to stepper(stepper(stepper(...))):

combinator = function(stepper)
                local and_yet_another_step = -- ... !!!
                local yet_another_step = function(arg)
                                            return stepper(and_yet_another_step)(arg)
                                         end
                local another_step = function(arg)
                                        return stepper(yet_another_step)(arg)
                                     end
                return function(arg)
                          return stepper(another_step)(arg)
                       end
             end

But no, it does not mean we’re stuck in a loop. It means we’re getting close.

What we missed is that when we considered what to pass to the first stepper, we simply said it had to be a function taking the numeric argument. But what we want is a function that returns the result of stepper’s computation, but also produces the function for the next step! What we need is another factory-style function like when we transformed fact into stepper. Instead of going down one step, we’ll make a factory function that generates another function that goes down one step. While we’re at it, and that’s a key point, we’ll remove from it the responsibility of figuring out how to descend to the next level. We’ll do it just like when we did when we got rid of the recursion — just assume you get what you need as a parameter:

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step)(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step)(arg)
                       end
             end

With a function like make_step, we can produce as many steps as we want. If you are mathematically inclined, by now you may be thinking of induction: yes, have we just constructed a way of solving one step of our problem assuming we have the solution for the next. That’s the spirit.

So, are we there yet? Does this work?

Not yet. Remember when we tried to do stepper(stepper)? It didn’t work because stepper doesn’t want a factory as an argument. It wants an actual step (remember that in our example it will use it to get the factorial of n-1). In other words, we don’t want to pass it a factory like make_step. We want make_step to make us a step. So let’s call it!

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step)(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step( --[[ ? ]] ))(arg)
                       end
             end

Ok, we’ll call it, but what will we give it? Let’s look at what the argument of make_step is used for.

Wait a second, it is used to make a step as well! So, do we just give it… itself?

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step(next_step))(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step(make_step))(arg)
                       end
             end

Yes, we pass it to itself. And we do the same with next_step too, since we’re doing the exact same thing. You see, here is where everything comes together: to have recursion, we need to have self-reference; and in lambda calculus, while a lambda term cannot reference itself in an abstraction (function definition), we have that a lambda term, when bound to a variable, can be applied to itself. The function above is indeed a fixed point combinator.

You may be finding strange that make_step passes itself as a parameter, then calls itself passing itself as a parameter… is this an infinite loop? Not necessarily, because in between each step, we don’t run stepper(next_step(next_step)) right away. It is “packed” inside a function(arg)...end. (These are the extra lambdas that the Z combinator has compared to the Y combinator.)

Speaking of that, is this code the same as the straight Lua translation of the Z combinator I presented above? Let’s recap:

Z = function(f)
       return (function(x)
                  return f(function (y)
                              return (x(x))(y)
                           end)
               end)(function(x)
                       return f(function (y)
                                   return (x(x))(y)
                                end)
                    end)
    end

Doesn’t look much like it, does it? But let’s take a closer look at our combinator. Turns out that in that final return, instead of building that step function explicitly, we can simply call make_step and get the same results:

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step(next_step))(arg)
                                            end
                                  end
                return make_step(make_step)
             end

(In compiler terms, it is as if the first iteration had been “unrolled” before.)

Remember when I said the local variables were just macro substitutions? If we expand the two instances of make_step, we get this:

combinator = function(stepper)
                return (function(next_step)
                           return function(arg)
                                     return stepper(next_step(next_step))(arg)
                                  end
                        end)(function(next_step)
                                return function(arg)
                                          return stepper(next_step(next_step))(arg)
                                       end
                             end)
             end

Now, the only difference is that stepper is being called inside function(arg)...end, while in the other one it’s being called outside. It works the same, because the purpose of function(arg)...end there is just to “hold” the expansion of arguments between each call of stepper. We need this because Lua does not use lazy evaluation. To make our function just like Z, we do this:

combinator = function(stepper)
                return (function(next_step)
                           return stepper(function(arg)
                                             return (next_step(next_step))(arg)
                                          end)
                        end)(function(next_step)
                                return stepper(function(arg)
                                                  return (next_step(next_step))(arg)
                                               end)
                             end)
             end

There we are! The exact same function, only with different variable names.

Finally, to test it:

local factorial_step = function(f)
                          return function (n)
                             if n == 0 then
                                return 1
                             else
                                return n * f(n - 1)
                             end
                          end
                       end
local factorial = combinator(factorial_step)

print(factorial(5)) -- we get 120, yet no function in our code ever calls itself

As we can see, there’s nothing magical about the Y combinator: it produces recursion by using the only form of self-reference provided by the lambda calculus, which is self-application of variables. To get the loop started, since there’s no way to bind the outermost abstraction (function) to a term (variable) so it can apply to (call) itself, it is simply written down twice.

I tried to explain this this as clearly I could (given the assumptions I made about prior knowledge about programming languages and basic lambda calculus). This was actually the flow of thought I followed when understanding the combinator. It clearly follows a “programmer” mindset, which may not be the best method for everyone, but I hope it may be useful for others as it was for me. Corrections, comments and suggestions are welcome.