2453: Excel Lambda

Explain xkcd: It's 'cause you're dumb.
Jump to: navigation, search
Excel Lambda
Extremely rude how Turing's later formulations of the halting problem called me out by name specifically.
Title text: Extremely rude how Turing's later formulations of the halting problem called me out by name specifically.


Cueball is computing and Ponytail criticizes him in a way that is reminiscent of the Code Quality series, although not as harsh. Cueball has lots of strange computer problems, and this will most likely result in another one.

The comic begins with Ponytail finding out that Microsoft Excel is adding a lambda function to their function library. This was announced by Microsoft for Beta users in December of 2020, but perhaps Ponytail has only discovered this recently. A lambda function is a fundamental mathematical structure that can (alternatively) be used to completely define all possible computations from the ground up, in what is known as lambda calculus, other than using for-loops, pointers and effect-ful functions that bear little resemblance to mathematical functions. They are commonly found in programming languages such as Lisp, Python, and many others. A lambda function is also called an anonymous function because in most languages it can be passed to other functions (including another lambda function) without needing to be given any formal name during coding, or given 'closure' under whatever name(s) its calling procedures desire.

Finding that Excel is adding a lambda function pleases Ponytail. Cueball claims that the lambda function is unnecessary, as when he needs arbitrary computation he just adds a block of columns to the side of his sheet and has a Turing machine process it. This would technically work as lambda calculus is formally equivalent to Turing machines. People have created Turing machines in Excel, although not for practical purposes.

Ponytail finds his solution absurd and is convinced Cueball is "doing computing wrong". But he claims that all computing is equally wrong, citing the Church-Turing thesis, a hypothesis which says that a function can be computed by executing a series of instructions if and only if that function is computable by a Turing machine. A classical Turing machine uses an infinitely long strip of tape as its memory; for Cueball, the large Excel column acts as the "tape". All ways of computing are "equally wrong" since, according to this thesis, they can all be translated to or from a Turing machine.

Ponytail and Cueball appear to have different ideas of 'computing'. Ponytail, like most programmers, probably includes efficiency and readability as important characteristics of 'doing computing right'. Cueball appears interested only in computability, a more theoretical point of view than Ponytail's.

Ponytail then says that Turing would change his mind if he saw Cueball's spreadsheet, presumably because of the extreme complexity of Cueball's code in the spreadsheet. Cueball's final statement is that Turing could ask him to stop, but would not be able to prove if he actually will stop.

Cueball's final statement is a reference to the halting problem mentioned in the title text. It is the problem of determining whether a given Turing machine will halt. The problem has been shown to be undecidable, i.e., it is impossible to build an algorithm that computes whether any arbitrary Turing machine will halt or not. Because of the way Cueball has behaved, he has been specifically mentioned in Turing's later formulations of the halting problem. Cueball finds this very rude. This is of course a joke,[citation needed] since Turing has been dead since 1954,[citation needed] presumably long before Cueball was born. But it would be crazy[citation needed] indeed if a scientist became so mad at a person that he would mention this person by name in his formulation of a serious problem.

Over-complicated spreadsheets were also mentioned in 2180: Spreadsheets.

While conditional loops with the ability to interact with the loop variable, and functions reading and altering parameters not passed to it, can be (ab)used creatively to great effect, the fact a same structure may have been vastly different control schemes puts burden on anyone reading preexisting code. Functional programming abstracts computation differently, and uses distinct constructs for plain iterating over a list (map and co., the inner function is forbidden to interact with the accumulator by semantics) and recursion and iteration with side-effects or implicit input (modeled as various flavors of monads). Constructs like map take functions as parameter, but giving every tidbit of code a name and hiding it 100+ lines away nullifies the readability. Lambda function is thus a much needed piece for a functional style of expression.

