Intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Programming in julia/Hecke/Oscar - Session 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Julia control flow\n",
    "\n",
    "Julia is an imparative language with all the known workflow constructions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### If conditions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f(x)\n",
    "    if x > 0\n",
    "        return false\n",
    "    elseif x < 0\n",
    "        return true\n",
    "    else\n",
    "        error(\"input must be nonzero\")\n",
    "    end\n",
    "end\n",
    "\n",
    "f(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "input must be nonzero",
     "output_type": "error",
     "traceback": [
      "input must be nonzero",
      "",
      "Stacktrace:",
      " [1] error(::String) at ./error.jl:33",
      " [2] f(::Int64) at ./In[1]:7",
      " [3] top-level scope at In[2]:1",
      " [4] include_string(::Function, ::Module, ::String, ::String) at ./loading.jl:1091"
     ]
    }
   ],
   "source": [
    "f(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### For loops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "53.5"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f(x)\n",
    "    for i in 1:10\n",
    "        if i == 2\n",
    "            continue\n",
    "        end\n",
    "        x += i # this is the same as x = x + i\n",
    "    end\n",
    "    return x\n",
    "end\n",
    "\n",
    "f(0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Range objects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that `1:10` is a range object, which represents the list `1,2,...,10`. Ranges come in different flavors. If one really needs the array of the elements in the range, one can use `collect`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UnitRange{Int64}\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n",
      "[1, 3, 5, 7, 9]\n",
      "[10, 7, 4]\n"
     ]
    }
   ],
   "source": [
    "x = 1:10\n",
    "println(typeof(x))\n",
    "println(collect(x))\n",
    "println(collect(1:2:10))\n",
    "println(collect(10:-3:2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### While loops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f(x)\n",
    "    while x < 100\n",
    "        x = x^2\n",
    "        if x < 50\n",
    "            break\n",
    "        end\n",
    "    end\n",
    "    return x\n",
    "end\n",
    "\n",
    "f(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Ternary conditional operator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-1, 1)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f(x)\n",
    "    return isodd(x) ? -1 : 1\n",
    "end\n",
    "\n",
    "f(3), f(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Basic julia types"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### `Int` (aka `Int64`)\n",
    "Values of this type are usually called machine integers, which is roughly equivalent to working modulo $2^{64}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Int64"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 1\n",
    "typeof(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 2^64"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int === Int64"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### `Float64`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "These are classical floating point numbers (with 53 bits of precision), which are also known as `double`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Float64"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 1.0\n",
    "typeof(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### `String`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "String"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"a + b\"\n",
    "typeof(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "There is something called string interpolation, which is quite useful when quickly printing some things:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x is of type Int64 with value 3\n"
     ]
    }
   ],
   "source": [
    "x = 3 # this is an Int\n",
    "println(\"x is of type $(typeof(x)) with value $(x)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### `BigInt`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "These is integers with arbitrary size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1267650600228229401496703205376"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = BigInt(2)^100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### `Vector`\n",
    "This is the basic types for lists. Note that the fullname is `Vector{T}`, where `T` is the type of the elements of the list. Here are some useful ways to construct lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Int64,1}:\n",
       " 1\n",
       " 2\n",
       " 3"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 2, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Int64,1}:\n",
       "  1\n",
       " -1\n",
       "  4"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = Vector{Int}(undef, 3) # Create a list for values of type `Int` with length 3. The entries in `v` are undefined.\n",
    "v[1] = 1; v[2] = -1; v[3] = 4\n",
    "v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4-element Array{Int64,1}:\n",
       " 0\n",
       " 0\n",
       " 0\n",
       " 0"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = zeros(Int, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### `Matrix`\n",
    "This is the basic type for 2-dimensional arrays. As for `Vector`, it actually is `Matrix{T}`, where `T` is the type of the elements of the list. Here are some constructors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Array{Int64,2}:\n",
       " 1  2\n",
       " 3  4"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1 2; 3 4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×3 Array{Int64,2}:\n",
       " 1  2  3\n",
       " 4  5  6"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = Matrix{Int}(undef, 2, 3)\n",
    "v[1, 1] = 1; v[1, 2] = 2; v[1, 3] = 3; v[2, 1] = 4; v[2, 2] = 5; v[2, 3] = 6;\n",
    "v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### `Array`\n",
    "These are multidimensional arrays, have full type `Array{T, N}`, where `T` is the type of the elements and `N` is the dimension. In fact, by definition we have `Vector{T} === Array{T, 1}` and `Matrix{T} === Array{T, 2}`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Of course, all of these constructions can be nested:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{Array{Int64,1},1}:\n",
       " [1, 2]\n",
       " [3, 4]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [[1, 2], [3, 4]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Methods and multiple dispatch\n",
    "\n",
    "One of the must useful features of julia is the ability to define multiple methods for the same function combined with multiple dispatch. It usually takes some time appreciate it. This also means that one should rarely do stuff like `if typeof(x) == ...`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 5.0)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f(x)\n",
    "    y = x^2\n",
    "    if x isa Int\n",
    "        return y - 1\n",
    "    else\n",
    "        return y + 1\n",
    "    end\n",
    "end\n",
    "\n",
    "f(2), f(2.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This is <b>bad</b>. Better:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 5.0)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function g(y::Int)\n",
    "    return y - 1\n",
    "end\n",
    "\n",
    "function g(y) # this is the same as g(y::Any)\n",
    "    return y + 1\n",
    "end\n",
    "\n",
    "function f(x)\n",
    "    y = x^2\n",
    "    return g(y)\n",
    "end\n",
    "\n",
    "f(2), f(2.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This works, because julia will always use the more specific method (the <i>function</i> `g` has two <i>methods</i>). Here is another example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int <: Integer <: Any"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The type `Int` is a subtype of `Integer`, which is a subtype of `Any`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3.0, 4, 5)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f(x) # same as f(x::Any)\n",
    "    return x + 1\n",
    "end\n",
    "\n",
    "function f(x::Integer)\n",
    "    return x + 2\n",
    "end\n",
    "\n",
    "function f(x::Int)\n",
    "    return x + 3\n",
    "end\n",
    "\n",
    "f(2.0), f(Int32(2)), f(2) # typeof(3) == Int and Int32 <: Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Of course this can also be used to allow only specific types"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f(x::Int)\n",
    "    return x^2\n",
    "end\n",
    "\n",
    "f(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "MethodError: no method matching f(::Float64)\nClosest candidates are:\n  f(!Matched::Int64) at In[34]:1",
     "output_type": "error",
     "traceback": [
      "MethodError: no method matching f(::Float64)\nClosest candidates are:\n  f(!Matched::Int64) at In[34]:1",
      "",
      "Stacktrace:",
      " [1] top-level scope at In[35]:1",
      " [2] include_string(::Function, ::Module, ::String, ::String) at ./loading.jl:1091"
     ]
    }
   ],
   "source": [
    "f(1.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This gives a `MethodError`, which tells us that julia knows of no method of `f` with accepts a `Float64`. To help us, julia will print methods of `f` that are known and why they don't match with our required arguments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Introspection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Having a function with multiple methods is quite powerful, but sometimes makes it hard to figure out which method is actually called. Luckily julia has some very useful tool for type introspection, namely the macro `@which` (we won't discuss what a macro actually is for now)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "f (generic function with 3 methods)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f(x::Number)\n",
    "   return x^2\n",
    "end\n",
    "\n",
    "function f(x::Integer)\n",
    "   return x + 1\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "f(x::<b>Number</b>) in Main at In[39]:1"
      ],
      "text/plain": [
       "f(x::Number) in Main at In[39]:1"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@which f(2.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "f(x::<b>Int64</b>) in Main at In[36]:1"
      ],
      "text/plain": [
       "f(x::Int64) in Main at In[36]:1"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@which f(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This works for almost any function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "+(x::<b>T</b>, y::<b>T</b>)<i> where T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}</i> in Base at <a href=\"https://github.com/JuliaLang/julia/tree/697e782ab86bfcdd7fd15550241fe162c51d9f98/base/int.jl#L86\" target=\"_blank\">int.jl:86</a>"
      ],
      "text/plain": [
       "+(x::T, y::T) where T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8} in Base at int.jl:86"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@which 1 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "push!(a::<b>Array{T,1}</b>, item)<i> where T</i> in Base at <a href=\"https://github.com/JuliaLang/julia/tree/697e782ab86bfcdd7fd15550241fe162c51d9f98/base/array.jl#L932\" target=\"_blank\">array.jl:932</a>"
      ],
      "text/plain": [
       "push!(a::Array{T,1}, item) where T in Base at array.jl:932"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@which push!([1, 2], 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A similar macro is `@less`, which actually shows the source code of the method that will be called."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Oscar/Hecke types\n",
    "\n",
    "The julia Basic types are an indespensible tool when programming in julia. But of course they are not sufficient for doing computer algebra, which requires univariate and multivaraite polynomials, power series, residue rings, residue fields or matrices.\n",
    "\n",
    "### Philosophy\n",
    "\n",
    "Similar to Sage and Magma, in the Oscar ecosystem everything has parents. In other words, elements of a ring/group/field do not exist alone, but every element has a parent. In fact very often, one first has to construct the parent before one can construct elements. Here is an example to construct the polynomial $x^2 + 2x \\in \\mathbf{Z}[x]$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2 + 2*x"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using Hecke;\n",
    "Zx, x = ZZ[\"x\"] # returns the polynomial ring together with the variable\n",
    "h = x^2 + 2x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Basic types\n",
    "Here are some common basic rings that one would like to construct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### The ring of integers: $\\mathbf Z$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Integer Ring"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = ZZ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### The field of rationals: $\\mathbf Q$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Rational Field"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F = QQ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Finite prime fields:  $\\mathbf F_p$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Galois field with characteristic 3"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = GF(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Finite fields: $\\mathbf F_{p^r}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Finite field of degree 2 over F_3, a)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F, a = FiniteField(3, 2, \"a\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that the second return value is an algebra generator for $\\mathbf F_{p^r}$ over $\\mathbf F_p$, that is, $\\mathbf F_{p^r} = \\mathbf F_p[a]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Residue rings of integers: $\\mathbf Z/n\\mathbf Z$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Integers modulo 4"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = ResidueRing(ZZ, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Number fields: $\\mathbf Q(\\alpha)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Number field over Rational Field with defining polynomial x^2 + 1, a)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Qx, x = QQ[\"x\"] # alternative syntax for PolynomialRing(QQ, \"x\")\n",
    "h = x^2 + 1\n",
    "K, a = NumberField(h, \"a\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The second return value is the class of $x$ in $\\mathbf Q[x]/(h)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Derived rings\n",
    "A second class of rings is obtained by taking old rings to create new rings or parents."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Univariate polynomial rings: $R[x]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Univariate Polynomial Ring in x over Integer Ring, x)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = ZZ\n",
    "Rx, x = ZZ[\"x\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Multivariate polynomial rings: $R[x_1,\\dotsc,x_n]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Multivariate Polynomial Ring in x1, x2 over Integer Ring, fmpz_mpoly[x1, x2])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = ZZ\n",
    "Rx, (x1, x2) = ZZ[\"x1\", \"x2\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Power series ring: $R[[x]]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Univariate power series ring in x over Integer Ring, x + O(x^31))"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = ZZ\n",
    "Rx, x = PowerSeriesRing(R, 30, \"x\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Matrix spaces: $\\operatorname{M}_{n\\times m}(R)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Matrix Space of 2 rows and 3 columns over Integer Ring"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = ZZ\n",
    "S = MatrixSpace(ZZ, 2, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Remark on matrices\n",
    "\n",
    "1. As we saw, elements are usually constructured. For matrices this is a bit cumbersome. Thus there is a way to directly construct a matrix over a given ring:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1  2  3]\n",
       "[4  5  6]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = matrix(ZZ, [1 2 3; 4 5 6]) # give a two-dimensional julia array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1  2  3]\n",
       "[4  5  6]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = matrix(ZZ, 2, 3, [1, 2, 3, 4, 5, 6]) # give a one-dimensional julia array and read it row-wise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "2. Matrices? As we saw, we already have some matrix type provided by julia, known as `Matrix`. Unfortunately, due to julias numerical linear algebra heritage, using the `Matrix` for linear algebra is only useful if one does linear algebra with floating point numbers. There are some dubious design decisions which render the `Matrix` useless for linear algebra."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2.0"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using LinearAlgebra\n",
    "x = [1 2; 3 4]\n",
    "det(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that this is a `Float64`. Julia promotes the matrix to matrix of `Float64` and then does the computations.   There are additional internal design decisions, which make it even less useful.\n",
    "\n",
    "On other hand:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = matrix(ZZ, [1 2; 3 4]) # this is a Oscar matrix\n",
    "det(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> Don't use the type `Matrix` to do linear algebra (unless you are doing numerical linear algebra). Use `Matrix` instead only for bookkeeping. To do exact linear algebra, use the matrix types provided by `Oscar/Hecke`.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### What can we do with elements?\n",
    "\n",
    "Please have a look at: https://nemocas.github.io/AbstractAlgebra.jl/latest/\n",
    "\n",
    "For example, https://nemocas.github.io/AbstractAlgebra.jl/latest/polynomial/ shows all the methods that (should) work with univariate polynomial rings.\n",
    "\n",
    "A very concise overview of the functionality for univariate polynomials can be found here:\n",
    "http://www.thofma.com/software/univariate.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Boosting productivity using Revise\n",
    "\n",
    "Assume that one is working on a file `test.jl`. One usually has a julia session open and then iterates the following steps:\n",
    "\n",
    "1. Make changes to `test.jl`.\n",
    "2. run `include(\"test.jl\")` in the julia session.\n",
    "3. Test if the changes lead to the desired outcome.\n",
    "\n",
    "This works quite well, but of course it does not scale. What if I have more than one file? Also it does not work when working directly on Hecke/Oscar?\n",
    "\n",
    "This is where the package \"Revise\" comes into play, which tracks local file changes and automatically loads functions/files that have changed. This basically eliminates step 2. First step is to install Revise using the package manager by invoking `]add Revise`. Once this is done, we load Revise and tell it to track our file \"test.jl\"\n",
    "\n",
    "```julia\n",
    "using Revise\n",
    "Revise.includet(\"test.jl\")\n",
    "```\n",
    "\n",
    "Julia development without Revise is very cumbersome! Always use Revise!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Some gotchas and tipps:\n",
    "- Typing `1/2` will produce `0.5`, which is a floating point number. The correct way is to use `//`, so `1//2` or `x//(x + 1)` rational numbers or a rational function.\n",
    "- Type `?bla` to get some information about the function `bla`.\n",
    "- Use tab completion:\n",
    "  - `gcd\\tab` will print all functions whose name start with `gcd`. (This also works with variables in a session.)\n",
    "  - `f(a, \\tab` will print the methods that work with `a` as the first argument for `f` .\n",
    "  - Sometimes methods are not exported, so one has to prefix them, like `Hecke.isprime_power`.\n",
    "- Use `@show f` to do some quick debugging."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Julia 1.5.1",
   "language": "julia",
   "name": "julia-1.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}