{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "Read(\"../gap/optim.g\"); Read(\"../gap/bench.g\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GAP Level Reflection\n",
    "\n",
    "This newly added feature of GAP allows GAP programs to examine and modify the\n",
    "code of executable GAP function objects within the workspace. This will provide a platform for optimisation, automatic parallelisation and Cython-like partial static typing. \n",
    "\n",
    "## A Small Optimisation\n",
    "\n",
    "It is natural in GAP to write `Int(x/y)` for integer division, but this is actually quite inefficient. If `x` is not divisible by `y` then a rational number object will be made on the heap and reduced to lowest terms before being rounded to the nearest integer below.  The `QuoInt` function exists to avoid this, but is unnatural and underused.\n",
    "\n",
    "We demonstrate the difference with a simple benchmark:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"137ns\""
      ]
     },
     "execution_count": 5,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "\"23ns\""
      ]
     },
     "execution_count": 6,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo := function(n) local i,x; for i in [1..n] do \n",
    "    x := Int(i/3); \n",
    "    od; end;;\n",
    "bar :=  function(n) local i,x; for i in [1..n] do \n",
    "    x := QuoInt(i,3); \n",
    "    od; end;;\n",
    "ns2string(timer(foo)); ns2string(timer(bar));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We show how `SyntaxTree` could be used to automatically fix this in the workspace. \n",
    "\n",
    "`f` below is a  test function. The second comment is a *pragma* -- a comment which is retained in the function object, which could be used to direct optimisation.\n",
    "\n",
    "Note that the pragma appears in the syntax tree, unlike the regular comment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EXPR_FUNC(name := f, nams := [ \"x\" ], variadic := false, narg := 1, nloc := 0,\\\n",
      " stats := STAT_SEQ_STAT2(\n",
      "              statements := [\n",
      "                STAT_PRAGMA(value := % optimise here ), STAT_RETURN_OBJ(\n",
      "                  obj := EXPR_SUM(\n",
      "                    right := EXPR_FUNCCALL_1ARGS(\n",
      "                      args := [\n",
      "                        EXPR_QUO(\n",
      "                          right := EXPR_INT(value := 11), left := EXPR_POW(\n",
      "                            right := EXPR_INT(\n",
      "                              value := 2), left := EXPR_REF_LVAR(lvar := 1)))\n",
      "                          ], funcref := EXPR_REF_GVAR(gvar := Int)\n",
      "                           ), left := EXPR_FUNCCALL_1ARGS(\n",
      "                          args := [\n",
      "                            EXPR_QUO(\n",
      "                              right := EXPR_INT(value := 3), left := EXPR_SUM(\n",
      "                                right := EXPR_INT(\n",
      "                                  value := 1), left := EXPR_REF_LVAR(\n",
      "                                  lvar := 1)))\n",
      "                              ], funcref := EXPR_REF_GVAR(gvar := Int))))]))\n",
      "                        "
     ]
    }
   ],
   "source": [
    "f := function(x) \n",
    "    # normal comment\n",
    "    #% optimise here \n",
    "    return Int((x+1)/3) + Int((x^2)/11);\n",
    "end;;\n",
    "Display(SyntaxTree(f));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now to produce an improved version of `f`, we define a *pattern* \n",
    "including placeholders `\"$1\"` and `\"$2\"` and a *replacement*. \n",
    "\n",
    "Both are essentially just fragments of syntax tree.\n",
    "Nicer pattern editing tools and in development."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "rec( args := [ rec( left := \"$1\", right := rec( type := \"EXPR_INT\", value := \"$2\" ), type := \"EXPR_QUO\" ) ], funcref := rec( gvar := \"Int\", type := \"EXPR_REF_GVAR\" ), type := \"EXPR_FUNCCALL_1ARGS\" )"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "rec( args := [ \"$1\", rec( type := \"EXPR_INT\", value := \"$2\" ) ], funcref := rec( gvar := \"QuoInt\", type := \"EXPR_REF_GVAR\" ), type := \"EXPR_FUNCCALL_2ARGS\" )"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pattern := rec(type := \"EXPR_FUNCCALL_1ARGS\", \n",
    "    funcref := rec(type := \"EXPR_REF_GVAR\", gvar := \"Int\"),\n",
    "    args := [rec(type := \"EXPR_QUO\", left := \"$1\", right := rec(type := \"EXPR_INT\", value := \"$2\"))]);\n",
    "replace := rec(type := \"EXPR_FUNCCALL_2ARGS\",\n",
    "    funcref := rec(type := \"EXPR_REF_GVAR\", gvar := \"QuoInt\"),\n",
    "    args := [\"$1\",rec(type := \"EXPR_INT\", value := \"$2\") ]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use these to rewrite `f`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "function ( x )\n",
      "                            #% optimise here \n",
      "                            return QuoInt( x + 1, 3 ) + QuoInt( x ^ 2, 11 );\n",
      "                        end\n",
      "                        "
     ]
    }
   ],
   "source": [
    "g := RewriteFunc(f, pattern, replace);;\n",
    "Display(g);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We compare the performance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"340ns\""
      ]
     },
     "execution_count": 17,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "\"95ns\""
      ]
     },
     "execution_count": 18,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ns2string(timer( function(n) local i; for  i in [1..n] do f(i); od; end));\n",
    "ns2string(timer( function(n) local i; for  i in [1..n] do g(i); od; end));\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "GAP 4",
   "language": "gap",
   "name": "gap-native"
  },
  "language_info": {
   "codemirror_mode": "gap",
   "file_extension": ".g",
   "mimetype": "text/x-gap",
   "name": "GAP 4",
   "nbconvert_exporter": "",
   "pygments_lexer": "gap",
   "version": "4.dev"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}