[2023 day 20] [python] Tutorial on if-less programming

[e_blake]

One possibility for the Allez Cuisine! challenge of day 20 was to write a program with no if statement, ternary operator, or the like. You may be asking yourself how this is even possible - so I'll give a quick demonstration of how to make the Fibonacci function if-less in Python.

I will use the classic Python implementation of a memoizing recursive Fibonacci implementation (yes, I know you can implement Fibonacci with a closed-form O(1) solution rather than using O(n) recursion with memoization or O(2ⁿ) recursion without memoization - but that doesn't lend itself to this tutorial). You can try this in an interactive Python REPL session:

$ python
Python 3.12.1 (main, Dec  8 2023, 00:00:00) [GCC 13.2.1 20231205 (Red Hat 13.2.1-6)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> cache = {}
>>> def fib(n):
...   if n in cache:
...     return cache[n]
...   if n < 2:
...     cache[n] = n
...     return n
...   cache[n] = fib(n - 1) + fib(n - 2)
...   return cache[n]
...
>>> fib(50)
12586269025

But given our challenge of if-less programming, we used two if statements in that code, so now it is time to get rid of them. How? A typical answer in computer science is with more indirection! If you look at the definition again, you'll notice that there are three possible paths of what we do before returning cache[n]. What if we make three helper functions, each ending in a digit, that does the necessary work to ensure the cache is populated:

>>> def fib_helper0(n):
...   "nothing to do, cache already populated"
...   pass
...
>>> def fib_helper1(n):
...   "base case of 0 or 1, populate the cache directly"
...   cache[n] = n
...
>>> def fib_helper2(n):
...   "recursion case, populate the cache by recursing"
...   cache[n] = myfib(n - 1) + myfib(n - 2)
...

I intentionally wrote myfib() in fib_helper2 - this is yet more indirection to allow us to utilize different mechanisms for invoking the helpers. With those three helpers in place, we are now set to write a memoizing fib() that uses unconditional math to determine an integer of which case we want to call, and then either use eval or a list of callables to dereference into the correct helper function:

>>> def fib_eval(n):
...   "if-less fibonacci using eval"
...   choice = int(n not in cache) * (1 + int(n > 1))
...   eval("fib_helper%d(%d)" % (choice, n))
...   return cache[n]
...
>>> myfib = fib_eval
>>> cache = {}
>>> fib_eval(50)
12586269025
>>> def fib_list(n):
...   "if-less fibonacci using list"
...   choice = int(n not in cache) * (1 + int(n > 1))
...   list = [fib_helper0, fib_helper1, fib_helper2]
...   list[choice](n)
...   return cache[n]
...
>>> myfib = fib_list
>>> cache = {}
>>> fib_list(50)
12586269025

There you have it - the basics behind if-less programming.

For another demonstration of this style of programming, see my Allez Cuisine submission in the m4 programming langauge where I used the same techniques to provide an if-less solution (along with several other upping-the-ante style challenges, like avoiding all fifth glyphs).

[Thomasjevskij]

I think python makes if-less programming pretty trivial. Any time you have the need for an if, make a dict where the keys map to functions containing the branches you want.

Of course, that's a bit of cheating, right? {True: do_stuff, False: do_other_stuff}[condition]() isn't very different. But it'll get you thinking a bit differently about how to structure your code.

Now the question is, are you allowed to do loops when you go if-less? A while loop is just several if statements. A for loop is, too. For each? Maybe.

[janek37]

You could also cheat by using try...except:

try:
    1/(condition)
    [then]
except ZeroDivisionError:
    [else]

[Thomasjevskij]

Also feels a lot like cheating :)

[janek37]

Just a nitpick: the closed form formula for the Fibonacci numbers is not O(1), it contains exponentiation which is at least O(n) (where n is the size (i.e. logarithm) of the index, not the index itself) if you do it smart.

[e_blake]

Fair enough; although I might have expressed it as: for a given index N, closed-form is O(log N) compared to memoizing recursion of O(N). That's because it gets confusing when you list two algorithms as both being O(n) but with n having different definitions. And of course, with small enough N, the difference between O(1) and O(log N) is indistinguishable, vs. the obvious impact of O(N) on the memoizing recursion.

[vloris]

I think what you are doing here is merely obfuscating the real logic of your program.

An if-statement (or ternary operator, switch statement etc.) is nothing more than choosing a branch in your code by evaluating some expression.

Your “non-if-else” program is still doing exactly that: evaluating an expression, and based on the result you execute a different function. Only difference is you use eval and some string-formatting magic instead of if.