Anonymous Functions in Math and CS

Consider:

This is how one normally declares a function in math: by describing what the value of the function applied to a variable would be. One consequence of this approach is that ir necessitates a variable name, in this case , being assigned to the function.

This may not sound significant or problematic, but consider what the parallel of this in a different class of objects, like numbers would be. Before doing anything, we’d have to assign a variable to the number! For example, we couldn’t just write , we’d have to write . This may still not seem significant. After all, it’s only functions; people only have to define them occasionally.

I’d like to mention a theory that someone (Kelly Rose, one of the leaders — read teachers — of hacklab.to‘s math reading group) mentioned to me recently, that the reason two people (Newton and Leibniz) effectively simultaneously discovered calculus after people failed to for however many thousand years was that notation had developed that allowed for the discovery. (Interesting side note: this individual suggested that category theory may be the next big change.)

If this is theory is correct (and I’m not sure how we could every be certain) then it is the best example I can think of, of something I’ve been thinking about for several weeks: the importance of notation. (I’m using the term `notation’ loosely as including something that isn’t truly a new idea but is a new way of presenting the idea.)

It seems obvious to me that if one makes an idea difficult to represent, a person will avoid using it (or make an easier way to represent it). In some ways, this is applying the Sapir-Whorf hypothesis to things other than spoken language: the medium (traditional language, visualisation, notation, etc) of thinking effects the thoughts themselves. (If you’ve been nodding along, consider the effects English must be having on you mind; you may now wish to look at Lojban.)

I believe this is true, to an extent that I am probably failing to convey. (It’s why, for example, I find it deeply troubling that isn’t defined as : think about all the students who would have had a better understanding of trigonometry and more respect for math in general if it wasn’t for the fact that Pi Is Wrong.)

But we’ve digressed. Back to functions. We need to ask, is there a way to avoid defining a variable when using functions. In fact there is: . For example, the following to statements are identical:

We call an anonymous function. Another notation for this is using lambda calculus. We represent a function with . For example, the earlier example would be .

This has endless usefullness in math. It can provide an ellegant way to represent the Mandelbrot set, for example:

Translation for non-mathematicians: the set of complex numbers such that if we square x, add x, square that and add x, and so on infinitely, we won’t end up with infinity.

We can also use this to define functions that return functions using it. For example, we can define the differential operator, :

We can also use anonymous functions in programing. For example, python allows us to use lambda calculus in it. The following is perfectly valid:

>>> (lambda x: x*x +3)(2)
7

Now, you may have noticed that we can do some really interesting things with this. And could do even more interesting things, if we could make recursive functions.

Some programing languages support anonymous recursive functions. For example, in javascript, functions are passed a `callee’ argument that allows one to recurse on itself. Thus, we can implement an anonymous function that gives us a term in the Fibonacci sequence.

(function (x) {
  if (x <= 2) {
    return 1;
  } else {
    return arguments.callee(x - 1) + arguments.callee(x - 2);
  }
})(6) // = 8

More on this is available here.

But what about in math? There doesn’t seem to be a well defined notation for anonymous recursive functions in math… So, I’ve had to invent my own.

In lambda calculus, I’ve always perceived the lambda to be a place holder for the function. So, I’m rather fond of the notation . If one uses that notation, it’s a small step to use a lambda on the other side of the the equals sign…

We can use this notation to do some very cool things. For example, we can use this to make the Cantor set:

Translation for non-mathematicians: Take the line segment from 0 to 1, remove the middle third, then remove the middle third from the remaining pieces, and so on infinitely.

Of course, this notation does run into problems when one wants to have nested lambda calculus, but this can be fixed by using subscripts, ie .

Tags: CS, math, notation