2 Naturalness of Code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f7a0ad46",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# The Naturalness of Code: Analyzing Code at Token Level"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f08be23c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In the last lecture we considered two very basic analyses (counting lines of code, and detecting code clones) at character level, by splitting lines. Since our clone analysis looks at lines, it can be very easily fooled simply by adding spurious whitespace (e.g. lines breaks). For example, here is our example function from the last lecture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0087d0b9",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code1 = \"\"\"\n",
    "public class Foo {\n",
    "  public void foo(int x) {\n",
    "    System.out.println(\"Hello Clone!\");\n",
    "    int j = 10;\n",
    "    for(int i = 0; i < x; i++) {\n",
    "      System.out.println(\"Another iteration\");\n",
    "    }\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98e47918",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Here is a method in a different class that contains exactly the same code, but has some changes to whitespace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63bb093f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code2 = \"\"\"\n",
    "public class Bar {\n",
    "  public void bar(int x) {\n",
    "    System.out.\n",
    "            println(\"Hello Clone!\");\n",
    "    int j=10;\n",
    "    for(int i = 0; \n",
    "        i < x;\n",
    "        i++) {\n",
    "        System.out.println(\"Another iteration\");\n",
    "    }\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3cc00e83",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's have a look what our clone analysis tells us about these two files. For this we need to reproduce the functions we used last time. The first function splits the source code into lines, but ignores empty lines, lines that contain only braces, or comment lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3ba46f8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_lines(code):\n",
    "    lines = [l.replace(\"}\", \"\").replace(\"{\", \"\").strip() for l in code.split(\"\\n\")]\n",
    "    code_lines = [l for l in lines if l and not l.startswith(\"//\")]\n",
    "\n",
    "    return code_lines"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51975e07",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The resulting lines are compared directly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "adfefd4e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def compare_lines(lines1, lines2):    \n",
    "    matrix = []\n",
    "    \n",
    "    for line1 in lines1:\n",
    "        row = []\n",
    "        for line2 in lines2:\n",
    "            row.append(1 if line1 == line2 else 0)\n",
    "            \n",
    "        matrix.append(row)\n",
    "                \n",
    "    return matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f709801c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A clone is found if there are diagonals of `1`s in the matrix produced by `compare_lines`. We can get the length of such a diagonal for a given location as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4b8bd5d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_block_at(matrix, x, y):\n",
    "    block = []\n",
    "    \n",
    "    while (x < len(matrix) and y < len(matrix[x]) and matrix[x][y]):\n",
    "        block.append((x, y))\n",
    "        x += 1\n",
    "        y += 1\n",
    "    \n",
    "    return block"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0d0eea6",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To get all diagonals of a minimum size we used the following function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d341d30",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_blocks(matrix, min_size = 3):\n",
    "    blocks = []\n",
    "    covered = set()\n",
    "    \n",
    "    width = len(matrix)\n",
    "    height = len(matrix[0])\n",
    "    \n",
    "    for x in range(width):\n",
    "        for y in range(height):\n",
    "            if (x, y) in covered:\n",
    "                continue\n",
    "                \n",
    "            block = get_block_at(matrix, x, y)\n",
    "            if len(block) >= min_size:\n",
    "                blocks.append(block)\n",
    "                for (bx, by) in block:\n",
    "                    covered.add((bx, by))\n",
    "    \n",
    "    return blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f29a4a4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Finally, here is the output function that shows us our clones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59c2e6e6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def print_clones(code1, code2):\n",
    "    lines1 = get_lines(code1)\n",
    "    lines2 = get_lines(code2)\n",
    "    \n",
    "    matrix = compare_lines(lines1, lines2)\n",
    "    clones = get_blocks(matrix)\n",
    "    \n",
    "    for clone in clones:\n",
    "        print(\"Code in snippet 1:\")\n",
    "        for i, j in clone:\n",
    "            print(str(i + 1).rjust(3, ' '), ':', lines1[i])\n",
    "\n",
    "        print(\"Code in snippet 2:\")\n",
    "        for i, j in clone:\n",
    "            print(str(j + 1).rjust(3, ' '), ':', lines2[j])\n",
    "        print(\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b474d3cf",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Can a clone be found by comparing `code1` and `code2`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c4059b6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print_clones(code1, code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "963f007e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As expected, no clones were found. Although our `get_lines` function removes whitespace at the beginning and the end of lines, it does not look at whitespace within lines. One idea to improve our clone analysis would therefore be to not look at entire lines, but at _words_ that are separated by whitespaces."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe6b1bd2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Splitting source code into words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8748588a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code1.split()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd31e1ad",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can easily adapt our clone analysis from using lines to the words produced by the `split` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab06a046",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def print_clones(code1, code2):\n",
    "    lines1 = code1.split()\n",
    "    lines2 = code2.split()\n",
    "    \n",
    "    matrix = compare_lines(lines1, lines2)\n",
    "    clones = get_blocks(matrix)\n",
    "    \n",
    "    for clone in clones:\n",
    "        print(\"Code in snippet 1:\")\n",
    "        for i, j in clone:\n",
    "            print(str(i + 1).rjust(3, ' '), ':', lines1[i])\n",
    "\n",
    "        print(\"Code in snippet 2:\")\n",
    "        for i, j in clone:\n",
    "            print(str(j + 1).rjust(3, ' '), ':', lines2[j])\n",
    "        print(\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6a3494e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Any luck?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fa912d16",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print_clones(code1, code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca4b173f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "It found something! However, the first clone is not really interesting, it's just because our minimum size of 3 probably is too low when looking at words rather than lines. The second clone is more interesting: the entire `for`-loop is now detected as a clone, which indeed it is. However, the two lines preceding the loop are not included. The reason is that natural text is separated into words with white spaces, but source code isn't (only). There are also special syntactical variants such as braces etc. In our example, `System.out.println` is not split into multiple words, even though it has multiple components from the point of view of a compiler reading the source code. Similarly, `int j=10` should be more than two words (`int`, `j=10`) -- ideally, the same number of words as `int j = 10` (`int`, `j`, `=`, `10`)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "444a27ff",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "There's another problem. Recall that _type 2_ clones may differ in terms of literals or identifiers and should still be considered as code clones:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c97bcd62",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code3 = \"\"\"\n",
    "public class Bar {\n",
    "  public void bar(int x) {\n",
    "    System.out.println(\"Completely different text!\");\n",
    "    int j = 200; // completely different numbers\n",
    "    for(int i = 100; i < x; i++) {\n",
    "      System.out.println(\"More completely different text\");\n",
    "    }\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "050991d2",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This snippet is identical to the first snippet, execpt for variable names and literals. However, the clones we can find are not particularly interesting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a40eadec",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print_clones(code1, code3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "615fea0d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Although there are multiple clones, these just make us wish we had set `min_size` to something much larger than 3, because none of these clones is interesting."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f63a507",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To identify type 2 clones we would need to modify our clone analysis such that it compares all parts of the program except the identifiers and literals. But how can our analysis know what are variables and literals, and how can we get around the problem that words are not always separated by whitespace?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e28e6de6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Lexing Source Code"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e30eac01",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Source code is processed by a compiler to create an internal tree-representation that allows it to translate it to another language (e.g. assembly), or to interpret it directly. The analysis phase of a compiler consists of two parts: A low-level part called a lexical analyser (mathematically, a finite automaton based on a regular grammar), and a high-level part called a syntax analyser, or parser (mathematically, a push-down automaton based on a context-free grammar, or BNF). Today, we will consider the first part, the lexical analysis."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ce89b2f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A lexer identifies substrings of the source program that belong together; these substrings are called *lexemes*."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43bc88c2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For example, given the string `for(int i = 0; i < x; i++) {` we would like to build a lexer that outputs the following lexemes:\n",
    "- `for`\n",
    "- `(`\n",
    "- `int`\n",
    "- `i`\n",
    "- `=`\n",
    "- `0`\n",
    "- `;`\n",
    "- `i`\n",
    "- `<`\n",
    "- `x`\n",
    "- `;`\n",
    "- `i`\n",
    "- `++`\n",
    "- `)`\n",
    "- `{`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ad73f83",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Some of the following examples are based on https://medium.com/@pythonmembers.club/building-a-lexer-in-python-a-tutorial-3b6de161fe84"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4de2d8f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will start by producing lexemes that separate strings on whitespaces. A simple way to do this would be to simply iterate over a string and store a lexeme whenever we encounter whitespace:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b5479608",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "string = 'I love software analysis'\n",
    "white_space = ' '\n",
    "lexemes = []\n",
    "\n",
    "lexeme = ''\n",
    "for i,char in enumerate(string):\n",
    "    lexeme += char\n",
    "    if (i+1 < len(string)):\n",
    "        if string[i+1] == white_space:\n",
    "            lexemes.append(lexeme)\n",
    "            lexeme = ''\n",
    "\n",
    "lexemes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e1812d8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "One issue here is that our string does not end in whitespace, so we need to always add the final lexeme:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3b7001b1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "string = 'I love software analysis'\n",
    "white_space = ' '\n",
    "lexemes = []\n",
    "\n",
    "lexeme = ''\n",
    "for i,char in enumerate(string):\n",
    "    lexeme += char\n",
    "    if (i+1 < len(string)):\n",
    "        if string[i+1] == white_space:\n",
    "            lexemes.append(lexeme)\n",
    "            lexeme = ''\n",
    "\n",
    "if lexeme:\n",
    "    lexemes.append(lexeme) \n",
    "\n",
    "lexemes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d02fa82",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We are still including the whitespace in our lexemes, which we should avoid really."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63a9f253",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "string = 'I love software analysis'\n",
    "white_space = ' '\n",
    "lexemes = []\n",
    "\n",
    "lexeme = ''\n",
    "for i,char in enumerate(string):\n",
    "    if char != white_space:\n",
    "        lexeme += char\n",
    "    if (i+1 < len(string)):\n",
    "        if string[i+1] == white_space:\n",
    "            lexemes.append(lexeme)\n",
    "            lexeme = ''\n",
    "\n",
    "if lexeme:\n",
    "    lexemes.append(lexeme) \n",
    "\n",
    "lexemes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b047c2bd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We've thus covered lexemes separated by whitespace, but not those separated by syntactical structures of source code. What we need is to define *keywords* that allow our lexer to identify when lexemes represent special syntactical source code elements. Keywords include reserved words like `public`, `class`, but we will treat symbols such as `(` or `{` the same way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3fc10b50",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "symbols = ['{', '}', '(', ')', '[', ']', '.', '\"', '*', '\\n', ':', ',', ';', '=']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8fadceae",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "keywords = ['public', 'class', 'void', 'main', 'String', 'int', 'for', '++']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "364ab8dd",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "KEYWORDS = symbols + keywords"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fa9eaab",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "white_space = [' ', '\\t', '\\n']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "658fabca",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lexemes = []\n",
    "string = code1\n",
    "\n",
    "lexeme = ''\n",
    "for i,char in enumerate(string):\n",
    "    if char not in white_space:\n",
    "        lexeme += char\n",
    "        \n",
    "    if (i+1 < len(string)):\n",
    "        if string[i+1] in white_space or string[i+1] in KEYWORDS or lexeme in KEYWORDS:\n",
    "            if lexeme:\n",
    "                lexemes.append(lexeme)\n",
    "            lexeme = ''\n",
    "\n",
    "if lexeme:\n",
    "    lexemes.append(lexeme) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ad535a6b",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "lexemes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da2debb9",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's put this in a function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a442d737",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def tokenize(code):\n",
    "    lexemes = []\n",
    "    lexeme = \"\"\n",
    "    for i,char in enumerate(code):\n",
    "        if char not in white_space:\n",
    "            lexeme += char\n",
    "        if (i+1 < len(code)):\n",
    "            if code[i+1] in white_space or code[i+1] in KEYWORDS or lexeme in KEYWORDS:\n",
    "                if lexeme:\n",
    "                    lexemes.append(lexeme)\n",
    "                    lexeme = ''\n",
    "    if lexeme:\n",
    "        lexemes.append(lexeme)\n",
    "    return lexemes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ef612fc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's compare the lexemes for our two variants of the same code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e635697",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "lexemes1 = tokenize(code1)\n",
    "lexemes2 = tokenize(code2)\n",
    "\n",
    "for i in range(min(len(lexemes1), len(lexemes2))):\n",
    "    print(lexemes1[i].ljust(20, ' '), lexemes2[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d3e753b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This looks promising, so let's adapt our clone detection to use our lexer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "65fead29",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def print_clones(code1, code2):\n",
    "    lexemes1 = tokenize(code1)\n",
    "    lexemes2 = tokenize(code2)\n",
    "    \n",
    "    matrix = compare_lines(lexemes1, lexemes2)\n",
    "    clones = get_blocks(matrix, 20) # more than 3 \n",
    "    \n",
    "    for clone in clones:\n",
    "        print(\"Code in snippet 1:\")\n",
    "        for i, j in clone:\n",
    "            print(str(i + 1).rjust(3, ' '), ':', lexemes1[i])\n",
    "\n",
    "        print(\"Code in snippet 2:\")\n",
    "        for i, j in clone:\n",
    "            print(str(j + 1).rjust(3, ' '), ':', lexemes2[j])\n",
    "        print(\"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "686618f9",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print_clones(code1, code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0d4e340",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our clone detection now matches the entire code of the two variants of the code snippet."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e866b2c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "However, let's consider a type 2 clone:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c9b8fd99",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code3 = \"\"\"\n",
    "public class Bar {\n",
    "  public void bar(int x) {\n",
    "    System.out.println(\"This is a different string!\");\n",
    "    int j = 50;\n",
    "    for(int i = 100; i < x; i++) {\n",
    "      System.out.println(\"Yet some more different text\");\n",
    "    }\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "933274f7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print_clones(code1, code3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3982efb",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As expected, no code clones were detected because the strings and numbers are different. An obvious way to fix this would be to replace all strings and numbers with some fixed values. However, how do we know which of our lexemes represent strings and numbers?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0ff1384",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## From lexemes to tokens"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21b13f19",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Lexemes match a character pattern, which is associated with a lexical category called a *token*. A token is the name for a set of lexemes, all of which have the same grammatical significance for the parser. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d37795aa",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We define a token as a named tuple that tells us the lexeme (its value), the type of token, and its position in the source code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c39f943c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "Token = namedtuple('Token', ['value', 'type', 'line', 'col'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c18c222f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For our code examples, we might want to distinguish the following token types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5d85c95a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from enum import Enum\n",
    "class TokenType(Enum):\n",
    "    INT = 1\n",
    "    STRING = 2\n",
    "    KEYWORD = 3\n",
    "    SYNTAX = 4\n",
    "    IDENTIFIER = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "646c9bba",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The tokenizer needs to distinguish token types based on the characters encountered."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a612f4b1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def tokenize(code):\n",
    "    tokens = []\n",
    "    lexeme = \"\"\n",
    "    line = 0\n",
    "    col = 0\n",
    "    i = 0\n",
    "    while i < len(code):\n",
    "        char = code[i]\n",
    "        col += 1\n",
    "        if char in white_space:\n",
    "            if char == '\\n':\n",
    "                line += 1\n",
    "                col = 0\n",
    "        elif char in KEYWORDS:\n",
    "            tokens.append(Token(char, TokenType.SYNTAX, line, col))\n",
    "            lexeme = ''\n",
    "        else:\n",
    "            lexeme += char \n",
    "            while code[i+1] not in KEYWORDS and code[i+1] not in white_space:\n",
    "                i += 1\n",
    "                col += 1\n",
    "                lexeme += code[i]\n",
    "            if lexeme in KEYWORDS:\n",
    "                tokens.append(Token(lexeme, TokenType.KEYWORD, line, col))\n",
    "            else:\n",
    "                tokens.append(Token(lexeme, TokenType.IDENTIFIER, line, col))\n",
    "            lexeme = ''\n",
    "        i += 1\n",
    "        \n",
    "    return tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ada568cb",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tokenize(code1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50933487",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can also identify number tokens if the first character of the lexeme is a digit, string tokens if the first character of a lexeme is a quote, and it is common to skip comments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4081e466",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def tokenize(code):\n",
    "    tokens = []\n",
    "    lexeme = \"\"\n",
    "    line = 0\n",
    "    col = 0\n",
    "    i = 0\n",
    "    while i < len(code):\n",
    "        char = code[i]\n",
    "        col += 1\n",
    "        if char == '/':\n",
    "            if code[i+1] == '/':\n",
    "                # Skip comments until end\n",
    "                i += 1\n",
    "                while code[i] != '\\n':\n",
    "                    i += 1\n",
    "        elif char.isnumeric():\n",
    "            lexeme += char\n",
    "            while code[i+1].isnumeric():\n",
    "                i += 1\n",
    "                char = code[i]\n",
    "                lexeme += char\n",
    "            tokens.append(Token(lexeme, TokenType.INT, line, col))\n",
    "            lexeme = ''\n",
    "        elif char in white_space:\n",
    "            if char == '\\n':\n",
    "                line += 1\n",
    "                col = 0\n",
    "        elif char == '\"':\n",
    "            while code[i+1] != '\"':\n",
    "                i += 1\n",
    "                lexeme += code[i]\n",
    "            i += 1\n",
    "            tokens.append(Token(lexeme, TokenType.STRING, line, col))\n",
    "            lexeme = ''\n",
    "        elif char in KEYWORDS:\n",
    "            tokens.append(Token(char, TokenType.SYNTAX, line, col))\n",
    "            lexeme = ''\n",
    "        else:\n",
    "            \n",
    "            lexeme += char \n",
    "            while code[i+1] not in KEYWORDS and code[i+1] not in white_space:\n",
    "                i += 1\n",
    "                lexeme += code[i]\n",
    "            if lexeme in KEYWORDS:\n",
    "                tokens.append(Token(lexeme, TokenType.KEYWORD, line, col))\n",
    "            else:\n",
    "                tokens.append(Token(lexeme, TokenType.IDENTIFIER, line, col))\n",
    "            lexeme = ''\n",
    "        i += 1\n",
    "            \n",
    "    return tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e4c9c32",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tokenize(code1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c2610680",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tokenize(code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59cc2edc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Given our new tokenizer, we can now define a function that normalizes strings and numbers by replacing them with a constant placeholder value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15155c97",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def normalized_tokens(tokens):\n",
    "    normalized_tokens = []\n",
    "    for token in tokens:\n",
    "        if token.type == TokenType.INT:\n",
    "            normalized_tokens.append(Token(\"<INT>\", TokenType.INT, token.line, token.col))\n",
    "        elif token.type == TokenType.STRING:\n",
    "            normalized_tokens.append(Token(\"<STR>\", TokenType.STRING, token.line, token.col))\n",
    "        else:\n",
    "            normalized_tokens.append(token)\n",
    "    \n",
    "    return normalized_tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bee50068",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "normalized_tokens(tokenize(code1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d17d7b56",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To use this in our clone analysis we need to refine our matrix generation to look at the lexemes of the tokens, since the comparison should not consider the location."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "701beeef",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def compare_tokens(tokens1, tokens2):\n",
    "    matrix = []\n",
    "    \n",
    "    for token1 in tokens1:\n",
    "        row = []\n",
    "        for token2 in tokens2:\n",
    "            row.append(1 if token1.value == token2.value else 0)\n",
    "            \n",
    "        matrix.append(row)\n",
    "                \n",
    "    return matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe2571ce",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Finally, here's our refined clone analysis that works at token level. We also refine the analysis to print the affected lines instead of lists of tokens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c1c8b73b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def print_clones(code1, code2):\n",
    "    tokens1 = tokenize(code1)\n",
    "    tokens2 = tokenize(code2)\n",
    "    \n",
    "    normalized_tokens1 = normalized_tokens(tokens1)\n",
    "    normalized_tokens2 = normalized_tokens(tokens2)\n",
    "   \n",
    "    matrix = compare_tokens(normalized_tokens1, normalized_tokens2)\n",
    "    \n",
    "    clones = get_blocks(matrix, 20)\n",
    "    \n",
    "    for clone in clones:\n",
    "        print(\"Clone\")\n",
    "        lines1 = []\n",
    "        lines2 = []\n",
    "        for i, j in clone:\n",
    "            line = tokens1[i].line\n",
    "            if line not in lines1:\n",
    "                lines1.append(line)\n",
    "                \n",
    "            line = tokens2[i].line\n",
    "            if line not in lines2:\n",
    "                lines2.append(line)\n",
    "        \n",
    "        print(\"Code in snippet 1:\")\n",
    "        code_lines = code1.split('\\n')\n",
    "        for line in lines1:\n",
    "            print(f\"{line+1}: {code_lines[line+1]}\")\n",
    "\n",
    "        print(\"Code in snippet 2:\")\n",
    "        code_lines = code2.split('\\n')\n",
    "        for line in lines2:\n",
    "            print(f\"{line+1}: {code_lines[line+1]}\")\n",
    "        print(\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa738376",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "First a sanity check: Does it still work on our type 1 clone?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f083e00",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print_clones(code1, code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5cf8e0a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "(Note that our clone detection is taking a number of shortcuts; we could improve how we are analyzing the matrix. If you reduce the `min_size` you'll currently see some redundant code clones.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f04cd4dd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now let's consider our type 2 clone."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3889656",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print_clones(code1, code3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "672996c7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "It works! "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63ab0239",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In practice, we wouldn't need to create a lexer by hand. Language recognition is an established problem in computer science, and compiler construction a mature topic with many supporting tools. The classical lexer generator tool is [Flex](https://github.com/westes/flex), which is based on the classic Unix utility [Lex](https://en.wikipedia.org/wiki/Lex_(software)). Tokens are specified as regular expressions, and Flex automatically generates the code that processes a character stream to generate tokens."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d6f806f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For Python code aiming to tokenize Java code, there is the  [javalang](https://github.com/c2nes/javalang) parser framework, which provides a tokenizer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "336dd433",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import javalang"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3498e051",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The output in principle is similar to what our tokenizer does."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12005935",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "list(javalang.tokenizer.tokenize(code1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe91e7f7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "It would be straightforward to adapt out clone detection to use javalang."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5adaefbb",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Language Models"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27c27ed4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The tokenizer allows us to split source code propely into words, just like we are able to do for regular text by whitespaces. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bd6bac0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Natural languages like English are rich and powerful, but in practice most human utterances are simple, repetitive and predictable. These utterances can be very usefully modeled using modern statistical methods. This has led to the phenomenal success of Natural Language Processing (NLP), i.e. statistical approaches to speech recognition, natural language translation, question-answering, and text mining and comprehension."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbdd5774",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since we can now split source code into words just like we can do for natural language, this raises the question whether we can apply NLP methods also to source code. Hindle et al. postulated that software is similarly natural, in the sense that it is created by humans at work, with all the attendant constraints and limitations, and is therefore also repetitive and predictable."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ffcaff1",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Abram Hindle, Earl T. Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. On the naturalness of software. In 2012 34th International Conference on Software Engineering (ICSE), pages 837–847, 2012.6"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2bf5750a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The _Naturalness Hypothesis_ states that code can be usefully modeled by statistical language models, and such models can be leveraged to support software engineers. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8738b7da",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A language model essentially assigns a probability to an utterance. It is typically formulated in terms of conditional probabilities, where the probability of the next word in a sequence is conditioned on all previous words in the sequence. Let's take a closer look at language models in the scope of natural language processing, before moving on to see how they can be used with software."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b086fc6a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### n-gram models"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a84a158a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The n-gram model is a simple statistical language model. Consider the sequence of tokens in a document (in our case, a system s), $a_1 a_2 \\ldots a_i \\ldots a_n$. An n-gram model estimates the probability of a sequence by statistically estimating how likely tokens are to follow other tokens. Thus, we can estimate the probability of a document based on the product of a series of conditional probabilities:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d1082b2",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "$p(s) = p(a_1) \\times p(a_2 | a_1) \\times p(a_3 | a_1a_2) \\ldots p(a_n | a_1 \\ldots a_{n−1})$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78cac76c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A n-gram model assumes a Markov property, i.e., token occurrences are influenced only by a limited\n",
    "prefix of length n, thus for 4-gram models, we assume"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bff1369f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "$p(a_i | a_1 \\ldots a_{i−1}) ≊ p(a_i | a_{i−3}a_{i−2}a_{i−1})$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19146958",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "These models are estimated from a corpus using simple maximum-likelihood based frequency-counting of token sequences. Thus, if ∗ is a wildcard, we ask, how relatively often are the tokens a1 , a2 , a3 followed by a4:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3da18635",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "$p(a_4 | a_1 a_2 a_3) = \\frac{count(a_1 a_2 a_3 a_4)}{count(a_1 a_2 a_3 ∗)}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4260e5ba",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will use the well-established NLTK library for n-gram models."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e6b8ec7a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from nltk.util import ngrams"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c58ea69",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's assume ab arbitary sentence in natural language."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a8710ec2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "string = \"there is a cat licking your birthday cake\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0762ed51",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's set `n=2` to start with. Using NLTK, we can extract all bigrams from our sentence easily."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "766b5cfb",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 2\n",
    "list(ngrams(string.split(), n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "992532e0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For common values of `n` NLTK also offers functions we can directly call without specifying `n`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "306c5b55",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from nltk.util import bigrams\n",
    "list(bigrams(string.split()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "629bd38d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Note that the first (`there`) and last (`cake`) word only occur once, while all other words are part of two bigrams. In order to allow the model to capture how often sentences start with `there` and end with `cake` NLTK let's us add special padding symbols to the sentence before splitting it into n-grams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b810d54",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from nltk.lm.preprocessing import pad_both_ends\n",
    "list(bigrams(pad_both_ends(string.split(), n=2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc1d45a8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To make our model more robust we could also train it on unigrams (single words) as well as bigrams, its main source of information. NLTK once again helpfully provides a function called everygrams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2365b879",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from nltk.util import everygrams\n",
    "list(everygrams(string.split(), max_len=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b9a451d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "During training and evaluation our model will rely on a vocabulary that defines which words are \"known\" to the model. To create this vocabulary we need to pad our sentences (just like for counting ngrams) and then combine the sentences into one flat stream of words. This is done by the pipeline function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17db9e65",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from nltk.lm.preprocessing import padded_everygram_pipeline\n",
    "string_tokens = [\"there is a cat licking your birthday cake\".split(),\n",
    "                \"he can't read so he does not know that the cake is not for him\".split(),\n",
    "                \"it might be his birthday too but the chance of that is slim\".split()\n",
    "                ]\n",
    "\n",
    "train, vocab = padded_everygram_pipeline(2, string_tokens)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8668afa7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "So as to avoid re-creating the text in memory, both train and vocab are lazy iterators. They are evaluated on demand at training time.\n",
    "\n",
    "For the sake of understanding the output of padded_everygram_pipeline, we'll \"materialize\" the lazy iterators by casting them into a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b64ff8bf",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "training_ngrams, padded_sentences = padded_everygram_pipeline(2, string_tokens)\n",
    "for ngramlize_sent in training_ngrams:\n",
    "    print(list(ngramlize_sent))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc1c30a3",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "list(padded_sentences)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0aaf37c7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Having prepared our data we are ready to start training a model. As a simple example, let us train a Maximum Likelihood Estimator (MLE).\n",
    "\n",
    "We only need to specify the highest ngram order to instantiate it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67af5e70",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from nltk.lm import MLE\n",
    "lm = MLE(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75b0bed9",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The model initially has no content:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72039b1b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(lm.vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64525bfc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We need to train the model with our n-grams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36115a4e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.fit(train, vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eacb507f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(lm.vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fce6396",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can look up vocabulary in the model, for example to check that our first sentence is contained in the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22a3ec69",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.vocab.lookup(string_tokens[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a4cd6176",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "If we lookup the vocab on unseen sentences not from the training data,  NLTK automatically replaces words not in the vocabulary with `<UNK>`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d72574e5",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.vocab.lookup('there is a cat licking your birthday foo'.split())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a40d8bef",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "When it comes to ngram models the training boils down to counting up the ngrams from the training corpus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6bf295cf",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print(lm.counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07c7a7dd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can check how often individual unigrams occur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "acbed421",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.counts[\"licking\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d732b7f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.counts[\"birthday\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "812c20e5",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can also check how often bigrams occur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3401a05",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.counts[[\"might\"]][\"be\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17286b70",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The real purpose of training a language model is to have it score how probable words are in certain contexts. This being MLE, the model returns the item's relative frequency as its score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "95f2ed5a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.score(\"licking\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e141259",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.score(\"birthday\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0ed761a4",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.score(\"be\", [\"might\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70fe171d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Items that are not seen during training are mapped to the vocabulary's \"unknown label\" token. All unknown tokens have the same probability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ef3ea0c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "lm.score(\"<UNK>\") == lm.score(\"foo\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f32c65b",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.score(\"<UNK>\") == lm.score(\"bar\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31bdc726",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To avoid underflow when working with many small score values it makes sense to take their logarithm. For convenience this can be done with the logscore method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b2d0c12b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.logscore(\"licking\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "478ceb0c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.logscore(\"birthday\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "edfb8e36",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.logscore(\"be\", [\"might\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "184e1de5",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Is Software Natural?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc3d2d24",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now that we know what a language model is, let's return to software. The core of the naturalness hypothesis is, that software is similarly repetitive and predictable as natural language."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70718ab6",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To determine how predictable a language is, a statistical language model, estimated carefully from a representative corpus, can be evaluated in terms of their _perplexity_ with respect to the contents of a new document drawn from the same population. A good model can guess the contents of the new document with very high probability; i.e., it will not find the new document particularly surprising or perplexing. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29285651",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The perplexity of a language model on a test set is the inverse probability of the test set, normalised by the number of words: $PP(W) = P(w_1w_2...w_N)^{-\\frac{1}{N}}$\n",
    "\n",
    "$PP(W) = \\sqrt[N]{\\prod_{i=1}^N{\\frac{1}{P(w_i|w_{i-1})}}}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e90fe6a5",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Perplexity can also be seen as the weighted average branching factor of a language, i.e., the number of possible next words that can follow any word."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2759558",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "It is common to use the log-transformed variant of perplexity, called _cross entropy_:\n",
    "\n",
    "$H(s)=-\\frac{1}{N}log(P(a_1...a_n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f4f794f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "NLTK of course offers a means to calculate the cross entropy. Let's first pick a dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0cc0baa",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import nltk\n",
    "from nltk.corpus import brown\n",
    "\n",
    "# Might be necessary the first time:\n",
    "# nltk.download('brown')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebf17046",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The Brown Corpus was the first million-word electronic corpus of English, created in 1961 at Brown University. This corpus contains text from 500 sources."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c45d205b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(brown.words())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "938e6e69",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In NLP it is common to apply various preprocessing steps before training a language model. We will keep it simple and just build a corpus of lower case versions of the words in the brown corpus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "119ecfcb",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "brown = nltk.corpus.brown\n",
    "corpus = [[word.lower() for word in sent] for sent in brown.sents()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "603e477d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "corpus[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0dba3b31",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's split the dataset into 95% training data, and 5 test data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d47fe1f1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "split = int(95*len(corpus)/100)\n",
    "train = corpus[:split]\n",
    "test  = corpus[split:]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84c2f7dd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now we can build a language model as we did previously, using a maximum likelihood estimator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e99f8783",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 2\n",
    "train_data, padded_sents = padded_everygram_pipeline(n, train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5934b42c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm = MLE(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ff3418df",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.fit(train_data, padded_sents)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff44a10b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To calculate the perplexity, we can use NLTK. The perplexity function in NLTK expects a list of n-grams as test set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb001ed7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from nltk.lm.preprocessing import padded_everygrams\n",
    "from nltk.lm.preprocessing import flatten\n",
    "\n",
    "test_data = list(flatten(padded_everygrams(n, sent) for sent in test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "edb9f672",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.perplexity(test_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1c82072",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can also calculate the log-transformed version of perplexity, the cross-entropy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4eb1d75f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm.entropy(test_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51ddaf3f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Whoops, infinitely surprised?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d17c80c3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This is a problem of data sparsity: Some n-grams may never occur in one corpus, but may in fact occur elsewhere. Consequently there may be some n-grams in the test data that are not in the training data."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e40f8da",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Smoothing is a technique to handle cases we where have not seen the n-grams yet and still produce usable results with sufficient statistical rigor. There exist a variety of techniques for smoothing the estimates of a very large number of coefficients, some of which are larger than they should be and others smaller. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61458a78",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The simplest smoothing technique is Laplace smoothing, which adds 1 to the count for every n-gram. In practice, this is not a recommended approach, and there are more sophisticated smoothing techniques such as Good-Turing estimates, Jelinek-Mercer smoothing, Katz smoothing, Witten-Bell smoothing, Absolute discounting, Kneser-Ney smoothing, Modified Kneser Ney smoothing, and others."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44ac2d6e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from nltk.lm import Laplace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d39ab46e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 3\n",
    "train_data, padded_sents = padded_everygram_pipeline(n, train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a168f04",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "brown_model = Laplace(n) \n",
    "brown_model.fit(train_data, padded_sents)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c8fd75c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's first calculate the perplexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d70aead0",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "brown_model.perplexity(test_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a2608b8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "...and now the cross entropy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3855b42d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "brown_model.entropy(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d99e321",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Hindle et al. evaluated the cross entropy for different values of `n` on the Brown and the Gutenberg corpus. We will replicate this experiment, but to keep the computation time down we'll skip the Gutenberg corpus and only use small values for `n`, and no cross-validation. It is worth noting, however, that the perplexity of two language models is only _directly_ comparable if they use identical vocabularies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9cb99f20",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for n in range(1,5):\n",
    "    train_data, padded_sents = padded_everygram_pipeline(n, train)\n",
    "    brown_model = Laplace(n) \n",
    "    brown_model.fit(train_data, padded_sents)\n",
    "    entropy = brown_model.entropy(test_data)\n",
    "    print(f\"n = {n}: {entropy}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21fa7664",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To see whether software is similar, we need a corpus of source code. Unfortunately, NLTK does not provide this for us. We will thus use an existing corpus provided by others."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "630712a3",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# This may take a while so is commented out\n",
    "#!wget https://s3.amazonaws.com/code2seq/datasets/java-small.tar.gz"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49f49d33",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will only need the lexemes rather than the full tokens, so let's define a helper function for this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbd0cf38",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def tokenize(code):\n",
    "    try:\n",
    "        tokens = [token.value for token in javalang.tokenizer.tokenize(code)]\n",
    "    except:\n",
    "        # Parse errors may occur\n",
    "        return []\n",
    "    return tokens"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "477ce425",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We use this to create a training and test corpus, where a \"sentence\" is represented as the tokenized version of a Java source code file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "375ade7e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import tarfile\n",
    "\n",
    "java_training = []\n",
    "java_test = []\n",
    "with tarfile.open(\"java-small.tar.gz\", \"r\") as f:\n",
    "    for tf in f.getmembers():\n",
    "        if tf.isfile() and tf.name.startswith(\"java-small/training\"):\n",
    "            f2=f.extractfile(tf)\n",
    "            content=f2.read()\n",
    "            java_training.append(tokenize(content))\n",
    "        elif tf.isfile() and tf.name.startswith(\"java-small/test\"):\n",
    "            f2=f.extractfile(tf)\n",
    "            content=f2.read()\n",
    "            java_test.append(tokenize(content))\n",
    "\n",
    "len(java_training)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8fb5792a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "java_test_data = list(flatten(padded_everygrams(n, sent) for sent in java_test if sent))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eae10b3c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Given this dataset, the steps to create a language model are identical to those for a natural language text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "33977935",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for n in range(1,5):\n",
    "    train_data, padded_sents = padded_everygram_pipeline(n, java_training)\n",
    "    java_model = Laplace(n) \n",
    "    java_model.fit(train_data, padded_sents)\n",
    "    entropy = java_model.entropy(java_test_data)\n",
    "    print(f\"n = {n}: {entropy}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fca0c865",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Stopwords"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2deacbfe",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In NLP it is common to remove stopwords before processing data. In our experiments we did not do this, and in particular there is the question what this means for source code: Intuitively, source code contains quite a substantial amount of syntactical overhead. The effects of this have been investigated in the following paper:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2772e493",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Rahman, M., Palani, D., & Rigby, P. C. (2019, May). Natural software revisited. In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE) (pp. 37-48). IEEE."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "613b6cca",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Lets also have a closer look at this. First we compare the language model on the Brown corpus with / without stopwords. We first build a 3-gram model with stopwords."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "506c11eb",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "corpus = [[word for word in sent] for sent in brown.sents()]\n",
    "split = int(95*len(corpus)/100)\n",
    "train = corpus[:split]\n",
    "test = corpus[split:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "035410f0",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 3\n",
    "train_data, padded_sents = padded_everygram_pipeline(n, train)\n",
    "\n",
    "lm_with = Laplace(n) \n",
    "lm_with.fit(train_data, padded_sents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bc022809",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test_data = list(flatten(padded_everygrams(n, sent) for sent in test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ee21a67b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm_with.entropy(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e94caad5",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now we build a pre-processed version of the corpus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42b7e59f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# nltk.download('stopwords')\n",
    "from nltk.corpus import stopwords\n",
    "stop_words = set(stopwords.words('english'))\n",
    "corpus_ns = [[word for word in sent if not word.lower() in stop_words] for sent in brown.sents()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "348a12ef",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "spl = int(95*len(corpus)/100)\n",
    "train_ns = corpus_ns[:spl]\n",
    "test_ns = corpus_ns[spl:]\n",
    "\n",
    "n = 3\n",
    "train_data, padded_sents = padded_everygram_pipeline(n, train_ns)\n",
    "\n",
    "lm_without = Laplace(n) \n",
    "lm_without.fit(train_data, padded_sents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58a0b596",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test_data = list(flatten(padded_everygrams(n, sent) for sent in test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d35f023b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lm_without.entropy(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63ade66c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Probably the effect is not large. However, let's now do this on source code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02bfb471",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "n = 3\n",
    "train_data, padded_sents = padded_everygram_pipeline(n, java_training) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "99840c86",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "java_with = Laplace(n) \n",
    "java_with.fit(train_data, padded_sents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e1b15a7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "java_with.entropy(java_test_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9215be32",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since our Java-corpus only contains the lexemes but no longer the token type information, we'll just re-build the corpus from scratch, but filter on separators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b9e01043",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def tokenize_without_stopwords(code):\n",
    "    try:\n",
    "        tokens = [token.value for token in javalang.tokenizer.tokenize(code) if not isinstance(token, javalang.tokenizer.Separator) ]\n",
    "    except:\n",
    "        return []\n",
    "    return tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7b2081ad",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "java_training = []\n",
    "java_test = []\n",
    "with tarfile.open(\"java-small.tar.gz\", \"r\") as f:\n",
    "    for tf in f.getmembers():\n",
    "        if tf.isfile() and tf.name.startswith(\"java-small/training\"):\n",
    "            f2 = f.extractfile(tf)\n",
    "            content = f2.read()\n",
    "            tokens = tokenize_without_stopwords(content)\n",
    "            if tokens:\n",
    "                java_training.append(tokens)\n",
    "        elif tf.isfile() and tf.name.startswith(\"java-small/test\"):\n",
    "            f2 = f.extractfile(tf)\n",
    "            content = f2.read()\n",
    "            tokens = tokenize_without_stopwords(content)\n",
    "            if tokens:\n",
    "                java_test.append(tokens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ec902590",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n=3\n",
    "train_data, padded_sents = padded_everygram_pipeline(n, java_training)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9f1e9974",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "java_without = Laplace(n) \n",
    "java_without.fit(train_data, padded_sents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d002d35",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test_data = list(flatten(padded_everygrams(n, sent) for sent in java_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b84d427e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "java_without.entropy(test_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9e3fc42",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The entropy of Java without separator characters is higher than without -- this shows that to a certain degree the repetitiveness of software is influenced by the syntactic overhead."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3175cbbf",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Code Completion"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2e38cf4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "n-gram models can be used to generate text, and we start by doing this on a classical corpus of natural language text available at: https://www.kaggle.com/datasets/kingburrito666/better-donald-trump-tweets?resource=download"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "daf04599",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "df = pd.read_csv('data/Donald-Tweets!.csv')\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2073aeaf",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We build the model as usual."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0299151",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from nltk import word_tokenize\n",
    "trump_corpus = list(df['Tweet_Text'].apply(word_tokenize))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22b1393d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Preprocess the tokenized text for 3-grams language modelling\n",
    "n = 3\n",
    "train_data, padded_sents = padded_everygram_pipeline(n, trump_corpus)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "999ff632",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "trump_model = MLE(n) \n",
    "trump_model.fit(train_data, padded_sents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3b5d8cf",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "trump_model.generate(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02efee37",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's use a helper function to turn this into more readable sentences."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a926e91",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Taken from https://www.kaggle.com/code/alvations/n-gram-language-model-with-nltk/notebook\n",
    "\n",
    "from nltk.tokenize.treebank import TreebankWordDetokenizer\n",
    "detokenize = TreebankWordDetokenizer().detokenize\n",
    "\n",
    "def generate_sent(model, num_words, random_seed=42):\n",
    "    \"\"\"\n",
    "    :param model: An ngram language model from `nltk.lm.model`.\n",
    "    :param num_words: Max no. of words to generate.\n",
    "    :param random_seed: Seed value for random.\n",
    "    \"\"\"\n",
    "    content = []\n",
    "    for token in model.generate(num_words, random_seed=random_seed):\n",
    "        if token == '<s>':\n",
    "            continue\n",
    "        if token == '</s>':\n",
    "            break\n",
    "        content.append(token)\n",
    "    return detokenize(content)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5f62f66",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "generate_sent(trump_model, num_words=20, random_seed=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8a8f46ec",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "generate_sent(trump_model, num_words=20, random_seed=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "414c3e3e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "generate_sent(trump_model, num_words=20, random_seed=21)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a4a4c55",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can also provide a context for the prediction in terms of a sentence. The last (n-1) tokens of this sentence are used to find the most likely n-gram."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "74c197df",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "trump_model.generate(1, text_seed = \"Democrats\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "404d84a8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Similarly, a simple approach to implement code completion is to build an n-gram model of source code, use the last (n-1) tokens as context, and look at the most likely n-gram."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "feaae2a8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Suppose we have typed `System.out.` and want to know what's next."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e7a10e5d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "context = \"System.out.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b9c79d94",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tokens = [token.value for token in list(javalang.tokenizer.tokenize(context))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "058889dd",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "java_with.generate(1, text_seed = tokens)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12fa01bf",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "What about for-loops?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb8aaa65",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "context = \"for (int i = 0; i < model.size(); i\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce41a637",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tokens = [token.value for token in list(javalang.tokenizer.tokenize(context))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "656b3dfa",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "java_with.generate(1, text_seed = tokens)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}