In the Excel example though, the point is you can finally create custom functions in the original formula language, not some too-powerful-not-to-be-abused-by-hackers macro language that any security-aware person would strip out before opening an Excel spreadsheet. Excel formulas take only explicit input (cells) and have explicit and controlled output (cells or function return value), fitting the Lambda notion nicely. Combine this with proper recursion support and you have a language that becomes Turing-complete without relying on evaluator abuse (circular reference and F7 for next iteration) or a wall of Turing machine states. Now one can express (pseudo-code follows) CellValue=iterate(recursive-function, num-of-steps) properly, with num-of-steps as an input not *number of F7 presses* or *starting value of a cell which get decremented to zero as recursion proceeds* or *row number from wall of states*. Excel probably still tracks the iteration with a variable in calculating the final value, but that implementation detail is decoupled from the language itself.

An example of a lambda function in Python that takes a parameter named a and computes the value a-squared minus 1:

   lambda a: (a ** 2) - 1

Lambda values are often used as parameters to other functions, such as map which applies a function to each item of an "iterable" such as this list of the numbers 1, 2, and 3:

   map(lambda a: (a ** 2) - 1, [1, 2, 3])  # will generate the values 0, 3, and 8 

You can copy/paste this statement into a Python interpreter (such as TutorialsPoint) to see it work (do not copy the leading spaces; that's a wiki thing):

   print(list(map(lambda a: (a ** 2) - 1, [1, 2, 3])))

In the above example, map takes each element of the list containing the values 1, 2, and 3 in turn, sending each value to the lambda function (as the parameter "a") and so generating the sequence of values: 0, 3, and 8. These are then reconstructed into a list to print the complete result: [0, 3, 8].

A recursive lambda might be:

  def pointless_recursion(v):
     # If current value (x) is evenly divisible by 4, return the source (v) * current (x)
     # Otherwise, print current, and then try the process again with the current value of x + 3
     r = lambda x: x * v if x % 4 == 0 else print(x) or r(x + 3)
     return r(v)
  pointless_recursion(12)   # returns 144 (i.e., 12*12)
  pointless_recursion(11)   # prints 11, 14, 17 then returns 220 (i.e., 20*11)

In this instance, the function is given the name 'r', and features a (conditional) call back to this self-same 'r' within it. The 'x' is whatever value is the latest passed to 'r', while 'v' is that which was first passed to the container function.

Ideally, such techniques should be used to reduce Spaghetti code, not increase it. But this isn't a foregone conclusion, especially in Cueball's hands.


[In a narrow panel, Ponytail is walking in from the left, looking down at her phone]
Ponytail: Oh cool, Excel is adding a lambda function, so you can recursively define functions.
[Ponytail, holding her phone to her side stands behind Cueball, who is sitting in an office chair with a hand on a laptop standing on his desk. He has turned around to face her, leaning with the other arm on the back of the chair.]
Cueball: Seems unnecessary.
Cueball: When I need to do arbitrary computation, I just add a giant block of columns to the side of my sheet and have a Turing machine traverse down it.
[In a frame-less panel Ponytail is standing in he same position behind Cueball, who has resumed working on his laptop with both hands on the keyboard.]
Ponytail: I think you're doing computing wrong.
Cueball: The Church-Turing thesis says that all ways of computing are equally wrong.
[Ponytail is still behind Cueball, who has a finger raised in the air, and the other hand is on the desk. Cueball's head has a visible sketch layer which has not been erased.]
Ponytail: I think if Turing saw your spreadsheets, he'd change his mind.
Cueball: He can ask me to stop making them, but not prove whether I will!


  • In the original version of the comic, in the final panel, there was a gray pencil outline, slightly different to Cueball's head that had not been removed.
    • This was later fixed in a re-upload.

comment.png add a comment! ⋅ comment.png add a topic (use sparingly)! ⋅ Icons-mini-action refresh blue.gif refresh comments!


Another ghost cueball comic! You can see it in the last panel. 06:03, 22 April 2021 (UTC)

Is that something that has happened before? First time noticing it. Is it just a remnant of the sketching? Of doest it mean something? 13:21, 22 April 2021 (UTC)
It has happened, and is now mentioned in the trivia section. --Kynde (talk) 16:43, 23 April 2021 (UTC)
Randall seems to have update the comic to remove the ghost head. Someone should update it here too. (I don't know how). DrPumpkinz (talk) 00:07, 23 April 2021 (UTC)

Someone needs to add an explanation of the Lambda, and possibly how Excel is implementing it. (I suppose it would immediately be useful for cutting down common re-use within a formula line, though =IF(ISERR(FIND(":",A1)),A1,RIGHT(A1,LEN(A1)-FIND(":",A1))) is a trivial repeat of the FIND, once to check, then again to do, I often need to do far more nested things, check for being a value, repeat the FIND to deal with the LEFT, etc.) But it has the smell of being effectively a Macro in this instance. Which already seems to me to be the only way to run a proper Turing Machine in an Excel column without hitting Circular Reference issues.

Would it be a stretch to say that Turing's inability to prove if Cueball will stop is actually equivalent to the halting problem, except it is for Cueball and not an arbitrary Turing machine? I thought that was pretty funny. xTheBHox (talk) 11:30, 22 April 2021 (UTC)

Microsoft themselves claim that the addition of LAMBDA makes Excel turing-comlpete (see here: https://techcommunity.microsoft.com/t5/excel-blog/announcing-lambda-turn-excel-formulas-into-custom-functions/ba-p/1925546). Based on this comic, I would argue that it already was... 12:55, 22 April 2021 (UTC)

Someone has already made Conway's game of life in excel (http://dailydoseofexcel.com/archives/2011/04/06/conways-game-of-life-simulation-in-excel) and game of life has been shown to be Turing complete. Kvarts314 (talk) 13:28, 22 April 2021 (UTC)
Since Excel has a way to store and do math on numbers, and also a way to 'point' to a certain cell, it is Turing-complete. A lambda function is not necessary for Turing-completeness (e.x. a turing machine does not have one.) 15:14, 22 April 2021 (UTC)

it should probably be mentioned that the number of excel rows is emphatically *not* infinite, so only simple turing machines could be implemented this way. 17:20, 22 April 2021 (UTC)

In fact, it technically isn't Turing complete, as it has only a finite amount of data. It might be a finite-state-machine or the like, though. -- 20:22, 22 April 2021 (UTC)
Turing completeness is a qualilty of a model of computing, not a particular physical implementation. There's no inherent limit to the size of a spreadsheet, so it's as Turing-complete as any programming language. Any actual implementation of a Turing Machine only has a finite tape, not an infinite tape like the theoretical model. Barmar (talk) 15:39, 23 April 2021 (UTC)
It may be worth citing this work. https://gotocon.com/amsterdam-2016/presentation/Pure%20Functional%20Programming%20in%20Excel Noehp (talk) 00:02, 23 April 2021 (UTC)

Zerothly, why is almost everyone here using weird 'indents', or maybe new-contributor-starts-here methods, in this article's Talk comments? Is this some lambdaesque in-joke being carried in here from some script/code dialect I'm not aware of? Primarily, though, I just wanted to say that the (external) explanations of how Lambda works in Python look a lot to me like a nuanced Eval-like process, rather than a typical Anonymous Function that becomes sequestered away as a code-chunk at the end of a loose-pointer, internally. Python's one of the languages I've not yet bothered to learn to write (just sufficiently understand to get the gist and flow), so maybe I'm reading the Lies-To-Children explanations for n00bs. Should we get some other languages represented here, either within the C-family or off into the clans of code that might have an even more interesting implementation? Nothing too esoteric, but a distinct grammar difference would be an interesting comparison. 11:22, 23 April 2021 (UTC)

Fixed the indents. PoolloverNathan[stalk the blue seas]UTSc 14:01, 21 May 2021 (UTC)

Now if only someone would find examples of creative loop variable abuse (I guess that'd be optimal solutions in lots of Code Golf or Code Olympics problems) that demonstrate the imperative style of code to its full glory. The corresponding solution in λ code is probably rife with applicative functors and monads i.e. ugly and awkward to anyone not familiar with these concepts. The Python example here merely looks like anonymous function sprinkled into an imperative style so not very helpful. 04:15, 18 October 2021 (UTC)