Exponential processing time increase with case statement nested parentheses

[Durbatuluk1701]

Throughout I am utilizing CakeML v2274.

Given two programs, one with and one without nested parentheses in case statements:

fun fib n = 
case (n = 1) of
	True => 1
| False =>
case (n = 2) of
	True => 2
| False =>
case (n = 3) of
	True => 3
| False =>
case (n = 4) of
	True => 5
| False =>
case (n = 5) of
	True => 8
| False =>
case (n = 6) of
	True => 13
| False =>
case (n = 7) of
	True => 21
| False =>
case (n = 8) of
	True => 34
| False =>
case (n = 9) of
	True => 55
| False =>fib (n - 1) + fib (n - 2)

vs.

fun fib n = 
case (n = 1) of
	True => 1
| False =>(
case (n = 2) of
	True => 2
| False =>(
case (n = 3) of
	True => 3
| False =>(
case (n = 4) of
	True => 5
| False =>(
case (n = 5) of
	True => 8
| False =>(
case (n = 6) of
	True => 13
| False =>(
case (n = 7) of
	True => 21
| False =>(
case (n = 8) of
	True => 34
| False =>(
case (n = 9) of
	True => 55
| False =>fib (n - 1) + fib (n - 2)
))))))))

The time it takes to run cake < fib.cml > /dev/null for the one WITH parentheses will take much longer than the one without.

In particular, I generated the following benchmark showing the exponential increase given the nesting depth:

Code used to generate benchmark

import math
import time
import subprocess
import matplotlib.pyplot as plt


def fib_spec(i):
    if i <= 1:
        return 1
    else:
        return fib_spec(i - 1) + fib_spec(i - 2)

def file_name(n, parens):
    return f"./test_dir/fib_{str('no_') if not parens else '_'}parens_{n}.cml"

def create_file_with_n(n, parens):
    with open(file_name(n, parens), "w+") as fd:
      fd.write(f"fun fib n = \n")
      for i in range(1, n):
          fd.write(f"case (n = {i}) of\n\tTrue => {fib_spec(i)}\n| False =>")
          if i == n - 1:
              fd.write("fib (n - 1) + fib (n - 2)\n")
              close_parens = ")" * (n - 2)
              if parens:
                  fd.write(close_parens)
          else:
              if parens:
                  fd.write("(\n")
              else:
                  fd.write("\n")


def time_file_exec(n, parens):
    create_file_with_n(n, parens)
    print(f"Processing fib({n}) with parens={parens}")
    fd = open(file_name(n, parens), "r")
    start = time.time()
    subprocess.run(["cake"], stdin=fd, stdout=subprocess.DEVNULL)
    end = time.time()
    return math.floor((end - start) * 1000)

min_iters = 5
max_iters = 20

x = [i for i in range(min_iters,max_iters)]
parens = [time_file_exec(i, True) for i in range(min_iters,max_iters)]
print(parens)
no_parens = [time_file_exec(i, False) for i in range(min_iters,max_iters)]

# Make an array for x vs. parens and x vs. no_parens
plt.plot(x, parens, label="With Parens")
plt.plot(x, no_parens, label="Without Parens")
plt.xlabel('depth')
plt.ylabel('Time (ms)')

# make the scale logarithmic base 2
plt.yscale('log', base=2)
# make y scale tick marks appear
plt.yticks([math.pow(2, i) for i in range(8, 15)])

# save the plot to a file
plt.savefig("fib_plot.png")

Another thing I will mention, I tried testing this with if statements and did not see the same exponential increase