{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# Reducing Failure-Inducing Inputs\n",
    "\n",
    "By construction, fuzzers create inputs that may be hard to read.  This causes issues during _debugging_, when a human has to analyze the exact cause of the failure.  In this chapter, we present techniques that _automatically reduce and simplify failure-inducing inputs to a minimum_ in order to ease debugging."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.511416Z",
     "iopub.status.busy": "2024-01-18T17:18:36.510759Z",
     "iopub.status.idle": "2024-01-18T17:18:36.572317Z",
     "shell.execute_reply": "2024-01-18T17:18:36.571978Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"640\"\n",
       "            height=\"360\"\n",
       "            src=\"https://www.youtube-nocookie.com/embed/JOv1xGVdXAU\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "            \n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.IFrame at 0x10734b3d0>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from bookutils import YouTubeVideo\n",
    "YouTubeVideo('JOv1xGVdXAU')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Prerequisites**\n",
    "\n",
    "* The simple \"delta debugging\" technique for reduction has no specific prerequisites.\n",
    "* As reduction is typically used together with fuzzing, reading the [chapter on basic fuzzing](Fuzzer.ipynb) is a good idea.\n",
    "* The later grammar-based techniques require knowledge on [derivation trees](GrammarFuzzer.ipynb) and [parsing](Parser.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Synopsis\n",
    "<!-- Automatically generated. Do not edit. -->\n",
    "\n",
    "To [use the code provided in this chapter](Importing.ipynb), write\n",
    "\n",
    "```python\n",
    ">>> from fuzzingbook.Reducer import <identifier>\n",
    "```\n",
    "\n",
    "and then make use of the following features.\n",
    "\n",
    "\n",
    "A _reducer_ takes a failure-inducing input and reduces it to the minimum that still reproduces the failure.  This chapter provides `Reducer` classes that implement such reducers.\n",
    "\n",
    "Here is a simple example: An arithmetic expression causes an error in the Python interpreter:\n",
    "\n",
    "```python\n",
    ">>> !python -c 'x = 1 + 2 * 3 / 0'\n",
    "Traceback (most recent call last):\r\n",
    "  File \"<string>\", line 1, in <module>\r\n",
    "ZeroDivisionError: division by zero\r\n",
    "\n",
    "```\n",
    "Can we reduce this input to a minimum?  To use a `Reducer`, one first has to build a `Runner` whose outcome is `FAIL` if the precise error occurs.  We therefore build a `ZeroDivisionRunner` whose `run()` method will specifically return a `FAIL` outcome if a `ZeroDivisionError` occurs.\n",
    "\n",
    "```python\n",
    ">>> from Fuzzer import ProgramRunner\n",
    ">>> import subprocess\n",
    ">>> class ZeroDivisionRunner(ProgramRunner):\n",
    ">>>     \"\"\"Make outcome 'FAIL' if ZeroDivisionError occurs\"\"\"\n",
    ">>> \n",
    ">>>     def run(self, inp: str = \"\") -> Tuple[subprocess.CompletedProcess, Outcome]:\n",
    ">>>         process, outcome = super().run(inp)\n",
    ">>>         if process.stderr.find('ZeroDivisionError') >= 0:\n",
    ">>>             outcome = 'FAIL'\n",
    ">>>         return process, outcome\n",
    "```\n",
    "If we feed this expression into a `ZeroDivisionRunner`, it will produce an outcome of `FAIL` as designed.\n",
    "\n",
    "```python\n",
    ">>> python_input = \"x = 1 + 2 * 3 / 0\"\n",
    ">>> python_runner = ZeroDivisionRunner(\"python\")\n",
    ">>> process, outcome = python_runner.run(python_input)\n",
    ">>> outcome\n",
    "'FAIL'\n",
    "```\n",
    "Delta Debugging is a simple and robust reduction algorithm.  We can tie a `DeltaDebuggingReducer` to this runner, and have it determine the substring that causes the `python` program to fail:\n",
    "\n",
    "```python\n",
    ">>> dd = DeltaDebuggingReducer(python_runner)\n",
    ">>> dd.reduce(python_input)\n",
    "'3/0'\n",
    "```\n",
    "The input is reduced to the minimum: We get the essence of the division by zero.\n",
    "\n",
    "![](PICS/Reducer-synopsis-1.svg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Why Reducing?\n",
    "\n",
    "At this point, we have seen a number of test generation techniques that all in some form produce inputs in order to trigger failures.  If they are successful – that is, the program actually fails – we must find out why the failure occurred and how to fix it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Here's an example of such a situation.  We have a class `MysteryRunner` with a `run()` method that – given its code – can occasionally fail.  But under which circumstances does this actually happen?  We have deliberately obscured the exact condition in order to make this non-obvious."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "button": false,
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.594592Z",
     "iopub.status.busy": "2024-01-18T17:18:36.594412Z",
     "iopub.status.idle": "2024-01-18T17:18:36.596571Z",
     "shell.execute_reply": "2024-01-18T17:18:36.596304Z"
    },
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import bookutils.setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.598074Z",
     "iopub.status.busy": "2024-01-18T17:18:36.597967Z",
     "iopub.status.idle": "2024-01-18T17:18:36.599516Z",
     "shell.execute_reply": "2024-01-18T17:18:36.599268Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from bookutils import quiz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.600876Z",
     "iopub.status.busy": "2024-01-18T17:18:36.600792Z",
     "iopub.status.idle": "2024-01-18T17:18:36.602479Z",
     "shell.execute_reply": "2024-01-18T17:18:36.602245Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from typing import Tuple, List, Sequence, Any, Optional"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.604056Z",
     "iopub.status.busy": "2024-01-18T17:18:36.603963Z",
     "iopub.status.idle": "2024-01-18T17:18:36.630635Z",
     "shell.execute_reply": "2024-01-18T17:18:36.630361Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from ExpectError import ExpectError"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.632256Z",
     "iopub.status.busy": "2024-01-18T17:18:36.632166Z",
     "iopub.status.idle": "2024-01-18T17:18:36.684307Z",
     "shell.execute_reply": "2024-01-18T17:18:36.684031Z"
    },
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "from Fuzzer import RandomFuzzer, Runner, Outcome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.685953Z",
     "iopub.status.busy": "2024-01-18T17:18:36.685870Z",
     "iopub.status.idle": "2024-01-18T17:18:36.687451Z",
     "shell.execute_reply": "2024-01-18T17:18:36.687212Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.688953Z",
     "iopub.status.busy": "2024-01-18T17:18:36.688867Z",
     "iopub.status.idle": "2024-01-18T17:18:36.690955Z",
     "shell.execute_reply": "2024-01-18T17:18:36.690719Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class MysteryRunner(Runner):\n",
    "    def run(self, inp: str) -> Tuple[str, Outcome]:\n",
    "        x = inp.find(chr(0o17 + 0o31))\n",
    "        y = inp.find(chr(0o27 + 0o22))\n",
    "        if x >= 0 and y >= 0 and x < y:\n",
    "            return (inp, Runner.FAIL)\n",
    "        else:\n",
    "            return (inp, Runner.PASS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let us fuzz the function until we find a failing input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.692579Z",
     "iopub.status.busy": "2024-01-18T17:18:36.692427Z",
     "iopub.status.idle": "2024-01-18T17:18:36.694802Z",
     "shell.execute_reply": "2024-01-18T17:18:36.694541Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "mystery = MysteryRunner()\n",
    "random_fuzzer = RandomFuzzer()\n",
    "while True:\n",
    "    inp = random_fuzzer.fuzz()\n",
    "    result, outcome = mystery.run(inp)\n",
    "    if outcome == mystery.FAIL:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.696222Z",
     "iopub.status.busy": "2024-01-18T17:18:36.696133Z",
     "iopub.status.idle": "2024-01-18T17:18:36.698279Z",
     "shell.execute_reply": "2024-01-18T17:18:36.698032Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "' 7:,>((/$$-/->.;.=;(.%!:50#7*8=$&&=$9!%6(4=&69\\':\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "failing_input = result\n",
    "failing_input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Something in this input causes `MysteryRunner` to fail.  But what is it?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Manual Input Reduction\n",
    "\n",
    "One important step in the debugging process is _reduction_ – that is, to identify those circumstances of a failure that are relevant for the failure to occur, and to _omit_ (if possible) those parts that are not.  As Kernighan and Pike \\cite{Kernighan1999} put it:\n",
    "\n",
    "> For every circumstance of the problem, check whether it is relevant for the problem to occur.  If it is not, remove it from the problem report or the test case in question."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Specifically for inputs, they suggest a _divide and conquer_ process:\n",
    "\n",
    "> Proceed by binary search.  Throw away half the input and see if the output is still wrong; if not, go back to the previous state and discard the other half of the input.\n",
    "\n",
    "This is something we can easily try out, using our last generated input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.699802Z",
     "iopub.status.busy": "2024-01-18T17:18:36.699698Z",
     "iopub.status.idle": "2024-01-18T17:18:36.701629Z",
     "shell.execute_reply": "2024-01-18T17:18:36.701380Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "' 7:,>((/$$-/->.;.=;(.%!:50#7*8=$&&=$9!%6(4=&69\\':\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "failing_input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For instance, we can see whether the error still occurs if we only feed in the first half:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.703020Z",
     "iopub.status.busy": "2024-01-18T17:18:36.702922Z",
     "iopub.status.idle": "2024-01-18T17:18:36.705076Z",
     "shell.execute_reply": "2024-01-18T17:18:36.704836Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(\" 7:,>((/$$-/->.;.=;(.%!:50#7*8=$&&=$9!%6(4=&69':\", 'PASS')"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "half_length = len(failing_input) // 2   # // is integer division\n",
    "first_half = failing_input[:half_length]\n",
    "mystery.run(first_half)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Nope – the first half alone does not suffice.  Maybe the second half?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.706517Z",
     "iopub.status.busy": "2024-01-18T17:18:36.706414Z",
     "iopub.status.idle": "2024-01-18T17:18:36.708437Z",
     "shell.execute_reply": "2024-01-18T17:18:36.708166Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#', 'PASS')"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "second_half = failing_input[half_length:]\n",
    "mystery.run(second_half)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This did not go so well either.  We may still proceed by cutting away _smaller chunks_ – say, one character after another.  If our test is deterministic and easily repeated, it is clear that this process eventually will yield a reduced input.  But still, it is a rather inefficient process, especially for long inputs.  What we need is a _strategy_ that effectively minimizes a failure-inducing input – a strategy that can be automated."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Delta Debugging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "One strategy to effectively reduce failure-inducing inputs is _delta debugging_ \\cite{Zeller2002}.  Delta Debugging implements the \"binary search\" strategy, as listed above, but with a twist: If neither half fails (also as above), it keeps on cutting away smaller and smaller chunks from the input, until it eliminates individual characters.  Thus, after cutting away the first half, we cut away\n",
    "the first quarter, the second quarter, and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let us illustrate this on our example, and see what happens if we cut away the first quarter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.710284Z",
     "iopub.status.busy": "2024-01-18T17:18:36.710164Z",
     "iopub.status.idle": "2024-01-18T17:18:36.712622Z",
     "shell.execute_reply": "2024-01-18T17:18:36.712362Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('50#7*8=$&&=$9!%6(4=&69\\':\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#',\n",
       " 'FAIL')"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quarter_length = len(failing_input) // 4\n",
    "input_without_first_quarter = failing_input[quarter_length:]\n",
    "mystery.run(input_without_first_quarter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Ah! This has failed, and reduced our failing input by 25%.  Let's remove another quarter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.714120Z",
     "iopub.status.busy": "2024-01-18T17:18:36.714022Z",
     "iopub.status.idle": "2024-01-18T17:18:36.716189Z",
     "shell.execute_reply": "2024-01-18T17:18:36.715921Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#', 'PASS')"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_without_first_and_second_quarter = failing_input[quarter_length * 2:]\n",
    "mystery.run(input_without_first_and_second_quarter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This is not too surprising, as we had that one before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.717639Z",
     "iopub.status.busy": "2024-01-18T17:18:36.717530Z",
     "iopub.status.idle": "2024-01-18T17:18:36.719399Z",
     "shell.execute_reply": "2024-01-18T17:18:36.719148Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "second_half"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.720807Z",
     "iopub.status.busy": "2024-01-18T17:18:36.720707Z",
     "iopub.status.idle": "2024-01-18T17:18:36.722622Z",
     "shell.execute_reply": "2024-01-18T17:18:36.722354Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_without_first_and_second_quarter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "How about removing the third quarter, then?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.724038Z",
     "iopub.status.busy": "2024-01-18T17:18:36.723929Z",
     "iopub.status.idle": "2024-01-18T17:18:36.726234Z",
     "shell.execute_reply": "2024-01-18T17:18:36.725960Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(\"50#7*8=$&&=$9!%6(4=&69':<7+1<2!4$>92+$1<(3%&5''>#\", 'PASS')"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_without_first_and_third_quarter = failing_input[quarter_length:\n",
    "                                                      quarter_length * 2] + failing_input[quarter_length * 3:]\n",
    "mystery.run(input_without_first_and_third_quarter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Ok.  Let us remove the fourth quarter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.727837Z",
     "iopub.status.busy": "2024-01-18T17:18:36.727724Z",
     "iopub.status.idle": "2024-01-18T17:18:36.729942Z",
     "shell.execute_reply": "2024-01-18T17:18:36.729668Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('50#7*8=$&&=$9!%6(4=&69\\':\\'<3+0-3.24#7=!&60)2/+\";+', 'FAIL')"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_without_first_and_fourth_quarter = failing_input[quarter_length:quarter_length * 3]\n",
    "mystery.run(input_without_first_and_fourth_quarter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Yes!  This has succeeded.  Our input is now 50% smaller."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We have now tried to remove pieces that make up $\\frac{1}{2}$ and $\\frac{1}{4}$ of the original failing string.  In the next iteration, we would go and remove even smaller pieces – $\\frac{1}{8}$, $\\frac{1}{16}$ and so on.  We continue until we are down to $\\frac{1}{97}$ – that is, individual characters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "However, this is something we happily let a computer do for us.  We first introduce a `Reducer` class as an abstract superclass for all kinds of reducers.  The `test()` method runs a single test (with logging, if wanted); the `reduce()` method will eventually reduce an input to the minimum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.731543Z",
     "iopub.status.busy": "2024-01-18T17:18:36.731441Z",
     "iopub.status.idle": "2024-01-18T17:18:36.734246Z",
     "shell.execute_reply": "2024-01-18T17:18:36.733945Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class Reducer:\n",
    "    \"\"\"Base class for reducers.\"\"\"\n",
    "\n",
    "    def __init__(self, runner: Runner, log_test: bool = False) -> None:\n",
    "        \"\"\"Attach reducer to the given `runner`\"\"\"\n",
    "        self.runner = runner\n",
    "        self.log_test = log_test\n",
    "        self.reset()\n",
    "\n",
    "    def reset(self) -> None:\n",
    "        \"\"\"Reset the test counter to zero. To be extended in subclasses.\"\"\"\n",
    "        self.tests = 0\n",
    "\n",
    "    def test(self, inp: str) -> Outcome:\n",
    "        \"\"\"Test with input `inp`. Return outcome.\n",
    "        To be extended in subclasses.\"\"\"\n",
    "\n",
    "        result, outcome = self.runner.run(inp)\n",
    "        self.tests += 1\n",
    "        if self.log_test:\n",
    "            print(\"Test #%d\" % self.tests, repr(inp), repr(len(inp)), outcome)\n",
    "        return outcome\n",
    "\n",
    "    def reduce(self, inp: str) -> str:\n",
    "        \"\"\"Reduce input `inp`. Return reduced input.\n",
    "        To be defined in subclasses.\"\"\"\n",
    "\n",
    "        self.reset()\n",
    "        # Default: Don't reduce\n",
    "        return inp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The `CachingReducer` variant saves test results, such that we don't have to run the same tests again and again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.735750Z",
     "iopub.status.busy": "2024-01-18T17:18:36.735649Z",
     "iopub.status.idle": "2024-01-18T17:18:36.737859Z",
     "shell.execute_reply": "2024-01-18T17:18:36.737601Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class CachingReducer(Reducer):\n",
    "    \"\"\"A reducer that also caches test outcomes\"\"\"\n",
    "\n",
    "    def reset(self):\n",
    "        super().reset()\n",
    "        self.cache = {}\n",
    "\n",
    "    def test(self, inp):\n",
    "        if inp in self.cache:\n",
    "            return self.cache[inp]\n",
    "\n",
    "        outcome = super().test(inp)\n",
    "        self.cache[inp] = outcome\n",
    "        return outcome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Here comes the _Delta Debugging_ reducer.  Delta Debugging implements the strategy sketched above: It first removes larger chunks of size $\\frac{1}{2}$; if this does not fail, then we proceed to chunks of size $\\frac{1}{4}$, then $\\frac{1}{8}$ and so on."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Our implementation uses almost the same Python code as Zeller in \\cite{Zeller2002}; the only difference is that it has been adapted to work on Python 3 and our `Runner` framework.  The variable `n` (initially 2) indicates the granularity – in each step, chunks of size $\\frac{1}{n}$ are cut away.  If none of the test fails (`some_complement_is_failing` is False), then `n` is doubled – until it reaches the length of the input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.739545Z",
     "iopub.status.busy": "2024-01-18T17:18:36.739428Z",
     "iopub.status.idle": "2024-01-18T17:18:36.742399Z",
     "shell.execute_reply": "2024-01-18T17:18:36.742102Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class DeltaDebuggingReducer(CachingReducer):\n",
    "    \"\"\"Reduce inputs using delta debugging.\"\"\"\n",
    "\n",
    "    def reduce(self, inp: str) -> str:\n",
    "        \"\"\"Reduce input `inp` using delta debugging. Return reduced input.\"\"\"\n",
    "\n",
    "        self.reset()\n",
    "        assert self.test(inp) != Runner.PASS\n",
    "\n",
    "        n = 2     # Initial granularity\n",
    "        while len(inp) >= 2:\n",
    "            start = 0.0\n",
    "            subset_length = len(inp) / n\n",
    "            some_complement_is_failing = False\n",
    "\n",
    "            while start < len(inp):\n",
    "                complement = inp[:int(start)] + \\\n",
    "                    inp[int(start + subset_length):]\n",
    "\n",
    "                if self.test(complement) == Runner.FAIL:\n",
    "                    inp = complement\n",
    "                    n = max(n - 1, 2)\n",
    "                    some_complement_is_failing = True\n",
    "                    break\n",
    "\n",
    "                start += subset_length\n",
    "\n",
    "            if not some_complement_is_failing:\n",
    "                if n == len(inp):\n",
    "                    break\n",
    "                n = min(n * 2, len(inp))\n",
    "\n",
    "        return inp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "To see how the `DeltaDebuggingReducer` works, let us run it on our failing input.  With each step, we see how the remaining input gets smaller and smaller, until only two characters remain:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.744073Z",
     "iopub.status.busy": "2024-01-18T17:18:36.743960Z",
     "iopub.status.idle": "2024-01-18T17:18:36.747364Z",
     "shell.execute_reply": "2024-01-18T17:18:36.747089Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1 ' 7:,>((/$$-/->.;.=;(.%!:50#7*8=$&&=$9!%6(4=&69\\':\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#' 97 FAIL\n",
      "Test #2 '\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#' 49 PASS\n",
      "Test #3 \" 7:,>((/$$-/->.;.=;(.%!:50#7*8=$&&=$9!%6(4=&69':\" 48 PASS\n",
      "Test #4 '50#7*8=$&&=$9!%6(4=&69\\':\\'<3+0-3.24#7=!&60)2/+\";+<7+1<2!4$>92+$1<(3%&5\\'\\'>#' 73 FAIL\n",
      "Test #5 \"50#7*8=$&&=$9!%6(4=&69':<7+1<2!4$>92+$1<(3%&5''>#\" 49 PASS\n",
      "Test #6 '50#7*8=$&&=$9!%6(4=&69\\':\\'<3+0-3.24#7=!&60)2/+\";+' 48 FAIL\n",
      "Test #7 '\\'<3+0-3.24#7=!&60)2/+\";+' 24 PASS\n",
      "Test #8 \"50#7*8=$&&=$9!%6(4=&69':\" 24 PASS\n",
      "Test #9 '9!%6(4=&69\\':\\'<3+0-3.24#7=!&60)2/+\";+' 36 FAIL\n",
      "Test #10 '9!%6(4=&69\\':=!&60)2/+\";+' 24 FAIL\n",
      "Test #11 '=!&60)2/+\";+' 12 PASS\n",
      "Test #12 \"9!%6(4=&69':\" 12 PASS\n",
      "Test #13 '=&69\\':=!&60)2/+\";+' 18 PASS\n",
      "Test #14 '9!%6(4=!&60)2/+\";+' 18 FAIL\n",
      "Test #15 '9!%6(42/+\";+' 12 PASS\n",
      "Test #16 '9!%6(4=!&60)' 12 FAIL\n",
      "Test #17 '=!&60)' 6 PASS\n",
      "Test #18 '9!%6(4' 6 PASS\n",
      "Test #19 '6(4=!&60)' 9 FAIL\n",
      "Test #20 '6(460)' 6 FAIL\n",
      "Test #21 '60)' 3 PASS\n",
      "Test #22 '6(4' 3 PASS\n",
      "Test #23 '(460)' 5 FAIL\n",
      "Test #24 '460)' 4 PASS\n",
      "Test #25 '(0)' 3 FAIL\n",
      "Test #26 '0)' 2 PASS\n",
      "Test #27 '(' 1 PASS\n",
      "Test #28 '()' 2 FAIL\n",
      "Test #29 ')' 1 PASS\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'()'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dd_reducer = DeltaDebuggingReducer(mystery, log_test=True)\n",
    "dd_reducer.reduce(failing_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Now we know why `MysteryRunner` fails – it suffices that the input contains two matching parentheses.  Delta Debugging determines this in 29 steps.  Its result is _1-minimal_, meaning that every character contained is required to produce the error; removing any (as seen in tests `#27` and `#29`, above) no longer makes the test fail.  This property is guaranteed by the delta debugging algorithm, which in its last stage always tries to delete characters one by one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A reduced test case such as the one above has many advantages:\n",
    "\n",
    "* A reduced test case __reduces the _cognitive load_ of the programmer__.  The test case is shorter and focused, and thus does not burden the programmer with irrelevant details.  A reduced input typically leads to shorter executions and smaller program states, both of which reduce the search space as it comes to understanding the bug.  In our case, we have eliminated lots of irrelevant input – only the two characters the reduced input contains are relevant.\n",
    "\n",
    "* A reduced test case __is easier to communicate__.  All one needs here is the summary: `MysteryRunner fails on \"()\"`, which is much better than `MysteryRunner fails on a 4100-character input (attached)`.\n",
    "\n",
    "* A reduced test case helps in __identifying duplicates__.  If similar bugs have been reported already, and all of them have been reduced to the same cause (namely that the input contains matching parentheses), then it becomes obvious that all these bugs are different symptoms of the same underlying cause – and would all be resolved at once with one code fix."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "How effective is delta debugging?  In the best case (when the left half or the right half fails), the number of tests is logarithmic proportional to the length $n$ of an input (i.e., $O(\\log_2 n)$); this is the same complexity as binary search.  In the worst case, though, delta debugging can require a number of tests proportional to $n^2$ (i.e., $O(n^2)$) – this happens in the case when we are down to character granularity, and we have to repeatedly tried to delete all characters, only to find that deleting the last character results in a failure \\cite{Zeller2002}.  (This is a pretty pathological situation, though.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In general, delta debugging is a robust algorithm that is easy to implement, easy to deploy, and easy to use – provided that the underlying test case is deterministic and runs quickly enough to warrant a number of experiments.  As these are the same prerequisites that make fuzzing effective, delta debugging makes an excellent companion to fuzzing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.748920Z",
     "iopub.status.busy": "2024-01-18T17:18:36.748840Z",
     "iopub.status.idle": "2024-01-18T17:18:36.752944Z",
     "shell.execute_reply": "2024-01-18T17:18:36.752717Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    \n",
       "    <script>\n",
       "    var bad_answers = new Map();\n",
       "\n",
       "    function answer(quiz_id) {\n",
       "        ans = 0;\n",
       "        for (i = 1;; i++) {\n",
       "            checkbox = document.getElementById(quiz_id + \"-\" + i.toString());\n",
       "            if (!checkbox)\n",
       "                break;\n",
       "            if (checkbox.checked)\n",
       "                ans |= (1 << i);\n",
       "        }\n",
       "        return ans;\n",
       "    }\n",
       "    function check_selection(quiz_id, correct_answer, multiple_choice, hint) {\n",
       "        given_answer = answer(quiz_id);\n",
       "        if (given_answer == correct_answer)\n",
       "        {\n",
       "            document.getElementById(quiz_id + \"-submit\").value = \"Correct!\";\n",
       "            document.getElementById(quiz_id + \"-hint\").innerHTML = \"\";\n",
       "\n",
       "            for (i = 1;; i++) {\n",
       "                checkbox = document.getElementById(quiz_id + \"-\" + i.toString());\n",
       "                label = document.getElementById(quiz_id + \"-\" + i.toString() + \"-label\")\n",
       "                if (!checkbox)\n",
       "                    break;\n",
       "    \n",
       "                if (checkbox.checked) {\n",
       "                    label.style.fontWeight = \"bold\";\n",
       "                }\n",
       "                else {\n",
       "                    label.style.textDecoration = \"line-through\";\n",
       "                }\n",
       "            }\n",
       "        }\n",
       "        else \n",
       "        {\n",
       "            document.getElementById(quiz_id + \"-submit\").value = \"Try again\";\n",
       "            \n",
       "            if (!bad_answers.has(quiz_id)) {\n",
       "                bad_answers.set(quiz_id, 1);\n",
       "            }\n",
       "            else {\n",
       "                bad_answers.set(quiz_id, bad_answers.get(quiz_id) + 1);\n",
       "            }\n",
       "\n",
       "            if (bad_answers.get(quiz_id) >= 2 && hint.length > 0) {\n",
       "                document.getElementById(quiz_id + \"-hint\").innerHTML = \n",
       "                    \"&nbsp;&nbsp;(Hint: <code>\" + hint + \"</code>)\";\n",
       "            }\n",
       "\n",
       "            if (!multiple_choice) {\n",
       "                for (i = 1;; i++) {\n",
       "                    checkbox = document.getElementById(quiz_id + \"-\" + i.toString());\n",
       "                    label = document.getElementById(quiz_id + \"-\" + i.toString() + \"-label\")\n",
       "\n",
       "                    if (!checkbox)\n",
       "                        break;\n",
       "                    if (checkbox.checked) {\n",
       "                        label.style.textDecoration = \"line-through\";\n",
       "                    }\n",
       "                }\n",
       "            }\n",
       "        }\n",
       "    }\n",
       "    function clear_selection(quiz_id) {\n",
       "        document.getElementById(quiz_id + \"-submit\").value = \"Submit\";\n",
       "        document.getElementById(quiz_id + \"-hint\").innerHTML = \"\";\n",
       "    }\n",
       "    </script>\n",
       "    \n",
       "    <div class=\"quiz\">\n",
       "    <h3 class=\"quiz_title\">Quiz</h3>\n",
       "    <p>\n",
       "    <div class=\"quiz_question\">What happens if the function under test does not fail?</div>\n",
       "    </p>\n",
       "    <p>\n",
       "    <div class=\"quiz_options\" title=\"Pick a choice.\">\n",
       "    \n",
       "        <input type=\"radio\" name=\"9d7f968a-b625-11ee-8665-6298cf1a5790\" id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-1\" onclick=\"clear_selection('9d7f968a-b625-11ee-8665-6298cf1a5790')\">\n",
       "        <label id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-1-label\" for=\"9d7f968a-b625-11ee-8665-6298cf1a5790-1\">Delta debugging searches for the minimal input that produces the same result</label><br>\n",
       "    \n",
       "        <input type=\"radio\" name=\"9d7f968a-b625-11ee-8665-6298cf1a5790\" id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-2\" onclick=\"clear_selection('9d7f968a-b625-11ee-8665-6298cf1a5790')\">\n",
       "        <label id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-2-label\" for=\"9d7f968a-b625-11ee-8665-6298cf1a5790-2\">Delta debugging starts a fuzzer to find a failure</label><br>\n",
       "    \n",
       "        <input type=\"radio\" name=\"9d7f968a-b625-11ee-8665-6298cf1a5790\" id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-3\" onclick=\"clear_selection('9d7f968a-b625-11ee-8665-6298cf1a5790')\">\n",
       "        <label id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-3-label\" for=\"9d7f968a-b625-11ee-8665-6298cf1a5790-3\">Delta debugging raises an AssertionError</label><br>\n",
       "    \n",
       "        <input type=\"radio\" name=\"9d7f968a-b625-11ee-8665-6298cf1a5790\" id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-4\" onclick=\"clear_selection('9d7f968a-b625-11ee-8665-6298cf1a5790')\">\n",
       "        <label id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-4-label\" for=\"9d7f968a-b625-11ee-8665-6298cf1a5790-4\">Delta debugging runs forever in a loop</label><br>\n",
       "    \n",
       "    </div>\n",
       "    </p>\n",
       "    <input id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-submit\" type=\"submit\" value=\"Submit\" onclick=\"check_selection('9d7f968a-b625-11ee-8665-6298cf1a5790', 8, 0, '0 ** 0 + 1 ** 0 + 0 ** 1 + 1 ** 1')\">\n",
       "    <span class=\"quiz_hint\" id=\"9d7f968a-b625-11ee-8665-6298cf1a5790-hint\"></span>\n",
       "    </div>\n",
       "    "
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quiz(\"What happens if the function under test does not fail?\",\n",
    "    [\n",
    "        \"Delta debugging searches for the minimal input\"\n",
    "        \" that produces the same result\",\n",
    "        \"Delta debugging starts a fuzzer to find a failure\",\n",
    "        \"Delta debugging raises an AssertionError\",\n",
    "        \"Delta debugging runs forever in a loop\",\n",
    "    ], '0 ** 0 + 1 ** 0 + 0 ** 1 + 1 ** 1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Indeed, `DeltaDebugger` checks if its assumptions hold. If not, an assertion fails."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.754420Z",
     "iopub.status.busy": "2024-01-18T17:18:36.754341Z",
     "iopub.status.idle": "2024-01-18T17:18:36.756150Z",
     "shell.execute_reply": "2024-01-18T17:18:36.755916Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1 'I am a passing input' 20 PASS\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Traceback (most recent call last):\n",
      "  File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_77032/3080932113.py\", line 2, in <cell line: 1>\n",
      "    dd_reducer.reduce(\"I am a passing input\")\n",
      "  File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_77032/2870451724.py\", line 8, in reduce\n",
      "    assert self.test(inp) != Runner.PASS\n",
      "AssertionError (expected)\n"
     ]
    }
   ],
   "source": [
    "with ExpectError():\n",
    "    dd_reducer.reduce(\"I am a passing input\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "toc-hr-collapsed": false
   },
   "source": [
    "## Grammar-Based Input Reduction\n",
    "\n",
    "If the input language is syntactically complex, delta debugging may take several attempts at reduction, and may not be able to reduce inputs at all.  In the second half of this chapter, we thus introduce an algorithm named _Grammar-Based Reduction_ (or GRABR for short) that makes use of _grammars_ to reduce syntactically complex inputs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Lexical Reduction vs. Syntactic Rules\n",
    "\n",
    "Despite its general robustness, there are situations in which delta debugging might be inefficient or outright fail.  As an example, consider some _expression input_ such as `1 + (2 * 3)`.  Delta debugging requires a number of tests to simplify the failure-inducing input, but it eventually returns a minimal input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.757832Z",
     "iopub.status.busy": "2024-01-18T17:18:36.757719Z",
     "iopub.status.idle": "2024-01-18T17:18:36.761018Z",
     "shell.execute_reply": "2024-01-18T17:18:36.760701Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1 '1 + (2 * 3)' 11 FAIL\n",
      "Test #2 '2 * 3)' 6 PASS\n",
      "Test #3 '1 + (' 5 PASS\n",
      "Test #4 '+ (2 * 3)' 9 FAIL\n",
      "Test #5 '+ ( 3)' 6 FAIL\n",
      "Test #6 ' 3)' 3 PASS\n",
      "Test #7 '+ (' 3 PASS\n",
      "Test #8 ' ( 3)' 5 FAIL\n",
      "Test #9 '( 3)' 4 FAIL\n",
      "Test #10 '3)' 2 PASS\n",
      "Test #11 '( ' 2 PASS\n",
      "Test #12 '(3)' 3 FAIL\n",
      "Test #13 '()' 2 FAIL\n",
      "Test #14 ')' 1 PASS\n",
      "Test #15 '(' 1 PASS\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'()'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expr_input = \"1 + (2 * 3)\"\n",
    "dd_reducer = DeltaDebuggingReducer(mystery, log_test=True)\n",
    "dd_reducer.reduce(expr_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Looking at the tests, above, though, only few of them actually represent syntactically valid arithmetic expressions.  In a practical setting, we may want to test a program which actually _parses_ such expressions, and which would _reject_ all invalid inputs.  We define a class `EvalMysteryRunner` which first _parses_ the given input (according to the rules of our expression grammar), and _only_ if it fits would it be passed to our original `MysteryRunner`.  This simulates a setting in which we test an expression interpreter, and in which only valid inputs can trigger the bug."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:36.762780Z",
     "iopub.status.busy": "2024-01-18T17:18:36.762691Z",
     "iopub.status.idle": "2024-01-18T17:18:37.205545Z",
     "shell.execute_reply": "2024-01-18T17:18:37.205223Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Grammars import EXPR_GRAMMAR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:37.207392Z",
     "iopub.status.busy": "2024-01-18T17:18:37.207263Z",
     "iopub.status.idle": "2024-01-18T17:18:37.290969Z",
     "shell.execute_reply": "2024-01-18T17:18:37.290635Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Parser import EarleyParser, Parser  # minor dependency"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:37.293253Z",
     "iopub.status.busy": "2024-01-18T17:18:37.293106Z",
     "iopub.status.idle": "2024-01-18T17:18:37.295482Z",
     "shell.execute_reply": "2024-01-18T17:18:37.295173Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class EvalMysteryRunner(MysteryRunner):\n",
    "    def __init__(self) -> None:\n",
    "        self.parser = EarleyParser(EXPR_GRAMMAR)\n",
    "\n",
    "    def run(self, inp: str) -> Tuple[str, Outcome]:\n",
    "        try:\n",
    "            tree, *_ = self.parser.parse(inp)\n",
    "        except SyntaxError:\n",
    "            return (inp, Runner.UNRESOLVED)\n",
    "\n",
    "        return super().run(inp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:37.297171Z",
     "iopub.status.busy": "2024-01-18T17:18:37.297056Z",
     "iopub.status.idle": "2024-01-18T17:18:37.298758Z",
     "shell.execute_reply": "2024-01-18T17:18:37.298482Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "eval_mystery = EvalMysteryRunner()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Under these circumstances, it turns out that delta debugging utterly fails.  None of the reductions it applies yield a syntactically valid input, so the input as a whole remains as complex as it was before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:37.300303Z",
     "iopub.status.busy": "2024-01-18T17:18:37.300187Z",
     "iopub.status.idle": "2024-01-18T17:18:37.311203Z",
     "shell.execute_reply": "2024-01-18T17:18:37.310890Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1 '1 + (2 * 3)' 11 FAIL\n",
      "Test #2 '2 * 3)' 6 UNRESOLVED\n",
      "Test #3 '1 + (' 5 UNRESOLVED\n",
      "Test #4 '+ (2 * 3)' 9 UNRESOLVED\n",
      "Test #5 '1 2 * 3)' 8 UNRESOLVED\n",
      "Test #6 '1 + ( 3)' 8 UNRESOLVED\n",
      "Test #7 '1 + (2 *' 8 UNRESOLVED\n",
      "Test #8 ' + (2 * 3)' 10 UNRESOLVED\n",
      "Test #9 '1+ (2 * 3)' 10 UNRESOLVED\n",
      "Test #10 '1 (2 * 3)' 9 UNRESOLVED\n",
      "Test #11 '1 + 2 * 3)' 10 UNRESOLVED\n",
      "Test #12 '1 + ( * 3)' 10 UNRESOLVED\n",
      "Test #13 '1 + (2 3)' 9 UNRESOLVED\n",
      "Test #14 '1 + (2 *3)' 10 UNRESOLVED\n",
      "Test #15 '1 + (2 * ' 9 UNRESOLVED\n",
      "Test #16 '1  (2 * 3)' 10 UNRESOLVED\n",
      "Test #17 '1 +(2 * 3)' 10 UNRESOLVED\n",
      "Test #18 '1 + (2* 3)' 10 UNRESOLVED\n",
      "Test #19 '1 + (2  3)' 10 UNRESOLVED\n",
      "Test #20 '1 + (2 * )' 10 UNRESOLVED\n",
      "Test #21 '1 + (2 * 3' 10 UNRESOLVED\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'1 + (2 * 3)'"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dd_reducer = DeltaDebuggingReducer(eval_mystery, log_test=True)\n",
    "dd_reducer.reduce(expr_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This behavior is possible if the program under test has several constraints regarding input validity.  Delta debugging is not aware of these constraints (nor of the input structure in general), so it might violate these constraints again and again."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### A Grammar-Based Reduction Approach\n",
    "\n",
    "To reduce inputs with high syntactical complexity, we use another approach: Rather than reducing the input string, we reduce the _tree_ representing its structure.  The general idea is to start with a _derivation tree_ coming from parsing the input, and then _substitute subtrees by smaller subtrees of the same type_.  These alternate subtrees can either come\n",
    "\n",
    "1. From the tree itself, or\n",
    "2. By applying an alternate grammar expansion using elements from the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let us show these two strategies using an example.  We start with a derivation tree from an arithmetic expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:37.313281Z",
     "iopub.status.busy": "2024-01-18T17:18:37.313091Z",
     "iopub.status.idle": "2024-01-18T17:18:37.314825Z",
     "shell.execute_reply": "2024-01-18T17:18:37.314578Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Grammars import Grammar\n",
    "from GrammarFuzzer import all_terminals, expansion_to_children, display_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:37.316404Z",
     "iopub.status.busy": "2024-01-18T17:18:37.316283Z",
     "iopub.status.idle": "2024-01-18T17:18:37.709449Z",
     "shell.execute_reply": "2024-01-18T17:18:37.709024Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (20230911.1827)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"210pt\" height=\"575pt\"\n",
       " viewBox=\"0.00 0.00 209.62 575.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 571)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-571 205.62,-571 205.62,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<text text-anchor=\"middle\" x=\"81.62\" y=\"-553.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;start&gt;</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<text text-anchor=\"middle\" x=\"81.62\" y=\"-503.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.62,-552.96C81.62,-546.74 81.62,-536.65 81.62,-527.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"85.13,-528.1 81.63,-518.1 78.13,-528.1 85.13,-528.1\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<text text-anchor=\"middle\" x=\"33.62\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M75.74,-502.71C68.76,-495.69 56.89,-483.76 47.53,-474.35\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"50.16,-472.03 40.63,-467.41 45.2,-476.97 50.16,-472.03\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<text text-anchor=\"middle\" x=\"81.62\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\"> + </text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>1&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.62,-502.71C81.62,-496.49 81.62,-486.4 81.62,-477.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"85.13,-477.85 81.63,-467.85 78.13,-477.85 85.13,-477.85\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<text text-anchor=\"middle\" x=\"127.62\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>1&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M87.27,-502.71C93.89,-495.76 105.1,-484 114.03,-474.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"116.53,-477.09 120.89,-467.44 111.46,-472.26 116.53,-477.09\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<text text-anchor=\"middle\" x=\"31.62\" y=\"-402.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.38,-452.46C33.12,-446.24 32.7,-436.15 32.34,-427.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"35.85,-427.45 31.93,-417.6 28.85,-427.74 35.85,-427.45\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<text text-anchor=\"middle\" x=\"27.62\" y=\"-352.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M31.13,-402.21C30.62,-395.99 29.78,-385.9 29.06,-377.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"32.56,-377.02 28.24,-367.35 25.58,-377.6 32.56,-377.02\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<text text-anchor=\"middle\" x=\"20.62\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M26.77,-351.96C25.86,-345.74 24.4,-335.65 23.13,-326.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"26.61,-326.48 21.71,-317.09 19.68,-327.49 26.61,-326.48\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<text text-anchor=\"middle\" x=\"20.62\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">1 (49)</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M20.62,-301.71C20.62,-295.49 20.62,-285.4 20.62,-276.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"24.13,-276.85 20.63,-266.85 17.13,-276.85 24.13,-276.85\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<text text-anchor=\"middle\" x=\"127.62\" y=\"-402.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.62,-452.46C127.62,-446.24 127.62,-436.15 127.62,-427.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"131.13,-427.6 127.63,-417.6 124.13,-427.6 131.13,-427.6\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<text text-anchor=\"middle\" x=\"127.62\" y=\"-352.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.62,-402.21C127.62,-395.99 127.62,-385.9 127.62,-377.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"131.13,-377.35 127.63,-367.35 124.13,-377.35 131.13,-377.35\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>11</title>\n",
       "<text text-anchor=\"middle\" x=\"74.62\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">( (40)</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M121.13,-351.96C113.34,-344.87 100.04,-332.76 89.65,-323.31\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"92.05,-320.75 82.3,-316.61 87.33,-325.93 92.05,-320.75\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>12</title>\n",
       "<text text-anchor=\"middle\" x=\"128.62\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>10&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.75,-351.96C127.88,-345.74 128.09,-335.65 128.27,-326.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"131.76,-327.17 128.47,-317.1 124.76,-327.03 131.76,-327.17\"/>\n",
       "</g>\n",
       "<!-- 24 -->\n",
       "<g id=\"node25\" class=\"node\">\n",
       "<title>24</title>\n",
       "<text text-anchor=\"middle\" x=\"182.62\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">) (41)</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;24 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>10&#45;&gt;24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M134.37,-351.96C142.53,-344.8 156.53,-332.51 167.36,-323.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"169.48,-325.81 174.69,-316.59 164.86,-320.55 169.48,-325.81\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>13</title>\n",
       "<text text-anchor=\"middle\" x=\"128.62\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M128.62,-301.71C128.62,-295.49 128.62,-285.4 128.62,-276.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.13,-276.85 128.63,-266.85 125.13,-276.85 132.13,-276.85\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>14</title>\n",
       "<text text-anchor=\"middle\" x=\"79.62\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>13&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122.62,-251.46C115.49,-244.44 103.37,-232.51 93.81,-223.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"96.34,-220.67 86.76,-216.15 91.43,-225.66 96.34,-220.67\"/>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>18</title>\n",
       "<text text-anchor=\"middle\" x=\"128.62\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\"> * </text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;18 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>13&#45;&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M128.62,-251.46C128.62,-245.24 128.62,-235.15 128.62,-226.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.13,-226.6 128.63,-216.6 125.13,-226.6 132.13,-226.6\"/>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node20\" class=\"node\">\n",
       "<title>19</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;19 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>13&#45;&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M134.27,-251.46C140.89,-244.51 152.1,-232.75 161.03,-223.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"163.53,-225.84 167.89,-216.19 158.46,-221.01 163.53,-225.84\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>15</title>\n",
       "<text text-anchor=\"middle\" x=\"79.62\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;15 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>14&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.62,-201.21C79.62,-194.99 79.62,-184.9 79.62,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"83.13,-176.35 79.63,-166.35 76.13,-176.35 83.13,-176.35\"/>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>16</title>\n",
       "<text text-anchor=\"middle\" x=\"79.62\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 15&#45;&gt;16 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>15&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.62,-150.96C79.62,-144.74 79.62,-134.65 79.62,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"83.13,-126.1 79.63,-116.1 76.13,-126.1 83.13,-126.1\"/>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>17</title>\n",
       "<text text-anchor=\"middle\" x=\"79.62\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">2 (50)</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;17 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>16&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.62,-100.71C79.62,-94.49 79.62,-84.4 79.62,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"83.13,-75.85 79.63,-65.85 76.13,-75.85 83.13,-75.85\"/>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node21\" class=\"node\">\n",
       "<title>20</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 19&#45;&gt;20 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>19&#45;&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.62,-201.21C174.62,-194.99 174.62,-184.9 174.62,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"178.13,-176.35 174.63,-166.35 171.13,-176.35 178.13,-176.35\"/>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node22\" class=\"node\">\n",
       "<title>21</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 20&#45;&gt;21 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>20&#45;&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.62,-150.96C174.62,-144.74 174.62,-134.65 174.62,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"178.13,-126.1 174.63,-116.1 171.13,-126.1 178.13,-126.1\"/>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node23\" class=\"node\">\n",
       "<title>22</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 21&#45;&gt;22 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>21&#45;&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.62,-100.71C174.62,-94.49 174.62,-84.4 174.62,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"178.13,-75.85 174.63,-65.85 171.13,-75.85 178.13,-75.85\"/>\n",
       "</g>\n",
       "<!-- 23 -->\n",
       "<g id=\"node24\" class=\"node\">\n",
       "<title>23</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-0.95\" font-family=\"Times,serif\" font-size=\"14.00\">3 (51)</text>\n",
       "</g>\n",
       "<!-- 22&#45;&gt;23 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>22&#45;&gt;23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.62,-50.46C174.62,-44.24 174.62,-34.15 174.62,-25.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"178.13,-25.6 174.63,-15.6 171.13,-25.6 178.13,-25.6\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x11c78fa90>"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "derivation_tree, *_ = EarleyParser(EXPR_GRAMMAR).parse(expr_input)\n",
    "display_tree(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Simplifying by Replacing Subtrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To simplify this tree, we could replace any `<expr>` symbol up in the tree with some `<expr>` subtree down in the tree.  For instance, we could replace the uppermost `<expr>` with its right `<expr>` subtree, yielding the string `(2 + 3)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:37.711515Z",
     "iopub.status.busy": "2024-01-18T17:18:37.711366Z",
     "iopub.status.idle": "2024-01-18T17:18:37.713383Z",
     "shell.execute_reply": "2024-01-18T17:18:37.713089Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:37.715069Z",
     "iopub.status.busy": "2024-01-18T17:18:37.714959Z",
     "iopub.status.idle": "2024-01-18T17:18:38.110433Z",
     "shell.execute_reply": "2024-01-18T17:18:38.109942Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (20230911.1827)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"157pt\" height=\"475pt\"\n",
       " viewBox=\"0.00 0.00 157.00 474.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 470.5)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-470.5 153,-470.5 153,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-402.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-452.46C76,-446.24 76,-436.15 76,-427.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-427.6 76,-417.6 72.5,-427.6 79.5,-427.6\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-352.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-402.21C76,-395.99 76,-385.9 76,-377.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-377.35 76,-367.35 72.5,-377.35 79.5,-377.35\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<text text-anchor=\"middle\" x=\"22\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">( (40)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-351.96C61.36,-344.8 47.62,-332.51 36.99,-323.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"39.59,-320.65 29.8,-316.6 34.93,-325.87 39.59,-320.65\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-351.96C76,-345.74 76,-335.65 76,-326.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-327.1 76,-317.1 72.5,-327.1 79.5,-327.1\"/>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>16</title>\n",
       "<text text-anchor=\"middle\" x=\"130\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">) (41)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;16 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>2&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M82.62,-351.96C90.64,-344.8 104.38,-332.51 115.01,-323.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"117.07,-325.87 122.2,-316.6 112.41,-320.65 117.07,-325.87\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-301.71C76,-295.49 76,-285.4 76,-276.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-276.85 76,-266.85 72.5,-276.85 79.5,-276.85\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.99,-251.46C62.86,-244.44 50.75,-232.51 41.19,-223.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"43.72,-220.67 34.14,-216.15 38.81,-225.66 43.72,-220.67\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\"> * </text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>5&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-251.46C76,-245.24 76,-235.15 76,-226.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-226.6 76,-216.6 72.5,-226.6 79.5,-226.6\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>11</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>5&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.64,-251.46C88.26,-244.51 99.47,-232.75 108.4,-223.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.9,-225.84 115.27,-216.19 105.84,-221.01 110.9,-225.84\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-201.21C27,-194.99 27,-184.9 27,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-176.35 27,-166.35 23.5,-176.35 30.5,-176.35\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-150.96C27,-144.74 27,-134.65 27,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-126.1 27,-116.1 23.5,-126.1 30.5,-126.1\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">2 (50)</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-100.71C27,-94.49 27,-84.4 27,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-75.85 27,-65.85 23.5,-75.85 30.5,-75.85\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>12</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>11&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-201.21C122,-194.99 122,-184.9 122,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-176.35 122,-166.35 118.5,-176.35 125.5,-176.35\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>13</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-150.96C122,-144.74 122,-134.65 122,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-126.1 122,-116.1 118.5,-126.1 125.5,-126.1\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>14</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>13&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-100.71C122,-94.49 122,-84.4 122,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-75.85 122,-65.85 118.5,-75.85 125.5,-75.85\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>15</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-0.95\" font-family=\"Times,serif\" font-size=\"14.00\">3 (51)</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;15 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>14&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-50.46C122,-44.24 122,-34.15 122,-25.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-25.6 122,-15.6 118.5,-25.6 125.5,-25.6\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x11c798130>"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_derivation_tree = copy.deepcopy(derivation_tree)\n",
    "# We really should have some query language\n",
    "sub_expr_tree = new_derivation_tree[1][0][1][2]\n",
    "display_tree(sub_expr_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:38.112698Z",
     "iopub.status.busy": "2024-01-18T17:18:38.112526Z",
     "iopub.status.idle": "2024-01-18T17:18:38.491060Z",
     "shell.execute_reply": "2024-01-18T17:18:38.490724Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (20230911.1827)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"157pt\" height=\"525pt\"\n",
       " viewBox=\"0.00 0.00 157.00 524.75\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 520.75)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-520.75 153,-520.75 153,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-503.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;start&gt;</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-502.71C76,-496.49 76,-486.4 76,-477.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-477.85 76,-467.85 72.5,-477.85 79.5,-477.85\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-402.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-452.46C76,-446.24 76,-436.15 76,-427.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-427.6 76,-417.6 72.5,-427.6 79.5,-427.6\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-352.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-402.21C76,-395.99 76,-385.9 76,-377.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-377.35 76,-367.35 72.5,-377.35 79.5,-377.35\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<text text-anchor=\"middle\" x=\"22\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">( (40)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-351.96C61.36,-344.8 47.62,-332.51 36.99,-323.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"39.59,-320.65 29.8,-316.6 34.93,-325.87 39.59,-320.65\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-351.96C76,-345.74 76,-335.65 76,-326.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-327.1 76,-317.1 72.5,-327.1 79.5,-327.1\"/>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>17</title>\n",
       "<text text-anchor=\"middle\" x=\"130\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">) (41)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;17 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>3&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M82.62,-351.96C90.64,-344.8 104.38,-332.51 115.01,-323.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"117.07,-325.87 122.2,-316.6 112.41,-320.65 117.07,-325.87\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-301.71C76,-295.49 76,-285.4 76,-276.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-276.85 76,-266.85 72.5,-276.85 79.5,-276.85\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.99,-251.46C62.86,-244.44 50.75,-232.51 41.19,-223.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"43.72,-220.67 34.14,-216.15 38.81,-225.66 43.72,-220.67\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>11</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\"> * </text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>6&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-251.46C76,-245.24 76,-235.15 76,-226.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-226.6 76,-216.6 72.5,-226.6 79.5,-226.6\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>12</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>6&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.64,-251.46C88.26,-244.51 99.47,-232.75 108.4,-223.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.9,-225.84 115.27,-216.19 105.84,-221.01 110.9,-225.84\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-201.21C27,-194.99 27,-184.9 27,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-176.35 27,-166.35 23.5,-176.35 30.5,-176.35\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-150.96C27,-144.74 27,-134.65 27,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-126.1 27,-116.1 23.5,-126.1 30.5,-126.1\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">2 (50)</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-100.71C27,-94.49 27,-84.4 27,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-75.85 27,-65.85 23.5,-75.85 30.5,-75.85\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>13</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-201.21C122,-194.99 122,-184.9 122,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-176.35 122,-166.35 118.5,-176.35 125.5,-176.35\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>14</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>13&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-150.96C122,-144.74 122,-134.65 122,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-126.1 122,-116.1 118.5,-126.1 125.5,-126.1\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>15</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;15 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>14&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-100.71C122,-94.49 122,-84.4 122,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-75.85 122,-65.85 118.5,-75.85 125.5,-75.85\"/>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>16</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-0.95\" font-family=\"Times,serif\" font-size=\"14.00\">3 (51)</text>\n",
       "</g>\n",
       "<!-- 15&#45;&gt;16 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>15&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-50.46C122,-44.24 122,-34.15 122,-25.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-25.6 122,-15.6 118.5,-25.6 125.5,-25.6\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x11c76b550>"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_derivation_tree[1][0] = sub_expr_tree\n",
    "display_tree(new_derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:38.493295Z",
     "iopub.status.busy": "2024-01-18T17:18:38.493149Z",
     "iopub.status.idle": "2024-01-18T17:18:38.495795Z",
     "shell.execute_reply": "2024-01-18T17:18:38.495479Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(2 * 3)'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_terminals(new_derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Replacing one subtree by another only works as long as individual elements such as `<expr>` occur multiple times in our tree.  In the reduced `new_derivation_tree`, above, we could replace further `<expr>` trees only once more."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Simplifying by Alternative Expansions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A second means to simplify this tree is to apply _alternative expansions_.  That is, for a symbol, we check whether there is an alternative expansion with a smaller number of children.  Then, we replace the symbol with the alternative expansion, filling in needed symbols from the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As an example, consider the `new_derivation_tree` above.  The applied expansion for `<term>` has been\n",
    "\n",
    "    <term> ::= <term> * <factor>\n",
    "    \n",
    "Let us replace this with the alternative expansion:\n",
    "\n",
    "    <term> ::= <factor>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:38.497584Z",
     "iopub.status.busy": "2024-01-18T17:18:38.497456Z",
     "iopub.status.idle": "2024-01-18T17:18:38.877414Z",
     "shell.execute_reply": "2024-01-18T17:18:38.876984Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (20230911.1827)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"157pt\" height=\"274pt\"\n",
       " viewBox=\"0.00 0.00 157.00 273.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 269.5)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-269.5 153,-269.5 153,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.99,-251.46C62.86,-244.44 50.75,-232.51 41.19,-223.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"43.72,-220.67 34.14,-216.15 38.81,-225.66 43.72,-220.67\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<text text-anchor=\"middle\" x=\"76\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\"> * </text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>0&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-251.46C76,-245.24 76,-235.15 76,-226.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"79.5,-226.6 76,-216.6 72.5,-226.6 79.5,-226.6\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>0&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.64,-251.46C88.26,-244.51 99.47,-232.75 108.4,-223.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.9,-225.84 115.27,-216.19 105.84,-221.01 110.9,-225.84\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-201.21C27,-194.99 27,-184.9 27,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-176.35 27,-166.35 23.5,-176.35 30.5,-176.35\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-150.96C27,-144.74 27,-134.65 27,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-126.1 27,-116.1 23.5,-126.1 30.5,-126.1\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">2 (50)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-100.71C27,-94.49 27,-84.4 27,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-75.85 27,-65.85 23.5,-75.85 30.5,-75.85\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-201.21C122,-194.99 122,-184.9 122,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-176.35 122,-166.35 118.5,-176.35 125.5,-176.35\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-150.96C122,-144.74 122,-134.65 122,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-126.1 122,-116.1 118.5,-126.1 125.5,-126.1\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-100.71C122,-94.49 122,-84.4 122,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-75.85 122,-65.85 118.5,-75.85 125.5,-75.85\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<text text-anchor=\"middle\" x=\"122\" y=\"-0.95\" font-family=\"Times,serif\" font-size=\"14.00\">3 (51)</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122,-50.46C122,-44.24 122,-34.15 122,-25.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.5,-25.6 122,-15.6 118.5,-25.6 125.5,-25.6\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x11c798310>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "term_tree = new_derivation_tree[1][0][1][0][1][0][1][1][1][0]\n",
    "display_tree(term_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:38.879445Z",
     "iopub.status.busy": "2024-01-18T17:18:38.879303Z",
     "iopub.status.idle": "2024-01-18T17:18:39.250142Z",
     "shell.execute_reply": "2024-01-18T17:18:39.249780Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (20230911.1827)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"62pt\" height=\"223pt\"\n",
       " viewBox=\"0.00 0.00 62.00 223.25\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 219.25)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-219.25 58,-219.25 58,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-201.21C27,-194.99 27,-184.9 27,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-176.35 27,-166.35 23.5,-176.35 30.5,-176.35\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-150.96C27,-144.74 27,-134.65 27,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-126.1 27,-116.1 23.5,-126.1 30.5,-126.1\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-100.71C27,-94.49 27,-84.4 27,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-75.85 27,-65.85 23.5,-75.85 30.5,-75.85\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-0.95\" font-family=\"Times,serif\" font-size=\"14.00\">3 (51)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-50.46C27,-44.24 27,-34.15 27,-25.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-25.6 27,-15.6 23.5,-25.6 30.5,-25.6\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x11c798af0>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shorter_term_tree = term_tree[1][2]\n",
    "display_tree(shorter_term_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.251747Z",
     "iopub.status.busy": "2024-01-18T17:18:39.251630Z",
     "iopub.status.idle": "2024-01-18T17:18:39.619786Z",
     "shell.execute_reply": "2024-01-18T17:18:39.619300Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (20230911.1827)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"147pt\" height=\"475pt\"\n",
       " viewBox=\"0.00 0.00 146.75 474.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 470.5)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-470.5 142.75,-470.5 142.75,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;start&gt;</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-402.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-452.46C69.38,-446.24 69.38,-436.15 69.38,-427.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-427.6 69.38,-417.6 65.88,-427.6 72.88,-427.6\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-352.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-402.21C69.38,-395.99 69.38,-385.9 69.38,-377.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-377.35 69.38,-367.35 65.88,-377.35 72.88,-377.35\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-351.96C69.38,-345.74 69.38,-335.65 69.38,-326.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-327.1 69.38,-317.1 65.88,-327.1 72.88,-327.1\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<text text-anchor=\"middle\" x=\"15.38\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">( (40)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M62.75,-301.71C54.74,-294.55 40.99,-282.26 30.36,-272.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"32.97,-270.4 23.18,-266.35 28.3,-275.62 32.97,-270.4\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-301.71C69.38,-295.49 69.38,-285.4 69.38,-276.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-276.85 69.38,-266.85 65.88,-276.85 72.88,-276.85\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>11</title>\n",
       "<text text-anchor=\"middle\" x=\"123.38\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">) (41)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>3&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76,-301.71C84.01,-294.55 97.76,-282.26 108.39,-272.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.45,-275.62 115.57,-266.35 105.78,-270.4 110.45,-275.62\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-251.46C69.38,-245.24 69.38,-235.15 69.38,-226.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-226.6 69.38,-216.6 65.88,-226.6 72.88,-226.6\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-201.21C69.38,-194.99 69.38,-184.9 69.38,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-176.35 69.38,-166.35 65.88,-176.35 72.88,-176.35\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-150.96C69.38,-144.74 69.38,-134.65 69.38,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-126.1 69.38,-116.1 65.88,-126.1 72.88,-126.1\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-100.71C69.38,-94.49 69.38,-84.4 69.38,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-75.85 69.38,-65.85 65.88,-75.85 72.88,-75.85\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<text text-anchor=\"middle\" x=\"69.38\" y=\"-0.95\" font-family=\"Times,serif\" font-size=\"14.00\">3 (51)</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.38,-50.46C69.38,-44.24 69.38,-34.15 69.38,-25.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.88,-25.6 69.38,-15.6 65.88,-25.6 72.88,-25.6\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x11c7986d0>"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_derivation_tree[1][0][1][0][1][0][1][1][1][0] = shorter_term_tree\n",
    "display_tree(new_derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.621664Z",
     "iopub.status.busy": "2024-01-18T17:18:39.621534Z",
     "iopub.status.idle": "2024-01-18T17:18:39.624002Z",
     "shell.execute_reply": "2024-01-18T17:18:39.623715Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(3)'"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_terminals(new_derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "If we replace derivation subtrees by (smaller) subtrees, and if we search for alternate expansions that again yield smaller subtrees, we can systematically simplify the input.  This could be much faster than delta debugging, as our inputs would always be syntactically valid.  However, we need a strategy for when to apply which simplification rule. This is what we develop in the remainder of this section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Excursion: A Class for Reducing with Grammars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We introduce the `GrammarReducer` class, which is again a `Reducer`. Note that we derive from `CachingReducer`, as the strategy will produce several duplicates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.625791Z",
     "iopub.status.busy": "2024-01-18T17:18:39.625643Z",
     "iopub.status.idle": "2024-01-18T17:18:39.628332Z",
     "shell.execute_reply": "2024-01-18T17:18:39.628029Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(CachingReducer):\n",
    "    \"\"\"Reduce inputs using grammars\"\"\"\n",
    "\n",
    "    def __init__(self, runner: Runner, parser: Parser, *,\n",
    "                 log_test: bool = False, log_reduce: bool = False):\n",
    "        \"\"\"Constructor.\n",
    "        `runner` is the runner to be used.\n",
    "        `parser` is the parser to be used.\n",
    "        `log_test` - if set, show tests and results.\n",
    "        `log_reduce` - if set, show reduction steps.\n",
    "        \"\"\"\n",
    "\n",
    "        super().__init__(runner, log_test=log_test)\n",
    "        self.parser = parser\n",
    "        self.grammar = parser.grammar()\n",
    "        self.start_symbol = parser.start_symbol()\n",
    "        self.log_reduce = log_reduce\n",
    "        self.try_all_combinations = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### A Few Helpers\n",
    "\n",
    "We define a number of helper functions, which we will need for our strategy.  `tree_list_to_string()` does what the name suggest, creating a string from a list of derivation trees:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.629966Z",
     "iopub.status.busy": "2024-01-18T17:18:39.629728Z",
     "iopub.status.idle": "2024-01-18T17:18:39.631560Z",
     "shell.execute_reply": "2024-01-18T17:18:39.631293Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from GrammarFuzzer import DerivationTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.633005Z",
     "iopub.status.busy": "2024-01-18T17:18:39.632883Z",
     "iopub.status.idle": "2024-01-18T17:18:39.634783Z",
     "shell.execute_reply": "2024-01-18T17:18:39.634522Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def tree_list_to_string(q: List[DerivationTree]) -> str:\n",
    "    return \"[\" + \", \".join([all_terminals(tree) for tree in q]) + \"]\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.636290Z",
     "iopub.status.busy": "2024-01-18T17:18:39.636173Z",
     "iopub.status.idle": "2024-01-18T17:18:39.638486Z",
     "shell.execute_reply": "2024-01-18T17:18:39.638174Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[1 + (2 * 3), 1 + (2 * 3)]'"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree_list_to_string([derivation_tree, derivation_tree])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The function `possible_combinations()` takes a list of lists $[[x_1, x_2], [y_1, y_2], \\dots]$ and creates a list of combinations $[[x_1, y_1], [x_1, y_2], [x_2, y_1], [x_2, y_2], \\dots]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.640100Z",
     "iopub.status.busy": "2024-01-18T17:18:39.639974Z",
     "iopub.status.idle": "2024-01-18T17:18:39.642604Z",
     "shell.execute_reply": "2024-01-18T17:18:39.642296Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def possible_combinations(list_of_lists: List[List[Any]]) -> List[List[Any]]:\n",
    "    if len(list_of_lists) == 0:\n",
    "        return []\n",
    "\n",
    "    ret = []\n",
    "    for e in list_of_lists[0]:\n",
    "        if len(list_of_lists) == 1:\n",
    "            ret.append([e])\n",
    "        else:\n",
    "            for c in possible_combinations(list_of_lists[1:]):\n",
    "                new_combo = [e] + c\n",
    "                ret.append(new_combo)\n",
    "\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.644119Z",
     "iopub.status.busy": "2024-01-18T17:18:39.644010Z",
     "iopub.status.idle": "2024-01-18T17:18:39.646818Z",
     "shell.execute_reply": "2024-01-18T17:18:39.646537Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 'a'], [1, 'b'], [2, 'a'], [2, 'b']]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "possible_combinations([[1, 2], ['a', 'b']])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The functions `number_of_nodes()` and `max_height()` return the number of nodes and the maximum height of the given tree, respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.648412Z",
     "iopub.status.busy": "2024-01-18T17:18:39.648286Z",
     "iopub.status.idle": "2024-01-18T17:18:39.650319Z",
     "shell.execute_reply": "2024-01-18T17:18:39.650038Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def number_of_nodes(tree: DerivationTree) -> int:\n",
    "    (symbol, children) = tree\n",
    "    if children is None:\n",
    "        return 1\n",
    "\n",
    "    return 1 + sum([number_of_nodes(c) for c in children])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.651812Z",
     "iopub.status.busy": "2024-01-18T17:18:39.651686Z",
     "iopub.status.idle": "2024-01-18T17:18:39.653835Z",
     "shell.execute_reply": "2024-01-18T17:18:39.653518Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "number_of_nodes(derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.655241Z",
     "iopub.status.busy": "2024-01-18T17:18:39.655140Z",
     "iopub.status.idle": "2024-01-18T17:18:39.657082Z",
     "shell.execute_reply": "2024-01-18T17:18:39.656841Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def max_height(tree: DerivationTree) -> int:\n",
    "    (symbol, children) = tree\n",
    "    if children is None or len(children) == 0:\n",
    "        return 1\n",
    "\n",
    "    return 1 + max([max_height(c) for c in children])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.658932Z",
     "iopub.status.busy": "2024-01-18T17:18:39.658752Z",
     "iopub.status.idle": "2024-01-18T17:18:39.661129Z",
     "shell.execute_reply": "2024-01-18T17:18:39.660851Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_height(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    },
    "toc-hr-collapsed": false
   },
   "source": [
    "#### Simplification Strategies\n",
    "\n",
    "Let us now implement our two simplification strategies – replacing subtrees and alternate expansions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### Finding Subtrees\n",
    "\n",
    "The method `subtrees_with_symbol()` returns all subtrees in the given tree which's root is equal to the given symbol.  If `ignore_root` is set (default), then the root node of `tree` is not compared against.  (The `depth` parameter will be discussed below.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.662682Z",
     "iopub.status.busy": "2024-01-18T17:18:39.662581Z",
     "iopub.status.idle": "2024-01-18T17:18:39.665386Z",
     "shell.execute_reply": "2024-01-18T17:18:39.665030Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def subtrees_with_symbol(self, tree: DerivationTree,\n",
    "                             symbol: str, depth: int = -1,\n",
    "                             ignore_root: bool = True) -> List[DerivationTree]:\n",
    "        \"\"\"Find all subtrees in `tree` whose root is `symbol`.\n",
    "        If `ignore_root` is true, ignore the root note of `tree`.\"\"\"\n",
    "\n",
    "        ret = []\n",
    "        (child_symbol, children) = tree\n",
    "        if depth <= 0 and not ignore_root and child_symbol == symbol:\n",
    "            ret.append(tree)\n",
    "\n",
    "        # Search across all children\n",
    "        if depth != 0 and children is not None:\n",
    "            for c in children:\n",
    "                ret += self.subtrees_with_symbol(c,\n",
    "                                                 symbol,\n",
    "                                                 depth=depth - 1,\n",
    "                                                 ignore_root=False)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Here's an example: These are all subtrees with `<term>` in our derivation tree `derivation_tree`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.666964Z",
     "iopub.status.busy": "2024-01-18T17:18:39.666856Z",
     "iopub.status.idle": "2024-01-18T17:18:39.668664Z",
     "shell.execute_reply": "2024-01-18T17:18:39.668377Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_reduce=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.670157Z",
     "iopub.status.busy": "2024-01-18T17:18:39.670057Z",
     "iopub.status.idle": "2024-01-18T17:18:39.672109Z",
     "shell.execute_reply": "2024-01-18T17:18:39.671823Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 + (2 * 3)'"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_terminals(derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.673512Z",
     "iopub.status.busy": "2024-01-18T17:18:39.673401Z",
     "iopub.status.idle": "2024-01-18T17:18:39.675693Z",
     "shell.execute_reply": "2024-01-18T17:18:39.675372Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '(2 * 3)', '2 * 3', '3']"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[all_terminals(t) for t in grammar_reducer.subtrees_with_symbol(\n",
    "    derivation_tree, \"<term>\")]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "If we want to replace `<term>` subtrees to simplify the tree, these are the subtrees we could replace them with."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### Alternate Expansions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Our second strategy, simplifying by alternate expansions, is a bit more complex.  We first fetch the possible expansions for the given symbol (starting with the ones with the fewest children).  For each expansion, we fill in values for the symbols from the subtree (using `subtrees_with_symbols()`, above).  We then pick the first possible combination (or _all_ combinations, if the attribute `try_all_combinations` is set)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.677770Z",
     "iopub.status.busy": "2024-01-18T17:18:39.677586Z",
     "iopub.status.idle": "2024-01-18T17:18:39.681209Z",
     "shell.execute_reply": "2024-01-18T17:18:39.680940Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def alternate_reductions(self, tree: DerivationTree, symbol: str, \n",
    "                             depth: int = -1):\n",
    "        reductions = []\n",
    "\n",
    "        expansions = self.grammar.get(symbol, [])\n",
    "        expansions.sort(\n",
    "            key=lambda expansion: len(\n",
    "                expansion_to_children(expansion)))\n",
    "\n",
    "        for expansion in expansions:\n",
    "            expansion_children = expansion_to_children(expansion)\n",
    "\n",
    "            match = True\n",
    "            new_children_reductions = []\n",
    "            for (alt_symbol, _) in expansion_children:\n",
    "                child_reductions = self.subtrees_with_symbol(\n",
    "                    tree, alt_symbol, depth=depth)\n",
    "                if len(child_reductions) == 0:\n",
    "                    match = False   # Child not found; cannot apply rule\n",
    "                    break\n",
    "\n",
    "                new_children_reductions.append(child_reductions)\n",
    "\n",
    "            if not match:\n",
    "                continue  # Try next alternative\n",
    "\n",
    "            # Use the first suitable combination\n",
    "            for new_children in possible_combinations(new_children_reductions):\n",
    "                new_tree = (symbol, new_children)\n",
    "                if number_of_nodes(new_tree) < number_of_nodes(tree):\n",
    "                    reductions.append(new_tree)\n",
    "                    if not self.try_all_combinations:\n",
    "                        break\n",
    "\n",
    "        # Sort by number of nodes\n",
    "        reductions.sort(key=number_of_nodes)\n",
    "\n",
    "        return reductions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.682759Z",
     "iopub.status.busy": "2024-01-18T17:18:39.682665Z",
     "iopub.status.idle": "2024-01-18T17:18:39.684567Z",
     "shell.execute_reply": "2024-01-18T17:18:39.684306Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_reduce=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.685887Z",
     "iopub.status.busy": "2024-01-18T17:18:39.685803Z",
     "iopub.status.idle": "2024-01-18T17:18:39.687930Z",
     "shell.execute_reply": "2024-01-18T17:18:39.687678Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 + (2 * 3)'"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_terminals(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Here are _all_ combinations for `<term>`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.689361Z",
     "iopub.status.busy": "2024-01-18T17:18:39.689274Z",
     "iopub.status.idle": "2024-01-18T17:18:39.691524Z",
     "shell.execute_reply": "2024-01-18T17:18:39.691253Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['1', '2', '3', '1 * 1', '1 * 3', '2 * 1', '2 * 3', '3 * 1', '3 * 3', '(2 * 3)', '1 * 2 * 3', '2 * 2 * 3', '3 * 2 * 3', '1 * (2 * 3)', '(2 * 3) * 1', '(2 * 3) * 3', '2 * (2 * 3)', '3 * (2 * 3)']\n"
     ]
    }
   ],
   "source": [
    "grammar_reducer.try_all_combinations = True\n",
    "print([all_terminals(t)\n",
    "       for t in grammar_reducer.alternate_reductions(derivation_tree, \"<term>\")])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The default, though, is simply to return the first of these:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.692875Z",
     "iopub.status.busy": "2024-01-18T17:18:39.692794Z",
     "iopub.status.idle": "2024-01-18T17:18:39.695090Z",
     "shell.execute_reply": "2024-01-18T17:18:39.694818Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '1 * 1']"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar_reducer.try_all_combinations = False\n",
    "[all_terminals(t) for t in grammar_reducer.alternate_reductions(\n",
    "    derivation_tree, \"<term>\")]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### Both Strategies Together"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let us now merge both strategies.  To replace a subtree with a given symbol, we first search for already existing subtrees (using `subtrees_with_symbol()`); then we go for alternate expansions (using `alternate_expansions()`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.696548Z",
     "iopub.status.busy": "2024-01-18T17:18:39.696465Z",
     "iopub.status.idle": "2024-01-18T17:18:39.698789Z",
     "shell.execute_reply": "2024-01-18T17:18:39.698522Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def symbol_reductions(self, tree: DerivationTree, symbol: str, \n",
    "                          depth: int = -1):\n",
    "        \"\"\"Find all expansion alternatives for the given symbol\"\"\"\n",
    "        reductions = (self.subtrees_with_symbol(tree, symbol, depth=depth)\n",
    "                      + self.alternate_reductions(tree, symbol, depth=depth))\n",
    "\n",
    "        # Filter duplicates\n",
    "        unique_reductions = []\n",
    "        for r in reductions:\n",
    "            if r not in unique_reductions:\n",
    "                unique_reductions.append(r)\n",
    "\n",
    "        return unique_reductions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.700243Z",
     "iopub.status.busy": "2024-01-18T17:18:39.700158Z",
     "iopub.status.idle": "2024-01-18T17:18:39.701966Z",
     "shell.execute_reply": "2024-01-18T17:18:39.701688Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_reduce=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.703547Z",
     "iopub.status.busy": "2024-01-18T17:18:39.703453Z",
     "iopub.status.idle": "2024-01-18T17:18:39.705520Z",
     "shell.execute_reply": "2024-01-18T17:18:39.705264Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 + (2 * 3)'"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_terminals(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "These are the possible reductions for `<expr>` nodes.  Note how we first return subtrees (`1 + (2 * 3)`, `(2 * 3)`, `2 * 3`) before going for alternate expansions of `<expr>` (`1`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.707111Z",
     "iopub.status.busy": "2024-01-18T17:18:39.707027Z",
     "iopub.status.idle": "2024-01-18T17:18:39.709514Z",
     "shell.execute_reply": "2024-01-18T17:18:39.709251Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[1 + (2 * 3), (2 * 3), 2 * 3, 1]'"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reductions = grammar_reducer.symbol_reductions(derivation_tree, \"<expr>\")\n",
    "tree_list_to_string([r for r in reductions])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "These are the possible reductions for `<term>` nodes.  Again, we first have subtrees of the derivation tree, followed by the alternate expansion `1 * 1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.711089Z",
     "iopub.status.busy": "2024-01-18T17:18:39.710968Z",
     "iopub.status.idle": "2024-01-18T17:18:39.713514Z",
     "shell.execute_reply": "2024-01-18T17:18:39.713256Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[1, (2 * 3), 2 * 3, 3, 1 * 1]'"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reductions = grammar_reducer.symbol_reductions(derivation_tree, \"<term>\")\n",
    "tree_list_to_string([r for r in reductions])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### The Reduction Strategy\n",
    "\n",
    "We are now able to return a number of alternatives for each symbol in the tree.  This is what we apply in the core function of our reduction strategy, `reduce_subtree()`.  Starting with `subtree`, for every child, we find possible reductions.  For every reduction, we replace the child with the reduction and test the resulting (full) tree.  If it fails, our reduction was successful; otherwise, we put the child back into place and try out the next reduction.  Eventually, we apply `reduce_subtree()` on all children, reducing these as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.715101Z",
     "iopub.status.busy": "2024-01-18T17:18:39.714987Z",
     "iopub.status.idle": "2024-01-18T17:18:39.719845Z",
     "shell.execute_reply": "2024-01-18T17:18:39.719541Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def reduce_subtree(self, tree: DerivationTree,\n",
    "                       subtree: DerivationTree, depth: int = -1):\n",
    "        symbol, children = subtree\n",
    "        if children is None or len(children) == 0:\n",
    "            return False\n",
    "\n",
    "        if self.log_reduce:\n",
    "            print(\"Reducing\", all_terminals(subtree), \"with depth\", depth)\n",
    "\n",
    "        reduced = False\n",
    "        while True:\n",
    "            reduced_child = False\n",
    "            for i, child in enumerate(children):\n",
    "                if child is None:\n",
    "                    continue\n",
    "\n",
    "                (child_symbol, _) = child\n",
    "                for reduction in self.symbol_reductions(\n",
    "                        child, child_symbol, depth):\n",
    "                    if number_of_nodes(reduction) >= number_of_nodes(child):\n",
    "                        continue\n",
    "\n",
    "                    # Try this reduction\n",
    "                    if self.log_reduce:\n",
    "                        print(\n",
    "                            \"Replacing\",\n",
    "                            all_terminals(\n",
    "                                children[i]),\n",
    "                            \"by\",\n",
    "                            all_terminals(reduction))\n",
    "                    children[i] = reduction\n",
    "                    if self.test(all_terminals(tree)) == Runner.FAIL:\n",
    "                        # Success\n",
    "                        if self.log_reduce:\n",
    "                            print(\"New tree:\", all_terminals(tree))\n",
    "                        reduced = reduced_child = True\n",
    "                        break\n",
    "                    else:\n",
    "                        # Didn't work out - restore\n",
    "                        children[i] = child\n",
    "\n",
    "            if not reduced_child:\n",
    "                if self.log_reduce:\n",
    "                    print(\"Tried all alternatives for\", all_terminals(subtree))\n",
    "                break\n",
    "\n",
    "        # Run recursively\n",
    "        for c in children:\n",
    "            if self.reduce_subtree(tree, c, depth):\n",
    "                reduced = True\n",
    "\n",
    "        return reduced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "All we now need is a few drivers.  The method `reduce_tree()` is the main entry point into `reduce_subtree()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.721372Z",
     "iopub.status.busy": "2024-01-18T17:18:39.721254Z",
     "iopub.status.idle": "2024-01-18T17:18:39.723234Z",
     "shell.execute_reply": "2024-01-18T17:18:39.722964Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def reduce_tree(self, tree):\n",
    "        return self.reduce_subtree(tree, tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The custom method `parse()` turns a given input into a derivation tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.724612Z",
     "iopub.status.busy": "2024-01-18T17:18:39.724528Z",
     "iopub.status.idle": "2024-01-18T17:18:39.726562Z",
     "shell.execute_reply": "2024-01-18T17:18:39.726331Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def parse(self, inp):\n",
    "        tree, *_ = self.parser.parse(inp)\n",
    "        if self.log_reduce:\n",
    "            print(all_terminals(tree))\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The method `reduce()` is the one single entry point, parsing the input and then reducing it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.728162Z",
     "iopub.status.busy": "2024-01-18T17:18:39.728078Z",
     "iopub.status.idle": "2024-01-18T17:18:39.730027Z",
     "shell.execute_reply": "2024-01-18T17:18:39.729781Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def reduce(self, inp):\n",
    "        tree = self.parse(inp)\n",
    "        self.reduce_tree(tree)\n",
    "        return all_terminals(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### End of Excursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let us try out our `GrammarReducer` class in practice on our input `expr_input` and the `mystery()` function.  How quickly can we reduce it?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.731597Z",
     "iopub.status.busy": "2024-01-18T17:18:39.731507Z",
     "iopub.status.idle": "2024-01-18T17:18:39.733658Z",
     "shell.execute_reply": "2024-01-18T17:18:39.733422Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 + (2 * 3)'"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expr_input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.735082Z",
     "iopub.status.busy": "2024-01-18T17:18:39.734997Z",
     "iopub.status.idle": "2024-01-18T17:18:39.740726Z",
     "shell.execute_reply": "2024-01-18T17:18:39.740477Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1 '(2 * 3)' 7 FAIL\n",
      "Test #2 '2 * 3' 5 PASS\n",
      "Test #3 '3' 1 PASS\n",
      "Test #4 '2' 1 PASS\n",
      "Test #5 '(3)' 3 FAIL\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'(3)'"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    eval_mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_test=True)\n",
    "grammar_reducer.reduce(expr_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Success!  In only five steps, our `GrammarReducer` reduces the input to the minimum that causes the failure.  Note how all tests are syntactically valid by construction, avoiding the `UNRESOLVED` outcomes that cause delta debugging to stall."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### A Depth-Oriented Strategy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Even if five steps are already good, we can still do better.  If we look at the log above, we see that after test `#2`, where the input (tree) is reduced to `2 * 3`, our `GrammarReducer` first tries to replace the tree with `2` and `3`, which are the alternate `<term>` subtrees.  This may work, of course; but if there are many possible subtrees, our strategy will spend quite some time trying one after the other."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Delta debugging, as introduced above, follows the idea of trying to cut inputs approximately in half, and thus quickly proceeds towards a minimal input.  By replacing a tree with much smaller subtrees, we _could_ possibly reduce a tree significantly, but may need several attempts to do so.  A better strategy is to only consider _large_ subtrees first – both for the subtree replacement and for alternate expansions.  To find such _large_ subtrees, we limit the _depth_ by which we search for possible replacements in the subtree – first, by looking at the direct descendants, later at lower descendants."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This is the role of the `depth` parameter used in `subtrees_with_symbol()` and passed through the invoking functions.  If set, _only_ symbols at the given depth are returned.  Here's an example, starting again with our derivation tree `derivation_tree`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.742401Z",
     "iopub.status.busy": "2024-01-18T17:18:39.742259Z",
     "iopub.status.idle": "2024-01-18T17:18:39.743994Z",
     "shell.execute_reply": "2024-01-18T17:18:39.743784Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_reduce=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.745678Z",
     "iopub.status.busy": "2024-01-18T17:18:39.745538Z",
     "iopub.status.idle": "2024-01-18T17:18:39.747689Z",
     "shell.execute_reply": "2024-01-18T17:18:39.747434Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 + (2 * 3)'"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_terminals(derivation_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:39.749183Z",
     "iopub.status.busy": "2024-01-18T17:18:39.749072Z",
     "iopub.status.idle": "2024-01-18T17:18:40.130151Z",
     "shell.execute_reply": "2024-01-18T17:18:40.129812Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (20230911.1827)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"210pt\" height=\"575pt\"\n",
       " viewBox=\"0.00 0.00 209.62 575.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 571)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-571 205.62,-571 205.62,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<text text-anchor=\"middle\" x=\"81.62\" y=\"-553.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;start&gt;</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<text text-anchor=\"middle\" x=\"81.62\" y=\"-503.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.62,-552.96C81.62,-546.74 81.62,-536.65 81.62,-527.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"85.13,-528.1 81.63,-518.1 78.13,-528.1 85.13,-528.1\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<text text-anchor=\"middle\" x=\"33.62\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M75.74,-502.71C68.76,-495.69 56.89,-483.76 47.53,-474.35\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"50.16,-472.03 40.63,-467.41 45.2,-476.97 50.16,-472.03\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<text text-anchor=\"middle\" x=\"81.62\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\"> + </text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>1&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.62,-502.71C81.62,-496.49 81.62,-486.4 81.62,-477.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"85.13,-477.85 81.63,-467.85 78.13,-477.85 85.13,-477.85\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<text text-anchor=\"middle\" x=\"127.62\" y=\"-453.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>1&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M87.27,-502.71C93.89,-495.76 105.1,-484 114.03,-474.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"116.53,-477.09 120.89,-467.44 111.46,-472.26 116.53,-477.09\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<text text-anchor=\"middle\" x=\"31.62\" y=\"-402.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.38,-452.46C33.12,-446.24 32.7,-436.15 32.34,-427.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"35.85,-427.45 31.93,-417.6 28.85,-427.74 35.85,-427.45\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<text text-anchor=\"middle\" x=\"27.62\" y=\"-352.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M31.13,-402.21C30.62,-395.99 29.78,-385.9 29.06,-377.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"32.56,-377.02 28.24,-367.35 25.58,-377.6 32.56,-377.02\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<text text-anchor=\"middle\" x=\"20.62\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M26.77,-351.96C25.86,-345.74 24.4,-335.65 23.13,-326.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"26.61,-326.48 21.71,-317.09 19.68,-327.49 26.61,-326.48\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<text text-anchor=\"middle\" x=\"20.62\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">1 (49)</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M20.62,-301.71C20.62,-295.49 20.62,-285.4 20.62,-276.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"24.13,-276.85 20.63,-266.85 17.13,-276.85 24.13,-276.85\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<text text-anchor=\"middle\" x=\"127.62\" y=\"-402.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.62,-452.46C127.62,-446.24 127.62,-436.15 127.62,-427.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"131.13,-427.6 127.63,-417.6 124.13,-427.6 131.13,-427.6\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<text text-anchor=\"middle\" x=\"127.62\" y=\"-352.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.62,-402.21C127.62,-395.99 127.62,-385.9 127.62,-377.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"131.13,-377.35 127.63,-367.35 124.13,-377.35 131.13,-377.35\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>11</title>\n",
       "<text text-anchor=\"middle\" x=\"74.62\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">( (40)</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M121.13,-351.96C113.34,-344.87 100.04,-332.76 89.65,-323.31\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"92.05,-320.75 82.3,-316.61 87.33,-325.93 92.05,-320.75\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>12</title>\n",
       "<text text-anchor=\"middle\" x=\"128.62\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;expr&gt;</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>10&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.75,-351.96C127.88,-345.74 128.09,-335.65 128.27,-326.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"131.76,-327.17 128.47,-317.1 124.76,-327.03 131.76,-327.17\"/>\n",
       "</g>\n",
       "<!-- 24 -->\n",
       "<g id=\"node25\" class=\"node\">\n",
       "<title>24</title>\n",
       "<text text-anchor=\"middle\" x=\"182.62\" y=\"-302.45\" font-family=\"Times,serif\" font-size=\"14.00\">) (41)</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;24 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>10&#45;&gt;24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M134.37,-351.96C142.53,-344.8 156.53,-332.51 167.36,-323.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"169.48,-325.81 174.69,-316.59 164.86,-320.55 169.48,-325.81\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>13</title>\n",
       "<text text-anchor=\"middle\" x=\"128.62\" y=\"-252.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M128.62,-301.71C128.62,-295.49 128.62,-285.4 128.62,-276.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.13,-276.85 128.63,-266.85 125.13,-276.85 132.13,-276.85\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>14</title>\n",
       "<text text-anchor=\"middle\" x=\"79.62\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>13&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M122.62,-251.46C115.49,-244.44 103.37,-232.51 93.81,-223.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"96.34,-220.67 86.76,-216.15 91.43,-225.66 96.34,-220.67\"/>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>18</title>\n",
       "<text text-anchor=\"middle\" x=\"128.62\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\"> * </text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;18 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>13&#45;&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M128.62,-251.46C128.62,-245.24 128.62,-235.15 128.62,-226.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.13,-226.6 128.63,-216.6 125.13,-226.6 132.13,-226.6\"/>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node20\" class=\"node\">\n",
       "<title>19</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-201.95\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;term&gt;</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;19 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>13&#45;&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M134.27,-251.46C140.89,-244.51 152.1,-232.75 161.03,-223.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"163.53,-225.84 167.89,-216.19 158.46,-221.01 163.53,-225.84\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>15</title>\n",
       "<text text-anchor=\"middle\" x=\"79.62\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;15 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>14&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.62,-201.21C79.62,-194.99 79.62,-184.9 79.62,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"83.13,-176.35 79.63,-166.35 76.13,-176.35 83.13,-176.35\"/>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>16</title>\n",
       "<text text-anchor=\"middle\" x=\"79.62\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 15&#45;&gt;16 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>15&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.62,-150.96C79.62,-144.74 79.62,-134.65 79.62,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"83.13,-126.1 79.63,-116.1 76.13,-126.1 83.13,-126.1\"/>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>17</title>\n",
       "<text text-anchor=\"middle\" x=\"79.62\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">2 (50)</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;17 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>16&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.62,-100.71C79.62,-94.49 79.62,-84.4 79.62,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"83.13,-75.85 79.63,-65.85 76.13,-75.85 83.13,-75.85\"/>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node21\" class=\"node\">\n",
       "<title>20</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-151.7\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;factor&gt;</text>\n",
       "</g>\n",
       "<!-- 19&#45;&gt;20 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>19&#45;&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.62,-201.21C174.62,-194.99 174.62,-184.9 174.62,-176.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"178.13,-176.35 174.63,-166.35 171.13,-176.35 178.13,-176.35\"/>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node22\" class=\"node\">\n",
       "<title>21</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;integer&gt;</text>\n",
       "</g>\n",
       "<!-- 20&#45;&gt;21 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>20&#45;&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.62,-150.96C174.62,-144.74 174.62,-134.65 174.62,-125.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"178.13,-126.1 174.63,-116.1 171.13,-126.1 178.13,-126.1\"/>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node23\" class=\"node\">\n",
       "<title>22</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-51.2\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;digit&gt;</text>\n",
       "</g>\n",
       "<!-- 21&#45;&gt;22 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>21&#45;&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.62,-100.71C174.62,-94.49 174.62,-84.4 174.62,-75.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"178.13,-75.85 174.63,-65.85 171.13,-75.85 178.13,-75.85\"/>\n",
       "</g>\n",
       "<!-- 23 -->\n",
       "<g id=\"node24\" class=\"node\">\n",
       "<title>23</title>\n",
       "<text text-anchor=\"middle\" x=\"174.62\" y=\"-0.95\" font-family=\"Times,serif\" font-size=\"14.00\">3 (51)</text>\n",
       "</g>\n",
       "<!-- 22&#45;&gt;23 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>22&#45;&gt;23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.62,-50.46C174.62,-44.24 174.62,-34.15 174.62,-25.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"178.13,-25.6 174.63,-15.6 171.13,-25.6 178.13,-25.6\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x11c77cf70>"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "display_tree(derivation_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "At a depth of 1, there is no `<term>` symbol:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.131912Z",
     "iopub.status.busy": "2024-01-18T17:18:40.131789Z",
     "iopub.status.idle": "2024-01-18T17:18:40.134220Z",
     "shell.execute_reply": "2024-01-18T17:18:40.133943Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[all_terminals(t) for t in grammar_reducer.subtrees_with_symbol(\n",
    "    derivation_tree, \"<term>\", depth=1)]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "At a depth of 2, we have the `<term>` subtree on the left-hand side:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.135732Z",
     "iopub.status.busy": "2024-01-18T17:18:40.135627Z",
     "iopub.status.idle": "2024-01-18T17:18:40.137926Z",
     "shell.execute_reply": "2024-01-18T17:18:40.137673Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1']"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[all_terminals(t) for t in grammar_reducer.subtrees_with_symbol(\n",
    "    derivation_tree, \"<term>\", depth=2)]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "At a depth of 3, we have the `<term>` subtree on the right-hand side:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.139421Z",
     "iopub.status.busy": "2024-01-18T17:18:40.139313Z",
     "iopub.status.idle": "2024-01-18T17:18:40.141609Z",
     "shell.execute_reply": "2024-01-18T17:18:40.141321Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['(2 * 3)']"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[all_terminals(t) for t in grammar_reducer.subtrees_with_symbol(\n",
    "    derivation_tree, \"<term>\", depth=3)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The idea is now to start with a depth of 0, subsequently increasing it as we proceed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.143056Z",
     "iopub.status.busy": "2024-01-18T17:18:40.142936Z",
     "iopub.status.idle": "2024-01-18T17:18:40.145050Z",
     "shell.execute_reply": "2024-01-18T17:18:40.144770Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class GrammarReducer(GrammarReducer):\n",
    "    def reduce_tree(self, tree):\n",
    "        depth = 0\n",
    "        while depth < max_height(tree):\n",
    "            reduced = self.reduce_subtree(tree, tree, depth)\n",
    "            if reduced:\n",
    "                depth = 0    # Start with new tree\n",
    "            else:\n",
    "                depth += 1   # Extend search for subtrees\n",
    "        return tree        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.146455Z",
     "iopub.status.busy": "2024-01-18T17:18:40.146355Z",
     "iopub.status.idle": "2024-01-18T17:18:40.152008Z",
     "shell.execute_reply": "2024-01-18T17:18:40.151762Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1 '(2 * 3)' 7 FAIL\n",
      "Test #2 '(3)' 3 FAIL\n",
      "Test #3 '3' 1 PASS\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'(3)'"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar_reducer = GrammarReducer(\n",
    "    mystery,\n",
    "    EarleyParser(EXPR_GRAMMAR),\n",
    "    log_test=True)\n",
    "grammar_reducer.reduce(expr_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We see that a depth-oriented strategy needs even fewer steps in our setting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Comparing Strategies\n",
    "\n",
    "We close by demonstrating the difference between text-based delta debugging and our grammar-based reduction.  We build a very long expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.153722Z",
     "iopub.status.busy": "2024-01-18T17:18:40.153600Z",
     "iopub.status.idle": "2024-01-18T17:18:40.155180Z",
     "shell.execute_reply": "2024-01-18T17:18:40.154948Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from GrammarFuzzer import GrammarFuzzer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.156469Z",
     "iopub.status.busy": "2024-01-18T17:18:40.156391Z",
     "iopub.status.idle": "2024-01-18T17:18:40.274405Z",
     "shell.execute_reply": "2024-01-18T17:18:40.274137Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'++---((-2 / 3 / 3 - -+1 / 5 - 2) * ++6 / +8 * 4 / 9 / 2 * 8 + ++(5) * 3 / 8 * 0 + 3 * 3 + 4 / 0 / 6 + 9) * ++++(+--9 * -3 * 7 / 4 + --(4) / 3 - 0 / 3 + 5 + 0) * (1 * 6 - 1 / 9 * 5 - 9 / 0 + 7) * ++(8 - 1) * +1 * 7 * 0 + ((1 + 4) / 4 * 8 * 9 * 4 + 4 / (4) * 1 - (4) * 8 * 5 + 1 + 4) / (+(2 - 1 - 9) * 5 + 3 + 6 - 2) * +3 * (3 - 7 + 8) / 4 - -(9 * 4 - 1 * 0 + 5) / (5 / 9 * 5 + 2) * 7 + ((7 - 5 + 3) / 1 * 8 - 8 - 9) * --+1 * 4 / 4 - 4 / 7 * 4 - 3 / 6 * 1 - 2 - 7 - 8'"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "long_expr_input = GrammarFuzzer(EXPR_GRAMMAR, min_nonterminals=100).fuzz()\n",
    "long_expr_input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "With grammars, we need only a handful of tests to find the failure-inducing input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.276036Z",
     "iopub.status.busy": "2024-01-18T17:18:40.275929Z",
     "iopub.status.idle": "2024-01-18T17:18:40.277555Z",
     "shell.execute_reply": "2024-01-18T17:18:40.277291Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Timer import Timer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.279126Z",
     "iopub.status.busy": "2024-01-18T17:18:40.279010Z",
     "iopub.status.idle": "2024-01-18T17:18:40.355275Z",
     "shell.execute_reply": "2024-01-18T17:18:40.354970Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(9)\n"
     ]
    }
   ],
   "source": [
    "grammar_reducer = GrammarReducer(eval_mystery, EarleyParser(EXPR_GRAMMAR))\n",
    "with Timer() as grammar_time:\n",
    "    print(grammar_reducer.reduce(long_expr_input))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.356864Z",
     "iopub.status.busy": "2024-01-18T17:18:40.356741Z",
     "iopub.status.idle": "2024-01-18T17:18:40.358925Z",
     "shell.execute_reply": "2024-01-18T17:18:40.358679Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar_reducer.tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.360320Z",
     "iopub.status.busy": "2024-01-18T17:18:40.360222Z",
     "iopub.status.idle": "2024-01-18T17:18:40.362158Z",
     "shell.execute_reply": "2024-01-18T17:18:40.361842Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0741315829945961"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar_time.elapsed_time()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Delta debugging, in contrast, requires orders of magnitude more tests (and consequently, time).  Again, the reduction is not closely as perfect as it is with the grammar-based reducer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:40.363829Z",
     "iopub.status.busy": "2024-01-18T17:18:40.363708Z",
     "iopub.status.idle": "2024-01-18T17:18:42.930786Z",
     "shell.execute_reply": "2024-01-18T17:18:42.930460Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((2 - 1 - 2) * 8 + (5) - (4)) / ((2) * 3) * (9) / 3 / 1 - 8\n"
     ]
    }
   ],
   "source": [
    "dd_reducer = DeltaDebuggingReducer(eval_mystery)\n",
    "with Timer() as dd_time:\n",
    "    print(dd_reducer.reduce(long_expr_input))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:42.932443Z",
     "iopub.status.busy": "2024-01-18T17:18:42.932314Z",
     "iopub.status.idle": "2024-01-18T17:18:42.934720Z",
     "shell.execute_reply": "2024-01-18T17:18:42.934464Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "900"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dd_reducer.tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:42.936385Z",
     "iopub.status.busy": "2024-01-18T17:18:42.936239Z",
     "iopub.status.idle": "2024-01-18T17:18:42.938389Z",
     "shell.execute_reply": "2024-01-18T17:18:42.938130Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.5649758750078036"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dd_time.elapsed_time()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We see that if an input is syntactically complex, using a grammar to reduce inputs is the best way to go."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Synopsis\n",
    "\n",
    "A _reducer_ takes a failure-inducing input and reduces it to the minimum that still reproduces the failure.  This chapter provides `Reducer` classes that implement such reducers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Here is a simple example: An arithmetic expression causes an error in the Python interpreter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:42.940041Z",
     "iopub.status.busy": "2024-01-18T17:18:42.939928Z",
     "iopub.status.idle": "2024-01-18T17:18:43.074239Z",
     "shell.execute_reply": "2024-01-18T17:18:43.073860Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traceback (most recent call last):\r\n",
      "  File \"<string>\", line 1, in <module>\r\n",
      "ZeroDivisionError: division by zero\r\n"
     ]
    }
   ],
   "source": [
    "!python -c 'x = 1 + 2 * 3 / 0'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Can we reduce this input to a minimum?  To use a `Reducer`, one first has to build a `Runner` whose outcome is `FAIL` if the precise error occurs.  We therefore build a `ZeroDivisionRunner` whose `run()` method will specifically return a `FAIL` outcome if a `ZeroDivisionError` occurs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:43.076268Z",
     "iopub.status.busy": "2024-01-18T17:18:43.076141Z",
     "iopub.status.idle": "2024-01-18T17:18:43.078124Z",
     "shell.execute_reply": "2024-01-18T17:18:43.077808Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Fuzzer import ProgramRunner\n",
    "import subprocess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:43.079686Z",
     "iopub.status.busy": "2024-01-18T17:18:43.079578Z",
     "iopub.status.idle": "2024-01-18T17:18:43.081791Z",
     "shell.execute_reply": "2024-01-18T17:18:43.081539Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class ZeroDivisionRunner(ProgramRunner):\n",
    "    \"\"\"Make outcome 'FAIL' if ZeroDivisionError occurs\"\"\"\n",
    "\n",
    "    def run(self, inp: str = \"\") -> Tuple[subprocess.CompletedProcess, Outcome]:\n",
    "        process, outcome = super().run(inp)\n",
    "        if process.stderr.find('ZeroDivisionError') >= 0:\n",
    "            outcome = 'FAIL'\n",
    "        return process, outcome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "If we feed this expression into a `ZeroDivisionRunner`, it will produce an outcome of `FAIL` as designed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:43.083287Z",
     "iopub.status.busy": "2024-01-18T17:18:43.083192Z",
     "iopub.status.idle": "2024-01-18T17:18:43.103567Z",
     "shell.execute_reply": "2024-01-18T17:18:43.103219Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'FAIL'"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_input = \"x = 1 + 2 * 3 / 0\"\n",
    "python_runner = ZeroDivisionRunner(\"python\")\n",
    "process, outcome = python_runner.run(python_input)\n",
    "outcome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Delta Debugging is a simple and robust reduction algorithm.  We can tie a `DeltaDebuggingReducer` to this runner, and have it determine the substring that causes the `python` program to fail:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:43.105395Z",
     "iopub.status.busy": "2024-01-18T17:18:43.105273Z",
     "iopub.status.idle": "2024-01-18T17:18:43.316993Z",
     "shell.execute_reply": "2024-01-18T17:18:43.316641Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'3/0'"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dd = DeltaDebuggingReducer(python_runner)\n",
    "dd.reduce(python_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The input is reduced to the minimum: We get the essence of the division by zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:43.318710Z",
     "iopub.status.busy": "2024-01-18T17:18:43.318588Z",
     "iopub.status.idle": "2024-01-18T17:18:43.320265Z",
     "shell.execute_reply": "2024-01-18T17:18:43.320007Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# ignore\n",
    "from ClassDiagram import display_class_hierarchy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-18T17:18:43.321719Z",
     "iopub.status.busy": "2024-01-18T17:18:43.321616Z",
     "iopub.status.idle": "2024-01-18T17:18:43.725145Z",
     "shell.execute_reply": "2024-01-18T17:18:43.724753Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (20230911.1827)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"476pt\" height=\"343pt\"\n",
       " viewBox=\"0.00 0.00 475.50 342.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 338.5)\">\n",
       "<g id=\"a_graph0\"><a xlink:title=\"DeltaDebuggingReducer class hierarchy\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-338.5 471.5,-338.5 471.5,4 -4,4\"/>\n",
       "</a>\n",
       "</g>\n",
       "<!-- DeltaDebuggingReducer -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>DeltaDebuggingReducer</title>\n",
       "<g id=\"a_node1\"><a xlink:href=\"#\" xlink:title=\"class DeltaDebuggingReducer:&#10;Reduce inputs using delta debugging.\">\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-39.88 0,-85.12 163.75,-85.12 163.75,-39.88 0,-39.88\"/>\n",
       "<text text-anchor=\"start\" x=\"8\" y=\"-68.83\" font-family=\"Patua One, Helvetica, sans-serif\" font-weight=\"bold\" font-size=\"14.00\" fill=\"#b03a2e\">DeltaDebuggingReducer</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"0,-59.12 163.75,-59.12\"/>\n",
       "<g id=\"a_node1_0\"><a xlink:href=\"#\" xlink:title=\"DeltaDebuggingReducer\">\n",
       "<g id=\"a_node1_1\"><a xlink:href=\"#\" xlink:title=\"reduce(self, inp: str) &#45;&gt; str:&#10;Reduce input `inp` using delta debugging. Return reduced input.\">\n",
       "<text text-anchor=\"start\" x=\"57.88\" y=\"-46.62\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-weight=\"bold\" font-style=\"italic\" font-size=\"10.00\">reduce()</text>\n",
       "</a>\n",
       "</g>\n",
       "</a>\n",
       "</g>\n",
       "</a>\n",
       "</g>\n",
       "</g>\n",
       "<!-- CachingReducer -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>CachingReducer</title>\n",
       "<g id=\"a_node2\"><a xlink:href=\"#\" xlink:title=\"class CachingReducer:&#10;A reducer that also caches test outcomes\">\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"111.38,-161.5 111.38,-218 226.38,-218 226.38,-161.5 111.38,-161.5\"/>\n",
       "<text text-anchor=\"start\" x=\"119.38\" y=\"-201.7\" font-family=\"Patua One, Helvetica, sans-serif\" font-weight=\"bold\" font-size=\"14.00\" fill=\"#b03a2e\">CachingReducer</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"111.38,-192 226.38,-192\"/>\n",
       "<g id=\"a_node2_2\"><a xlink:href=\"#\" xlink:title=\"CachingReducer\">\n",
       "<g id=\"a_node2_3\"><a xlink:href=\"#\" xlink:title=\"reset(self):&#10;Reset the test counter to zero. To be extended in subclasses.\">\n",
       "<text text-anchor=\"start\" x=\"147.88\" y=\"-179.5\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-style=\"italic\" font-size=\"10.00\">reset()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node2_4\"><a xlink:href=\"#\" xlink:title=\"test(self, inp):&#10;Test with input `inp`. Return outcome.&#10;To be extended in subclasses.\">\n",
       "<text text-anchor=\"start\" x=\"147.88\" y=\"-168.25\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-style=\"italic\" font-size=\"10.00\">test()</text>\n",
       "</a>\n",
       "</g>\n",
       "</a>\n",
       "</g>\n",
       "</a>\n",
       "</g>\n",
       "</g>\n",
       "<!-- DeltaDebuggingReducer&#45;&gt;CachingReducer -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>DeltaDebuggingReducer&#45;&gt;CachingReducer</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M97.23,-85.6C109.98,-103.96 128.38,-130.45 143.34,-151.98\"/>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"140.28,-153.72 148.86,-159.94 146.03,-149.73 140.28,-153.72\"/>\n",
       "</g>\n",
       "<!-- Reducer -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>Reducer</title>\n",
       "<g id=\"a_node3\"><a xlink:href=\"#\" xlink:title=\"class Reducer:&#10;Base class for reducers.\">\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"130.88,-255 130.88,-334 206.88,-334 206.88,-255 130.88,-255\"/>\n",
       "<text text-anchor=\"start\" x=\"144.12\" y=\"-317.7\" font-family=\"Patua One, Helvetica, sans-serif\" font-weight=\"bold\" font-size=\"14.00\" fill=\"#b03a2e\">Reducer</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"130.88,-308 206.88,-308\"/>\n",
       "<g id=\"a_node3_5\"><a xlink:href=\"#\" xlink:title=\"Reducer\">\n",
       "<g id=\"a_node3_6\"><a xlink:href=\"#\" xlink:title=\"__init__(self, runner: Fuzzer.Runner, log_test: bool = False) &#45;&gt; None:&#10;Attach reducer to the given `runner`\">\n",
       "<text text-anchor=\"start\" x=\"138.88\" y=\"-295.5\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-weight=\"bold\" font-size=\"10.00\">__init__()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node3_7\"><a xlink:href=\"#\" xlink:title=\"reduce(self, inp: str) &#45;&gt; str:&#10;Reduce input `inp`. Return reduced input.&#10;To be defined in subclasses.\">\n",
       "<text text-anchor=\"start\" x=\"138.88\" y=\"-284.25\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-weight=\"bold\" font-style=\"italic\" font-size=\"10.00\">reduce()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node3_8\"><a xlink:href=\"#\" xlink:title=\"reset(self) &#45;&gt; None:&#10;Reset the test counter to zero. To be extended in subclasses.\">\n",
       "<text text-anchor=\"start\" x=\"138.88\" y=\"-273\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-weight=\"bold\" font-style=\"italic\" font-size=\"10.00\">reset()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node3_9\"><a xlink:href=\"#\" xlink:title=\"test(self, inp: str) &#45;&gt; str:&#10;Test with input `inp`. Return outcome.&#10;To be extended in subclasses.\">\n",
       "<text text-anchor=\"start\" x=\"138.88\" y=\"-261.75\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-style=\"italic\" font-size=\"10.00\">test()</text>\n",
       "</a>\n",
       "</g>\n",
       "</a>\n",
       "</g>\n",
       "</a>\n",
       "</g>\n",
       "</g>\n",
       "<!-- CachingReducer&#45;&gt;Reducer -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>CachingReducer&#45;&gt;Reducer</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M168.88,-218.29C168.88,-226.06 168.88,-234.76 168.88,-243.42\"/>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"165.38,-243.17 168.88,-253.17 172.38,-243.17 165.38,-243.17\"/>\n",
       "</g>\n",
       "<!-- GrammarReducer -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>GrammarReducer</title>\n",
       "<g id=\"a_node4\"><a xlink:href=\"#\" xlink:title=\"class GrammarReducer:&#10;Reduce inputs using grammars\">\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"181.88,-0.5 181.88,-124.5 329.88,-124.5 329.88,-0.5 181.88,-0.5\"/>\n",
       "<text text-anchor=\"start\" x=\"201.88\" y=\"-108.2\" font-family=\"Patua One, Helvetica, sans-serif\" font-weight=\"bold\" font-size=\"14.00\" fill=\"#b03a2e\">GrammarReducer</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"181.88,-98.5 329.88,-98.5\"/>\n",
       "<g id=\"a_node4_10\"><a xlink:href=\"#\" xlink:title=\"GrammarReducer\">\n",
       "<g id=\"a_node4_11\"><a xlink:href=\"#\" xlink:title=\"__init__(self, runner: Fuzzer.Runner, parser: Parser.Parser, *, log_test: bool = False, log_reduce: bool = False):&#10;Constructor.&#10;`runner` is the runner to be used.&#10;`parser` is the parser to be used.&#10;`log_test` &#45; if set, show tests and results.&#10;`log_reduce` &#45; if set, show reduction steps.\">\n",
       "<text text-anchor=\"start\" x=\"189.88\" y=\"-86\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-weight=\"bold\" font-style=\"italic\" font-size=\"10.00\">__init__()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node4_12\"><a xlink:href=\"#\" xlink:title=\"reduce(self, inp):&#10;Reduce input `inp`. Return reduced input.&#10;To be defined in subclasses.\">\n",
       "<text text-anchor=\"start\" x=\"189.88\" y=\"-74.75\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-weight=\"bold\" font-style=\"italic\" font-size=\"10.00\">reduce()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node4_13\"><a xlink:href=\"#\" xlink:title=\"alternate_reductions(self, tree: DerivationTree, symbol: str, depth: int = &#45;1)\">\n",
       "<text text-anchor=\"start\" x=\"189.88\" y=\"-62.5\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-size=\"10.00\">alternate_reductions()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node4_14\"><a xlink:href=\"#\" xlink:title=\"parse(self, inp)\">\n",
       "<text text-anchor=\"start\" x=\"189.88\" y=\"-51.25\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-size=\"10.00\">parse()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node4_15\"><a xlink:href=\"#\" xlink:title=\"reduce_subtree(self, tree: DerivationTree, subtree: DerivationTree, depth: int = &#45;1)\">\n",
       "<text text-anchor=\"start\" x=\"189.88\" y=\"-40\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-size=\"10.00\">reduce_subtree()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node4_16\"><a xlink:href=\"#\" xlink:title=\"reduce_tree(self, tree)\">\n",
       "<text text-anchor=\"start\" x=\"189.88\" y=\"-28.75\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-size=\"10.00\">reduce_tree()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node4_17\"><a xlink:href=\"#\" xlink:title=\"subtrees_with_symbol(self, tree: DerivationTree, symbol: str, depth: int = &#45;1, ignore_root: bool = True) &#45;&gt; List[DerivationTree]:&#10;Find all subtrees in `tree` whose root is `symbol`.&#10;If `ignore_root` is true, ignore the root note of `tree`.\">\n",
       "<text text-anchor=\"start\" x=\"189.88\" y=\"-17.5\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-size=\"10.00\">subtrees_with_symbol()</text>\n",
       "</a>\n",
       "</g>\n",
       "<g id=\"a_node4_18\"><a xlink:href=\"#\" xlink:title=\"symbol_reductions(self, tree: DerivationTree, symbol: str, depth: int = &#45;1):&#10;Find all expansion alternatives for the given symbol\">\n",
       "<text text-anchor=\"start\" x=\"189.88\" y=\"-6.25\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-size=\"10.00\">symbol_reductions()</text>\n",
       "</a>\n",
       "</g>\n",
       "</a>\n",
       "</g>\n",
       "</a>\n",
       "</g>\n",
       "</g>\n",
       "<!-- GrammarReducer&#45;&gt;CachingReducer -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>GrammarReducer&#45;&gt;CachingReducer</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M213.39,-124.66C206.94,-133.95 200.45,-143.29 194.51,-151.85\"/>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"191.75,-149.69 188.92,-159.9 197.49,-153.68 191.75,-149.69\"/>\n",
       "</g>\n",
       "<!-- Legend -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>Legend</title>\n",
       "<text text-anchor=\"start\" x=\"348.25\" y=\"-78.5\" font-family=\"Patua One, Helvetica, sans-serif\" font-weight=\"bold\" font-size=\"10.00\" fill=\"#b03a2e\">Legend</text>\n",
       "<text text-anchor=\"start\" x=\"348.25\" y=\"-68.5\" font-family=\"Patua One, Helvetica, sans-serif\" font-size=\"10.00\">• </text>\n",
       "<text text-anchor=\"start\" x=\"354.25\" y=\"-68.5\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-weight=\"bold\" font-size=\"8.00\">public_method()</text>\n",
       "<text text-anchor=\"start\" x=\"348.25\" y=\"-58.5\" font-family=\"Patua One, Helvetica, sans-serif\" font-size=\"10.00\">• </text>\n",
       "<text text-anchor=\"start\" x=\"354.25\" y=\"-58.5\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-size=\"8.00\">private_method()</text>\n",
       "<text text-anchor=\"start\" x=\"348.25\" y=\"-48.5\" font-family=\"Patua One, Helvetica, sans-serif\" font-size=\"10.00\">• </text>\n",
       "<text text-anchor=\"start\" x=\"354.25\" y=\"-48.5\" font-family=\"'Fira Mono', 'Source Code Pro', 'Courier', monospace\" font-style=\"italic\" font-size=\"8.00\">overloaded_method()</text>\n",
       "<text text-anchor=\"start\" x=\"348.25\" y=\"-39.45\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\">Hover over names to see doc</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x11db1df00>"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ignore\n",
    "display_class_hierarchy([DeltaDebuggingReducer, GrammarReducer],\n",
    "                        public_methods=[\n",
    "                            Reducer.__init__,\n",
    "                            Reducer.reset,\n",
    "                            Reducer.reduce,\n",
    "                            DeltaDebuggingReducer.reduce,\n",
    "                            GrammarReducer.__init__,\n",
    "                            GrammarReducer.reduce,\n",
    "                        ],\n",
    "                        types={\n",
    "                            'DerivationTree': DerivationTree,\n",
    "                            'Grammar': Grammar,\n",
    "                            'Outcome': Outcome,\n",
    "                        },\n",
    "                        project='fuzzingbook')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Lessons Learned\n",
    "\n",
    "* Reducing failure-inducing inputs to a minimum is helpful for testing and debugging.\n",
    "* _Delta debugging_ is a simple and robust algorithm to easily reduce test cases.\n",
    "* For syntactically complex inputs, _grammar-based reduction_ is much faster and yields better results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Next Steps\n",
    "\n",
    "Our next chapter focuses on [Web GUI Fuzzing](WebFuzzer.ipynb), another domain where generating and reducing test cases is central."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Background\n",
    "\n",
    "The \"lexical\" delta debugging algorithm discussed here stems from \\cite{Zeller2002}; actually, this is the exact Python implementation as used by Zeller in 2002.  The idea of systematically reducing inputs has been discovered a number of times, although not as automatic and generic as delta debugging. \\cite{Slutz1998}, for instance, discusses systematic reduction of SQL statements for SQL databases; the general process as manual work is well described by \\cite{Kernighan1999}."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The deficits of delta debugging as it comes to syntactically complex inputs were first discussed in *compiler testing*, and _reducing tree inputs_ rather than string inputs was quickly discovered as an alternative.  *Hierarchical Delta Debugging* (*HDD*) \\cite{Misherghi2006} applies delta debugging on subtrees of a parse tree, systematically reducing a parse tree to a minimum.  _Generalized Tree Reduction_ \\cite{Herfert2017} generalizes this idea to apply arbitrary _patterns_ such as replacing a term by a compatible term in a subtree, as `subtrees_with_symbol()` does.  Using _grammars_ to reduce inputs was first implemented in the _Perses_ tool \\cite{Sun2018}; our algorithm implements very similar strategies.  Searching for alternate expansions (as `alternate_reductions()`) is a contribution of the present chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "While applying delta debugging to code lines does a decent job, _syntactic_ and especially _language-specific_ approaches can do a much better job for the programming language at hand:\n",
    "\n",
    "* *C-Reduce* \\cite{Regehr2012} is a reducer specifically targeting the reduction of programming languages.  Besides reductions in the style of delta debugging or tree transformations, C-Reduce comes with more than 30 source-to-source transformations that replace aggregates by scalars, remove function parameters at a definition and all call sites, change functions to return `void` and deleting all `return` statements, and many more.  While specifically instantiated for the C language (and used for testing C compilers), these principles extend to arbitrary programming languages following an ALGOL-like syntax.\n",
    "\n",
    "* Kalhauge and Palsberg \\cite{Kalhauge2019} introduce *binary reduction of dependency graphs*, a general solution for reducing arbitrary inputs with dependencies. Their *J-Reduce* tool specifically targets Java programs, and again is much faster than delta debugging and achieves a higher reduction rate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Reducing inputs also works well in the context of _property-based testing_; that is, generating data structures for individual functions, which can then be reduced (\"shrunk\") upon failure. The [Hypothesis](https://hypothesis.works) fuzzer has a number of type-specific shrinking strategies; this [blog article](https://hypothesis.works/articles/integrated-shrinking/) discusses some of its features."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The chapter on [\"Reducing Failure-Inducing Inputs\" in the Debugging Book](https://www.debuggingbook.org/html/DeltaDebugger.html) has an alternate implementation `DeltaDebugger` of delta debugging that is even easier to deploy; here, one simply writes\n",
    "\n",
    "```python\n",
    "with DeltaDebugger() as dd:\n",
    "    fun(args...)\n",
    "dd\n",
    "```\n",
    "\n",
    "to reduce the input in `args` for a failing (exception-throwing) function `fun()`. The chapter also  discusses further usage examples, including reducing _code_ to a minimum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This [blog post](https://www.drmaciver.com/2019/01/notes-on-test-case-reduction/) by David McIver contains lots of insights on how to apply reduction in practice, in particular multiple runs with different abstraction levels."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": true,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercises\n",
    "\n",
    "How to best reduce inputs is still an underdeveloped field of research, with lots of opportunities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution2": "hidden",
    "solution2_first": true
   },
   "source": [
    "### Exercise 1: Mutation-Based Fuzzing with Reduction\n",
    "\n",
    "When fuzzing with a population, it can be useful to occasionally _reduce_ the length of each element, such that future descendants are shorter, too, which typically speeds up their testing.\n",
    "\n",
    "Consider the `MutationFuzzer` class from [the chapter on mutation-based fuzzing](MutationFuzzer.ipynb). \n",
    "Extend it such that whenever a new input is added to the population, it is first reduced using delta debugging."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution": "hidden",
    "solution2": "hidden",
    "solution2_first": true,
    "solution_first": true
   },
   "source": [
    "### Exercise 2: Reduction by Production\n",
    "\n",
    "Grammar-based input reduction, as sketched above, might be a good algorithm, but is by no means the only alternative.  One interesting question is whether \"reduction\" should only be limited to elements already present, or whether one would be allowed to also create _new_ elements.  These would not be present in the original input, yet still allow producing a much smaller input that would still reproduce the original failure."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution": "hidden",
    "solution2": "hidden",
    "solution2_first": true,
    "solution_first": true
   },
   "source": [
    "As an example, consider the following grammar:\n",
    "\n",
    "```\n",
    "<number> ::= <float> | <integer> | <not-a-number>\n",
    "<float> ::= <digits>.<digits>\n",
    "<integer> ::= <digits>\n",
    "<not-a-number> ::= NaN\n",
    "<digits> ::= [0-9]+\n",
    "```\n",
    "\n",
    "Assume the input `100.99` fails.  We might be able to reduce it to a minimum of, say, `1.9`.  However, we cannot reduce it to an `<integer>` or to `<not-a-number>`, as these symbols do not occur in the original input.  By allowing to _create_ alternatives for these symbols, we could also test inputs such as `1` or `NaN` and further generalize the class of inputs for which the program fails."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution": "hidden",
    "solution2": "hidden",
    "solution2_first": true,
    "solution_first": true
   },
   "source": [
    "Create a class `GenerativeGrammarReducer` as subclass of `GrammarReducer`; extend the method `reduce_subtree()` accordingly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    },
    "solution": "hidden",
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "subslide"
    },
    "solution": "hidden",
    "solution2": "hidden",
    "solution2_first": true,
    "solution_first": true
   },
   "source": [
    "### Exercise 3: The Big Reduction Shoot-Out\n",
    "\n",
    "Create a _benchmark_ for the grammars already defined earlier, consisting of:\n",
    "\n",
    "1. A set of _inputs_, produced from these very grammars using `GrammarFuzzer` and derivatives;\n",
    "2. A set of _tests_ which check for the occurrence of individual symbols as well as pairs and triples of these symbols:\n",
    "    * Tests should be _unresolved_ if the input is not syntactically valid;\n",
    "    * Tests should _fail_ if the symbols (or pairs or triples thereof) occur;\n",
    "    * Tests should _pass_ in all other cases.\n",
    "    \n",
    "Compare delta debugging and grammar-based debugging on the benchmark.  Implement HDD \\cite{Misherghi2006} and _Generalized Tree Reduction_ \\cite{Herfert2017} and add them to your comparison.  Which approach performs best, and under which circumstances?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    },
    "slideshow": {
     "slide_type": "skip"
    },
    "solution": "hidden",
    "solution2": "hidden"
   },
   "source": [
    "**Solution.** Left to the reader."
   ]
  }
 ],
 "metadata": {
  "ipub": {
   "bibliography": "fuzzingbook.bib",
   "toc": true
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  },
  "toc-autonumbering": false,
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}